# Stochastic Multi-armed Bandits with Non-stationary Rewards Generated by a
Linear Dynamical System

Jonathan Gornet, Mehdi Hosseinzadeh and Bruno Sinopoli The authors are with
the Department of Electrical and Systems Engineering, Washington University in
St. Louis, St. Louis, MO 63130, USA (email<EMAIL_ADDRESS><EMAIL_ADDRESS>bsinopoli@wustl.edu). This material was based upon
work supported by awards ARO W911NF20S0009.

###### Abstract

The stochastic multi-armed bandit has provided a framework for studying
decision-making in unknown environments. We propose a variant of the
stochastic multi-armed bandit where the rewards are sampled from a stochastic
linear dynamical system. The proposed strategy for this stochastic multi-armed
bandit variant is to learn a model of the dynamical system while choosing the
optimal action based on the learned model. Motivated by mathematical finance
areas such as Intertemporal Capital Asset Pricing Model proposed by Merton and
Stochastic Portfolio Theory proposed by Fernholz that both model asset returns
with stochastic differential equations, this strategy is applied to
quantitative finance as a high-frequency trading strategy, where the goal is
to maximize returns within a time period.

##  I Introduction

The stochastic multi-armed bandit (MAB) problem, proposed by Thompson in 1933
[1], has provided a powerful modeling framework to investigate a large class
of decision making problems. In MAB, a learner interacts with the environment
where in each interaction, called a round, the learner chooses an action and
receives a reward. The performance of policies is usually evaluated as the
expectation of the cumulative difference between chosen and optimal actions,
and defined as regret. In its basic formulation rewards are sampled from a
stationary distribution, a very popular algorithm, called the Upper Confidence
Bound (UCB) algorithm [2], guarantees logarithmic growth of regret [3].

MAB has seen different applications in several areas such as machine learning,
dynamic pricing, and portfolio management. In machine learning, the MAB
formulation can be used to find a set of hyperparameters to increase the
performance of the learning process [4]. This has been extended further by
applying MAB to algorithm selection, where a learner searches for a high-
performing algorithm to use for training [5]. For dynamic pricing, when
selling a set of products, the price needs to be set according to the current
demand in order to maximize profit. To find the optimal pricing, MAB is used
where the model for demand is based on a low-dimensional demand model [6] or a
differential equation [7]. In portfolio selection, MAB formulation is natural
in the case where the manager creates a portfolio with multiple assets [8, 9].

In the examples mentioned above, the environments that the learner interacts
with has time correlations and correlations between the rewards for each
action. Hyperparameter optimization can be viewed as optimizing a cost
function with correlated decision variables [10] and the training process is
dynamic [4]. In dynamic pricing, the pricing for each product can be
correlated with each other based on a low dimensional demand model [6] and the
demand changes over time [7]. As for portfolio management, equations used in
Intertemporal Capital Asset Pricing Model (ICAPM) proposed by Merton [11] and
Stochastic Portfolio Theory proposed by Fernholz [12] model asset returns
using stochastic differential equations. The examples above motivate the need
to investigate non-stationary stochastic MAB where the rewards are sampled
from a stochastic dynamical system. Here the reward can be expressed as the
inner product between the action vector and a dynamic unknown parameter
vector. Previous work in non-stationary MAB studies the case where the change
in magnitude of the unknown parameter vector is bounded [13, 14] or when such
vector is is sampled from a predefined set [15, 16]. In both cases the unknown
parameter vector changes the distribution of the reward, making the original
stochastic MAB formulation non-stationary. To the best of our knowledge, the
bulk of papers in non-stationary MAB focus on the piece-wise stationary case,
where the distributions are stationary within set intervals. Papers for the
piece-wise stationary case focus on remembering-vs-forgetting trade-off using
either discounting or sliding windows [17] to forget early recorded rewards or
detecting the change in the distribution to decide when to restart the
learning process [18, 19, 20, 21]. Other papers in non-stationary MAB bound
the cumulative change of the reward mean in the form of variational budget
$V_{T}$ [22, 23]. However, the rewards sampled from a stochastic dynamical
system change in a very different manner, making previous work not well
suited. In this paper we tackle the stochastic multi-armed bandit problem when
the rewards are sampled from an unknown stochastic linear dynamical system
driven by Gaussian noise. Since the rewards are now dynamic, the paper
introduces a methodology that focuses on finding the optimal decision while
learning a model of the system. We will leverage and adapt results in [24] to
learn the linear model. We then use such model to design a policy based on
reward predictions. To illustrate the concept, we apply the algorithm to a
simple trading example.

The framework of the paper is as follows: Section II reviews the stochastic
multi-armed bandit and introduces a variant where the rewards are sampled from
a linear dynamical system. In section III, a methodology to model and predict
rewards is presented. Section IV then uses the model to develop a strategy to
maximize cumulative reward over a horizon. Section V performs regret analysis
and provides a theoretical upper bound for the regret of the proposed
algorithm. Section VI shows an application of the proposed algorithm to a
simple high frequency trading example. Finally, section VII provides
conclusions and future directions.

Notation. To denote the transpose of a matrix, the notation ⊤ is used. For
norms, $||\cdot||_{2}$ is the $\ell_{2}$-norm norm for vectors. The trace of a
matrix is denoted with $\mbox{Tr}(\cdot)$. For a normal distribution, notation
$\mathcal{N}(M,S)$ is used, where $M$ is the mean and $S$ is the covariance of
the distribution. Inner product is $\langle a,b\rangle\triangleq a^{\top}b$
where $a,b\in\mathbb{R}^{d}$. The term $\mathcal{O}(\cdot)$ is big-O notation.
For the equality

$g(n)=\mathcal{O}(f(n)),$

this implies that for some constant $M>0$ and $n_{0}\geq 0$, $g(n)\leq Mf(n)$
for all $n>n_{0}$ [25].

##  II Problem Framework

Suppose that for $k$ given actions $c_{a}\in\mathcal{A}\subset\mathbb{R}^{d}$,
the reward $X_{t}$ is sampled from the following stochastic linear dynamical
system

$\begin{cases}z_{t+1}&=\Gamma
z_{t}+\xi_{t},z_{0}\sim\mathcal{N}(\mu_{0},\Sigma_{0})\\\
\theta_{t}&=C_{\theta}z_{t}+\phi_{t}\\\ X_{t}&=\langle
c_{a},z_{t}\rangle+\mu_{a}+\eta_{t}\end{cases},$ (1)

where the unknown parameter vector $z_{t}\in\mathbb{R}^{d}$ is the state of
the system. For each round $t=1,\dots,n$, $n>d$, the learner observes the
reward $X_{t}\in\mathbb{R}$ based on the chosen action and the context
$\theta_{t}\in\mathbb{R}^{m}$. The context $\theta_{t}$ is a value that the
learner always observes and its observation matrix $C_{\theta}$ is constant.
The processes $\xi_{t}\in\mathbb{R}^{d}$, $\phi_{t}\in\mathbb{R}^{m}$, and
$\eta_{t}\in\mathbb{R}$ are i.i.d. normally distributed, i.e.
$\xi_{t}\sim\mathcal{N}(\mu_{\xi},Q)$,
$\phi_{t}\sim\mathcal{N}(\mu_{\phi},R_{\phi})$, and
$\eta_{t}\sim\mathcal{N}(0,\sigma_{\eta})$. The matrices $\Gamma$,
$C_{\theta}$, $Q$, $R_{\phi}$, $\Sigma_{0}$, vectors $\mu_{\xi}$,
$\mu_{\phi}$, $\mu_{0}$, and scalars $\sigma_{\eta}$, $\mu_{a}$
($a=1,\dots,k$) are assumed to be unknown. The dimension $d$ is unknown, but
dimension $m$ is known as it is the dimension of the context. For notation,
given that there are $k$ vectors $c_{a}\in\mathcal{A}$, we denote
$a\in\\{1,\dots,k\\}$ to be which vector $c_{a}$ is chosen. The system has the
following assumptions

###### Assumption 1

The matrix pair $(\Gamma,C_{\theta})$ is observable. The matrix $Q$ is
positive definite.

###### Assumption 2

The matrix $\Gamma$ is Schur, i.e. $\rho(\Gamma)<1$.

The goal of the learner is to maximize cumulative reward over a finite time
horizon $n$. To prove the performance of the learning strategy, regret
analysis is used [26]. Regret is defined as the cumulative, over all rounds,
expected difference between the highest reward (denoted as $X_{t}^{*}$) and
the reward for the chosen action at time $t$, i.e.

$R_{n}=\sum_{t=1}^{n}\mathbb{E}[X_{t}^{*}-X_{t}].$ (2)

##  III Modeling the System from Data

If the learner knew (1), then the Kalman filter could be used to predict the
state $z_{t}$ and consequently the reward $X_{t}$ for each action
$a\in\\{1,\dots,k\\}$:

$\begin{array}[]{ll}\hat{z}_{t+1|t}&=\Gamma\hat{z}_{t|t}+\mu_{\xi},\quad
P_{t+1|t}=\Gamma P_{t|t}\Gamma^{\top}+Q\\\
K_{t}&=P_{t|t-1}C_{\theta}^{\top}(C_{\theta}P_{t|t-1}C_{\theta}+R_{\phi})^{-1}\\\
\hat{z}_{t|t}&=\hat{z}_{t|t-1}+K_{t}(\theta_{t}-C_{\theta}\hat{z}_{t|t-1}-\mu_{\phi}),\\\
P_{t|t}&=P_{t|t-1}-K_{t}C_{\theta}P_{t|t-1},\\\ \hat{X}_{t|t-1}&=\langle
c_{a},\hat{z}_{t|t-1}\rangle+\mu_{a}\end{array},$ (3)

where $\hat{z}_{t|t}\triangleq\mathbb{E}[z_{t}|\mathcal{F}_{t}]$ and
$\mathcal{F}_{t}$ is the sigma algebra generated by previous contexts
$\theta_{0},\dots,\theta_{t}$. Since the Kalman gain matrix $K_{t}$ converges
thanks to assumption 1, then using the steady-state Kalman filter is
reasonable where the prediction of the state $\hat{z}_{t+1|t}$ and the
estimate of the state $\hat{z}_{t|t}$ can be combined into one equation

