# Controlling Unknown Linear Dynamics with Bounded Multiplicative
Regret††thanks: This work was supported by AFOSR grants FA9550-19-1-0005 and
FA9550-18-1-0069, and partially supported by NSF grant DMS-1700180 and by the
Joachim Herz Stiftung.

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

(September 2021)

###### Abstract

We consider a simple control problem in which the underlying dynamics depend
on a parameter that is unknown and must be learned. We exhibit a control
strategy which is optimal to within a multiplicative constant. While most
authors find strategies which are successful as the time horizon tends to
infinity, our strategy achieves lowest expected cost up to a constant factor
for a fixed time horizon.

##  1 Introduction

Here, as in our previous paper [12], we investigate control problems in which
we must make decisions with little time and little data available. Our
motivating example is the success of pilots learning in real time to fly and
safely land an airplane after it has been severely damaged, as documented in
[6].

To start to address these issues, we study a simple control problem whose
dynamics depend on a single unknown parameter $a\in\mathbb{R}$. We try to
minimize an expected cost $S(\sigma,a)$, where $\sigma$ denotes our control
strategy. For known $a$, classical control theory provides an optimal strategy
$\sigma_{\text{opt}}(a)$, i.e. $\sigma\mapsto S(\sigma,a)$ achieves a minimum
at $\sigma=\sigma_{\text{opt}}(a)$.

Now suppose we have no prior information about $a$. It is then natural to
evaluate a strategy $\sigma$ by comparing its expected cost to that of
$\sigma_{\text{opt}}(a)$ for each putative value of $a$. Accordingly, we
define the _additive_ and _multiplicative regret_ of a given strategy $\sigma$
to be the functions

$AR_{\sigma}(a):=S(\sigma,a)-S(\sigma_{\text{opt}}(a),a)$

and

$MR_{\sigma}(a):=\frac{S(\sigma,a)}{S(\sigma_{\text{opt}}(a),a)},$

respectively, for all $a\in\mathbb{R}$. The additive regret is often called
simply the “regret”, and the multiplicative regret is also called the
“competitive ratio”. (In the control theory literature, it’s common to define
regret by comparing our strategy to a particular class of competing
strategies. Here we allow arbitrary competing strategies.)

A natural is question is whether there exists a strategy $\sigma$ for which
the multiplicative regret $MR_{\sigma}(a)$ is even bounded for all $a$. This
is not obvious, even if the dynamics are linear, because if, for instance, the
parameter $a$ determines the stability of the linear system, an arbitrarily
large value of $a$ could make the cost $S(\sigma,a)$ arbitrarily large. The
main result of this paper is to answer this question. In particular, for the
common case of linear dynamics, we exhibit a strategy $\sigma_{*}$ whose
multiplicative regret remains bounded as the unknown $a$ varies over the whole
real line. Our strategy $\sigma_{*}$ controls the system while learning about
$a$ on the fly.

We next comment on the state of the art regarding control with learning, and
contrast the regime studied here with that considered previously. Then we
formulate our control problem, state our main theorem, and describe the
control strategy $\sigma_{*}$.

Control with learning has been considered in many application areas; see for
example [10], in which Dean et al. apply adaptive control techniques to learn
and control linear systems on the fly; the related [9]; as well as [3], in
which Abeille and Lazaric use Thompson Sampling in the same setting. Online
learning and control can further be expanded to other complementary problems
including the study of tracking adversarial targets [1] and derivative-free
optimisation for the linear quadratic problem [14].

As gradient descent methods are essential in offline optimization, studies
have also been undertaken that aim to apply these methods without prior
information; these include the derivation and implementation of adaptive
online gradient descent by Bartlett, Hazan, and Rakhlin [5], as well as the
introduction of _AdaGrad_ (adaptive gradient algorithm) by Duchi, Hazan, and
Singer [11], which has since become a staple in the machine learning
community.

We note work of Abbasi-Yadkori and Szepesvári [2], in which the authors were
able to prove that under certain assumptions the expected additive regret of
the adaptive controller is bounded by $\tilde{O}(\sqrt{T})$, where $T$ denotes
the time horizon. Further progress was made on this problem by Chen and Hazan
[8], who, assuming controllability of the system, gave the first efficient
algorithm capable of attaining sublinear additive regret in a single
trajectory in the setting of online nonstochastic control.

Much is known about the closely related “multi-armed bandit” problem; see, for
instance, the classic papers [17, 18], the more recent survey [7], or [4], in
which the authors introduce an efficient algorithm which achieves the optimal
sublinear additive regret for the related bandit optimization problem.

As this list of references by no means does justice to the breadth of studies
in the literature, we point the reader towards [15] for a more thorough
overview of online convex optimization.

In this paper, we consider a simple toy problem that differs from the work
cited above in two respects.

  * •

The time horizon $T$ is fixed, whereas the literature is mainly concerned with
asymptotic behavior as $T\rightarrow\infty$.

  * •

We must control a system that may be arbitrarily unstable.

###  1.1 The problem

To state our problem, we begin by recalling the classical linear quadratic
regulator (“LQR”) control problem [16] in its simplest form. We consider a
particle whose movement is governed by a simple linear system driven by
additive noise. We hope to keep that particle close to the origin by applying
a control. The position of the particle at time $t$ is
$q(t)\in\mathbb{R}^{1}$, and the control we apply is denoted by
$u(t)\in\mathbb{R}^{1}$.

The particle moves according to the stochastic ODE

$dq=(aq+u)dt+dW_{t},\qquad q(0)=0,$ (1)

where $a$ is a known constant and $(W_{t})$ denotes Brownian motion,
normalized so that $\mathbb{E}((W_{t})^{2})=t$. We are free to pick our
favorite $u(t)$ in (1), provided only that

  * •

$u(t)$ is determined by history up to time $t$ (i.e., by
$(q(\tau))_{0\leq\tau\leq t}$) and

  * •

the stochastic ODE (1) admits a unique solution.

We define such a choice of $u(t)$ for each $t$ and each history up to time $t$
to be a _strategy_ , and we write $\sigma,\sigma^{\prime},\tilde{\sigma}$,
etc. to denote strategies (we remark that in the control theory literature
strategies are often called “policies”).

Let us fix the parameter $a$ in (1). Once we pick a strategy $\sigma$, we can
solve the stochastic ODE (1) from time $t=0$ to time $t=T$; we define the
_cost_ of our strategy $\sigma$ to be the quantity111Usually, one sees
coefficients multiplying the terms $dW_{t}$ in (1) and $u^{2}$ in (2). These
coefficients can be easily scaled away.

$\int_{0}^{T}\left((q(t))^{2}+(u(t))^{2}\right)dt$ (2)

for a known “time horizon” $T$. The cost is a random variable, because the
noise $(W_{t})$ is random. We denote the expected value of the cost by
$S(\sigma,a)$.

The classic LQR problem is to pick $\sigma$ to minimize $S(\sigma,a)$ for
fixed known $a$. The minimizer $\sigma_{\text{opt}}(a)$ of $S(\sigma,a)$ for
fixed, given $a$ is well-known; it prescribes the control

$u(t)=-K(t,a)q(t),$ (3)

where $K(t,a)$ solves an ODE in the $t$-variable, with $a$ appearing as a
parameter. The expected cost of the optimal strategy is comparable to $a$ for
$a$ large positive, and to $|a|^{-1}$ for $a$ large negative. See Section 7
below.

Now we can state the problem studied here. Suppose our particle moves
according to (1), but we have absolutely no prior information about the
coefficient $a$. How should we pick our control strategy?

###  1.2 A strategy with bounded multiplicative regret

Our main result is as follows.

######  Theorem 1.

The control strategy $\sigma_{*}$, to be described below, satisfies the
inequality

$S(\sigma_{*},a)\leq CS(\sigma_{\text{opt}}(a),a)\quad\text{for all
}a\in\mathbb{R},$

where $C$ is a positive constant depending only on the time horizon $T$.

Thus, although $\sigma_{*}$ is independent of $a$, its expected cost differs
by at most a factor $C$ from that of the optimal strategy tailored to $a$;
this holds for all $a\in\mathbb{R}$. That is, for fixed $T$, the
multiplicative regret of the strategy $\sigma_{*}$ is bounded as $a$ varies
over the whole real line.

We explain further how the problem studied here differs from those considered
in [9, 10] or [2]. In the context of our simple LQR problem (1), (2), [9, 2]
assume that $a$ is bounded or that a stabilizing gain is provided [10], and
produce strategies whose additive regret exhibits favorable asymptotics as
$T\rightarrow\infty$.

Here, we study a simple toy problem in a different regime. We regard $T$ as
fixed, and exhibit a strategy whose multiplicative regret is bounded, even if
$a$ varies over the whole real line. The case $a\gg 1$ is dangerous, because
the dynamics are then highly unstable if we undercontrol, while overcontrol
will incur a high cost.

We next describe the strategy $\sigma_{*}$. We will partition the time
interval $[0,T]$ into a prologue and several epochs. Note that we can execute
our strategy without knowing $T$.

We begin the _Prologue_ at time $0$. During the Prologue we set $u(t)\equiv
0$, and observe $q(t)$. Perhaps $|q(t)|<1$ for all $t\in[0,T)$, in which case
the Prologue lasts until the end of the game at time $T$. On the other hand,
there may come a first time $t_{0}\in(0,T)$ when $|q(t_{0})|=1$. In that case,
we enter _Epoch 0_ at time $t_{0}$. During Epoch 0 we continue to set
$u(t)\equiv 0$.

Assuming Epoch 0 occurs, we may find that $|q(t)|<2$ for all $t\in[t_{0},T)$,
in which case Epoch 0 lasts until the end of the game. On the other hand,
assuming Epoch 0 occurs, there may come a first time $t_{1}\in(t_{0},T)$ when
$|q(t_{1})|=2$. At time $t_{1}$ we then enter _Epoch 1_ , during which we set

$a_{1}=4\frac{\ln(2)}{t_{1}-t_{0}}$ (4)

and apply the control

$u(t)=-2a_{1}q(t).$ (5)

Here, $\frac{1}{4}a_{1}$ is a guess for the unknown parameter $a$, and (5) is
a proxy for (3). We will motivate (4) later.

Suppose we have entered Epoch 1. It may happen that $|q(t)|<4$ for all
$t\in[t_{1},T)$, in which case Epoch 1 lasts until the end of the game. On the
other hand, it may happen that $|q(t_{2})|=4$ at some first time
$t_{2}\in(t_{1},T)$. In that case, we enter _Epoch 2_ , during which we set

$a_{2}=4\frac{\ln(2)}{t_{2}-t_{1}}+2^{12}a_{1},$ (6)

and apply the control

$u(t)=-2a_{2}q(t).$ (7)

We continue in this way, as many times as necessary. If we find ourselves in
Epoch $\nu\geq 1$ starting at time $t_{\nu}\in(0,T)$, then it may happen that
$|q(t)|<2^{\nu+1}$ for all $t\in[t_{\nu},T)$, in which case Epoch $\nu$ lasts
from time $t_{\nu}$ to the end of the game at time $T$. On the other hand, it
may happen that $|q(t_{\nu+1})|=2^{\nu+1}$ at some first time
$t_{\nu+1}\in(t_{\nu},T)$. In that case, we enter Epoch $\nu+1$ at time
$t_{\nu+1}$. During Epoch $(\nu+1)$, we set

$a_{\nu+1}=4\frac{\ln 2}{t_{\nu+1}-t_{\nu}}+2^{12}a_{\nu}$ (8)

and apply the control

$u(t)=-2a_{\nu+1}q(t).$ (9)

With probability 1 we will reach the end of the game after finitely many
epochs. This completes the description of our strategy $\sigma_{*}$.

We next comment on the proof of Theorem 1. The main challenge is to deal with
the case of large positive $a$, since then (1) may be highly unstable. Let us
see how our strategy $\sigma_{*}$ performs in that case.

During the Prologue and Epoch 0 we set $u\equiv 0$, hence (1) reduces to

$dq=aq\ dt+dW_{t},\quad q(0)=0\quad\text{ with }a\gg 1.$ (10)

It is then very likely that $q(t)$ will grow rapidly. In particular, we will
encounter times $t_{0}$ and $t_{1}$ with $|q(t_{0})|=1$ and $|q(t_{1})|=2$, as
in our description of the strategy $\sigma_{*}$.

In Epoch 0–the time interval $[t_{0},t_{1}]$–the stochastic ODE (10) tells us
that $q(t)\approx q(t_{0})\cdot\exp(a\cdot[t-t_{0}])$ with high probability.
Since $|q(t_{0})|=1$ and $|q(t_{1})|=2$, it follows that $a\approx\frac{\ln
2}{t_{1}-t_{0}}$ with high probability.

So, at the end of Epoch 0, we have an excellent guess for the unknown $a$.
That’s why we define $a_{1}$ by equation (4); the factor of 4 in that equation
is inserted as a margin of safety. As we enter Epoch 1, we very likely have
$a_{1}\approx 4a$, hence (5) yields $u\approx-8aq$, and (1) becomes

$dq\approx-7aq\ dt+dW_{t},\text{ with }a\gg 1.$ (11)

Equation (11) leads to extremely stable behavior. In particular, since
$|q(t_{1})|=2$, it is highly likely that soon after time $t_{1}$ the system
enters a regime in which $|q|\ll 1$ until the end of the game at time $T$. So
we will probably encounter the Prologue and Epochs 0 and 1, but no further
epochs. During the Prologue and Epoch 0 we gather enough information to guess
$a$ with high confidence, and in Epoch 1 we use that guess to control the
system and reverse the exponential growth of $|q|$. That’s what happens with
high probability.

We may be very unlucky; with small probability, it may happen that $a_{1}\ll
a$. In that case, (4) and (5) will lead us to undercontrol the system, and
$|q|$ will continue to grow exponentially. If that disaster occurs, then at
some first time $t_{2}\in(t_{1},T)$ we will have $|q(t_{2})|=4$. At time
$t_{2}$ we then enter Epoch 2. We increase our previous guess for the unknown
$a$ based on $a_{1}$ to a new guess based on $a_{2}$ given by (6). In place of
our previous rule (5), we now define our control $u(t)$ by (7). With high
probability we have $a_{2}>a$, which allows us to reverse the exponential
growth of $|q|$ starting in Epoch 2. Very likely, then, Epoch 2 lasts until
the end of the game at time 1.

However, we may be extraordinarily unlucky and end up with $a_{2}\ll a$. In
that exceedingly rare event, the exponential increase of $|q|$ continues
unabated until we enter Epoch 3.