$\begin{array}[]{ll}\hat{z}_{t+1}&=\Gamma\hat{z}_{t}+\mu_{\xi}+\Gamma
K(\theta_{t}-C_{\theta}\hat{z}_{t}-\mu_{\phi})\\\ \hat{X}_{t}&=\langle
c_{a},\hat{z}_{t}\rangle+\mu_{a}\end{array},$ (4) $\displaystyle K$
$\displaystyle=PC_{\theta}^{\top}(C_{\theta}PC_{\theta}^{\top}+R_{\phi})^{-1},$
$\displaystyle P$ $\displaystyle=\Gamma P\Gamma^{\top}+Q-\Gamma
PC_{\theta}^{\top}(C_{\theta}PC_{\theta}^{\top}+R_{\phi})^{-1}C_{\theta}P\Gamma^{\top},$
$\displaystyle\hat{z}_{t}$ $\displaystyle\triangleq\hat{z}_{t|t-1},$
$\displaystyle\hat{X}_{t}$ $\displaystyle\triangleq\hat{X}_{t|t-1}.$

Since using the steady-state Kalman filter prediction $\hat{X}_{t}$ provides a
good prediction of $X_{t}$, then learning the steady-state Kalman filter will
intuitively provide a good prediction of the reward $X_{t}$ for each action
$a\in\\{1,\dots,k\\}$. Therefore, to learn the steady-state Kalman filter, a
variation of [24] is used. Let $s>0$ be the horizon length of how far we look
into the past. We define a matrix $G_{a}$ for each $a\in\\{1,\dots,k\\}$ and a
vector $\Theta_{t}$ below

$\displaystyle G_{a}$
$\displaystyle\triangleq\left[\begin{matrix}c_{a}^{\top}(\Gamma-\Gamma
KC_{\theta})^{s-1}\Gamma K&\dots\end{matrix}\right.$
$\displaystyle\quad\quad\left.\begin{matrix}c_{a}^{\top}\Gamma
K&\sum_{\tau=1}^{s}\langle
c_{a},\Gamma^{\tau}(\mu_{\xi}-\mu_{\phi})\rangle+\mu_{a}\end{matrix}\right]\in\mathbb{R}^{1\times(ms+1)},$
$\displaystyle\Theta_{t}$
$\displaystyle\triangleq\begin{bmatrix}\theta_{t-s}^{\top}&\dots&\theta_{t-1}^{\top}&1\end{bmatrix}^{\top}\in\mathbb{R}^{ms+1\times
1}.$ (5)

Using $G_{a}$ and $\Theta_{t}$ defined above, it can be shown that the reward
$X_{t}$ has the following expression

$X_{t}=G_{a}\Theta_{t}+\langle c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{t-s}\rangle+\varepsilon_{a;t},$ (6)

where

$\displaystyle\varepsilon_{a;t}$ $\displaystyle\triangleq X_{t}-\hat{X}_{t},$
$\displaystyle=\langle c_{a},z_{t}-\hat{z}_{t}\rangle+\eta_{t},$
$\displaystyle\sim\mathcal{N}(0,c_{a}^{\top}Pc_{a}+\sigma_{\eta}).$

Note that since $\Gamma-\Gamma KC_{\theta}$ is Schur by construction, then the
magnitude of the term $\langle c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{t-s}\rangle$ decreases as $s$ increases. If given a
set of time instants $\mathcal{T}_{a}=\\{t_{1},\dots,t_{N_{a}}\\}$ then (6)
can be rearranged in the following form

$\begin{bmatrix}X_{t_{1}}^{\top}\\\ \vdots\\\
X_{t_{N_{a}}}^{\top}\end{bmatrix}^{\top}=G_{a}\begin{bmatrix}\Theta_{t_{1}}^{\top}\\\
\vdots\\\ \Theta_{t_{N_{a}}}^{\top}\end{bmatrix}^{\top}\\\
+\begin{bmatrix}\langle c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{t_{1}-s}\rangle^{\top}+\varepsilon_{a;t_{1}}^{\top}\\\
\vdots\\\ \langle c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{t_{N_{a}}-s}\rangle^{\top}+\varepsilon_{a;t_{N_{a}}}^{\top}\end{bmatrix}^{\top}.$
(7)

A regularized least squares estimate for (7) is

$\displaystyle\hat{G}_{a}$ $\displaystyle=\begin{bmatrix}X_{t_{1}}^{\top}\\\
\vdots\\\
X_{t_{N_{a}}}^{\top}\end{bmatrix}^{\top}\begin{bmatrix}\Theta_{t_{1}}^{\top}\\\
\vdots\\\ \Theta_{t_{N_{a}}}^{\top}\end{bmatrix}\left(\lambda
I+\begin{bmatrix}\Theta_{t_{1}}^{\top}\\\ \vdots\\\
\Theta_{t_{N_{a}}}^{\top}\end{bmatrix}^{\top}\begin{bmatrix}\Theta_{t_{1}}^{\top}\\\
\vdots\\\ \Theta_{t_{N_{a}}}^{\top}\end{bmatrix}\right)^{-1},$
$\displaystyle=\sum_{\tau\in\mathcal{T}_{a}}X_{\tau}\Theta_{\tau}^{\top}V_{a}^{-1}.$
(8)

where $V_{a}$ is defined to be

$V_{a}\triangleq\lambda
I+\sum_{\tau\in\mathcal{T}_{a}}\Theta_{\tau}\Theta_{\tau}^{\top},$ (9)

and $\lambda\geq 0$ is the regularization parameter. Note that the $\lambda I$
is added so that that $V_{a}$ is positive definite and therefore invertible.

##  IV Bandit Strategy

The action the learner ought to choose is the action that the learner predicts
will output the highest reward. This prediction is based on the matrix
$\hat{G}_{a}$, which is an estimate of the matrix $G_{a}$. Therefore, the
learner should focus on learning $\hat{G}_{a}$ for each action
$a\in\\{1,\dots,k\\}$ at the beginning and then choose an action based on
$\hat{G}_{a}$ after the initial phase.

The proposed strategy the learner will use is the following. The parameter to
set is $s$, where a larger $s$ value decreases the bias term $\langle
c_{a},(\Gamma-\Gamma KC_{\theta})^{s}\hat{z}_{t-s}\rangle$ in (6) which
impacts the identification error $||\hat{G}_{a}-G_{a}||_{2}$. At the start of
the algorithm, the learner will cycle through each action
$a\in\\{1,\dots,k\\}$ round $t=1$ to round $t=ks$. The learner will start
computing $\hat{G}_{a}$ once $t>s$. After round $t=ks$, the learner will
choose the action $a\in\\{1,\dots,k\\}$ that has the largest
$\hat{G}_{a}\Theta_{t}$ value and update $\hat{G}_{a}$.

The proposed Algorithm 1, inspired by Explore-Then-Commit [26], is summarized
below.

Algorithm 1 Systems-Based Explore-Then-Exploitation (SB-ETC)

$t\leftarrow 1$

for $a\in\\{1,\dots,k\\}$ do

$S_{a}\leftarrow 0$

$\hat{G}_{a}\leftarrow\mathbf{0}_{1\times ms+1}$

$\mathcal{T}_{a}\leftarrow\\{\\}$

end for

while $t\leq n$ do

if $t>ks$ then

$a\leftarrow\underset{a\in\\{1,\dots,k\\}}{\arg\max}\textbf{
}\hat{G}_{a}\Theta_{t}$

else

$a\leftarrow\underset{a\in\\{1,\dots,k\\}}{\arg\max}\textbf{ }\frac{1}{S_{a}}$

$S_{a}\leftarrow S_{a}+1$

end if

if $t>s$ then

for $a\in\\{1,\dots,k\\}$ do

Update $\mathcal{T}_{a}$

Learn $\hat{G}_{a}$ based on (8) and (9)

end for

end if

Sample $(\theta_{t},X_{t})$ based on (1)

$t\leftarrow t+1$

end while

##  V Regret Analysis of SB-ETC

The following theorem below provides a bound for regret defined in (2).

###### Theorem 1

Given a failure rate of $\delta\in(0,1)$, regret as in (2) has the following
bound with a probability of at least $1-\delta$:

$R_{n}\leq\sum_{t=1}^{ks}\sum_{a\neq a^{*}}\mathbb{E}[\langle\Delta
c_{a},z_{t}\rangle+\Delta\mu_{a}]\\\ +\sum_{t=ks+1}^{n}\sum_{a\neq
a^{*}}\mathbb{E}_{z}[\langle\Delta c_{a},z_{t}\rangle+\Delta\mu_{a}|a]\cdot\\\
\min\Bigg{\\{}B_{a}\mathbb{E}_{\Theta}\Bigg{[}\frac{||\Theta_{t}||_{2}}{|\Delta
G_{a}\Theta_{t}|}\Bigg{]},1\Bigg{\\}},$ (10)

where $\Delta c_{a}$, $\Delta\mu_{a}$ and $\Delta G_{a}$ are defined to be

$\displaystyle\Delta c_{a}$ $\displaystyle\triangleq c_{a^{*}}-c_{a},$ (11)
$\displaystyle\Delta\mu_{a}$ $\displaystyle\triangleq\mu_{a^{*}}-\mu_{a},$
(12) $\displaystyle\Delta G_{a}$ $\displaystyle\triangleq G_{a^{*}}-G_{a}.$
(13)

and $B_{a}$ is a bound such that with a probability of at least $1-\delta$:

$||\hat{G}_{a}-G_{a}||_{2}+||G_{a^{*}}-\hat{G}_{a^{*}}||_{2}\leq B_{a}.$ (14)

###### Proof:

Using the law of iterated expectations [27], the instanteneous regret for one
round $t=ks+1,\dots,n$ is

$\displaystyle\mathbb{E}[X_{t}^{*}-X_{t}]$
$\displaystyle=\mathbb{E}[\langle\Delta c_{a},z_{t}\rangle+\Delta\mu_{a}]$
$\displaystyle=\mathbb{E}_{a}[\mathbb{E}_{z}[\langle\Delta
c_{a},z_{t}\rangle+\Delta\mu_{a}|a]]$
$\displaystyle=\sum_{a=1}^{k}\mathbb{E}_{z}[\langle\Delta
c_{a},z_{t}\rangle+\Delta\mu_{a}|a]\mathbb{P}[a],$ (15)

where $\Delta c_{a}$ and $\Delta\mu_{a}$ are defined in (11) and (12). In the
following, we will provide an upper bound for $\mathbb{P}[a]$. Consider the
following event $\mathcal{E}_{a}$

$\mathcal{E}_{a}\triangleq\\{\hat{G}_{a}\Theta_{t}\geq\hat{G}_{a^{*}}\Theta_{t}\\},$
(16)

which implies that modeling error leads to selecting an action rather than the
optimal one. Note that $\mathbb{P}[a]$ is the following probability

$\displaystyle\mathbb{P}[a]$ $\displaystyle=\mathbb{P}\Big{[}\cap_{i\neq
a}\\{\hat{G}_{a}\Theta_{t}\geq\hat{G}_{i}\Theta_{t}\\}\Big{]}$
$\displaystyle=\mathbb{P}\Big{[}\cap_{i\neq
a,a^{*}}\\{\hat{G}_{a}\Theta_{t}\geq\hat{G}_{i}\Theta_{t}\\}\cap\\{\hat{G}_{a}\Theta_{t}\geq\hat{G}_{a^{*}}\Theta_{t}\\}\Big{]},$
(17)

implying that $\mathbb{P}[a]\leq\mathbb{P}[\mathcal{E}_{a}]$. Adjusting the
inequality in $\mathcal{E}_{a}$ provides the following

$\displaystyle\hat{G}_{a}\Theta_{t}$
$\displaystyle\geq\hat{G}_{a^{*}}\Theta_{t}$ $\displaystyle
G_{a}\Theta_{t}+(\hat{G}_{a}-G_{a})\Theta_{t}$ $\displaystyle\geq
G_{a^{*}}\Theta_{t}$
$\displaystyle\quad\quad-(G_{a^{*}}-\hat{G}_{a^{*}})\Theta_{t}.$ (18)

Let $\Delta G_{a}$ be as in (13). Then (18) can be written as follows:

$\displaystyle\Delta G_{a}\Theta_{t}$
$\displaystyle\leq(\hat{G}_{a}-G_{a})\Theta_{t}$
$\displaystyle\quad\quad+(G_{a^{*}}-\hat{G}_{a^{*}})\Theta_{t},$

which implies that

$\displaystyle\Delta G_{a}\Theta_{t}$
$\displaystyle\leq||\hat{G}_{a}-G_{a}||_{2}||\Theta_{t}||_{2}$
$\displaystyle\quad\quad+||G_{a^{*}}-\hat{G}_{a^{*}}||_{2}||\Theta_{t}||_{2}.$
(19)

At this stage, we use (8) and (9) to express $\hat{G}_{a}$ for any actions as
follows:

$\displaystyle\hat{G}_{a}$
$\displaystyle=\sum_{\tau\in\mathcal{T}_{a}}G_{a}\Theta_{\tau}\Theta_{\tau}^{\top}V_{a}^{-1}$
$\displaystyle\quad\quad+\langle c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{\tau-s}\rangle\Theta_{\tau}^{\top}V_{a}^{-1}$
$\displaystyle\quad\quad+\epsilon_{a;\tau}\Theta_{\tau}^{\top}V_{a}^{-1},$
$\displaystyle=G_{a}(V_{a}-\lambda I)V_{a}^{-1}$
$\displaystyle\quad\quad+\sum_{\tau\in\mathcal{T}_{a}}\langle
c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{\tau-s}\rangle\Theta_{\tau}^{\top}V_{a}^{-1}$
$\displaystyle\quad\quad+\sum_{\tau\in\mathcal{T}_{a}}\epsilon_{a;\tau}\Theta_{\tau}^{\top}V_{a}^{-1},$
$\displaystyle=G_{a}-\lambda G_{a}V_{a}^{-1}$
$\displaystyle\quad\quad+\sum_{\tau\in\mathcal{T}_{a}}\langle
c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{\tau-s}\rangle\Theta_{\tau}^{\top}V_{a}^{-1}$
$\displaystyle\quad\quad+\sum_{\tau\in\mathcal{T}_{a}}\epsilon_{a;\tau}\Theta_{\tau}^{\top}V_{a}^{-1}.$

Thus, the $\ell$-2 norm $||\hat{G}_{a}-G_{a}||_{2}$ is

$\displaystyle\hat{G}_{a}-G_{a}$ $\displaystyle=-\lambda G_{a}V_{a}^{-1}$
$\displaystyle\quad+\sum_{\tau\in\mathcal{T}_{a}}\langle c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{\tau-s}\rangle\Theta_{\tau}^{\top}V_{a}^{-1}$
$\displaystyle\quad+\sum_{\tau\in\mathcal{T}_{a}}\epsilon_{a;\tau}\Theta_{\tau}^{\top}V_{a}^{-1},$
$\displaystyle||\hat{G}_{a}-G_{a}||_{2}$ $\displaystyle\leq||\lambda
G_{a}V_{a}^{-1}||_{2}$
$\displaystyle\quad+\Bigg{|}\Bigg{|}\sum_{\tau\in\mathcal{T}_{a}}\langle
c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{\tau-s}\rangle\Theta_{\tau}^{\top}V_{a}^{-1}\Bigg{|}\Bigg{|}_{2}$
$\displaystyle\quad+\Bigg{|}\Bigg{|}\sum_{\tau\in\mathcal{T}_{a}}\epsilon_{a;\tau}\Theta_{\tau}^{\top}V_{a}^{-1}\Bigg{|}\Bigg{|}_{2}.$
(20)

Since $\rho(\Gamma)<1$, the estimate $\langle c_{a},(\Gamma-\Gamma
KC_{\theta})^{s}\hat{z}_{\tau-s}\rangle$ is bounded. For the product
$\epsilon_{a;t}\Theta_{t}^{\top}V_{a}^{-1}$, based on theorem 1 in [28], since
$\epsilon_{a;t}$ is conditionally $c_{a}^{\top}Pc_{a}+\sigma_{\eta}$-sub-
Gaussian and $\Theta_{t}$ is measurable, then given a failure rate
$\delta\in(0,1)$, this term is bounded with a probability of at least
$1-\delta$. Therefore, (14) is satisfied with a probability of at least
$1-\delta$. Denote (14) as $\mathcal{E}_{1}$. Now assuming $\mathcal{E}_{1}$
is given, the inequality (19) can be rewritten as

$\displaystyle B_{a}||\Theta_{t}||_{2}$ $\displaystyle\geq\Delta
G_{a}\Theta_{t}$ $\displaystyle\Rightarrow\frac{||\Theta_{t}||_{2}}{\Delta
G_{a}\Theta_{t}}$ $\displaystyle\geq\frac{1}{B_{a}}$
$\displaystyle\Rightarrow\frac{||\Theta_{t}||_{2}}{|\Delta G_{a}\Theta_{t}|}$
$\displaystyle\geq\frac{1}{B_{a}}.$ (21)

Let (21) be denoted as $\mathcal{E}_{2}|\mathcal{E}_{1}$. Based on the Markov
inequality [29], the following concentration bound is given

$\mathbb{P}[\mathcal{E}_{2}|\mathcal{E}_{1}]\leq\min\Bigg{\\{}B_{a}\mathbb{E}_{\Theta}\Bigg{[}\frac{||\Theta_{t}||_{2}}{|\Delta
G_{a}\Theta_{t}|}\Bigg{]},1\Bigg{\\}}.$ (22)

Note (16) and (21) can be rewritten the following way

$\displaystyle\mathcal{E}_{2}|\mathcal{E}_{1}$
$\displaystyle=\Big{\\{}B_{a}\frac{||\Theta_{t}||_{2}}{|\Delta
G_{a}\Theta_{t}|}\geq 1\Big{\\}},$ $\displaystyle\mathcal{E}_{a}$
$\displaystyle=\Big{\\{}\frac{(\hat{G}_{a}-G_{a})\Theta_{t}+(G_{a^{*}}-\hat{G}_{a^{*}})\Theta_{t}}{\Delta
G_{a}\Theta_{t}}\geq 1\Big{\\}}.$ (23)

Note that
$\mathbb{P}[\mathcal{E}_{a}]\leq\mathbb{P}[\mathcal{E}_{2}|\mathcal{E}_{1}]$
is true if the following inequality is true.

$B_{a}\frac{||\Theta_{t}||_{2}}{|\Delta
G_{a}\Theta_{t}|}\geq\frac{(\hat{G}_{a}-G_{a})\Theta_{t}+(G_{a^{*}}-\hat{G}_{a^{*}})\Theta_{t}}{\Delta
G_{a}\Theta_{t}}.$ (24)

Since (24) is satisfied with a probability of at least $1-\delta$ based on
(14), then
$\mathbb{P}[\mathcal{E}_{a}]\leq\mathbb{P}[\mathcal{E}_{2}|\mathcal{E}_{1}]$
with a probability of at least $1-\delta$. Therefore, (15) has the following
upper bound

$\displaystyle\mathbb{E}[X_{t}^{*}-X_{t}]$
$\displaystyle=\sum_{a=1}^{k}\mathbb{E}_{z}[\langle\Delta
c_{a},z_{t}\rangle+\Delta\mu_{a}|a]\mathbb{P}[a]$
$\displaystyle\leq\sum_{a\neq a^{*}}\mathbb{E}_{z}[\langle\Delta
c_{a},z_{t}\rangle+\Delta\mu_{a}|a]\mathbb{P}[\mathcal{E}_{a}]$
$\displaystyle\leq\sum_{a\neq a^{*}}\mathbb{E}_{z}[\langle\Delta
c_{a},z_{t}\rangle+\Delta\mu_{a}|a]\mathbb{P}[\mathcal{E}_{2}|\mathcal{E}_{1}].$

Using (22), this provides the upper-bound for (15) with a probability of at
least $1-\delta$

$\mathbb{E}[X_{t}^{*}-X_{t}]\leq\sum_{a\neq a^{*}}\mathbb{E}_{z}[\langle\Delta
c_{a},z_{t}\rangle+\Delta\mu_{a}|a]\cdot\\\
\min\Bigg{\\{}B_{a}\mathbb{E}_{\Theta}\Bigg{[}\frac{||\Theta_{t}||_{2}}{|\Delta
G_{a}\Theta_{t}|}\Bigg{]},1\Bigg{\\}}.$ (25)

Summing (25) over $t$ rounds gives the bound (10).

∎

Based on theorem 1, the regret performance is based on the bound for model
error $B_{a}$. Therefore, if the model is known, then $B_{a}=0$ sets the bound
to be zero after $t=ks$ which is reasonable. Note that $B_{a}$ is based on the
number of times action $a$ is chosen, which can affect the upper bound. For
now, the exploration period is set to $ks$ so that the learner has $s$ samples
for each action $a\in\\{1,\dots,k\\}$. Future work will focus on what is a
more effective length for the exploration period.