We continue in this way until we finally reach an Epoch in which $a_{\nu}>a$
and the game ends before we reach Epoch $\nu+1$. This happens with probability
1. Already the probability that we even reach Epoch 2 is exponentially small
for $a\gg 1$.

So our strategy $\sigma_{*}$ succeeds in controlling the system when $a\gg 1$.
In particular, our guesses (4), (6), (8) for $a$ and the consequent control
formulas (5), (7), (9) are reasonable.

Now let’s see how $\sigma_{*}$ performs when $a$ is large and negative. During
the Prologue, we take $u=0$, so our stochastic ODE (1) is simply

$dq=-|a|q\ dt+dW_{t},\quad q(0)=0\quad\text{ with }|a|\gg 1.$

Very likely, we never encounter $|q|=1$, and therefore the Prologue lasts
until the end of the game. Thus, $\sigma_{*}$ will very likely tell us to set
$u(t)\equiv 0$ for all $t$. The expected cost of that strategy (“do nothing”)
is comparable to the cost of the optimal strategy $\sigma_{\text{opt}}(a)$
when $a$ is large negative.

Finally, suppose $a$ is neither large positive nor large negative; say
$|a|\leq 1$. Then $S(\sigma_{\text{opt}}(a),a)$ and $S(\sigma_{*},a)$ are
bounded above and below by constants depending only on the time horizon $T$,
which immediately implies the conclusion of Theorem 1.

This concludes our introductory explanation of the proof of Theorem 1.
Detailed proofs are given in Sections 3-6 below; we warn the reader that the
rigorous proofs have to deal with low-probability disasters omitted from this
introduction. Section 7 reviews the classical LQR problems, in particular
deriving the asymptotic behavior of $S(\sigma_{\text{opt}}(a),a)$ for $|a|\gg
1$.

We would like to obtain a strengthened form of Theorem 1 in which the constant
$C$ is as small as possible up to an arbitrarily small error $\varepsilon>0$,
with the strategy $\sigma_{*}$ depending on $\varepsilon$. We believe that a
slight variant of our present $\sigma_{*}$ will be one ingredient in that
$\varepsilon$-dependent strategy.

We refer the reader to our previous paper [12] for additional problems
involving control with learning on the fly.

We are grateful to Amir Ali Ahmadi and Elad Hazan for helpful conversations.

##  2 Main Result and Outline of Proof

In this section we discuss the proof of Theorem 1. We adopt the following
notation for the remainder of the paper: we write
$S_{\text{opt}}(a):=S(\sigma_{\text{opt}}(a),a)$ and
$S_{*}(a):=S(\sigma_{*}(a),a)$. In order to prove Theorem 1, it is necessary
to understand the asymptotic behavior of $S_{\text{opt}}$. This is the content
of the following lemma.

######  Lemma 1.

There exists a constant $C>0$, depending only on the time horizon $T$, such
that the following hold:

  1. (i)

For all $|a|\leq 1$, $S_{\text{opt}}(a)\geq C$.

  2. (ii)

For all $a\geq 1$, $S_{\text{opt}}(a)\geq Ca$.

  3. (iii)

For all $a\leq-1$, $S_{\text{opt}}(a)\geq\frac{C}{|a|}$.

We prove Lemma 1 in Section 7. The following lemma, combined with Lemma 1,
proves Theorem 1.

######  Lemma 2.

There exists a constant $C>0$, depending only on the time horizon $T$, such
that the following holds:

  1. (i)

For any $a\geq 1$, $S_{*}(a)\leq Ca$.

  2. (ii)

For any $|a|\leq 1$, $S_{*}(a)\leq C$.

  3. (iii)

For any $a\leq-1$, $S_{*}(a)\leq\frac{C}{|a|}$.

The proof of Lemma 2 is given in Sections 4-6.

###  2.1 Conventions on constants

Throughout this paper we let $C,C^{\prime},C^{\prime\prime},\dots$ denote
positive constants depending only on $T$. If we wish to specify that a
positive constant depending only on $T$ is smaller than 1 we use
$c,c^{\prime},\dots$. These constants are not fixed throughout the paper and
will change from one line to another.

Given quantities $X,Y\geq 0$, we will write either $X\lesssim Y$ or $X=O(Y)$
if there exists a constant $C>0$ depending only on $T$ such that $X\leq CY$.
We write $X\approx Y$ if $X\lesssim Y$ and $Y\lesssim X$.

##  3 Preliminaries

We begin this section by establishing some notation. For $\nu\geq 0$, we
define $q_{\nu}:=2^{\nu}$. We also define $q_{-1}:=0$. For $\nu\geq-1$ we let
$t_{\nu}$ denote the first time $t\in[0,T]$ for which $|q(t)|=q_{\nu}$ if such
a time exists. If no such time exists we set $t_{\nu}=T$. Note that we always
have $t_{-1}=0$. For $\nu\geq 0$, we will refer to the time interval
$[t_{\nu},t_{\nu+1})$ as Epoch $\nu$. If $t_{\nu}<T$ then we say that _Epoch
$\nu$ occurs_. We let $E_{\nu}$ denote the event that Epoch $\nu$ occurs. We
refer to the time interval $[0,t_{0})$ as the Prologue; note that the Prologue
always occurs.

We now recall our strategy. Let us denote our control in the Prologue by
$u_{-1}(t)$ and our control in Epoch $\nu$ by $u_{\nu}(t)$, i.e. when Epoch
$\nu$ occurs we set $u(t)=u_{\nu}(t)$ for $t\in[t_{\nu},t_{\nu+1})$. In the
Prologue and Epoch 0 we exercise no control, i.e. we set $u_{-1},u_{0}\equiv
0$. When Epoch $\nu$ occurs, we control during Epoch $\nu$ with
$u_{\nu}(t)=-2a_{\nu}q(t)$, where $a_{\nu}$ will be defined shortly. We define
$a_{-1}=a_{0}=0$. We let $C_{0}$ and $C_{1}$ denote positive constants which
will be chosen later. Then when Epoch $\nu$ occurs for $\nu\geq 1$ we define

$a_{\nu}=C_{0}\frac{\log(2)}{t_{\nu}-t_{\nu-1}}+C_{1}a_{\nu-1}.$ (12)