##  VI Application to trading

This section will exemplify the use of the proposed framework. Let there be
two stocks, $i=1,2$ a trader is interested in. The trader can either buy then
sell either stock 1 or 2, or refrain from trading for each round
$t=1,\dots,10^{4}$. Figure 1 provides an example timeline of the trader’s
strategy.

Figure 1: Example timeline of trader’s strategy.

The context $\theta_{t}$ represent the price change for the stock. The reward
$X_{t}$ is the financial gain (loss) deriving from trading a stock. Both
variables are sampled from the following stochastic linear dynamical system,
where its derivation is in the Appendix.

$\begin{array}[]{ll}z_{t+1}^{\prime}&=\begin{bmatrix}0&0&0&0\\\ 0&0&0&0\\\
0&0&0.9512&0\\\ 0&0&0&0.6065\\\ \end{bmatrix}z_{t}^{\prime}+\xi_{t}\\\
\theta_{t}&=\begin{bmatrix}-1&0&0.0353&0\\\
0&-1&0&0.2987\end{bmatrix}z_{t}^{\prime}\\\ X_{t}&=\langle
c_{a},z_{t}^{\prime}\rangle\end{array},$ (26) $\displaystyle\xi_{t}$
$\displaystyle\sim\mathcal{N}\left(0,\begin{bmatrix}0.9672&0&20.0957&0\\\
0&0.6503&0&0.7536\\\ 20.09570&&1112.3&0\\\
0&0.7536&0&4.0537\end{bmatrix}\right),$ $\displaystyle c_{a}$
$\displaystyle\in\\{\begin{bmatrix}-1&0&0.0353&0\end{bmatrix},\begin{bmatrix}0&-1&0&0.2987\end{bmatrix},$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\begin{bmatrix}0&0&0&0\end{bmatrix}\\}.$

For the model, the number of previous contexts $\theta_{t}$ that are used is
$s=10$ and the regularization parameter $\lambda=10^{-1}$. Since $\Gamma$ is
Schur, one could argue that the reward $X_{t}$ is just Gaussian distributed as
$t>>0$. Therefore, using UCB is a reasonable method to use as a comparison.
The parameter used in UCB is $\delta=0.1$. To provide an upper bound on the
algorithm’s performance we use an oracle that leverages optimal predicted
awards generated by the Kalman filter $\hat{X}_{t|t-1}$ (3) to choose the
action $c_{a}\in\mathcal{A}$.

Figure 2 contains the instanteneous regret (the top plot) and regret (the
bottom plot) of the learner using UCB (the red line), algorithm 1 (the blue
line), and the oracle (the green line) averaged across 1,000 different
simulations. Even though the system converges to the steady-state, UCB still
performs sub-par compared to algorithm 1. Figure 3 is a comparison of just
algorithm 1 and the oracle. It can be observed that algorithm 1 instantenous
regret is converging to the oracle’s instanteneous regret.

Figure 2: Figure for algorithm performance for UCB, algorithm 1, and the
oracle.  Figure 3: Figure for algorithm performance for algorithm 1 and the
oracle.

##  VII Conclusion

This paper introduces a new variant of the stochastic multi-armed bandit where
the rewards are sampled from an unknown stochastic linear dynamical system. To
approach this problem, the learner first explores all the actions to learn the
underlying linear model. Using the learned model, the learner uses the model
to predict the action with the highest reward. Simulation results show how the
proposed strategy yields near optimal actions after the learning phase. An
application to high frequency trading is used to illustrate the methods and
the results.

## References

  * [1] W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” _Biometrika_ , vol. 25, no. 3/4, pp. 285–294, 1933.
  * [2] R. Agrawal, “Sample mean based index policies by o (log n) regret for the multi-armed bandit problem,” _Advances in Applied Probability_ , vol. 27, no. 4, pp. 1054–1078, 1995.
  * [3] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” _Machine learning_ , vol. 47, no. 2, pp. 235–256, 2002.
  * [4] L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar, “Hyperband: A novel bandit-based approach to hyperparameter optimization,” _The Journal of Machine Learning Research_ , vol. 18, no. 1, pp. 6765–6816, 2017.
  * [5] M. Gagliolo and J. Schmidhuber, “Algorithm selection as a bandit problem with unbounded losses,” in _International conference on learning and intelligent optimization_. Springer, 2010, pp. 82–96.
  * [6] J. W. Mueller, V. Syrgkanis, and M. Taddy, “Low-rank bandit methods for high-dimensional dynamic pricing,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [7] S. Agrawal, S. Yin, and A. Zeevi, “Dynamic pricing and learning under the bass model,” in _Proceedings of the 22nd ACM Conference on Economics and Computation_ , 2021, pp. 2–3.
  * [8] W. Shen, J. Wang, Y.-G. Jiang, and H. Zha, “Portfolio choices with orthogonal bandit learning,” in _Twenty-fourth international joint conference on artificial intelligence_ , 2015.
  * [9] X. Huo and F. Fu, “Risk-aware multi-armed bandit problem with application to portfolio selection,” _Royal Society open science_ , vol. 4, no. 11, p. 171377, 2017.
  * [10] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. De Freitas, “Taking the human out of the loop: A review of bayesian optimization,” _Proceedings of the IEEE_ , vol. 104, no. 1, pp. 148–175, 2015.
  * [11] R. C. Merton, “An intertemporal capital asset pricing model,” _Econometrica: Journal of the Econometric Society_ , pp. 867–887, 1973.
  * [12] R. Fernholz and B. Shay, “Stochastic portfolio theory and stock market equilibrium,” _The Journal of Finance_ , vol. 37, no. 2, pp. 615–624, 1982\.
  * [13] W. C. Cheung, D. Simchi-Levi, and R. Zhu, “Learning to optimize under non-stationarity,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 1079–1087.
  * [14] A. Javanmard, “Perishability of data: dynamic pricing under varying-coefficient models,” _The Journal of Machine Learning Research_ , vol. 18, no. 1, pp. 1714–1744, 2017.
  * [15] Y. Qin, T. Menara, S. Oymak, S. Ching, and F. Pasqualetti, “Non-stationary representation learning in sequential linear bandits,” _arXiv preprint arXiv:2201.04805_ , 2022.
  * [16] Y. Qin, T. Menara, S. Oymak, and F. Pasqueletti, “Representation learning for stochastic sequential linear bandits,” _IEEE Conference on Decision and Control_ , 2021.
  * [17] A. Garivier and E. Moulines, “On upper-confidence bound policies for non-stationary bandit problems,” _arXiv preprint arXiv:0805.3415_ , 2008\.
  * [18] C. Hartland, N. Baskiotis, S. Gelly, M. Sebag, and O. Teytaud, “Change point detection and meta-bandits for online learning in dynamic environments,” in _CAp 2007: 9è Conférence francophone sur l’apprentissage automatique_ , 2007, pp. 237–250.
  * [19] F. Liu, J. Lee, and N. Shroff, “A change-detection based framework for piecewise-stationary multi-armed bandit problem,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 32, no. 1, 2018.
  * [20] Y. Cao, Z. Wen, B. Kveton, and Y. Xie, “Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 418–427.
  * [21] J. Mellor and J. Shapiro, “Thompson sampling in switching environments with bayesian online change detection,” in _Artificial intelligence and statistics_. PMLR, 2013, pp. 442–450.
  * [22] L. Wei and V. Srivastava, “Nonstationary stochastic multiarmed bandits: Ucb policies and minimax regret,” _arXiv preprint arXiv:2101.08980_ , 2021.
  * [23] O. Besbes, Y. Gur, and A. Zeevi, “Stochastic multi-armed-bandit problem with non-stationary rewards,” _Advances in neural information processing systems_ , vol. 27, pp. 199–207, 2014.
  * [24] A. Tsiamis and G. J. Pappas, “Finite sample analysis of stochastic system identification,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 2019, pp. 3648–3654.
  * [25] D. E. Knuth, “Big omicron and big omega and big theta,” _SIGACT News_ , vol. 8, no. 2, p. 18–24, Apr. 1976.
  * [26] T. Lattimore and C. Szepesvári, _Bandit algorithms_. Cambridge University Press, 2020.
  * [27] J. M. Wooldridge, _Econometric analysis of cross section and panel data_. MIT press, 2010.
  * [28] Y. Abbasi-yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” in _Advances in Neural Information Processing Systems_ , J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, Eds., vol. 24. Curran Associates, Inc., 2011.
  * [29] S. Boucheron, G. Lugosi, and P. Massart, _Concentration inequalities: A nonasymptotic theory of independence_. Oxford university press, 2013.
  * [30] A. Gelb _et al._ , _Applied optimal estimation_. MIT press, 1974.
  * [31] C. Van Loan, “Computing integrals involving the matrix exponential,” _IEEE transactions on automatic control_ , vol. 23, no. 3, pp. 395–404, 1978\.

##  Appendix A Derivation for (26)

The trader models the price evolution of stock $i$ (denoted as
$S_{\tau}^{[i]}$) using the following stochastic differential equation for
$\tau\in[0,T]$ based on [11].

$\begin{array}[]{ll}\frac{dS_{\tau}^{[i]}}{S_{\tau}^{[i]}}&=M_{\tau}^{[i]}d\tau+dW_{\tau}^{[i]}\\\
dM_{\tau}^{[i]}&=\kappa_{[i]}\Big{(}\frac{1}{2}-M_{\tau}^{[i]}\Big{)}d\tau+\sigma_{[i]}dV_{\tau}^{[i]}\end{array},$
(27)

where $\kappa_{[i]}$ and $\sigma_{[i]}$, $i=1,2$, are defined to be

$\displaystyle\begin{bmatrix}\kappa_{[1]}\\\ \kappa_{[2]}\end{bmatrix}$
$\displaystyle\triangleq\begin{bmatrix}10^{-1}\\\ 1\end{bmatrix},$
$\displaystyle\begin{bmatrix}\sigma_{[1]}\\\ \sigma_{[2]}\end{bmatrix}$
$\displaystyle\triangleq\begin{bmatrix}10\\\ 1\end{bmatrix}.$ (28)

The variable $M_{\tau}^{[i]}$ is the drift rate of stock $i$, $\kappa_{[i]}$
is the speed of reversion (the rate $M_{\tau}^{[i]}$ returns to its mean), and
$\sigma_{[i]}$ sets the magnitude of $dV_{\tau}^{[i]}$. Both $dW_{\tau}^{[i]}$
and $dV_{\tau}^{[i]}$ are independent Gaussian distributed random variables
with a variance of $1$ with no time correlation, i.e.
$dW_{\tau}^{[i]}\sim\mathcal{N}(0,\delta_{\tau})$ and
$dV_{\tau}^{[i]}\sim\mathcal{N}(0,\delta_{\tau})$ where $\delta_{\tau}$ is the
delta dirac function. Let $Y_{\tau}^{[i]}=\log(S_{\tau}^{[i]})$. Using Itô’s
lemma, the stochastic differential equation for $\log(S_{\tau}^{[i]})$ is

$\displaystyle d\log(S_{\tau}^{[i]})$
$\displaystyle=\Bigg{\langle}\frac{\partial\log(S_{\tau}^{[i]})}{\partial
S_{\tau}^{[i]}},S_{\tau}^{[i]}M_{\tau}^{[i]}\Bigg{\rangle}d\tau$
$\displaystyle\quad\quad\quad\quad+\frac{1}{2}\Bigg{\langle}\frac{\partial^{2}\log(S_{\tau}^{[i]})}{\partial(S_{\tau}^{[i]})^{2}},(S_{\tau}^{[i]})^{2}\Bigg{\rangle}d\tau$
$\displaystyle\quad\quad\quad\quad+\Bigg{\langle}\frac{\partial\log(S_{\tau}^{[i]})}{\partial
S_{\tau}^{[i]}},S_{\tau}^{[i]}\Bigg{\rangle}dW_{\tau}^{[i]},$ (29)
$\displaystyle d\log(S_{\tau}^{[i]})$
$\displaystyle=\frac{1}{S_{\tau}^{[i]}}S_{\tau}^{[i]}M_{\tau}^{[i]}d\tau+\Bigg{(}\frac{1}{2}\Bigg{)}\Bigg{(}\frac{-1}{(S_{\tau}^{[i]})^{2}}\Bigg{)}(S_{\tau}^{[i]})^{2}d\tau$
$\displaystyle\quad\quad\quad\quad+\frac{1}{S_{\tau}^{[i]}}S_{\tau}^{[i]}dW_{\tau}^{[i]},$
(30) $\displaystyle d\log(S_{\tau}^{[i]})$
$\displaystyle=\Big{(}M_{\tau}^{[i]}-\frac{1}{2}\Big{)}d\tau+dW_{\tau}^{[i]}.$
(31)

This leads to the following stochastic differential equations:

$\begin{array}[]{ll}dY_{\tau}^{[i]}&=\Big{(}M_{\tau}^{[i]}-\frac{1}{2}\Big{)}d\tau+dW_{\tau}^{[i]}\\\
dM_{\tau}^{[i]}&=\kappa_{[i]}\Big{(}\frac{1}{2}-M_{\tau}^{[i]}\Big{)}d\tau+\sigma_{[i]}dV_{\tau}^{[i]}\end{array}.$
(32)

Let the following matrices and vectors be defined as below:

$\displaystyle y(\tau)$
$\displaystyle\triangleq\begin{bmatrix}Y_{\tau}^{[1]}&Y_{\tau}^{[2]}\end{bmatrix}^{\top},$
$\displaystyle m(\tau)$
$\displaystyle\triangleq\begin{bmatrix}M_{\tau}^{[1]}&M_{\tau}^{[2]}\end{bmatrix}^{\top},$
$\displaystyle\kappa$ $\displaystyle\triangleq\begin{bmatrix}\kappa_{[1]}&0\\\
0&\kappa_{[2]}\end{bmatrix},$ $\displaystyle F$
$\displaystyle\triangleq\left[\begin{array}[]{c|c}\mathbf{0}&I_{2}\\\
\hline\cr\mathbf{0}&-\kappa\\\ \end{array}\right],$ (35) $\displaystyle
dw(\tau)$ $\displaystyle\triangleq\begin{bmatrix}dW_{\tau}\\\ \sigma
dV_{\tau}\end{bmatrix}\sim\mathcal{N}(0,\Sigma\delta_{\tau}),$
$\displaystyle\Sigma$ $\displaystyle\triangleq\begin{bmatrix}1&0&0&0\\\
0&1&0&0\\\ 0&0&\sigma_{[1]}^{2}&0\\\ 0&0&0&\sigma_{[2]}^{2}\end{bmatrix},$
$\displaystyle B_{\mu}$ $\displaystyle\triangleq\begin{bmatrix}-1/2\\\ -1/2\\\
\kappa_{[1]}/2\\\ \kappa_{[2]}/2\end{bmatrix}.$ (36)

This provides the stochastic linear dynamical system

$\begin{bmatrix}dy(\tau)\\\
dm(\tau)\end{bmatrix}=\Big{(}F\begin{bmatrix}y(\tau)\\\
m(\tau)\end{bmatrix}+B_{\mu}\Big{)}dt+dw(\tau).$ (37)

System (37) is discretized with intervals of size $\Delta T$ ($n\Delta T=T$)
which gives the following discrete-time stochastic linear dynamical system

$\begin{bmatrix}y(t\Delta T+\Delta T)\\\ m(t\Delta T+\Delta
T)\end{bmatrix}=\exp(F\Delta T)\begin{bmatrix}y(t\Delta T)\\\ m(t\Delta
T)\end{bmatrix}\\\ +\Delta B_{\mu}+\Delta w(t\Delta T),$ (38)

where $\Delta B_{\mu}$ and $\Delta w(t\Delta T)$ are defined below.

$\displaystyle\Delta B_{\mu}$
$\displaystyle\triangleq\sum_{i=0}^{\infty}F^{i}B_{\mu}\frac{\Delta
T^{i+1}}{(i+1)!},$ (39) $\displaystyle\Delta w(t\Delta T)$
$\displaystyle\sim\mathcal{N}(0,\Xi),$ $\displaystyle\Xi$
$\displaystyle=\int_{t\Delta T}^{(t+1)\Delta T}e^{F((t+1)\Delta
T-\tau)}Se^{F^{\top}(t+1)\Delta T-\tau)}d\tau.$ (40)

Equations (39) and (40) are from [30]. Evaluating (40) is analytically
intractable; therefore, [31] is used to approximate $\Xi$.

$\displaystyle\left[\begin{array}[]{c|c}\Phi_{1,1}&\Phi_{1,2}\\\
\hline\cr\mathbf{0}&\Phi_{2,2}\\\ \end{array}\right]$
$\displaystyle=\exp\left(\left[\begin{array}[]{c|c}-F^{\top}&\Sigma\\\
\hline\cr\mathbf{0}&F\\\ \end{array}\right]\Delta T\right),$ (45)
$\displaystyle\Phi_{2,2}^{\top}\Phi_{1,2}$ $\displaystyle\approx\Xi.$ (46)

Say that the trader uses the following strategy: the trader buys stock $i$ at
the start of time $t\Delta T-\Delta T$ and then sells that stock at time
$t\Delta T$. Define reward $X_{t}$ for this time period to be

$X_{t}\triangleq Y_{t\Delta T}^{[i]}-Y_{(t-1)\Delta
T}^{[i]}=\log\Big{(}\frac{S_{t\Delta T}^{[i]}}{S_{(t-1)\Delta
T}^{[i]}}\Big{)}.$ (47)

Therefore, the difference $Y_{t\Delta T}^{[i]}-Y_{(t-1)\Delta T}^{[i]}$ is the
logarithm of the percentage increase/decrease of buying at $t\Delta T-\Delta
T$ and then selling at $t\Delta T$. We extend (38) by using the following
matrices and vectors:

$\displaystyle z_{t}$ $\displaystyle\triangleq\begin{bmatrix}y(t\Delta T)\\\
m(t\Delta T)\\\ y(t\Delta T-\Delta T)\end{bmatrix}\in\mathbb{R}^{6},$
$\displaystyle\Gamma$
$\displaystyle\triangleq\left[\begin{array}[]{c|c}F&\mathbf{0}\\\ \hline\cr
I_{2}&\mathbf{0}\end{array}\right],$ (50) $\displaystyle\mu_{\xi}$
$\displaystyle\triangleq\begin{bmatrix}\Delta
B_{\mu}^{\top}&\mathbf{0}^{\top}\end{bmatrix}^{\top},$ $\displaystyle\xi_{t}$
$\displaystyle\sim\mathcal{N}(\mu_{\xi},Q),$ $\displaystyle Q$
$\displaystyle\triangleq\left[\begin{array}[]{c|c}\Phi_{2,2}^{\top}\Phi_{1,2}&\mathbf{0}\\\
\hline\cr\mathbf{0}&\mathbf{0}\\\ \end{array}\right],$ (53) $\displaystyle
C_{\theta}$ $\displaystyle\triangleq\begin{bmatrix}1&0&0&0&-1&0\\\
0&1&0&0&0&-1\end{bmatrix},$ $\displaystyle c_{a}$
$\displaystyle\in\\{\begin{bmatrix}1&0&0&0&-1&0\end{bmatrix}^{\top},$
$\displaystyle\quad\quad\quad\quad\begin{bmatrix}0&1&0&0&0&-1\end{bmatrix}^{\top},$
$\displaystyle\quad\quad\quad\quad\begin{bmatrix}0&0&0&0&0&0\end{bmatrix}^{\top}\\}.$
(54)

Finally, the eigenvectors $\begin{bmatrix}U&U^{\prime}\end{bmatrix}$ of
$\Gamma$ are computed, where $(C_{\theta}U,U^{-1}\Gamma U)$ is observable and
$U^{-1}\Gamma U$ is Schur. This transformation provides (26).


# A Refinement of Expurgation

Giuseppe Cocco, Albert Guillén i Fàbregas and Josep Font-Segura Giuseppe Cocco
is with the Department of Signal Theory and Communications, Universitat
Politècnica de Catalunya, 08034, Barcelona, Spain (e-mail:
giuseppe.cocco@upc.edu). Albert Guillén i Fàbregas is with the Department of
Engineering, University of Cambridge, CB2 1PZ Cambridge, U.K., and also with
the Department of Information and Communication Technologies, Universitat
Pompeu Fabra, 08018 Barcelona, Spain (e-mail: guillen@ieee.org). Josep Font-
Segura is with the Department of Information and Communication Technologies,
Universitat Pompeu Fabra, 08018, Barcelona, Spain (e-mail:
josep.font@ieee.org). This work was supported in part by the Ramon y Cajal
fellowship program (grant RYC2021-033908-I) funded by the Spanish Government
through MCIN/AEI/10.13039/501100011033 and the European Union
“NextGenerationEU” Recovery Plan, the European Research Council under ERC
Agreement 725411 and by the Spanish Ministry of Economy and Competitiveness
under Grant PID2020-116683GB-C22.