Note that when Epoch $\nu$ occurs for $\nu\geq 1$ we are guaranteed to have
$a_{\nu}>0$. In Lemma 10 we fix $C_{0}=4$ and $C_{1}=2^{\ell_{\\#}}$, where
$\ell_{\\#}$ is a universal constant which is chosen to be sufficienlty large
in the later sections (we will see that it suffices to take $\ell_{\\#}=12$,
and so we can take $C_{1}=2^{12}$ as in (8)).

Finally, for a given value of $a$ in (1) we will write $S_{\nu}(a)$ to denote
the cost incurred in Epoch $\nu$ using strategy $\sigma_{*}$ and $S_{-1}(a)$
to denote the cost incurred in the Prologue using strategy $\sigma_{*}$.
Specifically, we set

$S_{\nu}(a):=\int_{t_{\nu}}^{t_{\nu+1}}(q^{2}(t)+u_{\nu}^{2}(t))dt.$

Note that $S_{\nu}(a)$ is a random variable depending on the noise $(W_{t})$
in (1).

We now state and prove some preliminary lemmas.

######  Lemma 3.

Fix $b\neq 0$ and $\nu\geq-1$. Define

$X_{t}^{(b)}:=e^{-bt}\tilde{q}(t)-q_{\nu},$

where $\tilde{q}$ is a random process satisfying $\tilde{q}(0)=q_{\nu}$ and
governed by

$d\tilde{q}=(b\tilde{q})dt+d\widetilde{W}_{t},$ (13)

where $(\widetilde{W}_{t})$ is standard Brownian motion. Then the following
hold:

  1. 1.

For fixed $t$, $X_{t}^{(b)}$ is a normal random variable with mean $0$ and
variance $\frac{1-e^{-2bt}}{2b}$.

  2. 2.

Define

$M_{t}^{(b)}:=\sup_{0\leq s\leq t}X_{s}^{(b)}.$

Then for any $\eta>0$,

$\mathbb{P}(M_{t}^{(b)}>\eta)=2\mathbb{P}(X_{t}^{(b)}>\eta).$

###### Proof.

Using an integrating factor of the form $e^{-bt}\tilde{q}$ gives

$d(e^{-bt}\tilde{q})=e^{-bt}d\tilde{q}-be^{-bt}\tilde{q}dt=e^{-bt}d\widetilde{W}\;.$

For fixed $t$, $e^{-bt}d\widetilde{W}$ is normally distributed with mean 0 and
variance $e^{-2bt}dt$. Integrating from 0 to t gives

$e^{-bt}\tilde{q}(t)-q_{\nu}=\int_{0}^{t}e^{-bs}d\widetilde{W_{s}}\;.$ (14)

The RHS of (14) is normally distributed with mean 0 and (by the Itô isometry)
variance $\frac{1-e^{-2bt}}{2b}$. This proves the first claim.

Note that if we replace $X_{t}^{(b)}$ by Brownian motion then the second claim
is simply the reflection principle for Brownian motion (see, for example,
[13]). Therefore we refer to this claim as the reflection principle for
$X_{t}^{(b)}$. Note, however, that for fixed $b$, $X_{t}^{(b)}$ has a.s.
continuous paths. Moreover, $X_{t}^{(b)}$ satisfies the strong Markov property
and $(X_{t+t^{\prime}}^{(b)}-X_{t}^{(b)})\sim e^{-bt}X_{t^{\prime}}^{(b)}$ is
symmetric. Examining the proof of the reflection principle for Brownian motion
in [13] shows that these conditions are sufficient to prove the reflection
principle for $X_{t}^{(b)}$. ∎

######  Remark 1.

We first note that if, in Lemma 3, we assume instead that
$\tilde{q}(0)=-q_{\nu}$ then, due to the symmetry of (13), we have that
$(e^{-bt}\tilde{q}(t)+q_{\nu})$ is distributed the same as $X_{t}^{(b)}$ given
$\tilde{q}(0)=q_{\nu}$.

We also note that, when we apply Lemma 3, we will be taking
$\tilde{q}(t)=q(t_{\nu}+t)$ in Epoch $\nu$, conditioned on an event that
specifies $a_{\nu}$ and is independent of the noise in Epoch $\nu$. In this
case, we will be taking $b=a-2a_{\nu}$.

######  Remark 2.

We record here a few simple observations which we will use repeatedly
throughout this paper. First, we note that there exists a constant $c\in(0,1)$
such that

  1. (a)

When $|bt|\leq 1/10$, then

$c\cdot(bt)\leq 1-e^{-bt}\leq bt.$

  2. (b)

When $bt\geq 1/10$, then

$c\leq 1-e^{-bt}<1.$

Second, for any positive integer $N$ there exists a constant $C_{N}$ such that

$\exp(-x)\leq C_{N}\cdot x^{-N}$

for all $x>0$.

Finally, we note that there exist constants $C>0$ and $c\in(0,1)$ such that if
$Y$ is a normal random variable with mean 0 and standard deviation $\sigma$
then for any $x>0$ we have

$\mathbb{P}(|Y|>x\sigma)\leq C\exp(-cx^{2}).$

######  Lemma 4.

Fix $\delta>0$ and $\nu\geq 0$, and suppose $\tilde{q}$ is governed by (13)
with $b\neq 0$. Suppose that $|\tilde{q}(t_{\nu})|=2^{\nu}$. Then

  1. 1.

If $b>0$, then for each $t>0$ the probability that
$|\tilde{q}(t_{\nu}+t)|\notin[2^{\nu}e^{bt}(1-\delta),2^{\nu}e^{bt}(1+\delta)]$
is at most $Ce^{-c\delta^{2}2^{2\nu}b}$.

  2. 2.

For each $t\in\left[0,\frac{1}{10|b|}\right]$, the probability that
$|\tilde{q}(t_{\nu}+t)|\notin[2^{\nu}e^{bt}(1-\delta),2^{\nu}e^{bt}(1+\delta)]$
is at most $Ce^{-c\delta^{2}2^{2\nu}/t}$.

###### Proof.

We write $I:=[2^{\nu}e^{bt}(1-\delta),2^{\nu}e^{bt}(1+\delta)]$. First note
that

$\begin{split}\mathbb{P}(|\tilde{q}(t_{\nu}+t)|\notin
I)&\leq\mathbb{P}(|\tilde{q}(t_{\nu}+t)|\notin
I|\tilde{q}(t_{\nu})=2^{\nu})\\\ &+\mathbb{P}(|\tilde{q}(t_{\nu}+t)|\notin
I|\tilde{q}(t_{\nu})=-2^{\nu}).\end{split}$ (15)

Now, since the event $|\tilde{q}(t_{\nu}+t)|\notin I$ implies the events
$\tilde{q}(t_{\nu}+t)\notin I$ and $-\tilde{q}(t_{\nu}+t)\notin I$, we
continue from (15) to get

$\begin{split}\mathbb{P}(|\tilde{q}(t_{\nu}+t)|\notin
I)&\leq\mathbb{P}(\tilde{q}(t_{\nu}+t)\notin I|\tilde{q}(t_{\nu})=2^{\nu})\\\
&+\mathbb{P}(-\tilde{q}(t_{\nu}+t)\notin
I|\tilde{q}(t_{\nu})=-2^{\nu}).\end{split}$ (16)

Note that when $\tilde{q}(t_{\nu})=2^{\nu}$, $\tilde{q}(t_{\nu}+t)\notin I$
means that
$e^{-bt}\tilde{q}(t_{\nu}+t)-2^{\nu}\notin[-2^{\nu}\delta,2^{\nu}\delta]$.
Therefore

$\mathbb{P}(\tilde{q}(t_{\nu}+t)\notin
I|\tilde{q}(t_{\nu})=2^{\nu})\leq\mathbb{P}(X_{t}^{(b)}\notin[-2^{\nu}\delta,2^{\nu}\delta]),$
(17)

where $X_{t}^{(b)}$ is as defined in Lemma 3. Similarly, when
$\tilde{q}(t_{\nu})=-2^{\nu}$, $-\tilde{q}(t_{\nu}+t)\notin I$ means that

$-e^{-bt}\tilde{q}(t_{\nu}+t)-2^{\nu}\notin[-2^{\nu}\delta,2^{\nu}\delta].$
(18)

By Remark 1,

$\begin{split}\mathbb{P}(\tilde{q}(t_{\nu}+t)+2^{\nu}\notin[-2^{\nu}\delta,2^{\nu}\delta]|\tilde{q}(t_{\nu})=-2^{\nu})=\mathbb{P}(X_{t}^{(b)}\notin[-2^{\nu}\delta,2^{\nu}\delta]).\end{split}$
(19)

Combining (16)–(19) gives

$\begin{split}\mathbb{P}(|\tilde{q}(t_{\nu}+t)|\notin
I)\lesssim\mathbb{P}(X_{t}^{(b)}\notin[-2^{\nu}\delta,2^{\nu}\delta]).\end{split}$
(20)

By Remark 2 and Lemma 3, when $|tb|\leq 1/10$ the standard deviation of
$X_{t}^{(b)}$ is

$\sigma=\left(\frac{1-e^{-2bt}}{2b}\right)^{1/2}\approx t^{1/2},$

and when $tb\geq 1/10$ the standard deviation of $X_{t}^{(b)}$ is

$\sigma=\left(\frac{1-e^{-2bt}}{2b}\right)^{1/2}\approx\frac{1}{b^{1/2}}.$

Note that when $X_{t}^{(b)}\notin[-2^{\nu}\delta,2^{\nu}\delta]$ holds, the
normal random variable $X_{t}^{(b)}$ is at least
$N:=\frac{2^{\nu}\delta}{\sigma}$ standard deviations from its mean. By Remark
2, this implies that the probability of
$X_{t}^{(b)}\notin[-2^{\nu}\delta,2^{\nu}\delta]$ holding for a given $t$ is
at most $C\exp(-cN^{2})$. Therefore

$\mathbb{P}(X_{t}^{(b)}\notin[-2^{\nu}\delta,2^{\nu}\delta])\lesssim\begin{cases}\exp\left(-\frac{c2^{2\nu}\delta^{2}}{t}\right)&\text{
when }t|b|<1/10\\\ \exp\left(-c2^{2\nu}\delta^{2}b\right)&\text{ when
}tb>1/10\end{cases}.$ (21)

Note that $t|b|<1/10$ implies that

$\exp\left(-\frac{c2^{2\nu}\delta^{2}}{t}\right)\lesssim\exp(-c2^{2\nu}\delta^{2}b);$
(22)

combining (20), (21), and (22) proves the lemma.

∎

######  Remark 3.

Throughout this note we will analyze probabilities which are conditioned on
events of the form $a_{\nu}\in I$ for some interval $I$. We clarify here that
this event will always mean “Epoch $\nu$ occurs and $a_{\nu}\in I$”.

Before stating the next lemma, we remind the reader of the constants $C_{0}$
and $C_{1}$ appearing in the definition of $a_{\nu}$ (see Equation (12)).
Recall that $C_{0}=4$ and $C_{1}=2^{\ell_{\\#}}$, where $\ell_{\\#}$ is a
universal constant which is chosen to be sufficiently large in the later
sections.

######  Lemma 5.

Let $\nu\geq 1$ and $a\in\mathbb{R}$. Let $X\subset[0,\infty)$,
$\gamma:X\rightarrow(0,\infty)$, $\beta:X\rightarrow(0,\infty)$. Suppose

$|a-2x|\leq\gamma(x)$

and

$\frac{\gamma(x)}{\beta(x)}<\frac{1}{10C_{0}\log(2)}$

for all $x\in X$. Let

$\beta^{*}=\inf_{x\in X}\beta(x).$

Then

$\mathbb{P}\left((a_{\nu}-C_{1}a_{\nu-1})\geq\beta(a_{\nu-1})|a_{\nu-1}\in
X\right)\lesssim\exp\left(-c2^{2\nu}\beta^{*}\right).$

###### Proof.

Fix $\tilde{a}\in X$. Using the definition of $a_{\nu}$, we have

$\begin{split}\mathbb{P}\left(a_{\nu}-C_{1}\tilde{a}\right.&\left.\geq\beta(\tilde{a})|(a_{\nu-1}=\tilde{a})\right)\\\
&=\mathbb{P}\left(\left.\frac{C_{0}\log(2)}{t_{\nu}-t_{\nu-1}}\geq\beta(\tilde{a})\right.|(a_{\nu-1}=\tilde{a})\right)\\\
&=\mathbb{P}(\exists
t\in[0,t^{*}(\tilde{a})]:|q(t_{\nu-1}+t)|>2^{\nu}|(a_{\nu-1}=\tilde{a}))\end{split}$
(23)

where $t^{*}:X\rightarrow\mathbb{R}$ is defined by

$t^{*}(x):=\frac{C_{0}\log(2)}{\beta(x)}.$ (24)

Using our hypotheses on $\gamma$ and $\beta$ gives

$|(a-2\tilde{a})t^{*}(\tilde{a})|<\frac{1}{10}.$ (25)

Now observe that

$\begin{split}\mathbb{P}(&\exists
t\in[0,t^{*}(\tilde{a})]:|q(t_{\nu-1}+t)|>2^{\nu}|(a_{\nu-1}=\tilde{a}))\\\
&\leq\mathbb{P}(\exists
t\in[0,t^{*}(\tilde{a})]:q(t_{\nu-1}+t)>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(q(t_{\nu-1})=2^{\nu-1}))\\\
&+\mathbb{P}(\exists
t\in[0,t^{*}(\tilde{a})]:q(t_{\nu-1}+t)<-2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(q(t_{\nu-1})=2^{\nu-1}))\\\
&+\mathbb{P}(\exists
t\in[0,t^{*}(\tilde{a})]:q(t_{\nu-1}+t)>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(q(t_{\nu-1})=-2^{\nu-1}))\\\
&+\mathbb{P}(\exists
t\in[0,t^{*}(\tilde{a})]:q(t_{\nu-1}+t)<-2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(q(t_{\nu-1})=-2^{\nu-1})).\\\
\end{split}$ (26)

If $t\in[0,t^{*}(\tilde{a})]$ and $q(t_{\nu-1}+t)>2^{\nu}$, then by Remark 2
and (25) we have

$q(t_{\nu-1}+t)e^{(a-2\tilde{a})t}-2^{\nu-1}>2^{\nu-1}\left(2\cdot\frac{9}{10}-1\right)>c2^{\nu-1}$
(27)

and

$q(t_{\nu-1}+t)e^{(a-2\tilde{a})t}+2^{\nu-1}>2^{\nu-1}>c2^{\nu-1}$ (28)

for all $t\in[0,t^{*}(\tilde{a})]$. Similarly, if $t\in[0,t^{*}(\tilde{a})]$
and $q(t_{\nu-1}+t)<-2^{\nu}$ then

$q(t_{\nu-1}+t)e^{(a-2\tilde{a})t}-2^{\nu-1}<-2^{\nu-1}<-c2^{\nu-1}$ (29)

and

$q(t_{\nu-1}+t)e^{(a-2\tilde{a})t}+2^{\nu-1}<-2^{\nu-1}\left(2\cdot\frac{9}{10}-1\right)<-c2^{\nu-1}.$
(30)

Combining (26) through (30) with the definition of $X_{t}^{(b)}$ and Remark 1
gives

$\begin{split}\mathbb{P}(&\exists
t\in[0,t^{*}(a_{\nu-1})]:|q(t_{\nu-1}+t)|>2^{\nu}|a_{\nu-1}=\tilde{a})\\\
&\lesssim\mathbb{P}(\exists
t\in[0,t^{*}(\tilde{a})]:X_{t}^{(a-2\tilde{a})}>c2^{\nu-1}).\end{split}$ (31)

The reflection principle for $X_{t}^{(b)}$ (the second part of Lemma 3) gives

$\begin{split}\mathbb{P}(\exists
t\in[0,t^{*}(\tilde{a})]:X_{t}^{(a-2\tilde{a})}>c2^{\nu-1})\approx\mathbb{P}(X_{t^{*}(\tilde{a})}^{(a-2\tilde{a})}>c2^{\nu-1}).\end{split}$
(32)

By (21), (24), and (25) we have

$\mathbb{P}(X_{t^{*}(\tilde{a})}^{(a-2\tilde{a})}>\tilde{c}2^{\nu-1})\lesssim\exp\left(-\frac{c2^{2\nu}}{t^{*}(\tilde{a})}\right)\lesssim\exp\left(-c^{\prime}2^{2\nu}\beta^{*}\right).$
(33)

Combining (23) with (31) - (33) finishes the proof of the lemma. ∎

Before stating the next lemma we remind the reader that we write $E_{\nu}$ to
denote the event that we reach Epoch $\nu$.

######  Lemma 6.

Let $m,M\in\mathbb{R}$ satisfy $0<m<M$. Let $\nu\geq 1$ be an integer. Let
$X\subset[0,\infty)$ such that if $\tilde{a}\in X$ then $m<2\tilde{a}-a<M$.
Then

$\mathbb{P}(E_{\nu}|a_{\nu-1}\in X)\lesssim M\exp(-c2^{2\nu}m).$

###### Proof.

Fix $\tilde{a}\in X$ and $\tilde{t}\in(0,T)$. Define
$\tilde{b}:=a-2\tilde{a}$, $\Delta t:=\frac{1}{10M}$,
$N:=\lfloor\frac{T-\tilde{t}}{\Delta t}\rfloor$, and
$I_{j}:=[\alpha_{j},\beta_{j}]$ for $j=0,1,\dots,N$; here $\alpha_{j}:=j\Delta
t$ for $j=0,1,\dots,N$, $\beta_{j}=(j+1)\Delta t$ for $j=0,1,\dots,N-1$, and
$\beta_{N}=(T-\tilde{t})$. We remark that $\beta_{N}\leq(N+1)\Delta t$. Note
that $\tilde{b}\in(-M,-m)$. We have

$\begin{split}\mathbb{P}(E_{\nu}|&(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\\\
&=\mathbb{P}(\exists
t\in(0,T-\tilde{t}):|q(\tilde{t}+t)|>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\\\
&\leq\sum_{j=0}^{N}\mathbb{P}(\exists t\in
I_{j}:|q(\tilde{t}+t)|>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})).\end{split}$
(34)

We claim that

$\mathbb{P}(\exists t\in
I_{j}:|q(\tilde{t}+t)|>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\lesssim\exp\left(-c2^{2\nu}m\right).$
(35)

Combining (34) and (35), and using the fact that $N\lesssim M$ gives

$\mathbb{P}\left(E_{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right)\lesssim
M\exp\left(-c2^{2\nu}m\right).$

This proves the lemma. Thus it just remains to establish (35). We begin by
noting that

$\begin{split}\mathbb{P}(\exists t&\in
I_{j}:|q(\tilde{t}+t)|>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\\\
&\lesssim\mathbb{P}(\exists t\in
I_{j}:q(\tilde{t}+t)>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\cap(q(t_{\nu-1})=2^{\nu-1}))\\\
&+\mathbb{P}(\exists t\in
I_{j}:q(\tilde{t}+t)<-2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\cap(q(t_{\nu-1})=2^{\nu-1}))\\\
&+\mathbb{P}(\exists t\in
I_{j}:q(\tilde{t}+t)>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\cap(q(t_{\nu-1})=-2^{\nu-1}))\\\
&+\mathbb{P}(\exists t\in
I_{j}:q(\tilde{t}+t)<-2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\cap(q(t_{\nu-1})=-2^{\nu-1}))\end{split}$
(36)

Since $\tilde{b}<0$, we have $e^{-\tilde{b}t}\geq e^{-\tilde{b}j\Delta t}$ for
$t\in I_{j}$. Thus the existence of $t^{\prime}\in I_{j}$ for which
$q(\tilde{t}+t^{\prime})>2^{\nu}$ implies that

$q(\tilde{t}+t^{\prime})e^{-\tilde{b}t^{\prime}}-2^{\nu-1}\gtrsim
2^{\nu}e^{-\tilde{b}t^{\prime}}\geq 2^{\nu}e^{-\tilde{b}j\Delta t}.$ (37)

Similarly, if there exists $t^{\prime}\in I_{j}$ for which
$q(\tilde{t}+t^{\prime})<-2^{\nu}$ then we have

$q(\tilde{t}+t^{\prime})e^{-\tilde{b}t^{\prime}}-2^{\nu-1}<-2^{\nu}e^{-\tilde{b}t^{\prime}}-2^{\nu-1}<-2^{\nu}e^{-\tilde{b}t^{\prime}}\leq-2^{\nu}e^{-\tilde{b}j\Delta
t}.$ (38)

This shows that the first two terms on the right hand side of (36) are each
bounded by

$\mathbb{P}(\exists t\in
I_{j}:X_{t}^{(\tilde{b})}>c2^{\nu}e^{-\tilde{b}j\Delta t}),$ (39)

where $X_{t}^{(\tilde{b})}$ is as in Lemma 3.

By Remark 1, $q(t_{\nu-1}+t)e^{-\tilde{b}t}+2^{\nu-1}$ given
$q(t_{\nu-1})=-2^{\nu-1}$ has the same distribution as $X_{t}^{(\tilde{b})}$.
Using this observation, and arguing as in (37) and (38), shows that the third
and fourth terms on the right hand side of (36) are also each bounded by (39).
Therefore

$\begin{split}\mathbb{P}(\exists t\in
I_{j}&:|q(\tilde{t}+t)|>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\\\
&\lesssim\mathbb{P}(\exists t\in
I_{j}:X_{t}^{(\tilde{b})}>c2^{\nu}e^{-\tilde{b}j\Delta t}).\end{split}$ (40)

The right hand side of (40) is bounded by

$\mathbb{P}(\exists
t\in[0,\beta_{j}]:X_{t}^{(\tilde{b})}>c2^{\nu}e^{-\tilde{b}j\Delta t}),$ (41)

which, by the reflection principle for $X_{t}^{(\tilde{b})}$ (the second part
of Lemma 3), is equal to

$2\mathbb{P}(X_{\beta_{j}}^{(\tilde{b})}>c2^{\nu}e^{-\tilde{b}j\Delta t}).$
(42)

By Lemma 3, the standard deviation of $X_{\beta_{j}}^{(\tilde{b})}$ is

$\left(\frac{1-e^{-2\tilde{b}\beta_{j}}}{2\tilde{b}}\right)^{1/2}.$

Note that Remark 2 and the fact that $|\tilde{b}\Delta t|<1/10$ tell us that
$e^{\tilde{b}\Delta t}\geq(1+\tilde{b}\Delta t)>c$. Also, since $\tilde{b}<0$,
and since $(j+1)\Delta t\geq\beta_{j}$ for all $0\leq j\leq N$, we have
$|e^{2\tilde{b}(j+1)\Delta t}-e^{2\tilde{b}((j+1)\Delta t-\beta_{j})}|\leq 1$
for all $0\leq j\leq N$. Therefore

$\frac{c2^{\nu}e^{-\tilde{b}j\Delta
t}|\tilde{b}|^{1/2}}{|1-e^{-2\tilde{b}\beta_{j}}|^{1/2}}=\frac{c2^{\nu}|\tilde{b}|^{1/2}e^{\tilde{b}\Delta
t}}{|e^{2\tilde{b}(j+1)\Delta t}-e^{2\tilde{b}((j+1)\Delta
t-\beta_{j})}|^{1/2}}\geq c^{\prime}2^{\nu}|\tilde{b}|^{1/2}\geq
c^{\prime\prime}2^{\nu}m^{1/2}.$

Thus when $X_{\beta_{j}}^{(\tilde{b})}>c2^{\nu}e^{-\tilde{b}j\Delta t}$, the
normal random variable $X_{\beta_{j}}^{(\tilde{b})}$ is at least
$c2^{\nu}m^{1/2}$ standard deviations from its mean. Therefore, by Remark 2,

$\displaystyle\mathbb{P}(X_{\beta_{j}}^{(\tilde{b})}>c2^{\nu}e^{-\tilde{b}j\Delta
t})$ $\displaystyle\leq C\exp(-c2^{2\nu}m).$

This completes the proof of (35), thereby completing the proof of the lemma. ∎

######  Lemma 7.

Let $M\geq 0$ and $m>0$ be real numbers. Let $\nu\geq-1$ be an integer. Let
$X$ be an event which is determined by $a_{\nu}$ and $a_{\nu-1}$ and which
implies that $\frac{a+m}{2}\leq a_{\nu}\leq M$. Then

$\mathbb{E}[S_{\nu}(a)|X]\lesssim\frac{(1+M^{2})(1+q_{\nu}^{2})}{m}.$

###### Proof.

Fix $\tilde{a}$ with $\frac{a+m}{2}\leq\tilde{a}\leq M$. Since the event $X$
is independent of the noise in Epoch $\nu$ we can apply Lemma 3 to get that

$\mathbb{E}\left[q^{2}(t_{\nu}+t)|(a_{\nu}=\tilde{a})\cap
X\right]=q^{2}_{\nu}e^{2(a-2\tilde{a})t}+\frac{e^{2(a-2\tilde{a})t}-1}{2(a-2\tilde{a})}$
(43)

(since $q(t_{\nu}+t)$ is governed by $dq=(a-2\tilde{a})qdt+dW_{t}$ and
$|q(t_{\nu})|=q_{\nu}$). Let $\chi_{I}$ denote the indicator function of an
interval $I\subset\mathbb{R}$. Note that

$\begin{split}\mathbb{E}[S_{\nu}(a)|(a_{\nu}=\tilde{a})\cap
X]&\lesssim\left(1+M^{2}\right)\mathbb{E}\left[\left.\int_{0}^{t_{\nu+1}-t_{\nu}}q^{2}(t_{\nu}+t)dt\right|(a_{\nu}=\tilde{a})\cap
X\right]\\\
&=\left(1+M^{2}\right)\mathbb{E}\left[\left.\int_{0}^{T}q^{2}(t_{\nu}+t)\chi_{[0,t_{\nu+1}-t_{\nu}]}(t)dt\right|(a_{\nu}=\tilde{a})\cap
X\right]\\\
&=\left(1+M^{2}\right)\int_{0}^{T}\mathbb{E}\left[q^{2}(t_{\nu}+t)\chi_{[0,t_{\nu+1}-t_{\nu}]}(t)|(a_{\nu}=\tilde{a})\cap
X\right]dt\\\
&\leq\left(1+M^{2}\right)\int_{0}^{T}q^{2}_{\nu}e^{2(a-2\tilde{a})t}+\frac{e^{2(a-2\tilde{a})t}-1}{2(a-2\tilde{a})}dt,\end{split}$
(44)

where the last line follows from (43). Next, note that

$\int_{0}^{T}q^{2}_{\nu}e^{2(a-2\tilde{a})t}dt=\frac{q^{2}_{\nu}\left(e^{(2(a-2\tilde{a})T}-1\right)}{2(a-2\tilde{a})}.$
(45)

Since $2\tilde{a}-a>m>0$, we have

$\frac{q^{2}_{\nu}\left(e^{(2(a-2\tilde{a})T}-1\right)}{2(a-2\tilde{a})}\lesssim\frac{q^{2}_{\nu}}{m}$
(46)

and

$\frac{e^{2(a-2\tilde{a})t}-1}{2(a-2\tilde{a})}\lesssim\frac{1}{m}$ (47)

for all $t\in[0,T]$. Combining (44)–(47) gives

$\displaystyle\mathbb{E}[S_{\nu}(a)|(a_{\nu}=\tilde{a})\cap X]$
$\displaystyle\lesssim\left(1+M^{2}\right)\left(\frac{q^{2}_{\nu}+1}{m}\right)$

for any $\frac{a+m}{2}<\tilde{a}\leq M$. Since $X$ implies that
$\frac{a+m}{2}<\tilde{a}\leq M$, we have that

$\mathbb{E}[S_{\nu}(a)|X]\leq\frac{(1+M^{2})(q_{\nu}^{2}+1)}{m}.$

∎

######  Lemma 8.

Let $\nu\geq 1$ and $a>0$. Fix $\tilde{a}\leq\frac{1}{4}a$,
$\tilde{t}\in[0,T)$, and $\delta\in(0,1)$. Define

$t^{\prime}:=\frac{\log(2)-\log(1+\delta)}{a-2\tilde{a}}$

and

$t^{\prime\prime}:=\frac{\log(2)-\log(1-\delta)}{a-2\tilde{a}}\;.$

Then

  1. 1.

If $\tilde{t}+t^{\prime}\leq T$, then

$\mathbb{P}(t^{\prime}<t_{\nu}-\tilde{t}<t^{\prime\prime}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\geq
1-C\exp(-2^{2\nu}a\delta^{2}c).$

  2. 2.

If $\tilde{t}+t^{\prime}\geq T$, then

$\mathbb{P}(E_{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\leq
C\exp(-2^{2\nu}a\delta^{2}c).$

###### Proof.

First, observe that when $\tilde{t}+t^{\prime}\leq T$, we have

$\begin{split}\mathbb{P}(t_{\nu}-&\tilde{t}<t^{\prime}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right)\\\
&\leq\mathbb{P}\left(\exists\tau\in[0,t^{\prime}]:|q(\tilde{t}+\tau)|>2^{\nu}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right).\end{split}$
(48)

Define $b:=(a-2\tilde{a})$. Note that $\tilde{a}\leq\frac{1}{4}a$ implies that
$b\geq\frac{1}{2}a$. In particular, $b>0$ and thus we have
$e^{b\tau}(1+\delta)\leq e^{bt^{\prime}}(1+\delta)=2$ for any
$\tau\in[0,t^{\prime}]$. Therefore,

$\begin{split}\mathbb{P}&\left(\exists\tau\in[0,t^{\prime}]:|q(\tilde{t}+\tau)|>2^{\nu}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right)\\\
&\leq\mathbb{P}\left(\exists\tau\in[0,t^{\prime}]:|q(\tilde{t}+\tau)|>2^{\nu-1}e^{b\tau}(1+\delta)\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right)\\\
&\leq\mathbb{P}\left(\exists\tau\in[0,t^{\prime}]:|q(\tilde{t}+\tau)|\notin
I\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right),\end{split}$
(49)

where we write $I$ to denote the interval
$[2^{\nu-1}e^{b\tau}(1-\delta),2^{\nu-1}e^{b\tau}(1+\delta)]$. Arguing as in
equations (15) through (20), we have

$\begin{split}\mathbb{P}&\left(\exists\tau\in[0,t^{\prime}]:|q(\tilde{t}+\tau)|\notin
I\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right)\\\
&\lesssim\mathbb{P}\left(\exists\tau\in[0,t^{\prime}]:|X_{\tau}^{(b)}|>2^{\nu-1}\delta\right).\end{split}$
(50)

By the reflection principle for $X_{t}^{(b)}$ (the second part of Lemma 3),

$\begin{split}\mathbb{P}&\left(\exists\tau\in[0,t^{\prime}]:|X_{\tau}^{(b)}|>2^{\nu-1}\delta\right)\\\
&\approx\mathbb{P}\left(|X_{t^{\prime}}^{(b)}|>2^{\nu-1}\delta\right).\end{split}$
(51)

Combining (21) with (49)–(51), and using that $b\geq\frac{1}{2}a$, gives

$\begin{split}\mathbb{P}\left(\exists\tau\right.&\left.\in[0,t^{\prime}]:|q(\tilde{t}+\tau)|>2^{\nu}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right)\\\
&\lesssim\exp\left(-c{2}^{2\nu}\delta^{2}b\right)\lesssim\exp(-c^{\prime}2^{2\nu}\delta^{2}a).\end{split}$

Combining this with (48) implies that

$\mathbb{P}(t_{\nu}-\tilde{t}<t^{\prime}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right)\lesssim\exp(-c^{\prime}{2}^{2\nu}\delta^{2}a)$
(52)

when $\tilde{t}+t^{\prime}\leq T$. Note that

$\begin{split}\mathbb{P}(E_{\nu}|(a_{\nu-1}=\tilde{a})&\cap(t_{\nu-1}=\tilde{t}))\\\
&=\mathbb{P}(\exists\tau\in[0,T-\tilde{t}):q(\tilde{t}+\tau)|>2^{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})).\end{split}$

Arguing as in the proof of (52) shows that we have

$\mathbb{P}(E_{\nu}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right)\lesssim\exp(-c^{\prime}{2}^{2\nu}\delta^{2}a)$

when $\tilde{t}+t^{\prime}\geq T$; this proves the second assertion of the
lemma.

Note that if $\tilde{t}+t^{\prime\prime}>T$, then

$\mathbb{P}(t_{\nu}>\tilde{t}+t^{\prime\prime})=0.$

This, combined with (52), proves the first assertion of the lemma when
$\tilde{t}+t^{\prime\prime}>T$. Now observe that when
$\tilde{t}+t^{\prime\prime}\leq T$ we have

$\begin{split}\mathbb{P}((t_{\nu}-\tilde{t})>t^{\prime\prime}&\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right)\\\
&=\mathbb{P}\left(\forall\tau\in[0,t^{\prime\prime}),|q(\tilde{t}+\tau)|<2^{\nu}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right)\\\
&\leq\mathbb{P}\left(|q(\tilde{t}+t^{\prime\prime}]|<2^{\nu}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right).\end{split}$
(53)

Since $2^{\nu}=2^{\nu-1}e^{bt^{\prime\prime}}(1-\delta)$,

$\begin{split}\mathbb{P}&\left(|q(\tilde{t}+t^{\prime\prime})|<2^{\nu}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right)\\\
&=\mathbb{P}\left(|q(\tilde{t}+t^{\prime\prime})|<2^{\nu-1}e^{bt^{\prime\prime}}(1-\delta)\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right).\end{split}$

By Lemma 4, and again using that $b\geq\frac{1}{2}a$,

$\begin{split}\mathbb{P}&\left(|q(\tilde{t}+t^{\prime\prime})|<2^{\nu-1}e^{bt^{\prime\prime}}(1-\delta)\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right.\right)\\\
&\lesssim\exp(-c\delta^{2}2^{2\nu}b)\lesssim\exp(-c^{\prime}\delta^{2}{2}^{2\nu}a).\end{split}$

Therefore,

$\mathbb{P}(t_{\nu}-\tilde{t}>t^{\prime\prime}\left|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t})\right)\lesssim\exp\left(-c\delta^{2}2^{2\nu}a\right).$
(54)

Combining (52) and (54) finishes the proof of the first assertion of the
lemma. ∎

##  4 When $a$ is large and positive

The goal of this section is to prove Lemma 2.i. In particular, we will show
that

$S_{*}(a)\lesssim a.$ (55)

when $a\geq 1$. We define:

$\displaystyle A_{o}$ $\displaystyle:=\\{b\in\mathbb{R}:2^{\ell_{\\#}}a\leq
b\\}$ $\displaystyle A_{p}$ $\displaystyle:=\left\\{b\in\mathbb{R}:a\leq
b<2^{\ell_{\\#}}a\right\\}$ $\displaystyle A_{u}$
$\displaystyle:=\left\\{b\in\mathbb{R}:0\leq b<a\right\\}$

where $\ell^{\\#}$ is as in Section 3. We have

$\begin{split}\mathbb{E}[S_{\nu}(a)]&=\mathbb{E}[S_{\nu}(a)|a_{\nu}\in
A_{o}]\cdot\mathbb{P}(a_{\nu}\in A_{o})\\\ &+\mathbb{E}[S_{\nu}(a)|a_{\nu}\in
A_{p}]\cdot\mathbb{P}(a_{\nu}\in A_{p})\\\ &+\mathbb{E}[S_{\nu}(a)|a_{\nu}\in
A_{u}]\cdot\mathbb{P}(a_{\nu}\in A_{u}).\end{split}$ (56)

We now state a lemma which will allow us to control (56).

######  Lemma 9.

If $a\geq 1$ and $\nu\geq 1$, then

  1. (i)

$\mathbb{E}[S_{\nu}(a)|a_{\nu}\in A_{u}]\cdot\mathbb{P}(a_{\nu}\in
A_{u})\lesssim\frac{1}{2^{2\nu}}$,

  2. (ii)

$\mathbb{E}[S_{\nu}(a)|a_{\nu}\in A_{p}]\cdot\mathbb{P}(a_{\nu}\in
A_{p})\lesssim\frac{a}{2^{2\nu}}$, and

  3. (iii)

$\mathbb{E}[S_{\nu}(a)|a_{\nu}\in A_{o}]\cdot\mathbb{P}(a_{\nu}\in
A_{o})\lesssim\frac{1}{2^{2\nu}}$.

Note that we have

$S_{*}(a)=\sum_{\nu=-1}^{\infty}\mathbb{E}[S_{\nu}(a)].$

Combining this with (56) and the lemma above gives

$\sum_{\nu\geq
1}\mathbb{E}[S_{\nu}(a)]\lesssim\sum_{\nu=1}^{\infty}\frac{a}{2^{2\nu}}\lesssim
a.$

We note that $\mathbb{E}[S_{-1}(a)]=O(1)$ and $\mathbb{E}[S_{0}(a)]=O(1)$. So
once we prove Lemma 9, we’ll have proved (55). The proof of Lemma 9 is
contained in Sections 4.1–4.2. It relies on the following lemma, which we
devote the remainder of this section to proving.

Recall that $E_{\nu}$ denotes the event that Epoch $\nu$ occurs. We write
$E_{\nu}^{c}$ to denote the complement of this event, i.e. the event that
Epoch $\nu$ does not occur.

######  Lemma 10.

If $\nu\geq 1$, $a>0$, and $0<\tilde{a}\leq\frac{1}{4}a$, then

$\mathbb{P}\left((a_{\nu}\in A_{p})\cup
E_{\nu}^{c}\left|a_{\nu-1}=\tilde{a}\right.\right)\geq 1-C\exp(-c2^{2\nu}a).$

###### Proof.

Fix $\tilde{t}\in(0,T)$ and write $b=a-2\tilde{a}$. Define

$t^{\prime}=\frac{\log(2)-\log\left(1+\frac{1}{2}\right)}{b}=\frac{\log\left(\frac{4}{3}\right)}{b}$
(57)

and

$t^{\prime\prime}=\frac{\log(2)-\log\left(1-\frac{1}{2}\right)}{b}=\frac{2\log(2)}{b}.$
(58)

Then, since $\tilde{a}\leq\frac{1}{4}a$, Lemma 8 tells us that when
$\tilde{t}+t^{\prime}\geq T$ we have

$\mathbb{P}(E_{\nu}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\lesssim\exp(-c2^{2\nu}a).$
(59)

When $\tilde{t}+t^{\prime}\leq T$, then Lemma 8 tells us that

$\mathbb{P}(t^{\prime}<t_{\nu}-\tilde{t}<t^{\prime\prime}|(a_{\nu-1}=\tilde{a})\cap(t_{\nu-1}=\tilde{t}))\geq
1-C\exp(-2^{2\nu}ac).$ (60)

Recall the definition of $a_{\nu}$:

$a_{\nu}=C_{0}\frac{\log(2)}{t_{\nu}-t_{\nu-1}}+C_{1}a_{\nu-1}.$

Combining this with (60) tells us that after conditioning on the events
$(a_{\nu-1}=\tilde{a})$ and $(t_{\nu-1}=\tilde{t})$, we have that

$C_{0}\frac{\log(2)}{t^{\prime\prime}}\leq a_{\nu}\leq
C_{0}\frac{\log(2)}{t^{\prime}}+\frac{C_{1}}{4}a$ (61)

holds with probability $\geq 1-C\exp(-2^{2\nu}ac)$. For reasons that will
become clear throughout the proof of Lemma 2, we’d like
$C_{1}=2^{\ell_{\\#}}$. We would like to guarantee that (61) implies
$a_{\nu}\in A_{p}$, therefore we need to choose $\ell_{\\#}$ and $C_{0}$ so
that

$a\leq C_{0}\frac{\log(2)}{t^{\prime\prime}}$ (62)

and

$C_{0}\frac{\log(2)}{t^{\prime}}<2^{\ell_{\\#}}a-\frac{C_{1}}{4}a=2^{\ell_{\\#}}a\frac{3}{4}.$
(63)

Since $b\geq\frac{1}{2}a$ (this follows from the hypothesis that
$\tilde{a}\leq\frac{1}{4}a$), we have

$C_{0}\frac{\log(2)}{t^{\prime\prime}}=C_{0}\frac{b}{2}\geq
C_{0}\frac{1}{4}a.$

Therefore setting $C_{0}=4$ ensures that (62) holds. Note that since $b<a$,

$C_{0}\frac{4\log(2)}{3t^{\prime}}=\frac{16\log(2)b}{3\log\left(\frac{4}{3}\right)}<13a.$

Thus, provided $\ell_{\\#}\geq 4$, we have

$C_{0}\frac{4\log(2)}{3t^{\prime}}<2^{\ell_{\\#}}a$

and (63) holds. This proves the lemma in the remaining case
$\tilde{t}+t^{\prime}\leq T$. ∎

###  4.1 Proof of Lemma 9.i and 9.ii

###### Proof of Lemma 9.i.

Recall the definition of $a_{\nu}$:

$a_{\nu}=C_{0}\frac{\log(\rho)}{t_{\nu}-t_{\nu-1}}+C_{1}a_{\nu-1},$

where $C_{0}=4$ and $C_{1}=2^{\ell_{\\#}}$. Notice that $a_{\nu}\geq
C_{1}a_{\nu-1}$ and we can choose $\ell_{\\#}$ to ensure
$C_{1}=2^{\ell_{\\#}}>4$. Therefore $a_{\nu}\in A_{u}$ implies that

$a_{\nu-1}\leq\frac{a}{C_{1}}<\frac{a}{4},$

and so we have

$\displaystyle\mathbb{P}(a_{\nu}\in A_{u})$
$\displaystyle=\mathbb{P}\left((a_{\nu}\in
A_{u})\cap\left(a_{\nu-1}\leq\frac{a}{4}\right)\right)$
$\displaystyle\leq\mathbb{P}\left(a_{\nu}\in
A_{u}\left|a_{\nu-1}\leq\frac{a}{4}\right.\right).$

Applying Lemma 10 gives

$\displaystyle\mathbb{P}\left(a_{\nu}\in
A_{u}\left|a_{\nu-1}\leq\frac{1}{4}a\right.\right)$ $\displaystyle\leq
1-\mathbb{P}\left((a_{\nu}\in A_{p})\cup
E_{\nu}^{c}\left|a_{\nu-1}\leq\frac{1}{4}a\right.\right)$
$\displaystyle\lesssim\exp(-c2^{2\nu}a).$

Combining these gives that

$\mathbb{P}(a_{\nu}\in A_{u})\lesssim\exp(-c2^{2\nu}a)$ (64)

for $\nu\geq 1$. Recall that we write $\chi_{I}$ to denote the indicator
function of an interval $I\subset\mathbb{R}$. Note that since $a_{\nu}\in
A_{u}$ implies that $a_{\nu}\leq a$, we have that

$\displaystyle\mathbb{E}[S_{\nu}(a)|a_{\nu}\in A_{u}]$
$\displaystyle=\mathbb{E}\left[\left.(1+(2a_{\nu})^{2})\int_{t_{\nu}}^{t_{\nu+1}}q^{2}(t)dt\right|a_{\nu}\in
A_{u}\right]$ $\displaystyle\lesssim
a^{2}\int_{0}^{T}\mathbb{E}[q^{2}(t)\cdot\chi_{[t_{\nu},t_{\nu+1}]}(t)|a_{\nu}\in
A_{u}]dt$ $\displaystyle\lesssim a^{2}2^{2(\nu+1)},$

where the last inequality uses the fact that $|q(t)|\leq 2^{\nu+1}$ for
$t_{\nu}\leq t\leq t_{\nu+1}$. Combining this with (64) and applying Remark 2
finishes the proof. ∎

###### Proof of Lemma 9.ii .

By applying Lemma 7, with $M=2^{\ell_{\\#}}a$ and $m=a$ we obtain

$\mathbb{E}[S_{\nu}(a)|a_{\nu}\in A_{p}]\lesssim a2^{2\nu}.$ (65)

Using the trivial bound $\mathbb{P}(a_{1}\in A_{p})\leq 1$, we see that

$\mathbb{E}[S_{1}(a)|a_{1}\in A_{p}]\cdot\mathbb{P}(a_{1}\in A_{p})\lesssim
a.$ (66)

We now claim that

$\mathbb{P}(a_{\nu}\in A_{p})=O\left(\frac{1}{a^{2}2^{4\nu}}\right)$ (67)

for $\nu>1$. As in the proof of Lemma 9.i, we observe that $a_{\nu}\geq
C_{1}a_{\nu-1}$. Note that if $a_{\nu}\in A_{p}$, then
$a_{\nu}<2^{\ell_{\\#}}a$; our choice of $C_{1}=2^{\ell_{\\#}}$ therefore
guarantees that $a_{\nu-1}<a$ when $a_{\nu}\in A_{p}$. Therefore

$\mathbb{P}\left(a_{\nu}\in A_{p}\right)=\mathbb{P}\left(\left(a_{\nu}\in
A_{p}\right)\cap\left(a_{\nu-1}\in
A_{u}\right)\right)\leq\mathbb{P}\left(a_{\nu-1}\in A_{u}\right).$ (68)

By (64) and Remark 2, we have that

$\mathbb{P}(a_{\nu-1}\in
A_{u})\lesssim\exp\left(-c2^{2\nu}a\right)=O\left(\frac{1}{a^{2}2^{4\nu}}\right)$
(69)

for $\nu>1$. This proves (67). Combining (65) and (67), we get

$\mathbb{E}[S_{\nu}(a)|a_{\nu}\in A_{p}]\cdot\mathbb{P}(a_{\nu}\in
A_{p})\lesssim\frac{1}{a2^{2\nu}}\leq\frac{a}{2^{2\nu}}$

when $\nu>1$. Combining this with (66) proves the lemma. ∎

###  4.2 Proof of Lemma 9.iii

We begin this section by introducing some notation. We define, for integers
$\ell\geq\ell_{\\#}$ and $\nu>1$,

$\displaystyle A_{o,\nu}^{\ell}$
$\displaystyle:=\\{b\in\mathbb{R}:2^{\ell}a_{\nu-1}\leq
b<2^{\ell+1}a_{\nu-1}\\}$ $\displaystyle A_{o}^{\ell}$
$\displaystyle:=\\{b\in\mathbb{R}:2^{\ell}a\leq b<2^{\ell+1}a\\}$

As in the proof of Lemma 9.i, note that $a_{\nu}\geq 2^{\ell_{\\#}}a_{\nu-1}$.
Therefore, when $\nu>1$, we have

$\begin{split}\mathbb{E}[S_{\nu}(a)&|a_{\nu}\in
A_{o}]\cdot\mathbb{P}(a_{\nu}\in A_{o})\\\
=&\sum_{\begin{subarray}{c}\ell_{1}\geq\ell_{\\#}\\\
\ell_{2}\geq\ell_{\\#}\end{subarray}}\mathbb{E}\left[S_{\nu}(a)|(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in
A_{o}^{\ell_{1}})\right]\cdot\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in A_{o}^{\ell_{1}})\right)\\\
&+\sum_{\ell\geq\ell_{\\#}}\mathbb{E}\left[S_{\nu}(a)|(a_{\nu}\in
A_{o,\nu}^{\ell})\cap(a_{\nu-1}\in
A_{p})\right]\cdot\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell})\cap(a_{\nu-1}\in A_{p})\right)\\\
&+\sum_{\ell\geq\ell_{\\#}}\mathbb{E}\left[S_{\nu}(a)|(a_{\nu}\in
A_{o}^{\ell})\cap(a_{\nu-1}\in A_{u})\right]\cdot\mathbb{P}\left((a_{\nu}\in
A_{o}^{\ell})\cap(a_{\nu-1}\in A_{u})\right)\end{split}$ (70)

When $\nu=1$, we have instead

$\begin{split}\mathbb{E}[&S_{1}(a)|a_{1}\in A_{o}]\cdot\mathbb{P}(a_{1}\in
A_{o})\\\ &=\sum_{\ell\geq\ell_{\\#}}\mathbb{E}[S_{1}(a)|(a_{1}\in
A_{o}^{\ell})\cap(a_{0}\in A_{u})]\cdot\mathbb{P}((a_{\nu}\in
A_{o}^{\ell})\cap(a_{0}\in A_{u})).\end{split}$ (71)

This is because $a_{0}=0$, and so $a_{0}\in A_{u}$. We write $a_{0}\in A_{u}$
in (71) rather than $a_{0}=0$ to be consistent with (70).

###### Proof of Lemma 9.iii.

Let $\nu\geq 1$. We will apply Lemma 7 three times. First, when
$\ell_{1}\geq\ell_{\\#}$ and $\ell_{2}\geq\ell_{\\#}$ we take
$M=2^{\ell_{2}+\ell_{1}+2}a$ and $m=(2^{\ell_{1}+\ell_{2}}-1)a$ to get

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in
A_{o}^{\ell_{1}})]\lesssim 2^{\ell_{1}+\ell_{2}}a2^{2\nu}.$ (72)

Next, when $\ell\geq\ell_{\\#}$ we take $M=2^{\ell+\ell_{\\#}+1}a$ and
$m=(2^{\ell}-1)a$ to get

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in A_{o,\nu}^{\ell})\cap(a_{\nu-1}\in
A_{p})]\lesssim 2^{\ell}a2^{2\nu}.$ (73)

Last, when $\ell\geq\ell_{\\#}$, we take $M=2^{\ell+1}a$ and $m=(2^{\ell}-1)a$
to get

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in A_{o}^{\ell})\cap(a_{\nu-1}\in
A_{u})]\lesssim 2^{\ell}a2^{2\nu}.$ (74)

Now let $\nu>1$. Note that the event $(a_{\nu-1}\in A_{o}^{\ell_{1}})$ implies
that $(2^{\ell_{1}+1}-1)a\leq 2a_{\nu-1}-a<(2^{\ell_{1}+2}-1)a$. By Remark 3,
the event $(a_{\nu}\in A_{o,\nu}^{\ell_{\\#}})$ implies the occurrence of the
event $E_{\nu}$ (recall that $E_{\nu}$ is the event that Epoch $\nu$ occurs).
Therefore for $\ell_{1}\geq\ell_{\\#}$ we have

$\mathbb{P}((a_{\nu}\in A_{o,\nu}^{\ell_{\\#}})\cap(a_{\nu-1}\in
A_{o}^{\ell_{1}}))\leq\mathbb{P}(E_{\nu}|(a_{\nu-1}\in A_{o}^{\ell_{1}})).$

We can then use Lemma 6 to get that

$\mathbb{P}(E_{\nu}|(a_{\nu-1}\in A_{o}^{\ell_{1}}))\lesssim
2^{\ell_{1}}a\exp(-c2^{2\nu}2^{\ell_{1}}a).$

Combining the last two inequalities and applying Remark 2 gives

$\mathbb{P}((a_{\nu}\in A_{o,\nu}^{\ell_{\\#}})\cap(a_{\nu-1}\in
A_{o}^{\ell_{1}}))\lesssim\frac{1}{2^{6\nu}2^{2\ell_{1}}a^{2}}.$ (75)

Similarly, note that the event $(a_{\nu-1}\in A_{p})$ implies that $a\leq
2a_{\nu-1}-a\leq(2^{\ell_{\\#}+1}-1)a$. We note that

$\mathbb{P}((a_{\nu}\in A_{o,\nu}^{\ell_{\\#}})\cap(a_{\nu-1}\in
A_{p}))\leq\mathbb{P}(E_{\nu}|(a_{\nu-1}\in A_{p}))$

and apply Lemma 6 to get that

$\mathbb{P}(E_{\nu}|(a_{\nu-1}\in A_{p}))\lesssim a\exp(-c2^{2\nu}a).$

Combining the last two inequalities and applying Remark 2 gives

$\mathbb{P}((a_{\nu}\in A_{o,\nu}^{\ell_{\\#}})\cap(a_{\nu-1}\in
A_{p}))\lesssim\frac{1}{2^{4\nu}a}.$ (76)

Next, note that when $\nu\geq 2$ we can apply (64) to get

$\begin{split}\mathbb{P}\left((a_{\nu}\in A_{o}^{\ell_{\\#}})\cap(a_{\nu-1}\in
A_{u})\right)&\leq\mathbb{P}(a_{\nu-1}\in A_{u})\\\
&\lesssim\exp\left(-c2^{2\nu}a\right)\\\
&\lesssim\frac{1}{2^{4\nu}a^{2}}.\end{split}$ (77)

When $\nu=1$, we apply Lemma 10 to get that

$\mathbb{P}(a_{1}\in A_{o}^{\ell_{\\#}})\leq 1-\mathbb{P}((a_{1}\in A_{p})\cup
E_{1}^{c})\lesssim\exp(-ca)\lesssim\frac{1}{a^{2}}.$ (78)

Now suppose $\ell>\ell_{\\#}$ and $\nu\geq 1$. Note that when $a_{\nu}\in
A_{o}^{\ell}$ and $a_{\nu-1}\in A_{u}$ we have

$a_{\nu}-C_{1}a_{\nu-1}\geq 2^{\ell}a-2^{\ell_{\\#}}a\geq 2^{\ell-1}a$

since $C_{1}=2^{\ell_{\\#}}$. Moreover, $a_{\nu-1}\in A_{u}$ implies that
$|a-2a_{\nu-1}|\leq a$. We choose $\ell_{\\#}$ to be sufficiently large to
guarantee that

$\frac{1}{2^{\ell-1}}\leq\frac{1}{2^{\ell_{\\#}}}<\frac{1}{10C_{0}\log(2)};$

this allows us to apply Lemma 5 with $\gamma(x):=a$ and
$\beta(x):=2^{\ell-1}a$ for all $x\in A_{u}$ to get

$\begin{split}\mathbb{P}\left((a_{\nu}\in
A_{o}^{\ell})\cap\right.&\left.(a_{\nu-1}\in
A_{u})\right)\leq\mathbb{P}\left((a_{\nu}\in A_{o}^{\ell})|(a_{\nu-1}\in
A_{u})\right)\\\ &\leq\mathbb{P}\left((a_{\nu}-C_{1}a_{\nu-1})\geq
2^{\ell-1}a|a_{\nu-1}\in A_{u}\right)\\\
&\lesssim\exp\left(-c2^{2\nu}2^{\ell-1}a\right)\lesssim\frac{1}{2^{4\nu}2^{2\ell}a^{2}}.\end{split}$
(79)

Now suppose $\ell_{2}>\ell_{\\#}$ and $\nu>1$. Then $(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})$ implies that

$a_{\nu}-C_{1}a_{\nu-1}\geq 2^{\ell_{2}-1}a_{\nu-1}$

(where we’ve used that $C_{1}=2^{\ell_{\\#}}$). If $a_{\nu-1}\geq a$, then

$|a-2a_{\nu-1}|\leq 2a_{\nu-1}.$

Again, we choose $\ell_{\\#}$ to be sufficiently large to guarantee that

$\frac{1}{2^{\ell_{2}-2}}\leq\frac{1}{2^{\ell_{\\#}-1}}<\frac{1}{10C_{0}\log(2)};$

this allows us to apply Lemma 5 with $\gamma(x)=2x$ and
$\beta(x)=2^{\ell_{2}-1}x$ for $x\in A_{o}^{\ell_{1}}$ to get

$\begin{split}\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap\right.&\left.(a_{\nu-1}\in
A_{o}^{\ell_{1}})\right)\leq\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})|(a_{\nu-1}\in A_{o}^{\ell_{1}})\right)\\\
&\leq\mathbb{P}\left((a_{\nu}-C_{1}a_{\nu-1})\geq
2^{\ell_{2}-1}a_{\nu-1}|(a_{\nu-1}\in A_{o}^{\ell_{1}})\right)\\\
&\lesssim\exp\left(-c2^{2\nu}2^{\ell_{2}+\ell_{1}}a\right)\lesssim\frac{1}{2^{4\nu}2^{2(\ell_{1}+\ell_{2})}a^{2}}\end{split}$
(80)

and again with $x\in A_{p}$ to get

$\begin{split}\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap\right.&(a_{\nu-1}\left.\in
A_{p})\right)\leq\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})|(a_{\nu-1}\in A_{p})\right)\\\
&\leq\mathbb{P}\left((a_{\nu}-C_{1}a_{\nu-1})\geq
2^{\ell_{2}-1}a_{\nu-1}|(a_{\nu-1}\in A_{p})\right)\\\
&\lesssim\exp\left(-c2^{2\nu}2^{\ell_{2}}a\right)\lesssim\frac{1}{2^{4\nu}2^{2\ell_{2}}a^{2}}.\end{split}$
(81)

Combining (72), (75), and (80) gives

$\begin{split}\sum_{\begin{subarray}{c}\ell_{1}\geq\ell_{\\#}\\\
\ell_{2}\geq\ell_{\\#}\end{subarray}}\mathbb{E}[S_{\nu}(a)&|(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in
A_{o}^{\ell_{1}})]\cdot\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in A_{o}^{\ell_{1}})\right)\\\
&\lesssim\sum_{\begin{subarray}{c}\ell_{1}\geq\ell_{\\#}\\\
\ell_{2}\geq\ell_{\\#}\end{subarray}}2^{\ell_{1}+\ell_{2}}a2^{2\nu}\cdot\left(\frac{1}{2^{4\nu}2^{2(\ell_{1}+\ell_{2})}a^{2}}\right)\\\
&\lesssim 2^{-2\nu}\end{split}$ (82)

when $\nu>1$. Next, combine (73), (76), and (81) to get

$\begin{split}\sum_{\ell\geq\ell_{\\#}}\mathbb{E}[S_{\nu}(a)&|(a_{\nu}\in
A_{o,\nu}^{\ell})\cap(a_{\nu-1}\in A_{p})]\cdot\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell})\cap(a_{\nu-1}\in A_{p})\right)\\\
&\lesssim\sum_{\ell\geq\ell_{\\#}}2^{\ell}a2^{2\nu}\cdot\left(\frac{1}{2^{4\nu}2^{2\ell}a}\right)\\\
&\lesssim 2^{-2\nu}\end{split}$ (83)

when $\nu>1$. Finally, combine (74), (77), (78), and (79) to get

$\begin{split}\sum_{\ell\geq\ell_{\\#}}\mathbb{E}[S_{\nu}(a)&|(a_{\nu}\in
A_{o}^{\ell})\cap(a_{\nu-1}\in A_{u})]\cdot\mathbb{P}((a_{\nu}\in
A_{o}^{\ell})\cap(a_{\nu-1}\in A_{u}))\\\
&\lesssim\sum_{\ell\geq\ell_{\\#}}2^{\ell}a2^{2\nu}\cdot\left(\frac{1}{2^{4\nu}2^{2\ell}a^{2}}\right)\\\
&\leq 2^{-2\nu}\end{split}$ (84)

when $\nu\geq 1$. Combining these three bounds with (70) proves the lemma for
$\nu>1$. Combining (84) and (71) proves the lemma for $\nu=1$. ∎

##  5 When $|a|$ is bounded

In this section we prove Lemma 2.ii, i.e. we show that there exists a constant
$C>1$ depending only on $T$ such that $S_{*}(a)\leq C$ for all $|a|\leq 1$. We
first remark that

$\sum_{\nu=-1}^{0}\mathbb{E}[S_{\nu}(a)]=O(1)$ (85)

since $a_{-1}=a_{0}=0$ (and thus $u_{-1}=u_{0}=0$) and $|q(t)|\leq 2$ for all
$t\in[0,t_{1}]$. Next, recall that

$a_{\nu}=C_{0}\frac{\log(2)}{t_{\nu}-t_{\nu-1}}+C_{1}\cdot a_{\nu-1},$ (86)

where $C_{0}=4$ and $C_{1}=2^{\ell_{\\#}}$. Since we always have
$t_{\nu}-t_{\nu-1}\leq T$, whenever we reach Epoch $\nu$ we have
$a_{\nu}\geq\frac{C_{0}\log(2)C_{1}^{\nu-1}}{T}>\frac{2C_{1}^{\nu-1}}{T}$. We
define

$\nu_{*}:=\left\lceil\frac{\log(T\cdot
2^{\ell_{\\#}})}{\log(C_{1})}\right\rceil+1;$

observe that $\nu_{*}=O(1)$. Note that if we reach Epoch $\nu_{*}$ we are
guaranteed to have

$a_{\nu_{*}}>2^{\ell_{\\#}+1}.$

This implies that when $\nu\geq\nu_{*}+1$ we have

$\mathbb{E}[S_{\nu}(a)]=\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}\geq
1)]\cdot\mathbb{P}(a_{\nu-1}\geq 1).$ (87)

We will show that when $\nu\geq 2$ we have

$\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}\geq 1)]\cdot\mathbb{P}(a_{\nu-1}\geq
1)=O\left(\frac{1}{2^{2\nu}}\right).$ (88)

Combining (87) and (88) gives

$\sum_{\nu=\nu_{*}+1}^{\infty}\mathbb{E}[S_{\nu}(a)]\leq\sum_{\nu=\nu_{*}+1}^{\infty}\frac{C}{2^{2\nu}}=O(1).$
(89)

We now prove (88). Define

$\widehat{A}_{o}^{\ell}:=\\{b\in\mathbb{R}:2^{\ell}\leq b<2^{\ell+1}\\}$

for $\ell\geq 0$. Fix $\nu\geq 2$. We have

$\begin{split}\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}\geq
1)]&\cdot\mathbb{P}(a_{\nu-1}\geq 1)\\\
&=\sum_{\ell_{1}=0}^{\infty}\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})]\cdot\mathbb{P}(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}}).\end{split}$
(90)

Given $a_{\nu-1}>0$, we define

$A_{o,\nu}^{\ell}:=\\{b\in\mathbb{R}:2^{\ell}a_{\nu-1}\leq
b<2^{\ell+1}a_{\nu-1}\\}$

for $\ell\geq 0$. Note that $a_{\nu}\geq 2^{\ell_{\\#}}a_{\nu-1}$; this
follows from (86). Continuing from (90), we get

$\begin{split}\mathbb{E}&[S_{\nu}(a)|(a_{\nu-1}\geq
1)]\cdot\mathbb{P}(a_{\nu-1}\geq 1)\\\ &=\sum_{\begin{subarray}{c}\ell_{1}\geq
0\\\ \ell_{2}\geq\ell_{\\#}\end{subarray}}\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})]\cdot\mathbb{P}((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})).\end{split}$
(91)

The event $(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})$, along with
the assumption that $|a|\leq 1$, implies that $a_{\nu}\leq
2^{\ell_{1}+\ell_{2}+2}$ and $2a_{\nu}-a\geq 2^{\ell_{1}+\ell_{2}+1}-1\geq
2^{\ell_{1}+\ell_{2}}$. Therefore we can apply Lemma 7 to get

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})]\lesssim
2^{2\nu}2^{\ell_{2}+\ell_{1}}.$ (92)

Note that

$\begin{split}\mathbb{P}((a_{\nu}\in
A_{o,\nu}^{\ell_{\\#}})\cap(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}}))&\leq\mathbb{P}((a_{\nu}\in
A_{o,\nu}^{\ell_{\\#}})|(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}}))\\\
&\leq\mathbb{P}(E_{\nu}|(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})).\end{split}$

Since the event $(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})$ for $\ell_{1}\geq
0$ implies that $2a_{\nu-1}-a\leq 2^{\ell_{1}+2}+1\lesssim 2^{\ell_{1}}$ and
that $2a_{\nu-1}-a\geq 2^{\ell_{1}+1}-1\geq 2^{\ell_{1}}$, we can apply Lemma
6 to get

$\mathbb{P}(E_{\nu}|(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}}))\lesssim
2^{\ell_{1}}\exp(-c2^{2\nu}2^{\ell_{1}}).$

Therefore

$\mathbb{P}((a_{\nu}\in
A_{o,\nu}^{\ell_{\\#}})\cap(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}}))\lesssim
2^{\ell_{1}}\exp(-c2^{2\nu}2^{\ell_{1}}).$ (93)

Now suppose that $\ell_{2}>\ell_{\\#}$. In this case, the event $(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})$ implies that

$a_{\nu}-C_{1}a_{\nu-1}\geq(2^{\ell_{2}}-2^{\ell_{\\#}})a_{\nu-1}\geq
2^{\ell_{2}-1}a_{\nu-1}.$

Therefore,

$\begin{split}\mathbb{P}((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap&(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}}))\\\
&\leq\mathbb{P}(a_{\nu}\in
A_{o,\nu}^{\ell_{2}}|a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})\\\
&\leq\mathbb{P}(a_{\nu}-C_{1}a_{\nu-1}\geq
2^{\ell_{2}-1}a_{\nu-1}|a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}}).\end{split}$

Note that $|a-2a_{\nu-1}|\leq 3a_{\nu-1}$ (since we assume $|a|\leq 1\leq
a_{\nu-1}$). We are going to apply Lemma 5 with $\beta(x)=2^{\ell_{2}-1}x$,
$\gamma(x)=3x$, and $X=\widehat{A}_{o}^{\ell_{1}}$. Note that in this case
$\beta^{*}=2^{\ell_{2}+\ell_{1}-1}$. We choose $\ell_{\\#}$ to be large enough
to ensure that the hypothesis

$\frac{\gamma(x)}{\beta(x)}=\frac{3}{2^{\ell_{2}-1}}\leq\frac{3}{2^{\ell_{\\#}}}<\frac{1}{C_{0}10\log(2)}.$

holds. Applying Lemma 5 gives

$\mathbb{P}(a_{\nu}-C_{1}a_{\nu-1}\geq
2^{\ell_{2}-1}a_{\nu-1}|a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}})\lesssim\exp(-c2^{2\nu}2^{\ell_{2}+\ell_{1}}).$

Consequently,

$\mathbb{P}((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in\widehat{A}_{o}^{\ell_{1}}))\lesssim\exp(-c2^{2\nu}2^{\ell_{2}+\ell_{1}}).$
(94)

Combining (91) - (94) and applying Remark 2, we get that

$\begin{split}\mathbb{E}[&S_{\nu}(a)|(a_{\nu-1}\geq
1)]\cdot\mathbb{P}(a_{\nu-1}\geq 1)\\\
&\leq\sum_{\ell_{1}=0}^{\infty}2^{2\nu}2^{2\ell_{1}}\exp(-c2^{2\nu}2^{\ell_{1}})+\sum_{\begin{subarray}{c}\ell_{1}\geq
0\\\
\ell_{2}>\ell_{\\#}\end{subarray}}2^{2\nu}2^{\ell_{2}+\ell_{1}}\exp(-c2^{2\nu}2^{\ell_{2}+\ell_{1}})\\\
&=O\left(\frac{1}{2^{2\nu}}\right).\end{split}$

This proves (88). By (85) and (89), we will have proved Lemma 2.ii once we
show that

$\sum_{\nu=1}^{\nu_{*}}\mathbb{E}[S_{\nu}(a)]=O(1).$ (95)

Note that (88), which we’ve just proved, implies that

$\mathbb{E}[S_{\nu}(a)]=\mathbb{E}[S_{\nu}(a)|a_{\nu-1}<1]\cdot\mathbb{P}(a_{\nu-1}<1)+O(1)$

for $2\leq\nu\leq\nu_{*}$. Therefore, since $a_{0}=0$ and $\nu_{*}=O(1)$, (95)
is implied by showing that

$\mathbb{E}[S_{\nu}(a)|a_{\nu-1}<1]\cdot\mathbb{P}(a_{\nu-1}<1)=O(1)$ (96)

for any $1\leq\nu\leq\nu_{*}$. We first claim that

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}\leq 2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1)]=O(1)$

when $1\leq\nu\leq\nu_{*}$. Recall that we have $|q(t)|\leq 2^{\nu_{*}+1}$
when $t\in[t_{1},t_{\nu_{*}+1}]$ and $u(t)=-2a_{\nu}q(t)$ when
$t\in[t_{\nu},t_{\nu+1}]$. Therefore the assumption $(a_{\nu}\leq
2^{\ell_{\\#}+1})$ implies that $|u(t)|=O(1)$ for all
$t\in[t_{1},t_{\nu_{*}+1}]$. This shows that when $1\leq\nu\leq\nu_{*}$, we
have

$\begin{split}\mathbb{E}&[S_{\nu}(a)|(a_{\nu}\leq
2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1)]\\\
&=\mathbb{E}\left[\left.\int_{t_{\nu}}^{t_{\nu+1}}(q^{2}(t)+u^{2}(t))dt\right|(a_{\nu}\leq
2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1)\right]=O(1).\end{split}$ (97)

Thus, in order to prove (96), it remains to control

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}>2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1)]\cdot\mathbb{P}((a_{\nu}>2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1)).$

for $1\leq\nu\leq\nu_{*}$. Note that we have

$\begin{split}\mathbb{E}&[S_{\nu}(a)|(a_{\nu}>2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1)]\cdot\mathbb{P}((a_{\nu}>2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1))\\\
&=\sum_{\ell=\ell^{\\#}+1}^{\infty}\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in\widehat{A}_{o}^{\ell})\cap(a_{\nu-1}<1)]\cdot\mathbb{P}((a_{\nu-1}<1)\cap(a_{\nu}\in\widehat{A}_{o}^{\ell})).\end{split}$
(98)

The event $(a_{\nu}\in\widehat{A}_{o}^{\ell})\cap(a_{\nu-1}<1)$ (and the
assumption that $|a|\leq 1$) implies that $a_{\nu}\leq 2^{\ell+1}$ and
$2a_{\nu}-a\geq 2^{\ell+1}-1\geq 2^{\ell}$. Therefore we can apply Lemma 7 to
get

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in\widehat{A}_{o}^{\ell})\cap(a_{\nu-1}<1)]\lesssim
2^{\ell}.$ (99)

Next, observe that the event $(a_{\nu}\in\widehat{A}_{o}^{\ell})$ given the
event $(a_{\nu-1}<1)$, along with the fact that $\ell>\ell_{\\#}$, implies
that

$a_{\nu}-C_{1}a_{\nu-1}>2^{\ell}-2^{\ell_{\\#}}\geq 2^{\ell-1}.$

Therefore

$\begin{split}\mathbb{P}((a_{\nu-1}<1)\cap(a_{\nu}\in\widehat{A}_{o}^{\ell}))&\leq\mathbb{P}((a_{\nu}\in\widehat{A}_{o}^{\ell})|(a_{\nu-1}<1))\\\
&\leq\mathbb{P}(a_{\nu}-C_{1}a_{\nu-1}>2^{\ell-1}|(a_{\nu-1}<1)).\end{split}$
(100)

Note that $|2a_{\nu-1}-a|\leq 3$. We will apply Lemma 5 with
$X=\\{b\in\mathbb{R}:b<1\\}$, $\beta(x)=2^{\ell-1}$, and $\gamma(x)=3$. We
choose $\ell_{\\#}$ to be sufficiently large to guarantee that

$\frac{\gamma(x)}{\beta(x)}=\frac{3}{2^{\ell-1}}<\frac{3}{2^{\ell_{\\#}}}<\frac{1}{10C_{0}\log(2)}.$

Then we apply Lemma 5 to get that

$\mathbb{P}(a_{\nu}-C_{1}a_{\nu-1}>2^{\ell-1}|(a_{\nu-1}<1))\lesssim\exp(-c2^{\ell-1}).$
(101)

Combining (98) - (101) gives

$\begin{split}\mathbb{E}[S_{\nu}(a)&|(a_{\nu}>2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1)]\cdot\mathbb{P}((a_{\nu}>2^{\ell_{\\#}+1})\cap(a_{\nu-1}<1))\\\
&\lesssim\sum_{\ell=\ell^{\\#}+1}^{\infty}2^{\ell}\exp(-c2^{\ell-1})\\\
&=O(1).\end{split}$ (102)

This completes the proof of (96), and thus completes the proof of Lemma 2.ii.

##  6 When $a$ is large and negative

In this section we prove Lemma 2.iii, i.e. we show that for all $a\leq-1$ we
have $S_{*}(a)\lesssim\frac{1}{|a|}$. We first note that

$S_{*}(a)=\sum_{\nu=-1}^{\infty}\mathbb{E}[S_{\nu}(a)].$

Since $a_{-1}=a_{0}=0$, we apply Lemma 7 with $m=|a|$ and $M=0$ to get

$\mathbb{E}[S_{-1}(a)+S_{0}(a)]\lesssim\frac{1}{|a|}.$

It remains to show that

$\sum_{\nu=1}^{\infty}\mathbb{E}[S_{\nu}(a)]=O\left(\frac{1}{|a|}\right).$

Let $A_{o,\nu}^{\ell}$ be as in Section 4.2. Define

$B_{o}^{\ell}:=\\{b\in\mathbb{R}:2^{\ell}|a|\leq b<2^{\ell+1}|a|\\}.$

When $\nu\geq 2$, we have

$\begin{split}\mathbb{E}[S_{\nu}(a)]&\leq\sum_{\ell_{1}\geq
0}\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}\in
B_{o}^{\ell_{1}})]\cdot\mathbb{P}(a_{\nu-1}\in B_{o}^{\ell_{1}})\\\
&+\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}<|a|)]\cdot\mathbb{P}(a_{\nu-1}<|a|).\end{split}$
(103)

When $\nu=1$, we have

$\mathbb{E}[S_{1}(a)]=\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}<|a|)]\cdot\mathbb{P}(a_{\nu-1}<|a|).$
(104)

We first show how to control the first term in (103). Recall (see (12)) that
$a_{\nu}\geq 2^{\ell_{\\#}}a_{\nu-1}$. Therefore

$\begin{split}\mathbb{E}[S_{\nu}(a)|&(a_{\nu-1}\in
B_{o}^{\ell_{1}})]\cdot\mathbb{P}(a_{\nu-1}\in B_{o}^{\ell_{1}})\\\
&=\sum_{\ell_{2}\geq\ell_{\\#}}\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in
B_{o}^{\ell_{1}})]\cdot\mathbb{P}\left((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in B_{o}^{\ell_{1}})\right).\end{split}$
(105)

The event $(a_{\nu}\in A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in
B_{o}^{\ell_{1}})$ implies that $a_{\nu}\leq 2^{\ell_{2}+\ell_{1}+2}|a|$ and
$2a_{\nu}-a\geq 2^{\ell_{2}+\ell_{1}}|a|$. Therefore we can apply Lemma 7 to
get

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in
B_{o}^{\ell_{1}})]\lesssim 2^{\ell_{1}+\ell_{2}}\cdot 2^{2\nu}\cdot|a|.$ (106)

Suppose $\ell_{2}>\ell_{\\#}$. Then the event $(a_{\nu}\in
A_{o,\nu}^{\ell_{2}})\cap(a_{\nu-1}\in B_{o}^{\ell_{1}})$ implies that

$a_{\nu}-C_{1}a_{\nu-1}\geq(2^{\ell_{2}}-2^{\ell_{\\#}})\cdot a_{\nu-1}\geq
2^{\ell_{2}-1+\ell_{1}}|a|$

and that

$|a-2a_{\nu-1}|\leq|a|+2^{\ell_{1}+2}|a|\leq 2^{\ell_{1}+3}|a|.$

We are going to apply Lemma 5 with $\gamma(x)=2^{\ell_{1}+3}|a|$ and
$\beta(x)=2^{\ell_{1}+\ell_{2}-1}|a|$ and $X=B_{o}^{\ell_{1}}$. Choosing
$\ell_{\\#}$ sufficiently large guarantees that

$\frac{\gamma(x)}{\beta(x)}=\frac{1}{2^{\ell_{2}-4}}<\frac{1}{2^{\ell_{\\#}-4}}<\frac{1}{10C_{0}\log(2)}.$

Therefore we apply Lemma 5 to get that

$\begin{split}\mathbb{P}((a_{\nu}\in A_{o,\nu}^{\ell_{2}})\cap(&a_{\nu-1}\in
B_{o}^{\ell_{1}}))\leq\mathbb{P}((a_{\nu}\in
A_{o,\nu}^{\ell_{2}})|(a_{\nu-1}\in B_{o}^{\ell_{1}}))\\\
&\leq\mathbb{P}(a_{\nu}-C_{1}a_{\nu-1}\geq|a|\cdot
2^{\ell_{2}+\ell_{1}-1}|(a_{\nu-1}\in B_{o}^{\ell_{1}}))\\\
&\lesssim\exp(-c2^{2\nu}2^{\ell_{1}+\ell_{2}}|a|)\\\
&\lesssim\frac{1}{2^{4\nu}2^{2(\ell_{1}+\ell_{2})}|a|^{2}}.\end{split}$ (107)

Next, note that

$\mathbb{P}((a_{\nu}\in A_{o,\nu}^{\ell_{\\#}})\cap(a_{\nu-1}\in
B_{o}^{\ell_{1}}))\leq\mathbb{P}(E_{\nu}|(a_{\nu-1}\in B_{o}^{\ell_{1}})).$

Since the event $(a_{\nu-1}\in B_{o}^{\ell_{1}})$ implies that
$2a_{\nu-1}-a\leq 2^{\ell_{1}+2}|a|+|a|\leq 2^{\ell_{1}+3}|a|$ and
$2a_{\nu-1}-a\geq 2^{\ell_{1}+1}|a|+|a|\geq 2^{\ell_{1}+1}|a|$, we can apply
Lemma 6 to get

$\mathbb{P}(E_{\nu}|(a_{\nu-1}\in B_{o}^{\ell_{1}}))\lesssim
2^{\ell_{1}}|a|\exp(-c2^{2\nu}2^{\ell_{1}}|a|).$

The last two equations and Remark 2 give

$\mathbb{P}((a_{\nu}\in A_{o,\nu}^{\ell_{\\#}})\cap(a_{\nu-1}\in
B_{o}^{\ell_{1}}))\lesssim\frac{1}{2^{6\nu}2^{2\ell_{1}}|a|^{2}}.$ (108)

Combining (105) - (108) gives

$\begin{split}\sum_{\ell_{1}\geq 0}\mathbb{E}[S_{\nu}(a)|&(a_{\nu-1}\in
B_{o}^{\ell_{1}})]\cdot\mathbb{P}(a_{\nu-1}\in B_{o}^{\ell_{1}})\\\
&\lesssim\sum_{\begin{subarray}{c}\ell_{2}\geq\ell_{\\#}\\\ \ell_{1}\geq
0\end{subarray}}2^{\ell_{1}+\ell_{2}}2^{2\nu}|a|\left(\frac{1}{2^{4\nu}2^{2(\ell_{1}+\ell_{2})}|a|^{2}}\right)\lesssim\frac{1}{2^{2\nu}|a|}.\end{split}$
(109)

Next, we claim that

$\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}<|a|)]\cdot\mathbb{P}(a_{\nu-1}<|a|)=O\left(\frac{1}{2^{2\nu}|a|}\right)$
(110)

for $\nu\geq 1$. Combining this with (103), (104), and (109) gives

$\sum_{\nu=1}^{\infty}\mathbb{E}[S_{\nu}(a)]\lesssim\sum_{\nu=1}^{\infty}\frac{1}{2^{2\nu}|a|}\lesssim\frac{1}{|a|}.$

This completes the proof of Lemma 2.iii, and thus it just remains to establish
(110).

We have

$\begin{split}\mathbb{E}[S_{\nu}(a)|&(a_{\nu-1}<|a|)]\cdot\mathbb{P}(a_{\nu-1}<|a|)\\\
&=\sum_{\ell_{1}\geq\ell_{\\#}}\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in
A_{o}^{\ell_{1}})\cap(a_{\nu-1}<|a|)]\cdot\mathbb{P}((a_{\nu}\in
A_{o}^{\ell_{1}})\cap(a_{\nu-1}<|a|)).\end{split}$ (111)

Since the event $(a_{\nu}\in A_{o}^{\ell_{1}})\cap(a_{\nu-1}<|a|)$ implies
that $a_{\nu}\leq 2^{\ell_{1}+1}|a|$ and $2a_{\nu}-a\geq
2^{\ell_{1}+1}|a|+|a|\geq 2^{\ell_{1}+1}|a|$, we apply Lemma 7 to get

$\mathbb{E}[S_{\nu}(a)|(a_{\nu}\in
A_{o}^{\ell_{1}})\cap(a_{\nu-1}<|a|)]\lesssim 2^{2\nu}2^{\ell_{1}}|a|.$ (112)

For $\ell_{1}>\ell_{\\#}$, the event $(a_{\nu}\in
A_{o}^{\ell_{1}})\cap(a_{\nu-1}<|a|)$ implies that

$a_{\nu}-C_{1}a_{\nu-1}\geq(2^{\ell_{1}}-2^{\ell_{\\#}})\cdot|a|\geq
2^{\ell_{1}-1}|a|$

and that

$|a-2a_{\nu-1}|\leq 3\cdot|a|.$

We will apply Lemma 5 with $\beta(x)=2^{\ell_{1}-1}\cdot|a|$ and
$\gamma(x)=3\cdot|a|$. Choosing $\ell_{\\#}$ sufficiently large guarantees
that

$\frac{\gamma(x)}{\beta(x)}=\frac{3}{2^{\ell_{1}-1}}<\frac{3}{2^{\ell_{\\#}-1}}<\frac{1}{10C_{0}\log(2)}.$

Therefore we can apply Lemma 5 to get

$\begin{split}\mathbb{P}((a_{\nu}\in
A_{o}^{\ell_{1}})\cap(a_{\nu-1}<|a|))&\leq\mathbb{P}(a_{\nu}\in
A_{o}^{\ell_{1}}|a_{\nu-1}<|a|)\\\ &\leq\mathbb{P}(a_{\nu}-C_{1}a_{\nu-1}\geq
2^{\ell_{1}-1}|a||(a_{\nu-1}<|a|))\\\
&\lesssim\exp(-c2^{2\nu}2^{\ell_{1}-1}|a|)\\\
&\lesssim\frac{1}{2^{4\nu}2^{2\ell_{1}}|a|^{2}}.\end{split}$ (113)

Since the event $(a_{\nu-1}<|a|)$ implies that $2a_{\nu-1}-a\leq 3|a|$ and
$2a_{\nu-1}-a\geq|a|$, we can apply Lemma 6 to get

$\begin{split}\mathbb{P}((a_{\nu}\in
A_{o}^{\ell_{\\#}})\cap(a_{\nu-1}<|a|))&\leq\mathbb{P}(E_{\nu}|(a_{\nu-1}<|a|))\\\
&\lesssim|a|\exp(-c2^{2\nu}|a|)\\\
&\lesssim\frac{1}{2^{6\nu}|a|^{2}}.\end{split}$ (114)

Combining (111)-(114) gives

$\mathbb{E}[S_{\nu}(a)|(a_{\nu-1}<|a|)]\cdot\mathbb{P}(a_{\nu-1}<|a|)\lesssim\sum_{\ell_{1}\geq\ell_{\\#}}\frac{1}{2^{2\nu}2^{\ell_{1}}|a|}=O\left(\frac{1}{2^{2\nu}|a|}\right).$
(115)

This proves (110), finishing the proof of the lemma.

##  7 The optimal strategy for known $a$

The goal of this section is to prove Lemma 1. We define the _expected cost-to-
go_ of the optimal strategy $\sigma_{\text{opt}}(a)$ at time $t$ and position
$q$ by

$J_{0}(q,t;a)=\mathbb{E}\left[\int_{t}^{T}(q^{2}+u^{2})dt\right]\;.$ (116)

Note that (116) is more general than the quantity $S_{\text{opt}}(a)$
introduced in Section 2, but that we have $S_{\text{opt}}(a)=J_{0}(0,0;a)$. We
begin by deriving a Hamilton-Jacobi-Bellman equation for $J_{0}$. For a small
time increment $\Delta t$, we have

$\displaystyle J_{0}(q,t;a)=(q^{2}+u^{2})\Delta t+\mathbb{E}[J_{0}(q+\Delta
q,t+\Delta t;a)],$ (117)

where $\Delta q$ and $\Delta t$ are the corresponding increments of $q$ and
$t$. Expanding the last term in a Taylor series, we obtain

$\displaystyle J_{0}(q,t;a)=(q^{2}+u^{2})\Delta t$
$\displaystyle+J_{0}(q,t;a)+(\Delta
t)\partial_{t}J_{0}(q,t;a)+\mathbb{E}[\Delta q]\partial_{q}J_{0}(q,t;a)$
$\displaystyle+\frac{1}{2}\mathbb{E}[(\Delta
q)^{2}]\partial_{q}^{2}J_{0}(q,t;a)+o(\Delta t).$

Equation (1) implies that

$\displaystyle\mathbb{E}[\Delta q]=(qa+u)\Delta t$ (118)
$\displaystyle\mathbb{E}[\Delta q^{2}]=\Delta t.$ (119)

Thus, after dividing by $\Delta t$ and taking $\Delta t\rightarrow 0$, we
obtain for an optimal strategy $u$

$\displaystyle
0=\min_{u\in\mathbb{R}}\left\\{\partial_{t}J_{0}+(qa+u)\partial_{q}J_{0}+\frac{1}{2}\partial_{q}^{2}J_{0}+q^{2}+u^{2}\right\\}$
(120)

with $J_{0}(q,T;a)=0$. The minimum of the RHS with respect to $u$ occurs when

$\displaystyle u=-\frac{1}{2}\partial_{q}J_{0}.$ (121)

We thus arrive at a final PDE

$\displaystyle
0=\partial_{t}J_{0}+(qa)\partial_{q}J_{0}+\frac{1}{2}\partial_{q}^{2}J_{0}+q^{2}-\frac{1}{4}\left(\partial_{q}J_{0}\right)^{2}.$
(122)

We can now guess a solution to $J_{0}$ of the form

$J_{0}(q,t;a)=p(t;a)q^{2}+r(t;a)\;,$ (123)

where $p(t;a)$ and $r(t;a)$ are solutions to the following differential
equations:

$\displaystyle-p^{\prime}(t;a)$ $\displaystyle=2ap(t;a)+1-p^{2}(t;a),$
$\displaystyle p(T;a)=0$ (124) $\displaystyle-r^{\prime}(t;a)$
$\displaystyle=p,$ $\displaystyle r(T;a)=0$ (125)

Note that

$S_{\text{opt}}(a)=J_{0}(0,0;a)=r(0;a).$

Solving (124) explicitly gives

$p(t;a)=a-\sqrt{a^{2}+1}\tanh\left((t-T)\sqrt{a^{2}+1}+\tanh^{-1}\left(\frac{a}{\sqrt{a^{2}+1}}\right)\right)\;.$
(126)

We integrate (126) from $0$ to $T$ to get

$\displaystyle\begin{split}r(0;a)=aT&-\log\left(\cosh\left(\tanh^{-1}\left(\frac{a}{\sqrt{a^{2}+1}}\right)\right)\right)\\\
&+\log\left(\cosh\left(\tanh^{-1}\left(\frac{a}{\sqrt{a^{2}+1}}\right)-T\sqrt{a^{2}+1}\right)\right)\;.\end{split}$
(127)

Using the identity $\cosh\left(\tanh^{-1}(x)\right)=\frac{1}{\sqrt{1-x^{2}}}$,
(127) gives

$\displaystyle\begin{split}r(0;a)=aT&-\log(\sqrt{a^{2}+1})\\\
&+\log\left(\cosh\left(\tanh^{-1}\left(\frac{a}{\sqrt{a^{2}+1}}\right)-T\sqrt{a^{2}+1}\right)\right)\;.\end{split}$
(128)

Next, we use the identity
$\tanh^{-1}(x)=\frac{1}{2}\log\left(\frac{1+x}{1-x}\right)$ to get

$\tanh^{-1}\left(\frac{a}{\sqrt{a^{2}+1}}\right)=\frac{1}{2}\log\left(\frac{\sqrt{a^{2}+1}+a}{\sqrt{a^{2}+1}-a}\right)=\log\left(\sqrt{a^{2}+1}+a\right).\;$
(129)

Combining this with (128) gives

$\begin{split}r(0;a)=aT&-\log(\sqrt{a^{2}+1})\\\
&+\log\left(\cosh\left(\log\left(\sqrt{a^{2}+1}+a\right)-T\sqrt{a^{2}+1}\right)\right)\;.\end{split}$
(130)

One can check that

$S_{\text{opt}}^{\prime}(a)=\frac{\partial}{\partial a}\left(r(0;a)\right)>0.$

This shows that $S_{\text{opt}}$ is an increasing, continuous function of $a$.
One can also check that $S_{\text{opt}}(-1)=r(0;-1)>0$. Combining these facts
proves Lemma 1.i.

###  7.1 When $a$ is large and positive

We now prove Lemma 1.ii, i.e. we show that $S_{\text{opt}}(a)\gtrsim a$ when
$a\geq 1$. Since $S_{\text{opt}}$ is continuous, increasing, and nonnegative
it suffices to show that $S_{\text{opt}}(a)\gtrsim a$ for all $a$ sufficiently
large.

For large enough $a$, there exists some $C>0$ so that

$T\sqrt{a^{2}+1}-\log\left(\sqrt{a^{2}+1}+1\right)\geq Ca.$

Note that $\cosh(x)\geq\frac{e^{x}}{2}$ and $\cosh(x)$ is increasing for
$x>0$; this gives

$\log\left(\cosh\left(T\sqrt{a^{2}+1}-\log\left(\sqrt{a^{2}+1}+1\right)\right)\right)\geq\log\left(\frac{e^{Ca}}{2}\right).$

Combining this with (130) gives

$S_{\text{opt}}(a)=r(0;a)\geq aT+\log\left(\frac{e^{Ca}}{2}\right)\geq
C^{\prime}a$

for sufficiently large $a$.

###  7.2 When $a$ is large and negative

We now prove Lemma 1.iii, i.e. we show that
$S_{\text{opt}}(a)\gtrsim\frac{1}{|a|}$ when $a\leq-1$. As in the previous
section, it suffices to prove that $S_{\text{opt}}(a)\gtrsim\frac{1}{|a|}$ for
$a<0$ with $|a|$ sufficiently large.

Note that $\log(\sqrt{a^{2}+1}+a)=-\log(\sqrt{a^{2}+1}-a)$. Combining this
with (130) gives

$S_{\text{opt}}(a)=aT-\log\left(\sqrt{a^{2}+1}\right)+\log\left(\cosh\left(\log\left(\sqrt{a^{2}+1}+|a|\right)+T\sqrt{a^{2}+1}\right)\right).$

Note that

$\begin{split}\log\left(\cosh\left(\log\left(\sqrt{a^{2}+1}+|a|\right)+T\sqrt{a^{2}+1}\right)\right)\\\
\geq
T\sqrt{a^{2}+1}+\log\left(\frac{\sqrt{a^{2}+1}+|a|}{2}\right).\end{split}$

Therefore there exists $c>0$ such that

$S_{\text{opt}}(a)\geq
T\sqrt{a^{2}+1}-T|a|+\log\left(\frac{\sqrt{a^{2}+1}+|a|}{2\sqrt{a^{2}+1}}\right)\geq\frac{c}{|a|}$

for $a<0$ with $|a|$ sufficiently large.

## References

  * [1] Y. Abbasi-Yadkori, P. Bartlett, and V. Kanade.  Tracking adversarial targets.  In Proceedings of the 31st International Conference on Machine Learning, pages 369–377. PMLR, 2014.
  * [2] Y. Abbasi-Yadkori and C. Szepesvári.  Regret bounds for the adaptive control of linear quadratic systems.  In Proceedings of the 24th Annual Conference on Learning Theory, pages 1–26. JMLR Workshop and Conference Proceedings, 2011.
  * [3] M. Abeille and A. Lazaric.  Thompson sampling for linear-quadratic control problems.  In Artificial Intelligence and Statistics, pages 1246–1254. PMLR, 2017.
  * [4] J. D. Abernethy, E. Hazan, and A. Rakhlin.  Competing in the dark: An effifficient algorithm for bandit linear optimization.  page 13, 2009.
  * [5] P. Bartlett, E. Hazan, and A. Rakhlin.  Adaptive online gradient descent.  2007\.
  * [6] D. Brazy.  Group chairman’s factual report of investigation.  National Transportation Safety Board Docket No. SA-532, Exhibit No. 12, 2009.
  * [7] S. Bubeck and N. Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Foundations and Trends® in Machine Learning, 5(1):1–122, 2012\.
  * [8] X. Chen and E. Hazan.  Black-box control for linear dynamical systems.  In Conference on Learning Theory, pages 1114–1143. PMLR, 2021.
  * [9] A. Cohen, T. Koren, and Y. Mansour.  Learning linear-quadratic regulators efficiently with only $\sqrt{T}$ regret.  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1300–1309. PMLR, 09–15 Jun 2019\.
  * [10] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu.  Regret bounds for robust adaptive control of the linear quadratic regulator.  arXiv preprint arXiv:1805.09388, 2018.
  * [11] J. Duchi, E. Hazan, and Y. Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  Journal of machine learning research, 12(7), 2011.
  * [12] C. L. Fefferman, B. Guillen Pegueroles, C. W. Rowley, and M. Weber.  Optimal control with learning on the fly: a toy problem.  Revista Matematica Iberoamericana, 37(1), 2021.
  * [13] W. Feller.  An Introduction to Probability Theory and Its Applications, Volume 2.  John Wiley & Sons, Inc., 1971.
  * [14] L. Furieri, Y. Zheng, and M. Kamgarpour.  Learning the globally optimal distributed lq regulator.  In Learning for Dynamics and Control, pages 287–297. PMLR, 2020\.
  * [15] E. Hazan.  Introduction to online convex optimization.  arXiv preprint arXiv:1909.05207, 2019.
  * [16] H. Kwakernaak and R. Sivan.  Linear optimal control systems, volume 1.  Wiley-interscience New York, 1972.
  * [17] H. Robbins.  Some aspects of the sequential design of experiments.  Bulletin of the American Mathematical Society, 58(5):527–535, 1952\.
  * [18] J. Vermorel and M. Mohri.  Multi-armed bandit algorithms and empirical evaluation.  In European conference on machine learning, pages 437–448. Springer, 2005.