###### Abstract

We show that for a wide range of channels and code ensembles with pairwise-
independent codewords, with probability tending to $1$ with the code length,
expurgating an arbitrarily small fraction of codewords from a randomly
selected code results in a code attaining the expurgated exponent.

##  I Preliminaries

We consider the problem of reliable communication of $M_{n}$ equiprobable
messages over noisy channels described by a random transformation
$W^{n}\mkern-1.5mu(\boldsymbol{y}|\boldsymbol{x})$, where
$\boldsymbol{x}\in\mathcal{X}^{n}$ and $\boldsymbol{y}\in\mathcal{Y}^{n}$ are
the channel input and output sequences, and $\mathcal{X}$ and $\mathcal{Y}$
are the input and output alphabets, respectively. Each message
$m\in\\{1,\dotsc,M_{n}\\}$, where $M_{n}=\lceil 2^{nR}\rceil$, $R$ being the
code rate, is mapped onto an $n$-length codeword $\boldsymbol{x}_{m}$ sent
over the channel. The code is defined as
$\mathcal{C}(M_{n},n)=\\{\boldsymbol{x}_{1},\dotsc,\boldsymbol{x}_{M_{n}}\\}$.
We denote with $P_{{\rm e},m}\bigl{(}\mathcal{C}(M_{n},n)\bigr{)}$ the error
probability when codeword $m\in\\{1,\dotsc,M_{n}\\}$ from code
$\mathcal{C}(M_{n},n)$ is transmitted; similarly $P_{\rm
e}\bigl{(}\mathcal{C}(M_{n},n)\bigr{)}=\frac{1}{M_{n}}\sum_{m=1}^{M_{n}}P_{{\rm
e},m}\bigl{(}\mathcal{C}(M_{n},n)\bigr{)}$ denotes the average error
probability of the code. Let
$\mathsf{C}(M_{n},n)=\\{\boldsymbol{X}_{1},\dotsc,\boldsymbol{X}_{M_{n}}\\}$
be a random code, i.e., a set of $M_{n}$ random codewords generated with
probability
$\mathbb{P}[\mathsf{C}(M_{n},n)=\mathcal{C}(M_{n},n)]=\mathbb{P}[\boldsymbol{X}_{1}=\boldsymbol{x}_{1},\dotsc,\boldsymbol{X}_{M_{n}}=\boldsymbol{x}_{M_{n}}]$.
We assume that codewords are generated in a pairwise independent manner, that
is, for any two indices $m,k\in\\{1,\ldots,M_{n}\\},m\neq k$, it holds that
$\mathbb{P}[\boldsymbol{X}_{m}=\boldsymbol{x}_{m},\boldsymbol{X}_{k}=\boldsymbol{x}_{k}]=Q^{n}(\boldsymbol{x}_{m})Q^{n}(\boldsymbol{x}_{k})$,
where
$Q^{n}(\boldsymbol{x}_{m})=\mathbb{P}[\boldsymbol{X}_{m}=\boldsymbol{x}_{m}]$
is a probability distribution defined over $\mathcal{X}^{n}$.

Let $P_{{\rm e},m}\big{(}\mathsf{C}(M_{n},n)\big{)}$ and $P_{\rm
e}\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}$ be the random variables denoting the
error probability of the $m$-th codeword for random code $\mathsf{C}(M_{n},n)$
and the average error probability of the code, respectively. We denote the
$n$-length error exponents of such random variables by
$E_{m}\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}=-\frac{1}{n}\log P_{{\rm
e},m}\big{(}\mathsf{C}(M_{n},n)\big{)}$ and
$E\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}=-\frac{1}{n}\log P_{\rm
e}\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}$, respectively. For some ensembles and
channels the ensemble-average of the code error probability
$\mathbb{E}\bigl{[}P_{\rm e}\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}\bigr{]}$ is
known to decay exponentially in $n$ [1]. A lower bound on the error exponent
$-\frac{1}{n}\log\mathbb{E}\bigl{[}P_{\rm
e}\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}\bigr{]}$ is given by Gallager’s multi-
letter random coding exponent $E_{{\rm r}}^{n}(R,Q^{n})$ in [2, Eq. (5.6.16)].
For the DMC (DMC), this bound is known to coincide with the sphere-packing
upper bound on the reliability function [3, 4] in the high rate region.

In [5, Sec. 5.7] Gallager showed that, for some channels and ensembles, there
exists a code with strictly higher error exponent than $E_{{\rm
r}}^{n}(R,Q^{n})$ at low rates. In order to show this, Gallager considered a
pairwise-independent ensemble with $M_{n}^{\prime}=2M_{n}-1$ codewords. Using
Markov’s inequality he showed that

$\displaystyle\mathbb{P}\Bigl{[}P_{{\rm
e},m}(\mathsf{C}(M_{n}^{\prime},n))\geq 2^{\frac{1}{s}}\mathbb{E}[P_{{\rm
e},m}(\mathsf{C}(M_{n}^{\prime},n))^{s}]^{\frac{1}{s}}\Bigr{]}\leq\frac{1}{2}$
(1)

for any $s>0$. He then introduced the indicator function

$\displaystyle\varphi_{m}\bigl{(}\mathcal{C}(M_{n},n)\bigr{)}$ $\displaystyle\
=\begin{cases}1\ \text{ if }P_{{\rm
e},m}\bigl{(}\mathcal{C}(M_{n},n)\bigr{)}<2^{\frac{1}{s}}\mathbb{E}\bigl{[}P_{{\rm
e},m}\big{(}\mathsf{C}(M_{n},n)\big{)}^{s}\bigr{]}^{\frac{1}{s}}\\\ 0\ \text{
otherwise}\end{cases}$ (2)

and showed that, using (1) and (I), the following inequality holds

$\displaystyle\mathbb{E}\left[\sum_{m=1}^{M_{n}^{\prime}}\varphi_{m}(\mathsf{C}(M_{n}^{\prime},n))\right]\geq
M_{n}.$ (3)

From (3) it follows that, since the average number of codewords that have a
probability of error smaller than $2^{\frac{1}{s}}\mathbb{E}\bigl{[}P_{{\rm
e},m}\bigl{(}\mathcal{C}(M_{n}^{\prime},n)\bigr{)}^{s}\bigr{]}^{\frac{1}{s}}$
in a randomly generated code with $M_{n}^{\prime}=2M_{n}-1$ codewords is at
least $M_{n}$, there must exist a code having at least $M_{n}$ codewords, out
of the $M_{n}^{\prime}$, fulfilling this property. Thus, by removing
(expurgating) the worst half of the codewords from the code with
$M_{n}^{\prime}$ codewords we obtain a new code with $M_{n}$ codewords, each
of which satisfies the condition in the first line of the right-hand side in
(I). Finally, restricting $s$ to $0<s\leq 1$, Gallager derives a lower bound
on the exponent of $2^{\frac{1}{s}}\mathbb{E}[P_{{\rm
e},m}\bigl{(}\mathcal{C}(M_{n}^{\prime},n)\bigr{)}^{s}]^{\frac{1}{s}}$, given
by

$\displaystyle E_{\rm ex}^{n}(R,Q^{n})=E_{\rm
x}^{n}(\hat{\rho}_{n},Q^{n})-\hat{\rho}_{n}R,$ (4)

where

$\displaystyle E_{\rm x}^{n}(\rho,Q^{n})$
$\displaystyle=-\frac{1}{n}\log\biggl{(}\sum_{\boldsymbol{x}}\sum_{\boldsymbol{x}^{\prime}}Q^{n}(\boldsymbol{x})Q^{n}(\boldsymbol{x}^{\prime})Z_{n}(\boldsymbol{x},\boldsymbol{x}^{\prime})^{\frac{1}{\rho}}\biggr{)}^{\rho},$
(5)

$Z_{n}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\sum_{\boldsymbol{y}}\sqrt{W^{n}\mkern-1.5mu(\boldsymbol{y}|\boldsymbol{x})W^{n}\mkern-1.5mu(\boldsymbol{y}|\boldsymbol{x}^{\prime})}$
is the Bhattacharyya coefficient between codewords
$\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}^{n}$ while

$\displaystyle\hat{\rho}_{n}=\operatorname*{arg\,max}_{\rho\geq
1}\bigl{\\{}E_{\rm x}^{n}(\rho,Q^{n})-\rho R\bigr{\\}}$ (6)

is the parameter that yields the highest exponent. The preceding argument is
valid for the maximal probability of error, since every codeword in the
expurgated code attains the same exponent. In addition, observe that since (3)
uses the standard ensemble-average argument (i.e. by taking the average over
the ensemble) we show the existence of a code with the desired property. The
exponent in (4) is the expurgated exponent. We refer to the code with
$M_{n}^{\prime}$ codewords before expurgation as a mother code. We say that a
mother code is good if, once expurgated, we obtain a code with asymptotically
the same rate, the codewords of which each have an exponent at least as large
as the expurgated.

A refinement of the above follows from (1). Specifically, for $\epsilon>0$ it
can be shown that there exists a code with $M_{n}^{\prime}=M_{n}(1+\epsilon)$
codewords such that removing $\epsilon M_{n}$ codewords yields a code that
attains the expurgated exponent [6, Lemma 1]. Although [6, Lemma 1]
generalizes Gallager’s method, it still only shows the existence of a code
that attains the expurgated exponent.

##  II Main Result

This paper strengthens existing results on expurgation by showing that the
probability of finding a code with $M_{n}^{\prime}=(1+\epsilon)M_{n}$
codewords that contains a code with at least $M_{n}$ codewords each of which
achieving the expurgated exponent tends to $1$ with the code length. We define
the sequence $\delta_{n}=\frac{\hat{\rho}_{n}}{n}\log\gamma_{n}$, where
$\gamma_{n}$ is such that $\lim_{n\rightarrow\infty}\gamma_{n}=\infty$ while
$\lim_{n\rightarrow\infty}\frac{\log\gamma_{n}}{n}=0$, $\hat{\rho}_{n}$ being
a positive sequence defined in (6) that depends on the channel, the ensemble
and the rate. From the definition of $\delta_{n}$ it can be seen that if
$\hat{\rho}_{n}$ either converges to a constant or grows sufficiently slowly,
there exists a $\gamma_{n}$ such that $\delta_{n}\rightarrow 0$. Similarly to
Gallager, for a given $\delta_{n}$, we define the indicator function

$\displaystyle\phi_{m}\bigl{(}\mathcal{C}(M_{n},n)\bigr{)}=\begin{cases}1\
\text{ if }E_{m}\bigl{(}\mathcal{C}(M_{n},n)\bigr{)}>E_{\rm
ex}^{n}(R,Q^{n})-\delta_{n}\\\ 0\ \text{ otherwise},\end{cases}$ (7)

and the number of codewords attaining an exponent higher than $E_{\rm
ex}^{n}(R,Q^{n})-\delta_{n}$ as

$\displaystyle\Phi\bigl{(}\mathcal{C}(M_{n}^{\prime},n)\bigr{)}~{}{=}\sum_{m=1}^{M_{n}^{\prime}}\phi_{m}\bigl{(}\mathcal{C}(M_{n}^{\prime},n)\bigr{)}.$
(8)

###### Theorem 1

Consider a pairwise-independent code ensemble with
$M_{n}^{\prime}=M_{n}(1+\epsilon)$ codewords and any $\epsilon>0$. If the
sequence $\\{\delta_{n}\\}_{n=1}^{\infty}$, which depends on the channel and
the ensemble, satisfies $\lim_{n\rightarrow\infty}\delta_{n}=0$, then for any
$0<\epsilon_{1}<\epsilon$, it holds that

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}\bigl{[}\Phi\bigl{(}\mathsf{C}(M_{n}^{\prime},n)\bigr{)}\geq
M_{n}(1+\epsilon_{1})\bigr{]}=1.$ (9)

###### Proof:

See Section III. ∎

In words, with high probability we find a mother code with
$M_{n}^{\prime}=(1+\epsilon)M_{n}$ codewords, $M_{n}$ of which attain the
expurgated exponent. That is, good mother codes are found easily and only
contain an arbitrarily small fraction $\epsilon/(1+\epsilon)$ of codewords
that need to be expurgated. Theorem 1 extends Gallager’s method, and applies,
among others, to i.i.d. (i.i.d.) and constant composition codes over DMCs, as
well as channels with memory such as the finite-state channel in [2, Sec.
4.6], for which the expurgated exponent is derived in [7].

As a final remark, recent works [8, 9, 7, 10] show that for many ensembles,
most low-rate codes have an error exponent
$E\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}$ that is strictly larger than the
exponent of the ensemble average error probability, i.e., the random coding
exponent. Similarly, Theorem 1 implies that for most codes, almost any
codeword has an associated error exponent
$E_{m}\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}$ that is strictly larger than the
ensemble average of the exponent of the error probability of the codebook
$\mathbb{E}\big{[}E\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}\big{]}$. In both cases
the smaller error exponent of the average probability of error is due to a
relatively small number of elements (codes in the first case, codewords in the
second) that perform poorly. Furthermore, as shown in [9, 10] for i.i.d. and
constant composition codes over DMC, the error exponents of the codes in the
ensemble concentrate around the TRC (TRC) exponent [11, 8]. Similarly to such
works, it can be shown that the error exponent
$E_{m}\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}$, for any $m$, concentrates around
its mean, the expurgated exponent. The proof makes use of Lemma 1 in Section
III, and follows almost identical steps as in [10, Theorem 1], [7, Theorem 1]
and [7, Theorem 2] once $P_{\rm e}(\mathcal{C})$ is replaced by $P_{{\rm
e},m}\bigl{(}\mathcal{C}\bigr{)}$ and it is omitted here.

##  III Proof of Theorem 1

We start with the following lemma, whose proof is almost identical to that of
[7, Lemma 1].

###### Lemma 1

For a channel $W^{n}$ and a pairwise-independent $M_{n}^{\prime}$-codewords
code ensemble with codeword distribution $Q^{n}$, for any
${m}\in\\{1,\ldots,M_{n}^{\prime}\\}$ it holds that

$\mathbb{P}\bigl{[}E_{m}\bigl{(}\mathsf{C}(M_{n}^{\prime},n)\bigr{)}>E_{\rm
ex}^{n}(R,Q^{n})-\delta_{n}\bigr{]}\geq 1-\frac{1}{\gamma_{n}},$ (10)

where $\gamma_{n}$ and $\delta_{n}$ are positive real-valued sequences.

The proof of Lemma 1 follows from Markov’s inequality

$\displaystyle\mathbb{P}\Bigl{[}P_{{\rm
e},m}(\mathsf{C}_{n})\geq\gamma_{n}^{\frac{1}{s}}\mathbb{E}[P_{{\rm
e},m}(\mathsf{C}_{n})^{s}]^{\frac{1}{s}}\Bigr{]}\leq\frac{1}{\gamma_{n}}$ (11)

and applying the same steps as in [7, Theorem 1] once $P_{\rm
e}(\mathsf{C}_{n})$ is replaced with $P_{{\rm e},m}(\mathsf{C}_{n})$. The
sequences $\gamma_{n}$ and $\delta_{n}$ are the same as those introduced in
Section II. Observe that using inequality (11) and following similar steps as
in [7] it can be shown that $\lim_{n\rightarrow\infty}E_{\rm ex}^{n}(R,Q^{n})$
is a lower bound on
$\lim_{n\rightarrow\infty}\mathbb{E}[E_{m}\bigl{(}\mathsf{C}(M_{n},n)\bigr{)}]$.
Furthermore, using similar arguments as in [10] it can be shown that such
bound is tight at least for i.i.d. and constant composition codes over DMC.
That is, for such ensembles and channels
$\lim_{n\rightarrow\infty}\mathbb{E}\big{[}-\frac{1}{n}\log P_{{\rm
e},m}\big{(}\mathsf{C}(M_{n},n)\big{)}\big{]}=\lim_{n\rightarrow\infty}E_{\rm
ex}^{n}(R,Q^{n})$, i.e., the expurgated is the typical codeword exponent.

If the positive sequence $\hat{\rho}_{n}$, defined in (6), converges or grows
sufficiently slowly, then there exists a sequence $\gamma_{n}$ such that
$\lim_{n\rightarrow\infty}\gamma_{n}=\infty$,
$\lim_{n\rightarrow\infty}\frac{\log\gamma_{n}}{n}=0$, for which
$\delta_{n}=\frac{\hat{\rho}_{n}}{n}\log\gamma_{n}\rightarrow 0$. For rate
zero, that is when $\lim_{n\to\infty}\frac{1}{n}\log{M_{n}}=0$, the $n$-length
error exponent in (4) depends on the particular subexponential growth of
$M_{n}$, while $\hat{\rho}_{n}$ tends to infinity with a growth that depends
on the channel and the ensemble. In this case, as discussed in the paragraph
succeeding [7, Eq. (89)], the assumption that
$\frac{\hat{\rho}_{n}}{n}\log\gamma_{n}\rightarrow 0$ holds if the normalized
variance of the Bhattacharyya coefficient
$Z_{n}(\boldsymbol{x},\boldsymbol{x}^{\prime})$ grows slower than
$\smash{\sqrt{\frac{n}{\log\gamma_{n}}}}$. In any case, choosing such
$\gamma_{n}$ and applying Lemma 1 we have that

$\mathbb{P}\bigl{[}E_{m}\bigl{(}\mathsf{C}(M_{n}^{\prime},n)\bigr{)}>E_{\rm
ex}^{n}(R,Q^{n})-\delta_{n}\bigr{]}\geq 1-\frac{1}{\gamma_{n}}.$ (12)

The random variable $\Phi(\mathsf{C}(M_{n}^{\prime},n))$, averaged across the
ensemble, satisfies

$\displaystyle\mathbb{E}[\Phi(\mathsf{C}(M_{n}^{\prime},n))]$
$\displaystyle=\sum_{m=1}^{M_{n}(1+\epsilon)}\mathbb{E}[\phi_{m}(\mathsf{C}(M_{n}^{\prime},n))]$
(13)
$\displaystyle\geq\sum_{m=1}^{M_{n}(1+\epsilon)}\left(1-\frac{1}{\gamma_{n}}\right)$
(14) $\displaystyle=M_{n}(1+\epsilon)\left(1-\frac{1}{\gamma_{n}}\right),$
(15)

where (14) follows from the definition of the indicator function (7) and (12).

We define
$\Psi(\mathsf{C}(M_{n}^{\prime},n))=M_{n}^{\prime}-\Phi(\mathsf{C}(M_{n}^{\prime},n))$,
which is the number of codewords with exponent smaller than $E_{\rm
ex}^{n}(R,Q^{n})-\delta_{n}$. From (15) it follows that

$\displaystyle\mathbb{E}[\Psi(\mathsf{C}(M_{n}^{\prime},n))]\leq\frac{M_{n}(1+\epsilon)}{\gamma_{n}}.$
(16)

Then, for sufficiently large $n$ we have that

$\displaystyle\mathbb{P}\Big{[}\Psi(\mathsf{C}(M_{n}^{\prime},n))>\frac{M_{n}(1+\epsilon)}{\sqrt{\gamma_{n}}}\Big{]}$
$\displaystyle~{}{\leq}~{}\frac{1}{\sqrt{\gamma_{n}}},$ (17)

where (17) follows from Markov’s inequality and (16). This shows that the
probability of finding a code with many codewords with exponent strictly
smaller than $E_{\rm ex}^{n}(R,Q^{n})-\delta_{n}$ vanishes with $n$. To prove
our main result, we write the tail probability in (9) as

$\displaystyle\mathbb{P}\Big{[}\Phi(\mathsf{C}(M_{n}^{\prime},n))\geq
M_{n}(1+\epsilon_{1})\Big{]}$ $\displaystyle\
=1-\mathbb{P}\Big{[}\Phi(\mathsf{C}(M_{n}^{\prime},n))<M_{n}(1+\epsilon_{1})\Big{]}$
(18) $\displaystyle\
=1-\mathbb{P}\Big{[}\Psi(\mathsf{C}(M_{n}^{\prime},n))>M_{n}(\epsilon-\epsilon_{1})\Big{]},$
(19)

where we used the definitions of $\Psi(\mathsf{C}(M_{n}^{\prime},n))$ and
$M_{n}^{\prime}$. Since $\gamma_{n}$ tends to infinity, there must exist an
$n_{0}\in\mathbb{N}$ such that
$\epsilon-\epsilon_{1}>\frac{(1+\epsilon)}{\sqrt{\gamma_{n}}}$ for $n>n_{0}$
and therefore

$\displaystyle\lim_{n\to\infty}\mathbb{P}\Big{[}\Phi(\mathsf{C}(M_{n}^{\prime},n))\geq
M_{n}(1+\epsilon_{1})\Big{]}$ $\displaystyle\
\geq\lim_{n\to\infty}1-\mathbb{P}\Big{[}\Psi(\mathsf{C}(M_{n}^{\prime},n))>\frac{M_{n}(1+\epsilon)}{\sqrt{\gamma_{n}}}\Big{]}$
(20) $\displaystyle\ \geq\lim_{n\to\infty}1-\frac{1}{\sqrt{\gamma_{n}}},$ (21)

where (21) follows from (17). Finally, solving the limit yields the desired
result.

## References

  * [1] A. Feinstein, “Error bounds in noisy channels without memory,” _IRE Trans. on Information Theory_ , vol. 1, no. 2, pp. 13–14, 1955.
  * [2] R. Gallager, _Information Theory and Reliable Communication_. USA: John Wiley & Sons, Inc., 1968.
  * [3] C. Shannon, R. Gallager, and E. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless channels. I,” _Information and Control_ , vol. 10, no. 1, pp. 65–103, 1967. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0019995867900526
  * [4] R. Fano, _Transmission of Information: A Statistical Theory of Communication_. Massachusetts Institute of Technology Press, 1961.
  * [5] R. Gallager, “A simple derivation of the coding theorem and some applications,” _IEEE Trans. Inf. Theory_ , vol. 11, no. 1, pp. 3–18, 1965\.
  * [6] J. Scarlett, L. Peng, N. Merhav, A. Martinez, and A. Guillén i Fàbregas, “Expurgated random-coding ensembles: Exponents, refinements, and connections,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 8, pp. 4449–4462, 2014.
  * [7] G. Cocco, A. Guillén i Fàbregas, and J. Font-Segura, “Typical error exponents: A dual domain derivation,” _IEEE Trans. Inf. Theory_ , vol. 69, no. 2, pp. 776–793, Feb. 2023.
  * [8] N. Merhav, “Error exponents of typical random codes,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 9, pp. 6223–6235, Sep. 2018.
  * [9] R. Tamir, N. Merhav, N. Weinberger, and A. Guillén i Fàbregas, “Large deviations behavior of the logarithmic error probability of random codes,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 11, pp. 6635–6659, 2020\.
  * [10] L. V. Truong, G. Cocco, J. Font-Segura, and A. Guillén i Fàbregas, “Concentration properties of random codes,” _IEEE Trans. Inf. Theory_ , vol. 69, no. 12, pp. 7499–7537, Dec. 2023.
  * [11] A. Barg and G. Forney, “Random codes: Minimum distances and error exponents,” _IEEE Trans. Inf. Theory_ , vol. 48, no. 9, pp. 2568–2573, Sep. 2002.

  *[DMC]:
  *[i.i.d.]:
  *[TRC]:


journal=J. Topol.,

author=Kronheimer, Peter B.,
author=Mrowka, Tomasz S.,
title=Instantons and some concordance invariants of knots,
journal=J. Lond. Math. Soc. (2),

author=Konno, Hokuto,
author=Miyazawa, Jin,
author=Taniguchi, Masaki,
title=Involutions, knots, and Floer K-theory,
journal=preprint arXiv:2110.09258,

author=Konno, Hokuto,
author=Mallick, Abhishek,
author=Taniguchi, Masaki,
title=From diffeomorphisms to exotic phenomena in small 4-manifolds,
journal=preprint arXiv:2304.05997,

author=Konno, Hokuto,
author=Miyazawa, Jin,
author=Taniguchi, Masaki,
title=Involutions, links, and Floer cohomologies,
journal=preprint arXiv:2304.01115,
note=To appear in Journal of Topology,

author=Kim, Min Hoon,
author=Wu, Zhongtao,
title=On rational sliceness of Miyazaki's fibered, –amphicheiral
journal=Bull. Lond. Math. Soc.,

author=Lannes, Jean,
title=Sur les espaces fonctionnels dont la source est le classifiant
d'un $p$-groupe abélien élémentaire,
journal=Inst. Hautes Études Sci. Publ. Math.,
note=With an appendix by Michel Zisman,

author=Levine, Jerome P.,
title=Knot cobordism groups in codimension two,
journal=Comment. Math. Helv.,

author=Li, Jiakai,
title=Monopole Floer homology and real structures,
journal=preprint arXiv:2211.10768,

author=Li, Jiakai,
title=Real monopole Floer homology and skein exact triangles,
journal=preprint arXiv:2304.01742,

author=Litherland, Richard A.,
title=Cobordism of satellite knots,
booktitle=Four-manifold theory (Durham, N.H., 1982),
series=Contemp. Math.,
publisher=Amer. Math. Soc., Providence, RI,

author=Livingston, Charles,
title=Signed clasp numbers and four-genus bounds,
journal=preprint arXiv:2206.10432,

author=Lidman, Tye,
author=Manolescu, Ciprian,
title=The equivalence of two Seiberg-Witten Floer homologies,

author=Manolescu, Ciprian,
title=Seiberg–Witten–Floer stable homotopy type of
three-manifolds with $b_1=0$,
journal=Geom. Topol.,

author=Manolescu, Ciprian,
title=A gluing theorem for the relative Bauer–Furuta invariants,
journal=J. Differential Geom.,

author=Miller, Allison N.,
title=Amphichiral knots with large 4-genus,
journal=Bull. Lond. Math. Soc.,

author=Miyazawa, Jin,
title=A gauge theoretic invariant of embedded surfaces in $4$-manifolds
and exotic $p^2$-knots,
journal=preprint arXiv:2312.02041,

author=Miyazaki, Katura,
title=Nonsimple, ribbon fibered knots,
journal=Trans. Amer. Math. Soc.,

author=Manolescu, Ciprian,
author=Marengon, Marco,
author=Sarkar, Sucharit,
author=Willis, Michael,
title=A generalization of Rasmussen's invariant, with applications to
surfaces in some four-manifolds,
journal=Duke Math. J.,

author=Montague, Ian,
title=Seiberg–Witten Floer K-theory and cyclic group actions on
spin four-manifolds with boundary,
journal=preprint arXiv:2210.08565,

author=Mrowka, Tomasz S.,
author=Ozsváth, Peter S.,
author=Yu, Baozhen,
title=Seiberg-Witten monopoles on Seifert fibered spaces,
journal=Comm. Anal. Geom.,

author=Némethi, András,
title=On the Ozsváth–Szabó invariant of negative definite
plumbed 3-manifolds,
journal=Geom. Topol.,

author=Némethi, András,
title=Lattice cohomology of normal surface singularities,
journal=Publ. Res. Inst. Math. Sci.,

author=Nakamura, Nobuhiro,
title=$\rm{Pin}^-(2)$-monopole equations and intersection forms with
local coefficients of four-manifolds,
journal=Math. Ann.,

author=Nakamura, Nobuhiro,
title=$\rm{Pin}^-(2)$-monopole invariants,
journal=J. Differential Geom.,

author=Neumann, Walter D.,
title=An invariant of plumbed homology spheres,
booktitle=Topology Symposium, Siegen 1979 (Proc. Sympos., Univ.
Siegen, Siegen, 1979),
series=Lecture Notes in Math.,
publisher=Springer, Berlin,

author=Neumann, Walter D.,
author=Raymond, Frank,
title=Seifert manifolds, plumbing, $\mu $-invariant and orientation
reversing maps,
booktitle=Algebraic and geometric topology (Proc. Sympos., Univ.
California, Santa Barbara, Calif., 1977),
series=Lecture Notes in Math.,
publisher=Springer, Berlin-New York,

author=Ozsváth, Peter S.,
author=Szabó, Zoltán,
title=Absolutely graded Floer homologies and intersection forms for
four-manifolds with boundary,
journal=Adv. Math.,

author=Ozsváth, Peter S.,
author=Szabó, Zoltán,
title=On the Floer homology of plumbed three-manifolds,
journal=Geom. Topol.,

author=Ozsváth, Peter S.,
author=Szabó, Zoltán,
title=Holomorphic disks and knot invariants,
journal=Adv. Math.,

author=Plotnick, Steven P.,
title=Fibered knots in $S^4$—twisting, spinning, rolling, surgery,
and branching,
booktitle=Four-manifold theory (Durham, N.H., 1982),
series=Contemp. Math.,
publisher=Amer. Math. Soc., Providence, RI,

author=Rasmussen, Jacob,
title=Floer homology and knot complements,
publisher=ProQuest LLC, Ann Arbor, MI,
url=http://gateway.proquest.com/openurl?url_ver=Z39.88-2004   rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation   res_dat=xri:pqdiss   rft_dat=xri:pqdiss:3091665,
note=Thesis (Ph.D.)–Harvard University,

author=Rasmussen, Jacob,
title=Khovanov homology and the slice genus,
journal=Invent. Math.,

author=Rudolph, Lee,
title=How independent are the knot-cobordism classes of links of plane
curve singularities?,
journal=Notices Amer. Math. Soc,

author=Schiffman, Stephen J.,
title=A mod $p$ Whitehead theorem,
journal=Proc. Amer. Math. Soc.,

author=Shibuya, Tetsuo,
title=Some relations among various numerical invariants for links,
journal=Osaka Math. J.,

author=Siebenmann, Laurent,
title=On vanishing of the Rohlin invariant and nonfinitely
amphicheiral homology $3$-spheres,
booktitle=Topology Symposium, Siegen 1979 (Proc. Sympos., Univ.
Siegen, Siegen, 1979),
series=Lecture Notes in Math.,
publisher=Springer, Berlin,

author=tom Dieck, Tammo,
title=Transformation groups,
series=De Gruyter Studies in Mathematics,
publisher=Walter de Gruyter & Co., Berlin,

author=Tristram, Andrew,
title=Some cobordism invariants for links,
journal=Proc. Cambridge Philos. Soc.,

author=Tian, Gang,
author=Wang, Shuguang,
title=Orientability and real Seiberg–Witten invariants,
journal=Internat. J. Math.,