# Best Arm Identification in Restless Markov Multi–Armed Bandits

P. N. Karthik, Kota Srinivas Reddy, and Vincent Y. F. Tan
National University of Singapore
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We study the problem of identifying the best arm in a multi-armed bandit
environment when each arm is a time-homogeneous and ergodic discrete-time
Markov process on a common, finite state space. The state evolution on each
arm is governed by the arm’s transition probability matrix (TPM). A decision
entity that knows the set of arm TPMs but not the exact mapping of the TPMs to
the arms, wishes to find the index of the best arm as quickly as possible,
subject to an upper bound on the error probability. The decision entity
selects one arm at a time sequentially, and all the unselected arms continue
to undergo state evolution (restless arms). For this problem, we derive the
first-known problem instance-dependent asymptotic lower bound on the growth
rate of the expected time required to find the index of the best arm, where
the asymptotics is as the error probability vanishes. Further, we propose a
sequential policy that, for an input parameter $R$, forcibly selects an arm
that has not been selected for $R$ consecutive time instants. We show that
this policy achieves an upper bound that depends on $R$ and is monotonically
non-increasing as $R\to\infty$. The question of whether, in general, the
limiting value of the upper bound as $R\to\infty$ matches with the lower
bound, remains open. We identify a special case in which the upper and the
lower bounds match. Prior works on best arm identification have dealt with (a)
independent and identically distributed observations from the arms, and (b)
rested Markov arms, whereas our work deals with the more difficult setting of
restless Markov arms.

††publicationid: pubid: 978-1-5090-5356-8/17/$31.00 © 2017 IEEE

##  I Introduction

Consider a multi-armed bandit with $K\geq 2$ arms in which each arm is
associated with a time-homogeneous and ergodic discrete-time Markov process
evolving on a common, finite state space. The state evolutions on each arm are
governed by the arm’s transition probability matrix (TPM). Given a function
$f$ on the common state space of the arms, we define the best arm as the arm
with the largest average value of $f$, averaged over the arm’s stationary
distribution. A decision entity that has knowledge of the set of TPMs of the
arms, but does not know the exact mapping of the TPMs to the arms, wishes to
find the index of the best arm as quickly as possible, subject to an upper
bound on the error probability. Our interest is in the asymptotics as the
error probability vanishes.

The above problem, known popularly in the literature as best arm
identification, is an instance of an optimal stopping problem in decision
theory, and can be embedded within the framework of active sequential
hypothesis testing studied in the classical works of Chernoff [1] and Albert
[2]. Prior works on best arm identification have dealt with (a) independent
and identically distributed (i.i.d.) observations from the arms, as in [3],
and (b) rested Markov arms [4] in which the arms yield Markovian observations
and an arm evolves only when selected, and remains frozen otherwise. In this
work, we extend the results of [3, 5, 4] to the more difficult setting when
the unselected arms continue to evolve (restless arms). An examination of the
results in [3, 5, 4] shows that given an error probability threshold
$\epsilon>0$, the minimum expected expected time required to find the best arm
(or, expected stopping time) with an error probability no more than $\epsilon$
grows as $O(\log(1/\epsilon))$ in the limit as $\epsilon\downarrow 0$. We
anticipate a similar growth rate for the expected stopping time in the setting
of restless arms. Our goal is to characterise or bound the exact constant
multiplying $\log(1/\epsilon)$ for the setting of restless arms and attempt to
achieve the lower bound of $O(\log(1/\epsilon))$ in the limit as
$\epsilon\downarrow 0$. Additionally, we aim to devise an efficient policy
that achieves the fundamental limit.

###  I-A A Preliminary Trembling Hand Model

The continued evolution of the unselected arms in our work makes it necessary
for the decision entity to keep a record of (a) the time elapsed since each
arm was previously selected (the arm’s delay), and (b) the state of each arm
recorded at its previous selection instant (the arm’s last observed state).
The notion of arm delays is superfluous when the arms are rested because the
unobserved arms remain frozen. They are also redundant when the arms yield
i.i.d. observations because the observation from an arm at any given time is
independent of all its previous observations. When the arms are restless, the
arm delays are non-negative, integer-valued, and introduce a countably-
infinite dimension to the problem. In a related problem of identifying an
anomalous or odd arm in a restless multi-armed bandit, Karthik and Sundaresan
[6, 7] demonstrated that the arm delays and the last observed states
constitute a controlled Markov process. A key aspect of the works [6, 7] is
the notion of a trembling hand for selecting the arms that is defined in the
system model. Probabilistically, a trembling hand with parameter
$\gamma\in[0,1]$ selects an arm uniformly at random with probability $\gamma$,
and selects the intended arm with probability $1-\gamma$. As the authors note
in [6], when $\gamma>0$, the controlled Markov process (of arm delays and last
observed states) satisfies a key ergodicity property (see [6, Lemma 1]) which
is pivotal in establishing matching upper and lower bounds on the expected
time to find the odd arm. An understanding of whether the lower bound for the
case $\gamma=0$ admits a matching upper bound remains open.

###  I-B Forgoing the Trembling Hand Model and Constraining the Maximum Delay
of Each Arm

The trembling hand model of [6, 7] implies that at any given time, the
probability of selecting any arm is at least $\gamma/K$, irrespective of the
arm selection scheme used. In this work, we forgo the trembling hand
assumption and allow for arm selection schemes to put zero mass on certain
arms. We derive a lower bound on the expected time to find the best arm over
all arm selection schemes. However, such a generic lower bound may not be
achievable. In order to analyse the achievability of the lower bound, we
restrict attention to those arm selection policies which, for an input
parameter $R>K$, forcefully select an arm if its delay is equal to $R$. For
this class of policies, we derive an upper bound in terms of $R$ and show that
the sequence of upper bounds, one for each value of $R$, is monotonically non-
increasing as $R$ increases. An advantage of our method over the methods of
[6, 7] is that while the arm selection schemes in [6, 7] are not practically
implementable, the arm selection schemes we propose in this paper are easy to
implement.

The question of whether, in general, the limiting value of the upper bounds
matches the generic lower bound appears to be a difficult problem and remains
open. Notwithstanding this, we identify some special cases when the limiting
value of the upper bounds matches with the generic lower bound.

###  I-C Prior Works on Multi-Armed Bandits and Best Arm Identification

The problem of minimising regret for multi-armed bandits was introduced in the
seminal work of Lai and Robbins [8] when each arm yields i.i.d. observations.
Anantharam et al. [9] extended the results of Lai and Robbins to the setting
of rested arms. We refer the reader to [10] for an extensive survey of regret
minimization problems. In [11, 3], the authors derived a lower bound on the
sample complexity of best arm identification in multi-armed bandits with
i.i.d. observations from arms. Many follow-up works proposed algorithms to
achieve the lower bounds; notable among them are action-elimination algorithms
[12, 13], upper confidence bound (UCB) algorithms [14, 15], and lower and
upper confidence bound (LUCB) algorithms [16, 17]. Several extensions to the
classical setup of best-arm identification in multi-armed bandits have
appeared in the literature; notable among them are correlated bandits [18],
cascading bandits [19], bandits with switching costs [20], and bandits with
corrupted rewards [21].

For the problem of finding the best arm as quickly as possible subject to an
upper bound on the error probability, the paper [3] provided a problem
instance-dependent lower bound on the expected time required to find the best
arm for the setting of i.i.d. observations from the arms, and a track-and-stop
scheme that meets the lower bound asymptotically as the error probability
vanishes. Moulos [4] extended the results of [3] to the setting of rested arms
with hidden Markov observations. However, the lower and the upper bounds in
[4] differ by a constant multiplicative factor; the achievability analysis
therein uses novel concentration inequalities for Markov processes derived by
the author. For a related problem of finding the anomalous (or odd) arm in
multi-armed bandits, the works [22, 6, 7] obtain matching upper and lower
bounds on the expected time required to find the odd arm subject to an upper
bound on the error probability. While [22] studies the setting of rested arms,
the works [6, 7] focus on the setting of restless arms. A key aspect of the
works [6, 7] is a certain trembling hand model for selecting the arms,
motivated from a certain visual science experiment. The paper [6] assumes that
the TPMs of the odd arm and the non-odd arms are known beforehand to the
decision entity, whereas the works [22, 7] deal with the case when the arm
TPMs are unknown.

The recent works [23, 24, 25] study a more general problem of sequential
hypothesis testing in multi-armed bandits, some special cases of which are the
problems of best arm identification and odd arm identification, in the context
of i.i.d. observations from each arm. An extension of the results of [23, 24,
25] to the settings of rested and restless arms is a possible direction of
future work.

###  I-D Contributions

In this paper, we study the problem of finding the best arm in a restless
multi-armed bandit as quickly as possible, subject to an upper bound on the
error probability. Our technical contributions are as follows:

  * –

In Section V, we show that given any $\epsilon>0$, the expected time required
to find the best arm with an error probability no more than $\epsilon$ grows
as $O(\log(1/\epsilon))$ in the limit as $\epsilon\downarrow 0$. We explicitly
characterise the problem instance-dependent constant multiplying
$\log(1/\epsilon)$ that is a function of the arm TPMs.

  * –

For a problem instance $C$, the constant $T^{\star}(C)$ appearing in our lower
bound is the solution of a sup-min optimisation problem, where the supremum is
over all possible state-action occupancy measures associated with the
countable-state controlled Markov process of arm delays and last observed
states; see (21) for details. The question of whether the supremum in the
expression for $T^{\star}(C)$ lower bound is attained is still open. The key
difficulty in showing this is the presence of the countably-infinite valued
arm delays appearing in the expression for $T^{\star}(C)$, which makes further
simplifications of the expression for $T^{\star}(C)$ difficult. In the prior
works [3, 5, 4], further simplification of the expression for the constants
governing the lower bound is possible because the notion of arm delays is
superfluous in the settings of those works.

In a related problem of odd arm identification in restless multi-armed
bandits, Karthik and Sundaresan [6, 7] show that under a trembling hand model
for arms selection, the supremum in the expression for the lower bounds in
these works may be further simplified by restricting the supremum to the class
of all stationary arm selection policies; see [6, 7] for more details.
However, it is unclear if such a simplification is possible in the absence of
the trembling hand (as is the setting of this paper).

  * –

In our achievability analysis presented in Section VI, to ameliorate the
difficulty arising from the countably infinite-valued arm delays, we constrain
the maximum delay of each arm to be no more than $R$, and focus our attention
on those policies which select an arm forcibly if its delay equals $R$. This
constraint on the maximum delay of each arm makes the state-action space
finite and amenable to further analyses. To the best of our knowledge, this is
the first work to analyse delay-constrained policies for restless multi-armed
bandits.

It is worth noting that the achievability analyses in the works [6, 7] rely
crucially on a key ergodicity property (see [6, Lemma 1]) for the controlled
Markov process of arm delays and last observed states that is satisfied under
a trembling hand model for arms selection. This ergodicity property is pivotal
to the achievability analysis in [6, 7], and it is unclear if the same
property holds in the absence of the trembling hand.

  * –

We devise a policy that, for an input parameter $R$, forcibly pulls an arm if
its delay equals $R$, and achieves an upper bound of the order
$\Theta(\log(1/\epsilon))$. We show that the best (smallest) constant
multiplying $\log(1/\epsilon)$ is equal to $1/T_{R}^{\star}(C)$ under the
problem instance $C$; see (27) for the exact expression of $T_{R}^{\star}(C)$.
Our results imply that $1/T_{R}^{\star}(C)$ is a valid asymptotic upper bound
on the expected stopping time for all integers $R$.

  * –

We show that $T_{R}^{\star}(C)$ is non-decreasing in $R$, and that
$T_{R}^{*}(C)\leq T^{\star}(C)$ for all $R$, thus implying that
$\lim_{R\to\infty}\ T_{R}^{\star}(C)$ exists. Thus, the lower bound of our
work is given by $T^{\star}(C)^{-1}$, whereas the upper bound is governed by
$\lim_{R\to\infty}T_{R}^{\star}(C)^{-1}$. While it is certainly true that
$\lim_{R\to\infty}\ T_{R}^{\star}(C)\leq T^{\star}(C)$, showing that, in
general, this inequality is an equality seems to be a difficult problem and
remains open. In the special case when the TPM of each arm has identical rows,
which is akin to obtaining i.i.d. observations from the arms, the above
inequality is an equality, thus leading to matching upper and lower bounds in
this special setting. We are thus able to recover the results of the prior
works [5, 3] for the case when the i.i.d. observations from each arm come from
a finite alphabet.

###  I-E Paper Organisation

The rest of this paper is organised as follows. In Section II, we setup the
notations and state our central goal. In Section III, we introduce the notions
of arm delays, last observed states, and the Markov decision problem arising
from the arm delays and the last observed states. We provide expressions for
the log-likelihoods and the log-likelihood ratios, the basic quantities of
analysis, in Section IV, and present the asymptotic lower bound on the growth
rate of the expected time required to find the best arm in Section V. In
Section VI, we constrain the maximum delay of each arm to be no more than $R$
for some $R\in\mathbb{N}\cap(K,\infty)$, and describe a policy that forcibly
samples an arm whose delay equals $R$. We provide results on the performance
of the policy in Section VII, and state the main result in Section VIII. We
discuss the convergence of $T_{R}^{\star}(C)$ to $T^{\star}(C)$ as
$R\to\infty$ in Section IX, where we show that the convergence takes place in
the special case when the TPM of each arm has identical rows. We conclude the
paper in Section X. The proofs of all the results are contained in Appendices
A-I.

##  II Notations and Preliminaries

We consider a multi-armed bandit with $K\geq 2$ arms, and define
$\mathcal{A}\coloneqq\\{1,\ldots,K\\}$ to be the set of arms. We associate
with each arm an ergodic discrete-time Markov process on a common, finite
state space $\mathcal{S}$. We assume that the Markov process of each arm is
independent of those of the other arms. We write $\\{X_{t}^{a}:t\geq 0\\}$
denote the Markov process of arm $a\in\mathcal{A}$.111Throughout the paper,
time $t\in\\{0,1,2,\ldots\\}.$ The state evolution on each arm is governed by
its transition probability matrix (TPM). Given TPMs $P_{1},\ldots,P_{K}$ and a
permutation $\sigma:\\{1,\ldots,K\\}\to\\{1,\ldots,K\\}$, let
$C=(P_{\sigma(1)},\ldots,P_{\sigma(K)})$ denote an assignment of the TPMs to
the arms in which the TPM assigned to arm $a$ is $P_{\sigma(a)}$. In the
sequel, we refer to $C$ as an assignment of the TPMs, and we let $\mathcal{C}$
denote the collection of all possible assignments of the TPMs, i.e.,

$\mathcal{C}=\\{(P_{\sigma(1)},\ldots,P_{\sigma(K)}):\ \sigma\text{ is a
permutation on }\mathcal{A}\\}.$ (1)

For each $k=1,\ldots,K$, let $\mu_{k}=\\{\mu_{k}(i):\ i\in\mathcal{S}\\}$
denote the unique stationary distribution of the TPM $P_{k}$. Given a function
$f:\mathcal{S}\to\mathbb{R}$, let

$\nu_{a}\coloneqq\sum_{i\in\mathcal{S}}\ f(i)\,\mu_{a}(i),\quad
a\in\mathcal{A},$ (2)

denote the average value of $f$ under $\mu_{a}$. Define the best arm
$a^{\star}\in\mathcal{A}$ as

$a^{\star}\coloneqq\arg\max_{a\in\mathcal{A}}\
\nu_{a}=\arg\max_{a\in\mathcal{A}}\ \sum_{i\in\mathcal{S}}\ f(i)\,\mu_{a}(i).$
(3)

We assume throughout the paper that $a^{\star}$ is unique. Without loss of
generality, let $P_{a^{\star}}=P_{1}.$222The reader may recognise that this
does not necessarily imply $a^{\star}=1$.

For an integer $d\geq 1$ and a matrix $P$, let $P^{d}$ denote the matrix
obtained by multiplying $P$ with itself $d$ times. For $i,j\in\mathcal{S}$ and
$d\geq 1$, let $P^{d}(j|i)$ to denote the $(i,j)$th element of $P^{d}$. For
$a\in\mathcal{A}$, let each row of $P_{a}$ be mutually absolutely continuous
with the corresponding row of $P_{a^{\prime}}$ for all $a^{\prime}\neq a$. It
is easy to see that this implies that for all $d\geq 1$, each row of
$P_{a}^{d}$ is mutually absolutely continuous with the corresponding row of
$P_{a^{\prime}}^{d}$. The above assumption implies that the decision entity
cannot infer the best arm merely by observing certain specific state(s) or
state-transition(s) on the arm.

A decision entity that knows $P_{1},\ldots,P_{K}$ only up to a permutation
wishes to find the index of the best arm (i.e., the arm whose TPM is $P_{1}$)
as quickly as possible, subject to an upper bound on the error probability.
Clearly, this is accomplished if the decision entity finds $C\in\mathcal{C}$
that defines the problem instance. Given $C\in\mathcal{C}$, we write
$\textsf{Alt}(C)$ to denote the set of all assignments of the TPMs alternative
to $C$, i.e., those assignments of the TPMs in which the location of the best
arm is different from the one in $C$. In order to find the index of the best
arm in a problem instance $C$, the decision entity selects the arms
sequentially, one at each time $t$. Let $A_{t}$ be the arm selected at time
$t$. The decision entity observes the state of the arm $A_{t}$, denoted by
$\bar{X}_{t}$. In contrast to the previous works [3, 5, 4] that deal with
i.i.d. observations from the arms and rested arms, we assume that the
unobserved arms continue to undergo state evolution whether or not they are
selected (restless arms). Let
$(A_{0:t},\bar{X}_{0:t})\coloneqq(A_{0},\bar{X}_{0},\ldots,A_{t}\,\bar{X}_{t})$
denote the history of all the arm selections and observations seen up to time
$t$. All random variables are defined on a common probability space
$(\Omega,\mathcal{F},\mathbb{P})$. Define the filtration

$\mathcal{F}_{0}\coloneqq\\{\Omega,\emptyset\\},\quad\mathcal{F}_{t}\coloneqq\sigma(A_{0:t-1},\bar{X}_{0:t-1}),\quad
t\geq 1.$ (4)

###  II-A Policy and Problem Definition

A policy $\pi$ is defined by a collection of functions $\\{\pi_{t}:t\geq
0\\}$. At each time $t$, $\pi_{t}$ does one of the following based on the
history $\mathcal{F}_{t}$:

  * •

stop and declare the index of the best arm;

  * •

choose to pull arm $A_{t}$ according to a deterministic or a randomised rule.

Let $\pi$ denote a generic policy, and let $\tau(\pi)$ denote the stopping
time of policy $\pi$ (defined with respect to the filtration (4)). Let
$\theta(\tau(\pi))$ denote the index of the best arm declared by the policy
$\pi$ at the stopping time.

Let $P_{C}^{\pi}(\cdot)$ denote the probability computed under the assignment
of the TPMs $C$ and under the policy $\pi$. For $a\in\mathcal{A}$, let
$\mathcal{C}_{a}\subset\mathcal{C}$ denote the collection of all permutations
in which $P_{a}=P_{1}$. Clearly, the collection $\\{\mathcal{C}_{a}:\
a\in\mathcal{A}\\}$ is a partition of $\mathcal{C}$. Given an error
probability threshold $\epsilon>0$, let

$\Pi(\epsilon)\coloneqq\\{\pi:\ \text{for all }a\in\mathcal{A},\ \
P_{C}^{\pi}(\theta(\tau(\pi))\neq a)\leq\epsilon\ \forall
C\in\mathcal{C}_{a}\\}$ (5)

denote the collection of all policies whose error probability at the stopping
time is no more than $\epsilon$ for all possible assignments of TPMs. We
anticipate from similar results in the prior works [3, 5, 4] that

$\inf_{\pi\in\Pi(\epsilon)}\mathbb{E}_{C}^{\pi}[\tau(\pi)]=\Theta(\log(1/\epsilon)).$

Here, $\mathbb{E}_{C}^{\pi}[\cdot]$ denotes the expectation under the
assignment of the TPMs $C$ and policy $\pi$. Our interest is in
characterising, or at least bounding, the value of

$\lim_{\epsilon\downarrow 0}\inf_{\pi\in\Pi(\epsilon)}\
\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log(1/\epsilon)}.$ (6)

For simplicity, we assume that every policy starts by selecting arm $1$ at
time $t=0$, arm $2$ at time $t=1$, etc., and arm $K$ at time $t=K-1$. This
ensures that the Markov process of each arm is observed at least once.

##  III Delays, Last Observed States, and a Markov Decision Problem

The contents of this section are mostly borrowed from [6, Section II-B, II-C],
but modified appropriately to reflect the absence of the trembling hand
assumption of [6], with an intent to keep the material in the paper self-
contained. Recall that the decision entity observes only one of the arms at
each time $t$, while the unobserved arms continue to undergo state evolution.
This means that at any time $t$, the probability of the observation
$\bar{X}_{t}$ on the selected arm $A_{t}$ given the history $\mathcal{F}_{t}$
is a function of (a) the time elapsed since the previous time instant of
selection of arm $A_{t}$ (called the _delay_ of arm $A_{t}$), and (b) the
state of arm $A_{t}$ at its previous selection time instant (called the _last
observed state_ of arm $A_{t}$). Notice that when the arms are _rested_ , the
notion of arm delays is superfluous since each arm remains frozen at its
previously observed state until its next selection time instant. Also, the
notion of arm delays is redundant in the setting of iid observations because
the current state of the arm selected is independent of the state at its
previous selection. The notion of arm delays is a key distinguishing feature
of the setting of restless arms.

For $t\geq K$, let $d_{a}(t)$ and $i_{a}(t)$ respectively denote the delay and
the last observed state of arm $a$ at time $t$. Let
$\underline{d}(t)\coloneqq(d_{1}(t),\ldots,d_{K}(t))$ and
$\underline{i}(t)\coloneqq(i_{1}(t),\ldots,i_{K}(t))$ denote the vectors of
arm delays and the last observed states at time $t$. Note that arm delays and
last observed states are defined only for $t\geq K$ as these quantities are
well-defined only when at least one observation is available from each arm.
Set $\underline{d}(K)=(K,K-1,\ldots,1)$. Thus, $d_{a}(t)\geq 1$ for all $t\geq
K$, and that $d_{a}(t)=1$ if and only if arm $a$ is selected at time $t-1$.

The rule for updating the arm delays and last observed states is as follows:
if $A_{t}=a^{\prime}$, then

$\displaystyle{d}_{a}(t+1)=\begin{cases}d_{a}(t)+1,&a\neq a^{\prime},\\\
1,&a=a^{\prime},\end{cases}\qquad\qquad
i_{a}(t+1)=\begin{cases}i_{a}(t),&a\neq a^{\prime},\\\
X_{t}^{a},&a=a^{\prime},\end{cases}$ (7)

where $X_{t}^{a}=\bar{X}_{t}$ is the state of the arm $A_{t}=a^{\prime}$ at
time $t$. Thus, for all $t\geq K$, based on
$\\{(\underline{d}(s),\underline{i}(s)):K\leq s\leq t\\}$, the decision entity
chooses to pull $A_{t}$ and observes $\bar{X}_{t}$.333Note that specifying
$\\{(\underline{d}(s),\underline{i}(s)):K\leq s\leq t\\}$ is equivalent to
specifying $(A_{0:t-1},\bar{X}_{0:t-1})$ for all $t\geq K$. It then form
$(\underline{d}(t+1),\underline{i}(t+1))$. This repeats until the stopping
time, at which time it declares $\theta(\tau(\pi))$ (under policy $\pi$) as
the candidate best arm.

From the update rule in (7), it is clear that the process
$\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ takes values in a subset
$\mathbb{S}$ of the countable set $\mathbb{N}^{K}\times\mathcal{S}^{K}$, where
$\mathbb{N}=\\{1,2,\ldots\\}$ denotes the set of natural numbers. The subset
$\mathbb{S}$ is formed based on the constraint that at any time $t\geq K$,
exactly one of the components of $\underline{d}(t)$ is equal to $1$, and all
the other components are $>1$. Given any assignment of the TPMs
$C\in\mathcal{C}$ and policy $\pi$, note that for all
$(\underline{d}^{\prime},\underline{i}^{\prime})\in\mathbb{S}$ and $t\geq K$,

$\displaystyle
P_{C}^{\pi}(\underline{d}(t+1)=\underline{d}^{\prime},\underline{i}(t+1)=\underline{i}^{\prime}\mid\\{(\underline{d}(s),\underline{i}(s)),\
K\leq s\leq t\\},A_{0:t})$
$\displaystyle=P_{C}^{\pi}(\underline{d}(t+1)=\underline{d}^{\prime},\underline{i}(t+1)=\underline{i}^{\prime}\mid(\underline{d}(t),\underline{i}(t)),A_{t}).$
(8)

On account of (8) being satisfied, we say that under any policy $\pi$, the
evolution of the process $\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$
is _controlled_ by the sequence $\\{A_{t}\\}_{t\geq 0}$ of intended arm
selections under policy $\pi$. Alternatively,
$\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ is a controlled Markov
process, with $\\{A_{t}\\}_{t\geq 0}$ being the sequence of controls.444The
terminology used here follows that of Borkar [26]. Thus, we are in a Markov
decision problem (MDP) setting. We now make precise the state space, the
action space, the transition probabilities and our objective.

The state space of the MDP is $\mathbb{S}$, with the state at time $t$ denoted
$(\underline{d}(t),\underline{i}(t))$. The action space of the MDP is
$\mathcal{A}$, with action $A_{t}$ at time $t$ possibly depending on the
history $\mathcal{F}_{t}$. The transition probabilities for the MDP under an
assignment of the TPMs $C\in\mathcal{C}$ and a policy $\pi$ are given by

$\displaystyle
P_{C}^{\pi}(\underline{d}(t+1)=\underline{d}^{\prime},\underline{i}(t+1)=\underline{i}^{\prime}\mid\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},A_{t}=a)$
$\displaystyle=\begin{cases}(P_{C}^{a})^{d_{a}}(i_{a}^{\prime}|i_{a}),&\text{if
}d_{a}^{\prime}=1\text{ and }d^{\prime}_{\tilde{a}}=d_{\tilde{a}}+1\text{ for
all }\tilde{a}\neq a,\\\ &i_{\tilde{a}}^{\prime}=i_{\tilde{a}}\text{ for all
}\tilde{a}\neq a,\\\ 0,&\text{otherwise},\end{cases}$ (9)

where $P_{C}^{a}$ denotes the TPM of arm $a$ under the assignment of the TPMs
$C$. For instance, if $C=(P_{1},\ldots,P_{K})$, then $P_{C}^{a}=P_{a}$ for all
$a\in\mathcal{A}$. Note that the right hand side of (9) is not a function of
$t$ or $\pi$. Let
$Q_{C}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i},a)$
denote the transition probabilities in (9).

##  IV Log-Likelihoods and Log-Likelihood Ratios

Given $C\in\mathcal{C}$, let

$\displaystyle Z_{C}^{\pi}(n)\coloneqq\log P_{C}^{\pi}(A_{0:n},\bar{X}_{0:n})$
(10)

denote the log-likelihood of all the controls and observations seen up to time
$n$ under the policy $\pi$ when $C$ is the assignment of the TPMs. Under the
assumption that $\pi$ selects arm $1$ at time $t=0$, arm $2$ at time $t=1$,
etc., and arm $K$ at time $K-1$, (10) may be expressed as

$\displaystyle Z_{C}^{\pi}(n)$ $\displaystyle=\sum_{a=1}^{K}\log
P_{C}^{\pi}(X_{a-1}^{a})$ (11) $\displaystyle\hskip 28.45274pt+\sum_{t=K}^{n}\
\log P_{C}^{\pi}(A_{t}|A_{0:t-1},\,\bar{X}_{0:t-1})$ (12) $\displaystyle\hskip
56.9055pt+\sum_{t=K}^{n}\ \log
P_{C}^{\pi}(\bar{X}_{t}|A_{0:t},\,\bar{X}_{0:t-1}).$ (13)

Because $\pi$ is oblivious to the assignment of the TPMs $C$, (12) does not
depend on $C$. Furthermore, (13) may be expressed as

$\displaystyle\sum_{t=K}^{n}\ \log
P_{C}^{\pi}(\bar{X}_{t}|A_{0:t},\,\bar{X}_{0:t-1})$
$\displaystyle=\sum_{t=K}^{n}\ \sum_{a=1}^{K}\ \mathbb{I}_{\\{A_{t}=a\\}}\
\log P_{C}^{\pi}(\bar{X}_{t}|A_{0:t-1},A_{t}=a,\bar{X}_{0:t-1})$
$\displaystyle=\sum_{t=K}^{n}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\ \sum_{a=1}^{K}\
\mathbb{I}_{\\{\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i},\,A_{t}=a\\}}\,\log(P_{C}^{a})^{d_{a}}(\bar{X}_{t}|i_{a})$
$\displaystyle=\sum_{t=K}^{n}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\ \sum_{a=1}^{K}\
\sum_{j\in\mathcal{S}}\
\mathbb{I}_{\\{\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i},\,A_{t}=a,\,\bar{X}_{t}=j\\}}\,\log(P_{C}^{a})^{d_{a}}(j|i_{a})$
$\displaystyle=\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\ N(n,\underline{d},\underline{i},a,j)\
\log(P_{C}^{a})^{d_{a}}(j|i_{a}),$ (14)

where

$\displaystyle N(n,\underline{d},\underline{i},a,j)\coloneqq\sum_{t=K}^{n}\
\mathbb{I}_{\\{\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i},\,A_{t}=a,\,\bar{X}_{t}=j\\}}$
(15)

denotes the number of times up to time $n$ the process
$\\{(\underline{d}(t),\underline{i}(t)):\,t\geq K\\}$ is in the state
$(\underline{d},\underline{i})$, arm $a$ is selected subsequently, and the
state of arm $a$ is observed to be $j$. Let

$\displaystyle
N(n,\underline{d},\underline{i},a)\coloneqq\sum_{j\in\mathcal{S}}\
N(n,\underline{d},\underline{i},a,j),\quad
N(n,\underline{d},\underline{i})\coloneqq\sum_{a=1}^{K}\
\sum_{j\in\mathcal{S}}\ N(n,\underline{d},\underline{i},a,j).$ (16)

Given $C,C^{\prime}\in\mathcal{C}$, let

$\displaystyle Z_{CC^{\prime}}^{\pi}(n)\coloneqq
Z_{C}^{\pi}(n)-Z_{C^{\prime}}^{\pi}(n)=\log\frac{P_{C}^{\pi}(A_{0:n},\bar{X}_{0:n})}{P_{C^{\prime}}^{\pi}(A_{0:n},\bar{X}_{0:n})}$
(17)

denote the log-likelihood ratio (LLR) of the controls and observations seen
under the policy $\pi$ when the assignment of the TPMs is $C$ with respect to
that when the assignment of the TPMs is $C^{\prime}$. Using (14) in
conjunction with the fact that (12) does not depend on $C$, we get

$\displaystyle
Z_{CC^{\prime}}^{\pi}(n)=\sum_{a=1}^{K}\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}+\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\ N(n,\underline{d},\underline{i},a,j)\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}.$
(18)

##  V Lower Bound

We now present a lower bound for (6). Given two probability distributions
$\mu$ and $\nu$ on the finite state space $\mathcal{S}$, the Kullback–Leibler
(KL) divergence (also called the relative entropy) between $\mu$ and $\nu$ is
defined as

$D_{\textsf{KL}}(\mu\|\nu)\coloneqq\sum_{i\in\mathcal{S}}\mu(i)\log\frac{\mu(i)}{\nu(i)},$
(19)

where, by convention, $0\log\frac{0}{0}=0$.

###### Proposition 1

Suppose $C\in\mathcal{C}$ is the underlying assignment of the TPMs. Then,

$\liminf_{\epsilon\downarrow
0}\inf_{\pi\in\Pi(\epsilon)}\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log(1/\epsilon)}\geq\frac{1}{T^{\star}(C)},$
(20)

where $T^{\star}(C)$ is given by

$\displaystyle T^{\star}(C)\coloneqq\sup_{\nu}\
\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\ \sum_{a=1}^{K}\
\nu(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a})).$
(21)

In (21), the supremum is over all
$\nu=\\{\nu(\underline{d},\underline{i},a):(\underline{d},\underline{i})\in\mathbb{S},a\in\mathcal{A}\\}$
satisfying

$\displaystyle\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\leavevmode\nobreak\
\sum_{a=1}^{K}\,\nu(\underline{d},\underline{i},a)=1,$ (22)
$\displaystyle\nu(\underline{d},\underline{i},a)\geq 0\quad\text{for all
}(\underline{d},\underline{i},a)\in\mathbb{S}\times\mathcal{A}.$ (23)

###### Proof:

The proof proceeds in several steps. First, we derive an analogue of the
ubiquitous change-of-measure result [5, Lemma 18] for the setting of restless
arms. We then lower bound the expected LLR of any policy whose stoppage error
probability is at most $\epsilon$ by $d(\epsilon,1-\epsilon)$, where $d(x,y)$
denotes the relative entropy between two Bernoulli distributions with
parameters $x$ and $y$. Next, we derive an upper bound on the expected LLR in
terms of the expected stopping time. This involves deriving an analogue of
Wald’s identity for the setting of restless arms. Combining the upper and the
lower bounds for the expected LLR, we get (20). The details are in Appendix A.
∎

###  V-A A Flow Constraint

Notice that $T^{\star}(C)$ is the optimal value of an infinite-dimensional
linear program (LP). The question of whether there exists $\nu$ attaining the
supremum in (21) remains open. The key difficulty in showing this is that
because the set $\mathbb{S}$ is countably infinite, it is not clear whether
the set of all $\nu$ satisfying (22)-(23) (which is akin to the space of all
probability distributions on $\mathbb{S}\times\mathcal{A}$) is compact. Also,
because this supremum is over all probability distributions on
$\mathbb{S}\times\mathcal{A}$ which is a large class of distributions, the
lower bound in (20) may not be achievable. It seems necessary to introduce
additional constraints on $\nu$ to render the lower bound achievable. Indeed,
given $\delta>0$, suppose $\nu_{\delta}$ is a probability distribution on
$\mathbb{S}\times\mathcal{A}$ such that

$\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\ \sum_{a=1}^{K}\
\nu_{\delta}(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))\geq
T^{\star}(C)-\delta.$

One way to achieve the quantity on the left hand side of the above equation is
to ensure that for all
$(\underline{d},\underline{i},a)\in\mathbb{S}\times\mathcal{A}$, the value of
the fraction $N(n,\underline{d},\underline{i},a)/n$ is close to
$\nu_{\delta}(\underline{d},\underline{i},a)$ for all $n$ large (the regime of
large $n$ is akin to the regime of vanishing error probabilities). It seems
difficult to accomplish this in the absence of more structure on
$\nu_{\delta}$. It is worth noting here that in a related problem of odd arm
identification, the authors of [6] are confronted with a similar difficulty in
showing the achievability of the lower bound therein. To ameliorate the
difficulty, they introduce a version of the following flow constraint on
$\nu$:

$\textsf{flow
constraint}:\quad\sum_{a=1}^{K}\nu(\underline{d}^{\prime},\underline{i}^{\prime},a)=\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\
\sum_{a=1}^{K}\ \nu(\underline{d},\underline{i},a)\
Q_{C}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i},a)\quad\text{for
all }(\underline{d}^{\prime},\underline{i}^{\prime})\in\mathbb{S}.$ (24)

In (24), $Q_{C}$ is the MDP transition matrix defined in (9). The flow
constraint is, in fact, a global balance equation, and dictates that for any
$(\underline{d}^{\prime},\underline{i}^{\prime})\in\mathbb{S}$, the long-term
probability of a transition from
$(\underline{d}^{\prime},\underline{i}^{\prime})$ (the flow out of
$(\underline{d}^{\prime},\underline{i}^{\prime})$, captured by the left hand
side of (24)) is equal to the probability of a transition to
$(\underline{d}^{\prime},\underline{i}^{\prime})$ (the flow into
$(\underline{d}^{\prime},\underline{i}^{\prime})$, captured by the right hand
side of (24)). The authors of [6] show that their lower bound, after including
the flow constraint, can be achieved by a certain trembling hand-based policy;
see [6, Section V] for a description of the policy. However, the policy in [6]
is not practically implementable.

With an end goal of showing achievability of our lower bound, we take (24)
into consideration along with (22)-(23) when evaluating the supremum in (21),
and wish to design a policy that (a) is computationally feasible/tractable and
easy-to-implement, and (b) achieves the lower bound in (20). This forms the
content of the next section.

##  VI Achievability

As alluded to in the previous section, the trembling hand-based policy of [6]
is not practically implementable. One reason for this is that the arm delays
(which appear in the policy of [6]) take countably infinitely many values and
therefore cannot be handled on a machine with finite-size memory. To alleviate
the difficulty arising from the countably infinite-valued arm delays, we study
a simplified setting where the maximum delay of each arm is restricted to be
at most $R$ for some $R\in\mathbb{N}\cap(K,\infty),$555We consider $R>K$ to be
consistent with our assumption that each of the arms is sampled once in the
first $K$ time instants. and an arm whose delay is equal to $R$ at any given
time is forcibly selected in the following time instant. Let $\mathbb{S}_{R}$
denote the subset of $\mathbb{S}$ in which the delay of each arm is no more
than $R$. Further, for $a\in\mathcal{A}$, let $\mathbb{S}_{R,a}$ denote the
subset of $\mathbb{S}_{R}$ in which the delay of arm $a$ is equal to $R$.
Notice that $\mathbb{S}_{R,a}$ is a finite set for each $a$ and that
$\mathbb{S}_{R,a}$ and $\mathbb{S}_{R,a^{\prime}}$ are disjoint for all
$a^{\prime}\neq a$.

###  VI-A Modifications to the MDP Transition Probabilities Under Maximum
Delay Constraint

Recall that $\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ and
$\\{A_{t}:t\geq 0\\}$ together define a Markov decision problem (MDP) whose
state space is $\mathbb{S}$, the action space is $\mathcal{A}$, the state at
time $t$ is $(\underline{d}(t),\underline{i}(t))$, and the control (or action)
at time $t$ is $A_{t}$. From Section III, we know that the transition
probabilities of the MDP are given by (9). When the delay of each arm is
constrained to be no more than $R$, the modified state space of the MDP is
$\mathbb{S}_{R}$, and the modified transition probabilities for the MDP are as
follows:

  * •

Case 1: $(\underline{d},\underline{i})\notin\bigcup_{a=1}^{K}\
\mathbb{S}_{R,a}$. In this case, the transition probabilities are as in (9).

  * •

Case 2: $(\underline{d},\underline{i})\in\mathbb{S}_{R,a}$ for some
$a\in\mathcal{A}$. In this case, when $A_{t}=a$,

$\displaystyle
P_{C}^{\pi}(\underline{d}(t+1)=\underline{d}^{\prime},\underline{i}(t+1)=\underline{i}^{\prime}\mid\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},A_{t}=a)$
$\displaystyle=\begin{cases}(P_{C}^{a})^{R}(i_{a}^{\prime}|i_{a}),&\text{if
}d_{a}^{\prime}=1\text{ and }d^{\prime}_{\tilde{a}}=d_{\tilde{a}}+1\text{ for
all }\tilde{a}\neq a,\\\ &i_{\tilde{a}}^{\prime}=i_{\tilde{a}}\text{ for all
}\tilde{a}\neq a,\\\ 0,&\text{otherwise},\end{cases}$ (25)

and when $A_{t}\neq a$, the transition probabilities are undefined.

We write
$Q_{C,R}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i},a)$
to denote the transition probabilities in (25).

###  VI-B Capturing the Maximum Delay Constraint and a Finite Dimensional
Linear Program

Recall that in the absence of any constraints on the maximum delay of each
arm, the lower bound is as in (20), with the constant $T^{\star}(C)$ in (20)
as given in (21). Further, the supremum in (21) is over all $\nu$ satisfying
(22)-(24). When the delay of each arm is constrained to be no more than $R$,
the following additional constraint on $\nu$ comes into play:

$R\textsf{-max-delay-
constraint}:\quad\nu(\underline{d},\underline{i},a)=\sum_{a^{\prime}=1}^{K}\
\nu(\underline{d},\underline{i},a^{\prime})\quad\text{for all
}(\underline{d},\underline{i})\in\mathbb{S}_{R,a}.$ (26)

The condition in (26) captures the observation that any occurrence of the
state $(\underline{d},\underline{i})\in\mathbb{S}_{R,a}$ is followed by
selecting arm $a$ forcibly (i.e., with probability $1$), thus implying that
$\nu(\underline{d},\underline{i},a^{\prime})=0$ for all $a^{\prime}\neq a$
which is equivalent to (26). Let $T_{R}^{\star}(C)$ be the optimal value of
the following optimisation problem:

$\displaystyle\sup_{\nu}\ \min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a})),$
(27) subject to
$\displaystyle\sum_{a=1}^{K}\nu(\underline{d}^{\prime},\underline{i}^{\prime},a)=\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\,\nu(\underline{d},\underline{i},a)\
Q_{C,R}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i},a)\quad\text{for
all }(\underline{d}^{\prime},\underline{i}^{\prime})\in\mathbb{S}_{R},$ (28)
$\displaystyle\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \nu(\underline{d},\underline{i},a)=1,$ (29)
$\displaystyle\nu(\underline{d},\underline{i},a)\geq 0\quad\text{for all
}(\underline{d},\underline{i},a)\in\mathbb{S}_{R}\times\mathcal{A},$ (30)
$\displaystyle\nu(\underline{d},\underline{i},a)=\sum_{a^{\prime}=1}^{K}\
\nu(\underline{d},\underline{i},a^{\prime})\quad\text{for all
}(\underline{d},\underline{i})\in\mathbb{S}_{R,a},\quad a\in\mathcal{A}.$ (31)

Notice that the above optimisation problem is a finite-dimensional LP, and is
the analogue of the infinite-dimensional LP in (21) with the additional
condition in (31) to account for the case when an arm is forcibly selected if
its delay equals $R$. Because (a) $\mathbb{S}_{R}\times\mathcal{A}$ is finite,
(b) the space of all probability distributions on
$\mathbb{S}_{R}\times\mathcal{A}$ (say,
$\mathscr{P}(\mathbb{S}_{R}\times\mathcal{A})$) is compact with respect to the
topology arising from the Euclidean metric in
$\mathbb{R}^{|\mathbb{S}_{R}\times\mathcal{A}|}$, (c) the set of all $\nu$
satisfying (28)-(31) is a closed subset of
$\mathscr{P}(\mathbb{S}_{R}\times\mathcal{A})$ (and therefore compact), and
(d) the expression

$\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))$

is continuous in $\nu$, it follows by Weierstrass extreme value theorem that
there exists
$\nu_{C,R}^{\star}=\\{\nu_{C,R}^{\star}(\underline{d},\underline{i},a):(\underline{d},\underline{i},a)\in\mathbb{S}_{R}\times\mathcal{A}\\}$
that attains the supremum in (27). Although a closed-form expression for
$\nu_{C,R}^{\star}$ is not currently available, it can easily be evaluated
numerically. In the next section, we fix $R\in\mathbb{N}\cap(K,\infty)$ and
design a policy for finding the best arm that samples an arm forcibly if its
delay is equal to $R$. Additionally, we demonstrate that our policy (a) stops
in finite time almost surely, (b) satisfies the desired error probability, and
(c) achieves an upper bound of $1/T_{R}^{\star}(C)$ asymptotically as the
error probability vanishes. We shall see that our policy is easy to implement
as it operates on the finite set $\mathbb{S}_{R}$ instead of the countable set
$\mathbb{S}$.

###  VI-C A Policy for Finding the Best Arm Under a Maximum Delay Constraint

Fix an $R\in\mathbb{N}\cap(K,\infty)$. In this section, we design a policy for
finding the best arm when the delay of each arm is constrained to be no more
than $R$. Towards this, we first analyse a uniform arm selection policy that,
for all $t\geq K$, selects the arms uniformly whenever the delay of each arm
is $<R$, and forcibly selects an arm whose delay is equal to $R$. Let this
policy be denoted $\pi_{R}^{\textsf{unif}}$. It is clear that
$\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ is a Markov process under
$\pi_{R}^{\textsf{unif}}$ with $\mathbb{S}_{R}$ as its state space. The
following result shows that this Markov process is, in fact, ergodic.

###### Lemma 1

Fix $R\in\mathbb{N}\cap(K,\infty)$. Under every assignment of the TPMs
$C\in\mathcal{C}$, the process $\\{(\underline{d}(t),\underline{i}(t)):\ t\geq
K\\}$ is ergodic under the policy $\pi_{R}^{\textsf{unif}}$.

###### Proof:

See Appendix B. ∎

As a consequence of Lemma 1, the process
$\\{(\underline{d}(t),\underline{i}(t)):\ t\geq K\\}$ has a unique stationary
distribution, say
$\mu_{C,R}^{\textsf{unif}}=\\{\mu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i}):(\underline{d},\underline{i})\in\mathbb{S}_{R}\\}$,
under the policy $\pi_{R}^{\textsf{unif}}$ and under the assignment of the
TPMs $C$. We note that
$\mu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i})>0$ for all
$(\underline{d},\underline{i})\in\mathbb{S}_{R}$. Let

$\nu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i},a)\coloneqq\begin{cases}\frac{\mu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i})}{K},&(\underline{d},\underline{i})\notin\bigcup_{a^{\prime}=1}^{K}\
\mathbb{S}_{R,a^{\prime}},\\\
\mu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i}),&(\underline{d},\underline{i})\in\mathbb{S}_{R,a},\\\
0,&(\underline{d},\underline{i})\in\bigcup_{a^{\prime}\neq a}\
\mathbb{S}_{R,a^{\prime}}.\end{cases}$ (32)

denote the corresponding ergodic state-action occupancy measure. Observe that
$\nu_{C,R}^{\textsf{unif}}$ satisfies (28)-(31).

For $\eta\in(0,1]$ and $C\in\mathcal{C}$, let

$\displaystyle\nu_{\eta,R,C}(\underline{d},\underline{i},a)$
$\displaystyle\coloneqq\eta\
\nu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i},a)+(1-\eta)\
\nu_{C,R}^{\star}(\underline{d},\underline{i},a),$ (33)
$\displaystyle\mu_{\eta,R,C}(\underline{d},\underline{i})$
$\displaystyle\coloneqq\sum_{a=1}^{K}\
\nu_{\eta,R,C}(\underline{d},\underline{i},a).$ (34)

Observe that $\mu_{\eta,R,C}(\underline{d},\underline{i})\geq\frac{\eta}{K}\
\mu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i})>0$ for all
$(\underline{d},\underline{i})\in\mathbb{S}_{R}$. Also, $\nu_{\eta,R,C}$
satisfies (28)-(31) by virtue of the fact that both
$\nu_{C,R}^{\textsf{unif}}$ and $\nu_{C,R}^{\star}$ satisfy (28)-(31). Let
$\lambda_{\eta,R,C}=\\{\lambda_{\eta,R,C}(a|\underline{d},\underline{i}):a\in\mathcal{A},\
(\underline{d},\underline{i})\in\mathbb{S}_{R}\\}$ be defined as

$\lambda_{\eta,R,C}(a|\underline{d},\underline{i})=\frac{\nu_{\eta,R,C}(\underline{d},\underline{i},a)}{\mu_{\eta,R,C}(\underline{d},\underline{i})}\quad(\underline{d},\underline{i})\in\mathbb{S}_{R},\
a\in\mathcal{A}.$ (35)

Notice that for all
$(\underline{d},\underline{i})\notin\bigcup_{a^{\prime}=1}^{K}\
\mathbb{S}_{R,a^{\prime}}$,

$\displaystyle\lambda_{\eta,R,C}(a|\underline{d},\underline{i})\geq\frac{\eta}{K}\
\mu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i})$
$\displaystyle\geq\frac{\eta}{K}\ \mu_{R}^{\textsf{min}},$ (36)

where

$\mu_{R}^{\textsf{min}}\coloneqq\min_{C\in\mathcal{C}}\
\min_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\mu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i})>0.$
(37)

That is, whenever the delay of each arm is $<R$, the distribution
$\lambda_{\eta,R,C}(\cdot|\underline{d},\underline{i})$ puts a strictly
positive mass on each of the arms. Using the arm selection rule in (35)
instead of the uniform sampling rule and following the proof template in
Appendix B, it can be shown that the policy $\pi^{\lambda_{\eta,R,C}}$, which
selects the arms at each time instant according to the rule in (35), renders
the process $\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ ergodic. We
now claim that the stationary distribution of the process
$\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ under
$\pi^{\lambda_{\eta,R,C}}$ is $\mu_{\eta,R,C}$. Indeed, suppose
$Q^{C,R}=\\{Q^{C,R}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i}):(\underline{d}^{\prime},\underline{i}^{\prime}),(\underline{d},\underline{i})\in\mathbb{S}_{R}\\}$
denotes the transition probability matrix of the Markov process
$\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ under the policy
$\pi^{\lambda_{\eta,R,C}}$. Then,

$\displaystyle
Q^{C,R}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i})$
$\displaystyle=\sum_{a=1}^{K}\
\lambda_{\eta,R,C}(a|\underline{d},\underline{i})\
Q_{C,R}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i},a),$
(38)

from which it follows that for all
$(\underline{d}^{\prime},\underline{i}^{\prime})\in\mathbb{S}_{R}$,

$\displaystyle\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\mu_{\eta,R,C}(\underline{d},\underline{i})\
Q^{C,R}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i})$
$\displaystyle=\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \mu_{\eta,R,C}(\underline{d},\underline{i})\
\lambda_{\eta,R,C}(a|\underline{d},\underline{i})\
Q_{C,R}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i},a)$
$\displaystyle=\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \nu_{\eta,R,C}(\underline{d},\underline{i},a)\
Q_{C,R}(\underline{d}^{\prime},\underline{i}^{\prime}|\underline{d},\underline{i},a)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{a=1}^{K}\
\nu_{\eta,R,C}(\underline{d}^{\prime},\underline{i}^{\prime},a)$
$\displaystyle=\mu_{\eta,R,C}(\underline{d}^{\prime},\underline{i}^{\prime}),$
(39)

thus proving the claim. In the above set of equations, $(a)$ follows from the
fact that $\nu_{\eta,R,C}$ satisfies (28).

###### Remark 1

Observe that $\nu_{\eta,R,C}$ in (33) is a mixture of two terms, one arising
from the uniform arm selection rule under maximum delay constraints (the term
corresponding to $\nu_{C,R}^{\textsf{unif}}$), and the other arising from the
optimal solution to the finite-dimensional LP under a constraint on the delay
of each arm (the term corresponding to $\nu_{C,R}^{\star}$). A similar,
trembling hand-based mixture term appears in the works [6, 7]. While the
mixtures in [6, 7] arise from a restrictive system model that forces each arm
to be selected with a strictly positive probability, the mixture in (33)
ensures that each arm is selected with a strictly positive probability (except
when the delay of an arm is equal to the maximum allowed delay $R$ in which
case it is forcibly selected) without any restrictions on the system model. It
is also worth noting that the mixtures in [6, 7] give rise to a conditional
probability distribution on the arms, conditioned on the arm delays and the
last observed states (a quantity akin to
$\lambda(a|\underline{d},\underline{i}$)), whereas the mixture in (33) gives
rise to a joint probability distribution on the set
$\mathbb{S}_{R}\times\mathcal{A}$ (a quantity akin to
$\nu(\underline{d},\underline{i},a)$).

Our policy, which we call $R$-Delay-Constrained-Restless-BAI (or $R$-DCR-BAI
in short) or alternatively as $\pi^{\star}(L,\eta,R)$, is then as follows.
Here, $L>1$, $\eta\in(0,1]$ and $R\in\mathbb{N}\cap(K,\infty)$ are parameters
of the policy. As we shall see, the parameter $L$ controls the policy’s error
probability. In fact, we will see from Lemma 3 that if we set $L=1/\epsilon$,
the error probability is bounded above by $\epsilon$.  _Policy_ $R$-DCR-BAI /
$\pi^{\star}(L,\eta,R)$:
Fix $L>1$, $\eta\in(0,1]$, and $R\in\mathbb{N}\cap(K,\infty)$. Assume that
$A_{0}=1$, $A_{1}=2$, …, $A_{K-1}=K$. Let

$M_{C}^{\pi^{\star}(L,\eta,R)}(n)=\min_{C^{\prime}\in\textsf{Alt}(C)}Z_{CC^{\prime}}^{\pi^{\star}(L,\eta,R)}(n),\quad
C\in\mathcal{C}.$

Implement the following steps for all $n\geq K$.
(1) Compute $\bar{C}(n)\in\arg\max_{C\in\mathcal{C}}\
M_{C}^{\pi^{\star}(L,\eta,R)}(n)$. Resolve ties uniformly at random.
(2) If $M^{\pi^{\star}(L,\eta,R)}_{\bar{C}(n)}(n)\geq\log(L(K-1)(K-1)!)$, stop
and declare the index of the best arm in $\bar{C}(n)$.
(3) If $M^{\pi^{\star}(L,\eta,R)}_{\bar{C}(n)}(n)<\log(L(K-1)(K-1)!)$, select
arm $A_{n}$ according to the distribution

$P^{\pi^{\star}(L,\eta,R)}(A_{n}=a|A_{0:n-1},\bar{X}_{0:n-1})=\lambda_{\eta,R,\bar{C}(n)}(a|\underline{d}(n),\underline{i}(n)).$

In item (1) in $R$-DCR-BAI, $\bar{C}(n)$ denotes the estimate of the
underlying assignment of the TPMs based on all the controls (arm selections)
and observations seen up to time $n$. If the LLR between $\bar{C}(n)$ and its
nearest alternative assignment of the TPMs exceeds a certain threshold (i.e.,
$\geq\log(L(K-1)(K-1)!)$), then the policy is sufficiently confident that
$\bar{C}(n)$ is indeed the underlying assignment of the TPMs, and therefore
stops and declares the index of the best arm in $\bar{C}(n)$. Else, it samples
the next arm based on the value of $(\underline{d}(n),\underline{i}(n))$
according to the distribution
$\lambda_{\eta,R,\bar{C}(n)}(\cdot|\underline{d}(n),\underline{i}(n))$.

In the following section, we demonstrate that for a suitable choice of $L$,
the policy $R$-DCR-BAI achieves the desired error probability. Further,
letting $L\to\infty$, we show that the growth rate of its expected stopping
time satisfies an asymptotic upper bound that is arbitrarily close to
$1/T_{R}^{\star}(C)$ under the assignment of the TPMs $C$ for a suitable
choice of $\eta$.

##  VII Results on the Performance of Policy $R$-DCR-BAI

This section is organised as follows. In Section VII-A, we establish that for
a given $C\in\mathcal{C}$ and any $C^{\prime}\in\textsf{Alt}(C)$, the LLR
$Z_{CC^{\prime}}^{\pi}(n)$ has a strictly positive drift almost surely under
the assignment of the TPMs $C$ (Lemma 2), and therefore the policy $R$-DCR-BAI
stops in finite time almost surely. In Section VII-B, we show that $R$-DCR-BAI
satisfies any desired error probability for a suitable choice of $L$ (Lemma
3). In Section VII-C, we strengthen the result of Section VII-A by showing
that the LLR of $C$ with respect to its nearest alternative
$C^{\prime}\in\textsf{Alt}(C)$ is a certain constant that, in the limit as
$\eta\downarrow 0$, converges to $T_{R}^{\star}(C)$ (Lemma 2). In Section
VII-D, we show that the stopping time of $R$-DCR-BAI grows almost surely as
$L\to\infty$ (Lemma 4). In Section VII-E, we derive an almost sure upper bound
on the stopping time of $R$-DCR-BAI that, in the limit as $\eta\downarrow 0$,
converges to $1/T_{R}^{\star}(C)$. In Section VII-F, we show that the expected
stopping time of $R$-DCR-BAI satisfies the same upper bound as that derived in
Section VII-E. This is based on (a) showing that the family
$\\{\tau(\pi^{\star}(L,\eta,R))/\log L:L>1\\}$ is uniformly integrable, and
(b) combining the almost sure upper bound with the uniform integrability
result to obtain an upper bound in expectation. The proofs of all the results
are relegated to the appendices.

###  VII-A Strictly Positive Drift for the LLRs

Let $\pi_{\textsf{NS}}^{\star}(L,\eta,R)$ denote a version of $R$-DCR-BAI that
never stops, i.e., it does not check the second step in $R$-DCR-BAI and
continues to the last step indefinitely. We now show that under
$\pi_{\textsf{NS}}^{\star}(L,\eta,R)$, the LLRs have a strictly positive drift
as the number of rounds of arm selection $n\to\infty$.

###### Lemma 2

Fix $L>1$, $\eta\in(0,1]$, $R\in\mathbb{N}\cap(K,\infty)$, and
$C\in\mathcal{C}$. Under the assignment of the TPMs $C$ and the policy
$\pi=\pi_{\textsf{NS}}^{\star}(L,\eta,R)$,

$\liminf_{n\to\infty}\frac{Z_{CC^{\prime}}^{\pi}(n)}{n}>0\quad\text{almost
surely}\quad\text{for all }C^{\prime}\in\textsf{Alt}(C).$ (40)

###### Proof:

See Appendix C. ∎

Lemma 2 asserts that under the assignment of the TPMs $C$, we have

$\liminf_{n\to\infty}\frac{M_{C}^{\pi}(n)}{n}>0\quad\text{almost surely}$ (41)

when $\pi=\pi_{\textsf{NS}}^{\star}(L,\eta,R)$. This means that
$M_{C}^{\pi}(n)\geq\log(L(K-1)(K-1)!)$ for all $n$ large, almost surely. This
proves that $R$-DCR-BAI stops in finite time with probability $1$.

###  VII-B Desired Error Probability

In this section, we show that for an appropriate choice of the parameter $L$,
the policy $R$-DCR-BAI achieves any desired error probability.

###### Lemma 3

Fix an error probability threshold $\epsilon>0$. If $L=1/\epsilon$, then
$\pi^{\star}(L,\eta,R)\in\Pi(\epsilon)$ for all $\eta\in(0,1]$ and
$R\in\mathbb{N}\cap(K,\infty)$. Here, $\Pi(\epsilon)$ is as defined in (5).

###### Proof:

The proof uses the fact that the policy stops in finite time almost surely,
and is given in Appendix D. ∎

###  VII-C The Correct Asymptotic Drift of the LLRs

In this section, we strengthen the result of Section VII-A by showing that
under the constraint that the delay of each arm is at most $R$, the asymptotic
drift of the LLRs is arbitrarily close to $T_{R}^{\star}(C)$.

###### Proposition 2

Fix $L>1$, $\eta\in(0,1]$, $R\in\mathbb{N}\cap(K,\infty)$, and
$C\in\mathcal{C}$. Consider the policy
$\pi=\pi_{\textsf{NS}}^{\star}(L,\eta,R)$. Under the assignment of the TPMs
$C$, for all $C^{\prime}\in\textsf{Alt}(C)$,

$\lim_{n\to\infty}\frac{Z_{CC^{\prime}}^{\pi}(n)}{n}=\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \nu_{\eta,R,C}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))\quad\text{almost
surely}.$ (42)

Consequently, it follows that

$\displaystyle\lim_{n\to\infty}\frac{M_{C}^{\pi}(n)}{n}=\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{\eta,R,C}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))\quad\text{almost
surely}.$ (43)

###### Proof:

See Appendix E. ∎

From (33), we note that the right hand side of (43) may be lower bounded by

$\displaystyle\eta\ \min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))$
$\displaystyle\hskip 28.45274pt+(1-\eta)\ \min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{C,R}^{\star}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))$
$\displaystyle=\eta\ \min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))+(1-\eta)\
T_{R}^{\star}(C),$ (44)

which, as $\eta\downarrow 0$, converges to $T_{R}^{\star}(C)$. Using this
observation, we shall show later that our policy achieves an upper bound of
$1/T_{R}^{\star}(C)$ in the limit as $\eta\downarrow 0$.

###  VII-D Asymptotic Growth of Stopping Time

In this section, we demonstrate that $\tau(\pi^{\star}(L,\eta,R))$ grows as
$L\to\infty$ (equivalently $\epsilon\downarrow 0$).

###### Lemma 4

Fix $\eta\in(0,1]$, $R\in\mathbb{N}\cap(K,\infty)$, and $C\in\mathcal{C}$.
Under the assignment of the TPMs $C$,

$\liminf_{L\to\infty}\tau(\pi^{\star}(L,\eta,R))=\infty\text{ almost surely.}$
(45)

###### Proof:

See Appendix F. ∎

As a consequence of Lemma 4, we get that under the assignment of the TPMs $C$
and under $\pi=\pi^{\star}(L,\eta,R)$,

$\lim_{L\to\infty}\
\frac{M_{C}^{\pi}(\tau(\pi))}{\tau(\pi)}=\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \nu_{\eta,R,C}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))\quad\text{almost
surely}.$ (46)

###  VII-E Almost Sure Asymptotic Upper Bound on the Stopping Time

In this section, we derive an almost sure asymptotic upper bound on the
stopping time of $R$-DCR-BAI as $L\to\infty$, and show that this upper bound
is arbitrarily close to $1/T_{R}^{\star}(C)$ under the assignment of the TPMs
$C$. In the next section, we combine the almost sure upper bound of this
section with a certain uniform integrability result to claim that the expected
stopping time of $R$-DCR-BAI satisfies the same upper bound as that derived in
this section.

###### Lemma 5

Fix $\eta\in(0,1]$, $R\in\mathbb{N}\cap(K,\infty)$, and $C\in\mathcal{C}$.
Under the assignment of the TPMs $C$ and under the policy
$\pi=\pi^{*}(L,\eta,R)$,

$\displaystyle\limsup_{L\to\infty}\,\frac{\tau(\pi)}{\log L}$
$\displaystyle\leq\frac{1}{\min\limits_{C^{\prime}\in\textsf{Alt}(C)}\
\sum\limits_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum\limits_{a=1}^{K}\ \nu_{\eta,R,C}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))}$
$\displaystyle\leq\frac{1}{\eta\,T_{R}^{\textsf{unif}}(C)+(1-\eta)\
T_{R}^{\star}(C)}\quad\text{almost surely},$ (47)

where

$T_{R}^{\textsf{unif}}(C)\coloneqq\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a})).$

###### Proof:

See Appendix G ∎

###  VII-F Asymptotic Upper Bound on the Expected Stopping Time

In this section, we show that the expected value of the stopping time of
policy $R$-DCR-BAI satisfies an asymptotic upper bound that matches with the
right hand side of (47) as $L\to\infty$.

###### Proposition 3

Fix $\eta\in(0,1]$, $R\in\mathbb{N}\cap(K,\infty)$, and $C\in\mathcal{C}$.
Under the assignment of the TPMs $C$, the policy $R$-DCR-BAI satisfies

$\limsup_{L\to\infty}\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log
L}\leq\frac{1}{\eta\,T_{R}^{\textsf{unif}}(C)+(1-\eta)\ T_{R}^{\star}(C)}.$
(48)

###### Proof:

In the proof, which we provide in Appendix H, we first show that the family
$\\{\tau(\pi)/\log L:L>1\\}$ is uniformly integrable. Combining (47) with the
uniform integrability result yields (48). ∎

##  VIII A Key Monotonicity Property and the Main Result

In this section, we establish a key monotonicity property for
$T_{R}^{\star}(C)$, which is that $T_{R}^{\star}(C)\leq
T_{R^{\prime}}^{\star}(C)$ for all $R<R^{\prime}$. This, combined together
with the fact that $T_{R}^{\star}(C)\leq T^{\star}(C)$, implies that
$\lim_{R\to\infty}\ T_{R}^{\star}(C)$ exists. We conclude the section by
stating the main result of the paper.

###  VIII-A A Key Monotonicity Property

The below result asserts that $T_{R}^{\star}(C)$ is monotonically non-
decreasing as $R$ increases.

###### Lemma 6

$T_{R}^{\star}(C)\leq T_{R+1}^{\star}(C)$ for all
$R\in\mathbb{N}\cap(K,\infty)$.

###### Proof:

Fix $R\in\mathbb{N}\cap(K,\infty)$. The key idea behind the proof is to note
that (a) $\mathbb{S}_{R}\subset\mathbb{S}_{R+1}$, and (b) any $\nu$ that
satisfies (28)-(31) with parameter $R$ also satisfies them with parameter
$R+1$. The details follow. Let $\nu_{C,R}^{\star}$ and $\nu_{C,R+1}^{\star}$
be the optimal state-action measures when the arm delays are constrained to no
more than $R$ and $R+1$ respectively. Note that both $\nu_{C,R}^{\star}$ and
$\nu_{C,R+1}^{\star}$ satisfy (28)-(31) (with the corresponding parameters $R$
and $R+1$). Further, $\nu_{C,R}^{\star}$ satisfies (28)-(31) with parameter
$R+1$. Define $\widetilde{\nu}_{C,R+1}$ as

$\displaystyle\widetilde{\nu}_{C,R+1}(\underline{d},\underline{i},a)\coloneqq\begin{cases}\nu_{C,R}^{\star}(\underline{d},\underline{i},a)&\text{
if }(\underline{d},\underline{i})\in\mathbb{S}_{R},\\\ 0,&\text{
otherwise}.\\\ \end{cases}$

Clearly, $\widetilde{\nu}_{C,R+1}$ satisfies (28)-(31) with parameter $R+1$.
We therefore have

$\displaystyle T_{R+1}^{\star}(C)$
$\displaystyle=\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R+1}}\ \sum_{a=1}^{K}\
\nu_{C,R+1}^{\star}(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R+1}}\ \sum_{a=1}^{K}\
\widetilde{\nu}_{C,R+1}(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))$
$\displaystyle=\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\widetilde{\nu}_{C,R+1}(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))$
$\displaystyle=\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
{\nu}_{C,R}^{\star}(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))$
$\displaystyle=T_{R}^{\star}(C),$

thus establishing the desired result. ∎

Lemma 6, in conjunction with the observation that $T_{R}^{\star}(C)\leq
T^{\star}(C)$ for all $R$, implies that $\lim_{R\to\infty}T_{R}^{\star}(C)$
exists and $\lim_{R\to\infty}T_{R}^{\star}(C)\leq T^{\star}(C)$. The question
of whether this inequality is an equality seems difficult to prove, and is
discussed in the next section.

###  VIII-B Main Result

We are now ready to state the main result of the paper.

###### Theorem 4

Consider a multi-armed bandit with $K\geq 2$ arms in which each arm is a time
homogeneous and ergodic discrete-time Markov process on the finite state space
$\mathcal{S}$. Given TPMs $P_{1},\ldots,P_{K}$ and a permutation
$\sigma:\\{1,\ldots,K\\}\to\\{1,\ldots,K\\}$, let
$C=(P_{\sigma(1)},\ldots,P_{\sigma(K)})$ be the underlying assignment of the
TPMs where $P_{\sigma(a)}$ denotes the TPM of arm $a$. The growth rate of the
expected time required to find the best arm in $C$ satisfies the lower bound

$\displaystyle\liminf_{\epsilon\downarrow
0}\inf_{\pi\in\Pi(\epsilon)}\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log(1/\epsilon)}\geq\frac{1}{T^{\star}(C)}.$
(49)

Further, given any $\epsilon>0$, the policy
$\pi^{\star}(1/\epsilon,\eta,R)\in\Pi(\epsilon)$ for all $\eta\in(0,1]$ and
$R\in\mathbb{N}\cap(K,\infty)$. Additionally,

$\displaystyle\limsup_{R\to\infty}\ \limsup_{\eta\downarrow 0}\
\limsup_{L\to\infty}\
\frac{\mathbb{E}_{C}^{\pi^{\star}(L,\eta,R)}[\tau(\pi^{\star}(L,\eta,R))]}{\log
L}\leq\frac{1}{\lim_{R\to\infty}\ T_{R}^{\star}(C)},$ (50)

thereby yielding

$\displaystyle\frac{1}{T^{\star}(C)}$
$\displaystyle\leq\liminf_{\epsilon\downarrow
0}\inf_{\pi\in\Pi(\epsilon)}\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log(1/\epsilon)}$
$\displaystyle\leq\limsup_{\epsilon\downarrow
0}\inf_{\pi\in\Pi(\epsilon)}\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log(1/\epsilon)}$
$\displaystyle\leq\limsup_{R\to\infty}\ \limsup_{\eta\downarrow 0}\
\limsup_{L\to\infty}\
\frac{\mathbb{E}_{C}^{\pi^{\star}(L,\eta,R)}[\tau(\pi^{\star}(L,\eta,R))]}{\log
L}\leq\frac{1}{\lim_{R\to\infty}\ T_{R}^{\star}(C)}.$ (51)

Thus, the lower bound on the growth rate of the expected stopping time is
$1/T^{\star}(C)$, and the upper bound is $1/(\lim_{R\to\infty}\
T_{R}^{\star}(C))$.

###### Proof:

The asymptotic lower bound in (49) follows from Proposition 1. From Lemma 3,
we know that for any $\epsilon>0$, the policy
$\pi^{\star}(1/\epsilon,\eta,R)\in\Pi(\epsilon)$ for all $\eta\in(0,1]$ and
$R\in\mathbb{N}\cap(K,\infty)$. Therefore, it follows that

$\inf_{\pi\in\Pi(\epsilon)}\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log\left(1/\epsilon\right)}\leq\frac{\mathbb{E}^{\pi^{\star}(1/\epsilon,\eta,R)}[\tau(\pi^{\star}(1/\epsilon,\eta,R))]}{\log(1/\epsilon)}.$
(52)

Fixing $\eta$, $R$, and letting $\epsilon\downarrow 0$ (or equivalently,
substituting $L=1/\epsilon$ and letting $L\to\infty$) in (52), and using the
upper bound in (48), we get

$\displaystyle\limsup_{\epsilon\downarrow
0}\inf_{\pi\in\Pi(\epsilon)}\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log(1/\epsilon)}\leq\limsup_{L\to\infty}\frac{\mathbb{E}_{C}^{\pi^{\star}(L,\eta,R)}[\tau(\pi^{\star}(L,\eta,R))]}{\log
L}\leq\frac{1}{\eta\ T_{R}^{\textsf{unif}}(C)+(1-\eta)\ T_{R}^{\star}(C)}.$
(53)

Letting $\eta\downarrow 0$ in (53) and noting that the leftmost term in (53)
does not depend on $\eta$, we get

$\displaystyle\limsup_{\epsilon\downarrow
0}\inf_{\pi\in\Pi(\epsilon)}\frac{\mathbb{E}_{C}^{\pi}[\tau(\pi)]}{\log(1/\epsilon)}\leq\limsup_{\eta\downarrow
0}\
\limsup_{L\to\infty}\frac{\mathbb{E}_{C}^{\pi^{\star}(L,\eta,R)}[\tau(\pi^{\star}(L,\eta,R))]}{\log
L}\leq\frac{1}{T_{R}^{\star}(C)}.$ (54)

Finally, letting $R\to\infty$ in (54), we arrive at (51). ∎

##  IX On the Convergence of $T_{R}^{\star}(C)$ to $T^{\star}(C)$ as
$R\to\infty$

Recall that $T^{\star}(C)$ is the optimal value of the infinite-dimensional LP
in (21), where the supremum in (21) is over all $\nu$ satisfying (22)-(24),
and $T_{R}^{\star}(C)$ is the optimal value of the finite-dimensional LP in
(27) that arises when the the delay of each arm is constrained to be no more
than $R$. From our exposition in Section VIII-A, we know that
$\lim_{R\to\infty}T_{R}^{\star}(C)\leq T^{\star}(C)$. Showing that, in
general, this inequality is an equality appears to be difficult. In this
section, we show that in the special case when the arm TPMs
$P_{1},\ldots,P_{K}$ have identical rows, which is akin to obtaining i.i.d.
observations from the arms, we have
$\lim_{R\to\infty}T_{R}^{\star}(C)=T^{\star}(C)$, thus leading to matching
upper and lower bounds in this special setting.

Assume that the TPMs $P_{1},\ldots,P_{K}$ have identical rows, and suppose
that $\mu_{1},\ldots,\mu_{K}$ are the unique stationary distributions
associated with $P_{1},\ldots,P_{K}$ respectively. Then, by the convergence
result [27, Theorem 4.9] for finite-state Markov processes, each row of
$P_{k}$ must be equal to $\mu_{k}$, $k=1,\ldots,K$. In this special setting,
the below result states that $T_{R}^{\star}(C)=T^{\star}(C)$ for all
$R\in\mathbb{N}\cap(K,\infty)$, and therefore
$\lim_{R\to\infty}T_{R}^{\star}(C)=T^{\star}(C)$.

###### Lemma 7

Suppose each row of $P_{k}$ is equal to $\mu_{k}$, $k=1,\ldots,K$. In this
special setting, $T^{\star}(C)=T_{R}^{\star}(C)$ for all
$R\in\mathbb{N}\cap(K,\infty)$. Consequently,
$\lim_{R\to\infty}T_{R}^{\star}(C)=T^{\star}(C)$.

###### Proof:

The proof uses the key idea that for a given $C\in\mathcal{C}$ and for all
$d\in\mathbb{N}$, $i\in\mathcal{S}$, and $C^{\prime}\in\textsf{Alt}(C)$,

$D_{\textsf{KL}}((P_{C}^{a})^{d}(\cdot|i)\|(P_{C^{\prime}}^{a})^{d}(\cdot|i))=D_{\textsf{KL}}(\mu_{C}^{a}\|\mu_{C^{\prime}}^{a}),$

where $\mu_{C}^{a}$ denotes the stationary distribution associated with the
TPM $P_{C}^{a}$. The complete proof of Lemma 7 is given in Appendix I. ∎

As a consequence of Lemma 7, the common expressions for $T^{\star}(C)$ and
$T_{R}^{\star}(C)$ for all $R\in\mathbb{N}\cap(K,\infty)$ specialise to the
lower bounds of [5, 3] for the case when the i.i.d. observations from each arm
come from a finite alphabet, thus enabling us to recover the results of [5,
3]. For general arm TPMs with non-identical rows, we leave open the question
of whether $\lim_{R\to\infty}T_{R}^{\star}(C)$ equals $T^{\star}(C)$ for
future study.

##  X Concluding Remarks and Discussion

  1. 1.

We studied the problem of finding the best arm in a restless Markov multi-
armed bandit as quickly as possible, subject to an upper bound on the error
probability. For this optimal stopping problem, we showed that under the
problem instance $C$, the expected time required to find the best arm with an
error probability no more than $\epsilon$ is lower bounded by
$\log(1/\epsilon)/T^{\star}(C)$ in the limit as $\epsilon\downarrow 0$
(converse). Here, $T^{\star}(C)$ is a problem-instance dependent constant that
captures the hardness of the problem. We also devised a policy that, for an
input parameter $R\in\mathbb{N}\cap(K,\infty)$, forcibly selects an arm which
has not been selected for $R$ consecutive time instants, and finds the best
arm in at most $\log(1/\epsilon)/T_{R}^{\star}(C)$ time instants on the
average as $\epsilon\downarrow 0$ (achievability).

  2. 2.

We showed that $T_{R}^{\star}(C)$ is monotonically non-decreasing in $R$, and
that $\lim_{R\to\infty}T_{R}^{\star}(C)\leq T^{\star}(C)$. Showing that, in
general, this inequality is an equality appears to be a difficult problem and
remains open. Notwithstanding this, we showed that in the special case when
the TPM of each arm has identical rows (which is akin to obtaining i.i.d.
observations from each arm), the above inequality is indeed an equality. We
were thus able to recover the results of [5, 3] for the case of arms with a
common, finite alphabet.

  3. 3.

The trembling hand-based policy of [6] is not practically implementable
because it operates on the countable set $\mathbb{S}$ of all delays and last
observed states which cannot be handled on a machine with finite-size memory.
However, for any given $R\in\mathbb{N}\cap(K,\infty)$, our policy operates on
the finite set $\mathbb{S}_{R}$ which can easily be stored in finite-size
memory on a machine, thereby making it practically implementable.

  4. 4.

In our achievability analysis, we assumed that the initial state of each arm
follows a certain distribution $\phi$ that is independent of the underlying
assignment of the TPMs. However, this may not actually be the case. For
instance, if the Markov process of each arm has evolved for a sufficiently
long time and reached stationarity before the decision entity begins sampling
the arms at $t=0$, then the initial state of each arm follows the arm’s
stationary distribution. This will lead to a mismatch between the LLR
expressions in our work (resulting from $\phi$) and the actual LLR expressions
(resulting from the stationary distributions). Suppose
$\bar{Z}_{CC^{\prime}}^{\pi}(n)$ denotes the analogue of (18) resulting from
using the stationary distributions in place of $\phi$. Then, fixing
$C\in\mathcal{C}$, it can be shown that

$\lim_{n\to\infty}\frac{Z_{CC^{\prime}}^{\pi}(n)}{n}-\frac{\bar{Z}_{CC^{\prime}}^{\pi}(n)}{n}=0.$

That is, the asymptotic drift of $Z_{CC^{\prime}}^{\pi}(n)$ is identical to
that of $\bar{Z}_{CC^{\prime}}^{\pi}(n)$, and therefore the assumption
$X_{0}^{a}\sim\phi$ does not affect the asymptotic analysis in any way.

  5. 5.

It will be interesting to extend the results of our paper to the case when the
arm TPMs $P_{1},\ldots,P_{K}$ are not known to the decision entity beforehand.
The difficulty here is that for any given $C\in\mathcal{C}$, the set of
alternatives $\textsf{Alt}(C)$ is uncountably infinite. Also, the arm TPMs
they must be estimated on-the-fly using the observations from the arms. In
this case, showing that the TPM estimates converge to their true values is the
key challenge. It will be interesting to explore these issues further.

  6. 6.

The function $f$ appearing in the definition of the best arm in (3), also
appears implicitly in the analyses of the lower and the upper bounds wherever
one evaluates $\textsf{Alt}(C)$ for any given $C$. A more realistic setting
where we anticipate that $f$ will appear explicitly in the analyses of the
lower and the upper bounds is one in which the decision entity only observes
$Y_{t}^{a}=f(X_{t}^{a})$ and not the underlying state $X_{t}^{a}$ of arm $a$
at time $t$, i.e., the arms yield hidden Markov observations. More generally,
suppose that $Y_{t}^{a}|X_{t}^{a}\sim P^{a}(\cdot|X_{t}^{a})$ for some
conditional probability distribution $P^{a}$, $a\in\mathcal{A}$. Because
$\\{Y_{t}^{a}:t\geq 0\\}$ is not a Markov process in general, the analyses of
the lower and the upper bounds in this setting appear to be quite challenging.
It will be interesting to explore this setting in more detail.

## Acknowledgements

The authors are supported by a Singapore National Research Foundation
Fellowship (under grant number R-263-000-D02-281) and by the National Research
Foundation, Singapore under its AI Singapore Programme (AISG Award No:
AISG2-RP-2020-018).

##  Appendix A Proof of Proposition 1

It suffices to prove (20) for all $\pi$ such that
$\mathbb{E}_{C}^{\pi}[\tau(\pi)]<\infty$, as (20) trivially holds when
$\mathbb{E}_{C}^{\pi}[\tau(\pi)]=\infty$. This proof is organised as follows.
In Section A-A, we derive a change-of-measure result that is the analogue of
[5, Lemma 18] for the setting of restless arms (see (56)). Using the change-
of-measure result together with [5, Lemma 19], we derive in Section A-B a
lower bound for the expected LLR in terms of the error probability. In Section
A-C, we derive an upper bound for the expected LLR in terms of the expected
stopping time (see (73)). Combining the lower bound of Section A-B and the
upper bound of Section A-C, and letting the error probability vanish, we
arrive at the lower bound (20).

###  A-A A Change-of-Measure Result for Restless Arms

The following change-of-measure result is the analogue of [5, Lemma 18] for
the setting of restless arms. The proof technique is along the lines of the
proof of [5, Lemma 18].

###### Lemma 8

Fix $C,C^{\prime}\in\mathcal{C}$. Given a policy $\pi$ with stopping time
$\tau(\pi)$ such that $P_{C}^{\pi}(\tau(\pi)<\infty)=1$,
$P_{C^{\prime}}^{\pi}(\tau(\pi)<\infty)=1$, let

$\mathcal{F}_{\tau(\pi)}\coloneqq\\{E\in\mathcal{F}:E\cap\\{\tau(\pi)=t\\}\in\mathcal{F}_{t}\text{
for all }t\geq 0\\},$ (55)

where $\\{\mathcal{F}_{t}:t\geq 0\\}$ is as defined in (4). Then,

$P_{C^{\prime}}^{\pi}(E)=\mathbb{E}_{C}^{\pi}\big{[}\mathbb{I}_{E}\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(\tau(\pi))\big{)}\big{]},\quad
E\in\mathcal{F}_{\tau(\pi)}.$ (56)

###### Proof:

We prove (56) by first demonstrating, through mathematical induction, that the
relation

$\mathbb{E}_{C^{\prime}}[g(A_{0:t},\bar{X}_{0:t})]=\mathbb{E}_{C}^{\pi}\big{[}g(A_{0:t},\bar{X}_{0:t})\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}\big{]}$
(57)

holds for all $t\geq 0$ and for all measurable functions
$g:\mathcal{A}^{t+1}\times\mathcal{S}^{t+1}\to\mathbb{R}$. Then, (56) follows
from (57) by noting that for any $E\in\mathcal{F}_{\tau(\pi)}$,

$\displaystyle P_{C^{\prime}}^{\pi}(E)$
$\displaystyle=\mathbb{E}_{C^{\prime}}^{\pi}[\mathbb{I}_{E}]$
$\displaystyle=\mathbb{E}_{C^{\prime}}^{\pi}\bigg{[}\sum_{t\geq 0}\
\mathbb{I}_{E\cap\\{\tau(\pi)=t\\}}\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{t\geq 0}\
\mathbb{E}_{C^{\prime}}^{\pi}\left[\mathbb{I}_{E\cap\\{\tau(\pi)=t\\}}\right]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{t\geq 0}\
\mathbb{E}_{C}^{\pi}\left[\mathbb{I}_{E\cap\\{\tau(\pi)=t\\}}\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}\right]$
$\displaystyle=\sum_{t\geq 0}\
\mathbb{E}_{C}^{\pi}\left[\mathbb{I}_{E\cap\\{\tau(\pi)=t\\}}\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(\tau(\pi))\big{)}\right]$
$\displaystyle=\mathbb{E}_{C}^{\pi}\left[\mathbb{I}_{E}\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(\tau(\pi))\big{)}\right],$
(58)

where $(a)$ is due to the monotone convergence theorem, and $(b)$ above
follows from (57) and the fact that $E\in\mathcal{F}_{\tau(\pi)}$ implies that
$E\cap\\{\tau(\pi)=t\\}\in\mathcal{F}_{t}$ for all $t\geq 0$.

The proof of (57) for the case $t=0$ may be obtained as follows: for any
measurable $g:\mathcal{A}\times\mathcal{S}\to\mathbb{R}$,

$\displaystyle\mathbb{E}_{C^{\prime}}^{\pi}[g(A_{0},\bar{X}_{0})]$
$\displaystyle=\sum_{a=1}^{K}\ \sum_{i\in\mathcal{S}}\ g(a,i)\
P_{C^{\prime}}^{\pi}(A_{0}=a,\bar{X}_{0}=i)$ $\displaystyle=\sum_{a=1}^{K}\
\sum_{i\in\mathcal{S}}\ g(a,i)\ P_{C^{\prime}}^{\pi}(A_{0}=a)\
P_{C^{\prime}}^{\pi}(\bar{X}_{0}=i|A_{0}=a)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{a=1}^{K}\
\sum_{i\in\mathcal{S}}\ g(a,i)\ P_{C}^{\pi}(A_{0}=a)\ \phi(i)$
$\displaystyle=\sum_{a=1}^{K}\ \sum_{i\in\mathcal{S}}\ g(a,i)\
P_{C}^{\pi}(A_{0}=a)\ P_{C}^{\pi}(X_{0}^{a}=i|A_{0}=a)$
$\displaystyle=\mathbb{E}_{C}^{\pi}[g(A_{0},\bar{X}_{0})]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathbb{E}_{C}^{\pi}\big{[}g(A_{0},\bar{X}_{0})\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(0)\big{)}\big{]},$
(59)

where in writing $(a)$, we make use of (i) the fact that
$P_{C^{\prime}}^{\pi}(A_{0}=a)=P_{C}^{\pi}(A_{0}=a)$ because the policy $\pi$
selects arms without the knowledge of the underlying assignment of the TPMs,
and (ii) the assumption that $X_{0}^{a}\sim\phi$ for all $a\in\mathcal{A}$,
where $\phi$ is a probability distribution on $\mathcal{S}$ that does not
depend on the underlying assignment of the TPMs. In writing $(b)$ above, we
make use of the observation that

$\displaystyle
Z_{CC^{\prime}}^{\pi}(0)=\log\frac{P_{C}^{\pi}(A_{0},\bar{X}_{0})}{P_{C^{\prime}}^{\pi}(A_{0},\bar{X}_{0})}=0.$
(60)

We now assume that (57) is true for some $t>0$, and show that it also true for
$t+1$. By the law of iterated expectations,
$\mathbb{E}_{C^{\prime}}^{\pi}[g(A_{0:t+1},\bar{X}_{0:t+1})]=\mathbb{E}_{C^{\prime}}^{\pi}[\mathbb{E}_{C^{\prime}}^{\pi}[g(A_{0:t+1},\bar{X}_{0:t+1})|\mathcal{F}_{t+1}]]$.
Because
$\mathbb{E}_{C^{\prime}}^{\pi}[g(A_{0:t+1},\bar{X}_{0:t+1})|\mathcal{F}_{t+1}]$
is a measurable function of $(A_{0:t},\bar{X}_{0:t})$, by the induction
hypothesis, we have

$\displaystyle\mathbb{E}_{C^{\prime}}^{\pi}[g(A_{0:t+1},\bar{X}_{0:t+1})|\mathcal{F}_{t+1}]$
$\displaystyle=\mathbb{E}_{C}^{\pi}\big{[}\mathbb{E}_{C^{\prime}}^{\pi}[g(A_{0:t+1},\bar{X}_{0:t+1})\,\big{|}\,\mathcal{F}_{t+1}]\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}\big{]}$
$\displaystyle=\mathbb{E}_{C}^{\pi}\big{[}\mathbb{E}_{C^{\prime}}^{\pi}\big{[}g(A_{0:t+1},\bar{X}_{0:t+1})\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \mathcal{F}_{t+1}\big{]}\big{]},$ (61)

where the last line above follows by noting that $Z_{CC^{\prime}}^{\pi}(t)$ is
measurable with respect to $\mathcal{F}_{t+1}$. We now note that

$\displaystyle\mathbb{E}_{C^{\prime}}^{\pi}\big{[}g(A_{0:t+1},\bar{X}_{0:t+1})\
\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \mathcal{F}_{t+1}\big{]}$
$\displaystyle=\sum_{a=1}^{K}\ \sum_{i\in\mathcal{S}}\
g(A_{0:t},\bar{X}_{0:t},a,i)\
P_{C^{\prime}}^{\pi}(A_{t+1}=a|\mathcal{F}_{t+1})\
P_{C^{\prime}}^{\pi}(\bar{X}_{t+1}=i|A_{t+1}=a,\mathcal{F}_{t+1})\
\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{a=1}^{K}\
\sum_{i\in\mathcal{S}}\ g(A_{0:t},\bar{X}_{0:t},a,i)\
P_{C}^{\pi}(A_{t+1}=a|\mathcal{F}_{t+1})\
P_{C^{\prime}}^{\pi}(\bar{X}_{t+1}=i|A_{t+1}=a,\mathcal{F}_{t+1})\
\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)},$ (62)

where in writing $(a)$ above, we make use of the fact that
$P_{C^{\prime}}^{\pi}(A_{t+1}=a|\mathcal{F}_{t+1})=P_{C}^{\pi}(A_{t+1}=a|\mathcal{F}_{t+1})$
because $\pi$ selects arms without the knowledge of the underlying assignment
of the TPMs. Also, we note that

$\displaystyle
P_{C^{\prime}}^{\pi}(\bar{X}_{t+1}=i|A_{t+1}=a,\mathcal{F}_{t+1})\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}$
$\displaystyle=\frac{P_{C^{\prime}}^{\pi}(\bar{X}_{t+1}=i|A_{t+1}=a,\mathcal{F}_{t+1})}{P_{C}^{\pi}(\bar{X}_{t+1}=i|A_{t+1}=a,\mathcal{F}_{t+1})}\
\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}\
P_{C}^{\pi}(\bar{X}_{t+1}=i|A_{t+1}=a,\mathcal{F}_{t+1})$
$\displaystyle=\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t+1)\big{)}\,P_{C}^{\pi}(\bar{X}_{t+1}=i|A_{t+1}=a,\mathcal{F}_{t+1}).$
(63)

Substituting (63) in (62) and simplifying, we get

$\displaystyle\mathbb{E}_{C^{\prime}}^{\pi}\big{[}g(A_{0:t+1},\bar{X}_{0:t+1})\
\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t)\big{)}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \mathcal{F}_{t+1}\big{]}$
$\displaystyle=\sum_{a=1}^{K}\ \sum_{i\in\mathcal{S}}\
g(A_{0:t},\bar{X}_{0:t},a,i)\ P_{C}^{\pi}(A_{t+1}=a|\mathcal{F}_{t+1})\
P_{C}^{\pi}(\bar{X}_{t+1}=i|A_{t+1}=a,\mathcal{F}_{t+1})\
\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t+1)\big{)}$
$\displaystyle=\mathbb{E}_{C}^{\pi}\big{[}g(A_{0:t+1},\bar{X}_{0:t+1})\
\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t+1)\big{)}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \mathcal{F}_{t+1}\big{]}.$ (64)

Substituting (64) in (61), we get

$\displaystyle\mathbb{E}_{C^{\prime}}^{\pi}[g(A_{0:t+1},\bar{X}_{0:t+1})|\mathcal{F}_{t+1}]$
$\displaystyle=\mathbb{E}_{C}^{\pi}\big{[}\mathbb{E}_{C}^{\pi}\big{[}g(A_{0:t+1},\bar{X}_{0:t+1})\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t+1)\big{)}\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ \mathcal{F}_{t+1}\big{]}\big{]}$
$\displaystyle=\mathbb{E}_{C}^{\pi}\big{[}g(A_{0:t+1},\bar{X}_{0:t+1})\,\exp\big{(}-Z_{CC^{\prime}}^{\pi}(t+1)\big{)}\big{]}.$
(65)

Taking $\mathbb{E}_{C^{\prime}}^{\pi}[\cdot]$ on both sides of (65), we get
the desired result. ∎

###  A-B A Lower Bound for
$\mathbb{E}_{C}^{\pi}[Z_{CC^{\prime}}^{\pi}(\tau(\pi))]$ when
$\pi\in\Pi(\epsilon)$

We note the following lower bound on the expected LLR. We omit the proof as it
follows directly from the proof of [5, Lemma 19].

###### Lemma 9

Fix $C\in\mathcal{C}$, $C^{\prime}\in\textsf{Alt}(C)$, and $\pi$ such that
$P_{C}^{\pi}(\tau(\pi)<\infty)=1$, $P_{C^{\prime}}^{\pi}(\tau(\pi)<\infty)=1$.
Then,

  1. 1.

$P_{C}^{\pi}$ and $P_{C^{\prime}}^{\pi}$ are mutually absolutely continuous,
and

  2. 2.

for all $E\in\mathcal{F}_{\tau(\pi)}$ such that $P_{C}^{\pi}(E)>0$,
$P_{C^{\prime}}^{\pi}(E)>0$,

$\mathbb{E}_{C}^{\pi}[Z_{CC^{\prime}}^{\pi}(\tau(\pi))]\geq
d(P_{C}^{\pi}(E),P_{C^{\prime}}^{\pi}(E)),$ (66)

where $d(x,y)$ denotes the relative entropy between two Bernoulli
distributions with parameters $x$ and $y$.

Fix $\epsilon>0$. Recall the set $\Pi(\epsilon)$ in (5). A direct consequence
of Lemma 9 is that for any $\pi\in\Pi(\epsilon)$, setting
$E=\\{\omega\in\Omega:\theta(\tau(\pi))=a^{\star}(C)\\}$, where $a^{\star}(C)$
is the index of the best arm in $C$, noting that $P_{C}^{\pi}(E)\geq
1-\epsilon$, $P_{C^{\prime}}^{\pi}(E)\leq\epsilon$ for all
$C^{\prime}\in\textsf{Alt}(C)$, and using the fact that $x\mapsto d(x,y)$ is
monotone increasing for $x<y$ and the $y\mapsto d(x,y)$ is monotone decreasing
for any fixed $x$, we get

$\mathbb{E}_{C}^{\pi}[Z_{CC^{\prime}}^{\pi}(\tau(\pi))]\geq
d(\epsilon,1-\epsilon)$ (67)

for all $C^{\prime}\in\textsf{Alt}(C)$. Thus, it follows that
$\min_{C^{\prime}\in\textsf{Alt}(C)}\
\mathbb{E}_{C}^{\pi}[Z_{CC^{\prime}}^{\pi}(\tau(\pi))]\geq
d(\epsilon,1-\epsilon)$ whenever $\pi\in\Pi(\epsilon)$.

###  A-C An Upper Bound for
$\mathbb{E}_{C}^{\pi}[Z_{CC^{\prime}}^{\pi}(\tau(\pi))]$ in terms of
$\mathbb{E}_{C}^{\pi}[\tau(\pi)]$

We first note the following result.

###### Lemma 10

Fix $\pi$ and $C\in\mathcal{C}$. For all
$(\underline{d},\underline{i})\in\mathbb{S}$, $a\in\mathcal{A}$, and
$j\in\mathcal{S}$,

$\mathbb{E}_{C}^{\pi}\big{[}N(\tau(\pi),\underline{d},\underline{i},a,j)\big{]}=(P_{C}^{a})^{d_{a}}(j|i_{a})\
\mathbb{E}_{C}^{\pi}\big{[}N(\tau(\pi),\underline{d},\underline{i},a)\big{]}.$
(68)

###### Proof:

We note that

$\displaystyle\mathbb{E}_{C}^{\pi}[\mathbb{E}_{C}^{\pi}[N(\tau(\pi),\underline{d},\underline{i},a,j)|X_{a-1}^{a}]|\tau(\pi)]$
$\displaystyle=\mathbb{E}_{C}^{\pi}\bigg{[}\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{t=K}^{\tau(\pi)}1_{\\{\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},A_{t}=a,X_{t}^{a}=j\\}}\bigg{|}X_{a-1}^{a}\bigg{]}\bigg{|}\tau(\pi)\bigg{]}$
$\displaystyle=\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{t=K}^{\tau(\pi)}P_{C}^{\pi}(\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},A_{t}=a,X_{t}^{a}=j|X_{a-1}^{a})\,\bigg{|}\tau(\pi)\bigg{]}.$
(69)

For each $t$ in the range of the summation in (69), the conditional
probability term for $t$ may be expressed as

$\displaystyle
P_{C}^{\pi}(\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},A_{t}=a,X_{t}^{a}=j|X_{a-1}^{a})$
$\displaystyle=P_{C}^{\pi}(\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},A_{t}=a|X_{a-1}^{a})\cdot
P_{C}^{\pi}(X_{t}^{a}=j|A_{t}=a,\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},X_{a-1}^{a})$
$\displaystyle=P_{C}^{\pi}(\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},A_{t}=a|X_{a-1}^{a})\cdot(P_{C}^{a})^{d_{a}}(j|i_{a}).$
(70)

Plugging (70) back in (69) and taking $\mathbb{E}_{C}^{\pi}[\cdot]$ on both
sides of (69), we arrive at (68). ∎

From (18), we note that for all $C^{\prime}\in\textsf{Alt}(C)$,

$\displaystyle\mathbb{E}_{C}^{\pi}[Z_{CC^{\prime}}^{\pi}(\tau(\pi))]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}+\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\
N(\tau(\pi),\underline{d},\underline{i},a,j)\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}\bigg{]}$
$\displaystyle=\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}+\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\
\mathbb{E}_{C}^{\pi}\big{[}N(\tau(\pi),\underline{d},\underline{i},a,j)\big{]}\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}+\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\
\mathbb{E}_{C}^{\pi}\big{[}N(\tau(\pi),\underline{d},\underline{i},a)\big{]}\
(P_{C}^{a})^{d_{a}}(j|i_{a})\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}$
$\displaystyle=\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}+\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\
\sum_{a=1}^{K}\
\mathbb{E}_{C}^{\pi}\big{[}N(\tau(\pi),\underline{d},\underline{i},a)\big{]}\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})).$
(71)

In the above chain of equations, $(a)$ follows from the dominated convergence
theorem (noting that each row of $(P_{C}^{a})^{d}$ is mutually absolutely
continuous with respect to the corresponding row of $(P_{C^{\prime}}^{a})^{d}$
for all $d\geq 1$), and $(b)$ follows from Lemma 10. Continuing with (71), we
have

$\displaystyle\mathbb{E}_{C}^{\pi}[Z_{CC^{\prime}}^{\pi}(\tau(\pi))]\leq\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{1}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}$ $\displaystyle\hskip
85.35826pt+\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\ \sum_{a=1}^{K}\
\mathbb{E}_{C}^{\pi}\big{[}N(\tau(\pi),\underline{d},\underline{i},a)\big{]}\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a}))$
$\displaystyle\leq\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{1}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}$ $\displaystyle\hskip
42.67912pt+(\mathbb{E}_{C}^{\pi}[\tau(\pi)-K+1])\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\ \sum_{a=1}^{K}\
\frac{\mathbb{E}_{C}^{\pi}\big{[}N(\tau(\pi),\underline{d},\underline{i},a)\big{]}}{\mathbb{E}_{C}^{\pi}[\tau(\pi)-K+1]}\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})),$
(72)

for all $C^{\prime}\in\textsf{Alt}(C)$, from which it follows that

$\displaystyle\min_{C^{\prime}\in\textsf{Alt}(C)}\
\mathbb{E}_{C}^{\pi}[Z_{CC^{\prime}}^{\pi}(\tau(\pi))]\leq\min_{C^{\prime}\in\textsf{Alt}(C)}\
\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{1}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}$ $\displaystyle\hskip
28.45274pt+(\mathbb{E}_{C}^{\pi}[\tau(\pi)-K+1])\
\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\ \sum_{a=1}^{K}\
\frac{\mathbb{E}_{C}^{\pi}\big{[}N(\tau(\pi),\underline{d},\underline{i},a)\big{]}}{\mathbb{E}_{C}^{\pi}[\tau(\pi)-K+1]}\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a}))$
$\displaystyle\leq\min_{C^{\prime}\in\textsf{Alt}(C)}\
\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{1}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}$ $\displaystyle\hskip
28.45274pt+(\mathbb{E}_{C}^{\pi}[\tau(\pi)-K+1])\ \bigg{\\{}\sup_{\nu}\
\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}}\ \sum_{a=1}^{K}\
\nu(\underline{d},\underline{i},a)\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a}))\bigg{\\}},$
(73)

where the supremum in (73) is over all $\nu$ that satisfy (22)-(23). The
expression within braces in (73) is $T^{\star}(C)$.

###  A-D The Final Steps

Combining the results of Sections A-B and A-C, we get

$\displaystyle d(\epsilon,1-\epsilon)\leq\min_{C^{\prime}\in\textsf{Alt}(C)}\
\mathbb{E}_{C}^{\pi}\bigg{[}\sum_{a=1}^{K}\
\log\frac{1}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}\bigg{]}+(\mathbb{E}_{C}^{\pi}[\tau(\pi)-K+1])\
T^{\star}(C).$ (74)

Noting that (a) $d(\epsilon,1-\epsilon)/\log(1/\epsilon)\to 1$ as
$\epsilon\downarrow 0$, and (b) the first term on the right hand side of (74)
is bounded from above, by dividing (74) throughout by $d(\epsilon,1-\epsilon)$
and letting $\epsilon\downarrow 0$, we arrive at the lower bound (20).

##  Appendix B Proof of Lemma 1

Fix an assignment of the TPMs $C\in\mathcal{C}$. In this proof, we establish
that under the policy $\pi_{R}^{\textsf{unif}}$, the process
$\\{(\underline{d}(t),\underline{i}(t)):\ t\geq K\\}$ is irreducible,
aperiodic, positive recurrent, and therefore ergodic.

###### Proof:

Consider any two states
$(\underline{d},\underline{i}),(\underline{d}^{\prime},\underline{i}^{\prime})\in\mathbb{S}_{R}$,
and suppose that the process $\\{(\underline{d}(t),\underline{i}(t)):t\geq
K\\}$ is in the state $(\underline{d},\underline{i})$ at time $t=T_{0}$. We
now demonstrate that there exists an integer $N$ (possibly depending on
$(\underline{d},\underline{i})$ and
$(\underline{d}^{\prime},\underline{i}^{\prime})$) such that

$P_{C}^{\pi_{R}^{\textsf{unif}}}(\underline{d}(T_{0}+N)=\underline{d}^{\prime},\
\underline{i}(T_{0}+N)=\underline{i}^{\prime}|\underline{d}(T_{0})=\underline{d},\
\underline{i}(T_{0})=\underline{i})>0.$

Assume without loss of generality that $\underline{d}^{\prime}$, the vector of
arm delays in the destination state
$(\underline{d}^{\prime},\underline{i}^{\prime})$, is such that
$d_{1}^{\prime}>d_{2}^{\prime}>\cdots>d_{K}^{\prime}=1$. Noting that
$P_{1},\ldots,P_{K}$ are TPMs on the finite set $\mathcal{S}$, we use [27,
Proposition 1.7] for finite state Markov processes to deduce that there exist
integers $M_{1},\ldots,M_{K}$ such that for all $m\geq
M\coloneqq\max\\{M_{1},\ldots,M_{K}\\}$,

$P_{1}^{m}(j|i)>0,\ldots,P_{K}^{m}(j|i)>0\quad\text{ for all
}i,j\in\mathcal{S}.$ (75)

Order the components of $\underline{d}$, the vector of arm delays in the
starting state $(\underline{d},\underline{i})$, in decreasing order. Under
$\pi_{R}^{\textsf{unif}}$, consider the sequence of arm selections and
observations as follows: for a total of $M$ time instants, from $t=T_{0}$ to
$t=T_{0}+M-1$, select the arms in a round robin fashion in the decreasing
order of their component values in $\underline{d}$. At time $t=T_{0}+M$,
select arm $1$ and observe the state $i_{1}^{\prime}$ on it. Thereafter,
select arms $2,\ldots,K$ in a round robin fashion in the decreasing order of
their component values in $\underline{d}$ until time
$t=T_{0}+M+d_{1}^{\prime}-d_{2}^{\prime}-1$. At time
$t=T_{0}+M+d_{1}^{\prime}-d_{2}^{\prime}$, select arm $2$ and observe the
state $i_{2}^{\prime}$ on it. Continue the round robin sampling on arms
$3,\ldots,K$ till time $t=T_{0}+M+d_{1}^{\prime}-d_{3}^{\prime}-1$. At time
$t=T_{0}+M+d_{1}^{\prime}-d_{3}^{\prime}$, select arm $3$ and observe the
state $i_{3}^{\prime}$ on it. Continue this process till arm $K$ is selected
at time $t=T_{0}+M+d_{1}^{\prime}-1$ and the state $i_{K}^{\prime}$ is
observed on it.

Clearly, because of the round robin selection procedure, the delay of each arm
at any time is no more than $K$. Also, the above sequence of arm selections
and observations leads to the state
$(\underline{d}^{\prime},\underline{i}^{\prime})$ at time
$t=T_{0}+M+d_{1}^{\prime}$. Thus, the probability of starting from the state
$(\underline{d},\underline{i})$ and reaching the state
$(\underline{d}^{\prime},\underline{i}^{\prime})$ may be lower bounded by the
probability that the above sequence of actions and observations occur under
$\pi_{R}^{\textsf{unif}}$, which in turn may be lower bounded by

$\displaystyle\bigg{(}\frac{1}{K}\bigg{)}^{M+d_{1}^{\prime}}\cdot\left[\prod_{a=1}^{K}(P_{C}^{a})^{M+d_{a}+d_{1}^{\prime}-d_{a}^{\prime}}(i_{a}^{\prime}|i_{a})\right].$
(76)

Noting that $M\leq M+d_{1}+d_{1}^{\prime}-d_{a}^{\prime}\leq M+2R-1$, let

$\bar{\varepsilon}\coloneqq\min\Big{\\{}(P_{C}^{a})^{m}(j|i):\
i,j\in\mathcal{S},\ a\in\mathcal{A},\ M\leq m\leq M+2R-1\Big{\\}}.$ (77)

It is clear that $\bar{\varepsilon}>0$, and (76) may further be lower bounded
by

$\bigg{(}\frac{1}{K}\bigg{)}^{M+d_{1}^{\prime}}\bar{\varepsilon}^{K}>0.$ (78)

Thus, we see that the Markov process
$\\{(\underline{d}(t),\underline{i}(t):t\geq K)\\}$ is in the state
$(\underline{d}^{\prime},\underline{i}^{\prime})$ after $N=M+d_{1}^{\prime}$
time instants with a strictly positive probability. This establishes
irreducibility. ∎

###### Proof:

It suffices to show that for each
$(\underline{d},\underline{i})\in\mathbb{S}_{R}$, there exists $N$ (possibly
depending on $(\underline{d},\underline{i})$) such that the probability of the
process $\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ starting from the
state $(\underline{d},\underline{i})$ at some time $t=T_{0}$ and returning to
the state $(\underline{d},\underline{i})$ after $N$ time instants and also
after $N+1$ time instants is strictly positive. This follows directly from the
proof of irreducibility presented above by setting
$(\underline{d}^{\prime},\underline{i}^{\prime})=(\underline{d},\underline{i})$
and $N=M+d_{1}$, where $M$ is such that (75) holds for all $m\geq M$. ∎

###### Proof:

This follows from the facts that (a) $\mathbb{S}_{R}$ is finite, (b)
$\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ is irreducible under
$\pi_{R}^{\textsf{unif}}$, and (c) an irreducible Markov process evolving on a
finite state space is positive recurrent. ∎

##  Appendix C Proof of Lemma 2

This proof is organised as follows. First, we show in Section C-A that for all
$(\underline{d},\underline{i})\in\mathbb{S}_{R}$,

$\liminf_{n\to\infty}\frac{N(n,\underline{d},\underline{i})}{n}>0\quad\text{almost
surely}.$ (79)

Next, we show in Section C-B that almost surely,

$\liminf_{n\to\infty}\
\frac{N(n,\underline{d},\underline{i},a)}{n}\begin{cases}>0,&\text{if
}(\underline{d},\underline{i})\in\mathbb{S}_{R,a}\text{ or
}(\underline{d},\underline{i})\notin\bigcup_{a^{\prime}=1}^{K}\
\mathbb{S}_{R,a^{\prime}},\\\ =0,&\text{if
}(\underline{d},\underline{i})\in\mathbb{S}_{R,a^{\prime}}\text{ for some
}a^{\prime}\neq a.\end{cases}$ (80)

Using the above results, we establish (40) in Section C-C.

###  C-A Limiting Drift of $N(n,\underline{d},\underline{i})$

Let $M$ be sufficiently large so that (75) holds for all $m\geq M$. Fix an
arbitrary $(\underline{d},\underline{i})\in\mathbb{S}_{R}$, and assume without
loss of generality that $\underline{d}$ is such that
$d_{1}>d_{2}>\cdots>d_{K}=1$. Let $p_{C}(\underline{d},\underline{i})$ denote
the probability of the process $\\{(\underline{d}(t),\underline{i}(t)):t\geq
K\\}$ starting in the state $(\underline{d},\underline{i})$ and returning back
to the state $(\underline{d},\underline{i})$ under the assignment of the TPMs
$C$. Following the exposition in Appendix B, it can be shown that
$p_{C}(\underline{d},\underline{i})>0$. Now, the term
$N(n,\underline{d},\underline{i})$ may be lower bounded almost surely by the
number of visits to the state $(\underline{d},\underline{i})$ measured only at
times $t=K+M+d_{1},K+2(M+d_{1}),K+3(M+d_{1})$ and so on until time $t=n$. At
each of these time instants, the probability that the process
$\\{(\underline{d}(t),\underline{i}(t)):t\geq K\\}$ is in the state
$(\underline{d},\underline{i})$ under the assignment of the TPMs $C$ is equal
to $p_{C}(\underline{d},\underline{i})$. Thus, we have

$\displaystyle
N(n,\underline{d},\underline{i})\geq\text{Bin}\left(\frac{n-K+1}{M+d_{1}},\
p_{C}(\underline{d},\underline{i})\right)\quad\text{almost surely},$ (81)

where the notation $\text{Bin}(m,q)$ denotes a Binomial random variable with
parameters $m$ and $q$. It then follows that, almost surely,

$\displaystyle\liminf_{n\to\infty}\frac{N(n,\underline{d},\underline{i})}{n}$
$\displaystyle\geq\liminf_{n\to\infty}\frac{\text{Bin}\left(\frac{n-K+1}{M+d_{1}},\leavevmode\nobreak\
\leavevmode\nobreak\ p_{C}(\underline{d},\underline{i})\right)}{n}$
$\displaystyle=\liminf_{n\to\infty}\frac{\text{Bin}\left(\frac{n-K+1}{M+d_{1}},\
p_{C}(\underline{d},\underline{i})\right)}{\frac{n-K+1}{M+d_{1}}}\cdot\frac{n-K+1}{n}\cdot\frac{1}{M+d_{1}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{p_{C}(\underline{d},\underline{i})}{M+d_{1}}$
$\displaystyle>0,$ (82)

where $(a)$ above is due to the strong law of large numbers. This establishes
(79).

###  C-B Limiting Drift of $N(n,\underline{d},\underline{i},a)$

If $(\underline{d},\underline{i})\in\mathbb{S}_{R,a}$, then
$N(n,\underline{d},\underline{i},a)=N(n,\underline{d},\underline{i})$, and
consequently

$\liminf_{n\to\infty}\
\frac{N(n,\underline{d},\underline{i},a)}{n}=\liminf_{n\to\infty}\
\frac{N(n,\underline{d},\underline{i})}{n}>0\quad\text{almost surely}.$

If $(\underline{d},\underline{i})\in\mathbb{S}_{R,a^{\prime}}$ for some
$a^{\prime}\neq a$, then $N(n,\underline{d},\underline{i},a)=0$ for all $n\geq
K$. Thus, it remains to show (80) for
$(\underline{d},\underline{i})\notin\bigcup_{a^{\prime}=1}^{K}\
\mathbb{S}_{R,a^{\prime}}$. Fix one such arbitrary
$(\underline{d},\underline{i})$ and define

$S(n,\underline{d},\underline{i},a)\coloneqq\sum_{t=K}^{n}\Big{[}\mathbb{I}_{\\{A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}\\}}-P_{C}^{\pi}(A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}|A_{0:t-1},\bar{X}_{0:t-1})\Big{]}.$
(83)

For each $t\geq K$, because
$|\mathbb{I}_{\\{A_{t}=a,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}\\}}-P_{C}^{\pi}(A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}|A_{0:t-1},\bar{X}_{0:t-1})|\leq
2$ almost surely, and
$\mathbb{E}_{C}^{\pi}[\mathbb{I}_{\\{A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}\\}}-P_{C}^{\pi}(A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}|A_{0:t-1},\bar{X}_{0:t-1})|A_{0:t-1},\bar{X}_{0:t-1}]=0$
almost surely, the collection
$\\{\mathbb{I}_{\\{A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}\\}}-P_{C}^{\pi}(A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}|A_{0:t-1},\,\bar{X}_{0:t-1})\\}_{t\geq
K}$ is a bounded martingale difference sequence. Using the concentration
result [28, Theorem 1.2A] for bounded martingale difference sequences, and
subsequently applying the Borel–Cantelli lemma, we get that

$\frac{S(n,\underline{d},\underline{i},a)}{n}\longrightarrow 0\quad\text{as
}n\to\infty,\quad\text{almost surely}.$ (84)

This implies that for every choice of $\varepsilon>0$, there exists
$N_{\varepsilon}=N_{\varepsilon}(\underline{d},\underline{i},a)$ sufficiently
large such that

$\frac{N(n,\underline{d},\underline{i},a)}{n}\geq\frac{1}{n}\
\sum_{t=K}^{n}P_{C}^{\pi}(A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}|A_{0:t-1},\bar{X}_{0:t-1})-\varepsilon\quad\forall\
n\geq N_{\varepsilon},\text{ almost surely}.$ (85)

Now, for each $t\geq K$, under $\pi=\pi^{\star}(L,\eta,R)$,

$\displaystyle
P_{C}^{\pi}(A_{t}=a,\,\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}|A_{0:t-1},\,\bar{X}_{0:t-1})$
$\displaystyle=P_{C}^{\pi}(A_{t}=a|\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i},A_{0:t-1},\bar{X}_{0:t-1})\cdot
P_{C}^{\pi}(\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}|A_{0:t-1},\bar{X}_{0:t-1})$
$\displaystyle=\lambda_{\eta,R,\bar{C}(t)}(a|\underline{d},\underline{i})\cdot
P_{C}^{\pi}(\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}|A_{0:t-1},\bar{X}_{0:t-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{\eta\
\nu_{\bar{C}(t),R}^{\textsf{unif}}(\underline{d},\underline{i},a)+(1-\eta)\
\nu_{\bar{C}(t),R}^{\star}(\underline{d},\underline{i},a)}{\eta\
\mu_{\bar{C}(t),R}^{\textsf{unif}}(\underline{d},\underline{i})+(1-\eta)\
\sum_{a^{\prime}=1}^{K}\
\nu_{\bar{C}(t),R}^{\star}(\underline{d},\underline{i},a^{\prime})}\cdot\mathbb{I}_{\\{(\underline{d}(t)=\underline{d},\,\underline{i}(t)=\underline{i}\\}}$
$\displaystyle\geq\frac{\eta}{K}\cdot\mu_{\bar{C}(t),R}^{\textsf{unif}}(\underline{d},\underline{i})\cdot\mathbb{I}_{\\{(\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i}\\}}$
$\displaystyle\geq\frac{\eta}{K}\cdot\mu_{R}^{\textsf{min}}\cdot\mathbb{I}_{\\{(\underline{d}(t)=\underline{d},\underline{i}(t)=\underline{i}\\}},$
(86)

where in writing $(a)$ above, we use the fact that
$(\underline{d}(t),\underline{i}(t))$ is measurable with respect to the
history $(A_{0:t-1},\,\bar{X}_{0:t-1})$, and $\mu_{R}^{\textsf{min}}$ in (86)
is as defined in (37).

Plugging (86) in (85), we get

$\displaystyle\frac{N(n,\underline{d},\underline{i},a)}{n}$
$\displaystyle\geq\frac{\eta}{K}\cdot\mu_{R}^{\textsf{min}}\cdot\frac{N(n,\underline{d},\underline{i})}{n}-\varepsilon\quad\forall\leavevmode\nobreak\
n\geq N_{\varepsilon},\quad\text{almost surely}.$ (87)

Using (82) in (87), we get that

$\frac{N(n,\underline{d},\underline{i},a)}{n-K+1}\geq\frac{\eta}{K}\cdot\mu_{R}^{\textsf{min}}\cdot\frac{p_{C}(\underline{d},\underline{i})}{2(M+d_{1})}-\varepsilon$
(88)

for all $n$ large, almost surely. Setting
$\varepsilon=\frac{\eta}{2K}\cdot\mu_{R}^{\textsf{min}}\cdot\frac{p_{C}(\underline{d},\underline{i})}{2(M+d_{1})}$
establishes (80).

###  C-C Completing the Proof of Lemma 2

From (80), it follows that whenever $\liminf_{n\to\infty}\
N(n,\underline{d},\underline{i},a)/n>0$ almost surely, we may apply the
ergodic theorem to deduce that under the assignment of the TPMs $C$,

$\frac{N(n,\underline{d},\underline{i},a,j)}{N(n,\underline{d},\underline{i},a)}\longrightarrow(P_{C}^{a})^{d_{a}}(j|i_{a})\quad\text{as
}n\to\infty,\quad\text{almost surely}.$ (89)

Under the constraint that the delay of each arm is at most $R$,

$\displaystyle\frac{Z^{\pi}_{CC^{\prime}}(n)}{n}=\frac{1}{n}\
\sum_{a=1}^{K}\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}+\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\
\frac{N(n,\underline{d},\underline{i},a,j)}{n}\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}.$
(90)

The first term in (90) may be lower bounded as follows: assuming that
$X_{0}^{a}\sim\phi$ for all $a\in\mathcal{A}$, where $\phi$ is a probability
distribution on $\mathcal{S}$ that is independent of the underlying TPMs $C$
and puts a strictly positive mass on each state in $\mathcal{S}$, it follows
that

$\displaystyle\frac{1}{n}\
\sum_{a=1}^{K}\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}$
$\displaystyle\geq\frac{1}{n}\ \sum_{a=1}^{K}\log P_{C}^{\pi}(X_{a-1}^{a})$
$\displaystyle=\frac{1}{n}\ \sum_{j\in\mathcal{S}}\
\mathbb{I}_{\\{X_{a-1}^{a}=j\\}}\
\sum_{a=1}^{K}\log\left(\sum_{i\in\mathcal{S}}\ \phi(i)\
(P_{C}^{a})^{a-1}(j|i)\right).$ (91)

Because the right hand side of (91) converges to $0$ as $n\to\infty$, given
any $\varepsilon>0$, there exists $N_{1}=N_{1}(\varepsilon)$ such that

$\displaystyle\frac{1}{n}\
\sum_{a=1}^{K}\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}$
$\displaystyle\geq-\varepsilon\quad\text{for all }n\geq
N_{1},\quad\text{almost surely}$ (92)

The second term in (90) may be expressed as

$\displaystyle\sum_{(\underline{d},\underline{i})\notin\bigcup_{a^{\prime}=1}^{K}\mathbb{S}_{R,a^{\prime}}}\
\sum_{a=1}^{K}\ \frac{N(n,\underline{d},\underline{i},a,j)}{n}\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}+\sum_{a=1}^{K}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R,a}}\
\frac{N(n,\underline{d},\underline{i},a,j)}{n}\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}.$
(93)

Using the convergence in (89) and noting that
$\mathbb{S}_{R}\times\mathcal{A}$ is finite, we get that there exists
$N_{2}=N_{2}(\varepsilon)$ such that for all $n\geq N_{2}$, (93) is almost
surely lower bounded by

$\displaystyle\sum_{(\underline{d},\underline{i})\notin\bigcup_{a^{\prime}=1}^{K}\mathbb{S}_{R,a^{\prime}}}\
\sum_{a=1}^{K}\ \frac{N(n,\underline{d},\underline{i},a)}{n}\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a}))$
$\displaystyle\hskip 85.35826pt+\sum_{a=1}^{K}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R,a}}\
\frac{N(n,\underline{d},\underline{i},a)}{n}\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a}))-\varepsilon.$
(94)

Combining (92) and (93), we get that

$\displaystyle\frac{Z^{\pi}_{CC^{\prime}}(n)}{n}$
$\displaystyle\geq-2\varepsilon+\sum_{(\underline{d},\underline{i})\notin\bigcup_{a^{\prime}=1}^{K}\mathbb{S}_{R,a^{\prime}}}\
\sum_{a=1}^{K}\ \frac{N(n,\underline{d},\underline{i},a)}{n}\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a}))$
$\displaystyle\hskip 85.35826pt+\sum_{a=1}^{K}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R,a}}\
\frac{N(n,\underline{d},\underline{i},a)}{n}\
D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a}))$
(95)

for all $n\geq\max\\{N_{1},N_{2}\\}$, almost surely. Using the results in (79)
and (80), we see that the limit infimum of the last two terms in (95) is
strictly positive, almost surely. Because $\varepsilon>0$ is arbitrary, the
desired result follows.

##  Appendix D Proof of Lemma 3

The policy $\pi=\pi^{\star}(L,\eta,R)$ commits an error if one of the
following events is true:

  1. 1.

The policy does not stop in finite time.

  2. 2.

The policy stops in finite time and declares an incorrect best arm index.

The event in item $1$ above has zero probability, thanks to Lemma 2. Thus, the
probability of error of policy $\pi^{\star}(L,\eta,R)$ may be evaluated as
follows: for $C\in\mathcal{C}$, recall that $a^{\star}(C)$ is the index of the
best arm in $C$. Then, under the assignment of the TPMs $C$, the error
probability of $\pi^{\star}(L,\eta,R)$ is given by

$\displaystyle P^{\pi}_{C}(\theta(\tau(\pi))\neq a)$
$\displaystyle=P_{C}^{\pi}\bigg{(}\exists\ n\text{ and }a^{\prime}\neq a\text{
such that }\tau(\pi)=n\text{ and }\theta(n)=a^{\prime}\bigg{)}$
$\displaystyle=P_{C}^{\pi}\bigg{(}\exists\ n\text{ and
}C^{\prime}\in\textsf{Alt}(C)\text{ such that }\tau(\pi)=n\text{ and
}\theta(n)=a^{\star}(C^{\prime})\bigg{)}.$ (96)

Let
$\mathcal{R}_{a}(n)\coloneqq\\{\omega\in\Omega:\tau(\pi)(\omega)=n,\,\theta(n)(\omega)=a\\}$,
$a\in\mathcal{A}$, denote the set of all sample paths for which the policy
stops at time $n$ and declares $a$ as the index of the best arm. Clearly,
$\\{\mathcal{R}_{a}(n):a\in\mathcal{A},\ n\geq 0\\}$ is a collection of
mutually disjoint sets. Therefore, we have

$\displaystyle P_{C}^{\pi}(\theta(\tau(\pi))\neq a)$
$\displaystyle=P_{C}^{\pi}\left(\bigcup_{a^{\prime}\neq
a}\,\bigcup_{n=0}^{\infty}\mathcal{R}_{a^{\prime}}(n)\right)$
$\displaystyle=\sum_{a^{\prime}\neq a}\ \sum_{n=0}^{\infty}\
P_{C}^{\pi}(\tau(\pi)=n,\ \theta(n)=a^{\prime})$
$\displaystyle=\sum_{C^{\prime}\in\textsf{Alt}(C)}\ \sum_{n=0}^{\infty}\
P_{C}^{\pi}(\tau(\pi)=n,\ \theta(n)=a^{\star}(C^{\prime}))$
$\displaystyle=\sum_{C^{\prime}\in\textsf{Alt}(C)}\ \sum_{n=0}^{\infty}\
\int_{\mathcal{R}_{a^{\star}(C^{\prime})}(n)}\,dP_{C}^{\pi}(\omega)$
$\displaystyle=\sum_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{n=0}^{\infty}\leavevmode\nobreak\
\int_{\mathcal{R}_{a^{\star}(C^{\prime})}(n)}\ \exp(Z_{C}^{\pi}(n,\omega))\
d(A_{0:n}(\omega),\bar{X}_{0:n}(\omega))$
$\displaystyle=\sum_{C^{\prime}\in\textsf{Alt}(C)}\ \sum_{n=0}^{\infty}\
\int_{\mathcal{R}_{a^{\star}(C^{\prime})}(n)}\
\exp({-Z_{C^{\prime}C}^{\pi}(n,\omega)})\
\exp(Z_{C^{\prime}}^{\pi}(n,\omega))\
d(A_{0:n}(\omega),\bar{X}_{0:n}(\omega))$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{C^{\prime}\in\textsf{Alt}(C)}\sum_{n=0}^{\infty}\
\int_{\mathcal{R}_{a^{\star}(C^{\prime})}(n)}\
\frac{1}{L(K-1)(K-1)!}\leavevmode\nobreak\ dP^{\pi}_{C^{\prime}}(\omega)$
$\displaystyle=\sum_{C^{\prime}\in\textsf{Alt}(C)}\frac{1}{L(K-1)(K-1)!}\leavevmode\nobreak\
P_{C^{\prime}}^{\pi}\left(\bigcup_{n=0}^{\infty}\mathcal{R}_{a^{\star}(C^{\prime})}(n)\right)$
$\displaystyle\leq\frac{1}{L},$ (97)

where $(a)$ above follows by noting that for any
$C^{\prime}\in\textsf{Alt}(C)$, the condition
$M_{C^{\prime}}^{\pi}(n)\geq\log(L(K-1)(K-1)!)$ holds at the stopping time
$\tau(\pi)=n$ on the set $R_{a^{\star}(C^{\prime})}$. In particular, this
implies that $Z^{\pi}_{C^{\prime}C}(n)\geq\log(L(K-1)(K-1)!)$. Setting
$L=1/\epsilon$ in (97) yields the desired result.

##  Appendix E Proof of Proposition 2

We note that for all $C^{\prime}\in\textsf{Alt}(C)$, under the policy
$\pi=\pi_{\textsf{NS}}^{\star}(L,\eta,R)$, almost surely,

$\displaystyle\limsup_{n\to\infty}M_{C^{\prime}}^{\pi}(n)$
$\displaystyle=\limsup_{n\to\infty}\min_{C^{\prime\prime}\in\textsf{Alt}(C^{\prime})}\
Z_{C^{\prime}C^{\prime\prime}}^{\pi}(n)$
$\displaystyle\leq\limsup_{n\to\infty}\ Z_{C^{\prime}C}^{\pi}(n)$
$\displaystyle=\limsup_{n\to\infty}\ -Z_{CC^{\prime}}^{\pi}(n)$
$\displaystyle=-\liminf_{n\to\infty}\ Z_{CC^{\prime}}^{\pi}(n)$
$\displaystyle\leq-\liminf_{n\to\infty}\ M_{C}^{\pi}(n)$ $\displaystyle<0,$
(98)

where the last line above is due to Lemma 2. Furthermore, for any $\bar{C}\neq
C$ such that $a^{\star}(\bar{C})=a^{\star}(C)$,666Recall that $a^{\star}(C)$
denotes the index of the best arm in $C$. following the exposition in Appendix
C-C with $C^{\prime}$ replaced by $\bar{C}$, we get that
$\liminf_{n\to\infty}Z_{C\bar{C}}^{\pi}(n)/n>0$ almost surely, and therefore
$\liminf_{n\to\infty}Z_{C\bar{C}}^{\pi}(n)>0$ almost surely. This implies that
$\liminf_{n\to\infty}Z_{CC^{\prime}}^{\pi}(n)-Z_{\bar{C}C^{\prime}}^{\pi}(n)>0$
almost surely for all $C^{\prime}\in\textsf{Alt}(C)$, which in turn implies
that
$\liminf_{n\to\infty}Z_{CC^{\prime}}^{\pi}(n)>\limsup_{n\to\infty}Z_{\bar{C}C^{\prime}}^{\pi}(n)$
almost surely for all $C^{\prime}\in\textsf{Alt}(C)$. Noting that
$\textsf{Alt}(C)=\textsf{Alt}(\bar{C})$, it follows that

$\displaystyle\liminf_{n\to\infty}M_{C}^{\pi}(n)>\limsup_{n\to\infty}M_{\bar{C}}^{\pi}(n)\quad\text{almost
surely}$ (99)

for all $\bar{C}\neq C$ such that $a^{\star}(\bar{C})=a^{\star}(C)$. Combining
(99) and (98), we get that under $\pi=\pi_{\textsf{NS}}^{\star}(L,\eta,R)$,

$\bar{C}(n)=C\quad\text{for all }n\text{ large},\quad\text{almost surely},$
(100)

when the underlying assignment of the TPMs is $C$, from which we may deduce
that under $\pi=\pi_{\textsf{NS}}^{\star}(L,\eta,R)$,

$\displaystyle\lim_{n\to\infty}\
P^{\pi}(A_{n}=a|A_{0:n-1},\\{(\underline{d}(s),\underline{i}(s)):K\leq s\leq
n-1\\},\underline{d}(n)=\underline{d},\underline{i}(n)=\underline{i})$
$\displaystyle=\lim_{n\to\infty}\
\lambda_{\eta,R,\bar{C}(n)}(a|\underline{d},\underline{i})$
$\displaystyle=\lambda_{\eta,R,C}(a|\underline{d},\underline{i})$ (101)

almost surely. This shows that $\pi_{\textsf{NS}}^{\star}(L,\eta,R)$
eventually makes the process $\\{(\underline{d}(t),\underline{i}(t)):t\geq
K\\}$ ergodic with $\nu_{\eta,R,C}$ as its ergodic state-action occupancy
measure. As a consequence, for all
$(\underline{d},\underline{i})\in\mathbb{S}_{R}$ and $a\in\mathcal{A}$, it
follows that

$\lim_{n\to\infty}\
\frac{N(n,\underline{d},\underline{i},a)}{n}=\nu_{\eta,R,C}(\underline{d},\underline{i},a)\
\text{almost surely}.$ (102)

Therefore, under $\pi=\pi_{\textsf{NS}}^{\star}(L,\eta,R)$, we have

$\displaystyle\lim_{n\to\infty}\ \frac{Z_{CC^{\prime}}^{\pi}(n)}{n}$
$\displaystyle=\lim_{n\to\infty}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\sum_{j\in\mathcal{S}}\frac{N(n,\underline{d},\underline{i},a,j)}{n}\,\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}$
$\displaystyle=\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\ \lim_{n\to\infty}\
\frac{N(n,\underline{d},\underline{i},a,j)}{n}\,\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\
\nu_{\eta,R,C}(\underline{d},\underline{i},a)\cdot(P_{C}^{a})^{d_{a}}(j|i_{a})\cdot\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}$
$\displaystyle=\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\
\nu_{\eta,R,C}(\underline{d},\underline{i},a)\,D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))\quad\text{almost
surely},$ (103)

where $(a)$ follows from (89). Eq. (43) is then immediate from (103).

##  Appendix F Proof of Lemma 4

Because $\pi=\pi^{\star}(L,\eta,R)$ selects arm $1$ at time $t=0$, arm $2$ at
time $t=1$, etc., and arm $K$ at time $t=K-1$, in order to prove the lemma, it
suffices to prove that for all $m\geq K$,

$\lim_{L\to\infty}P_{C}^{\pi}(\tau(\pi)\leq m)=0.$ (104)

Fix an arbitrary $m\geq K$. Then,

$\displaystyle\limsup_{L\to\infty}\,P_{C}^{\pi}(\tau(\pi)\leq m)$
$\displaystyle=\limsup_{L\to\infty}\,P_{C}^{\pi}\bigg{(}\exists\leavevmode\nobreak\
K\leq n\leq m\text{ and }C^{\prime}\in\mathcal{C}\text{ such that
}M_{C^{\prime}}^{\pi}(n)\geq\log(L(K-1)(K-1)!)\bigg{)}$
$\displaystyle\leq\limsup_{L\to\infty}\sum_{C^{\prime}\in\mathcal{C}}\
\sum_{n=K}^{m}\ P_{C}^{\pi}(M_{C^{\prime}}^{\pi}(n)\geq\log(L(K-1)(K-1)!))$
$\displaystyle\leq\limsup_{L\to\infty}\ \frac{1}{\log(L(K-1)(K-1)!)}\
\sum_{C^{\prime}\in\mathcal{C}}\ \sum_{n=K}^{m}\
\mathbb{E}_{C}^{\pi}[M_{C^{\prime}}^{\pi}(n)],$ (105)

where the first and the second inequalities above follow from the union bound
and Markov’s inequality respectively. We now show that for each
$n\in\\{K,\ldots,m\\}$, the expectation term inside the summation in (105) is
finite. This will then imply that the limit supremum on the right-hand side of
(105) is equal to $0$, thus proving the desired result.

Note that

$\displaystyle
M_{C^{\prime}}^{\pi}(n)=\min_{\tilde{C}\in\textsf{Alt}(C^{\prime})}Z_{C^{\prime}\tilde{C}}^{\pi}(n)\leq
Z_{C^{\prime}\tilde{C}}^{\pi}(n)\text{ for all
}\tilde{C}\in\textsf{Alt}(C^{\prime}).$ (106)

Fix an arbitrary $\tilde{C}\in\textsf{Alt}(C^{\prime})$ and recall that

$\displaystyle Z_{C^{\prime}\tilde{C}}^{\pi}(n)$
$\displaystyle=\sum_{a=1}^{K}\log\frac{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}{P_{\tilde{C}}^{\pi}(X_{a-1}^{a})}+\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\ N(n,\underline{d},\underline{i},a,j)\
\log\frac{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}{(P_{\tilde{C}}^{a})^{d_{a}}(j|i_{a})}.$
(107)

Because each row of $(P_{C^{\prime}}^{a})^{d}$ is mutually absolutely
continuous with the corresponding row of $(P_{\tilde{C}}^{a})^{d}$ for all
$d\geq 1$, we may upper bound the second term in (107) as

$\displaystyle\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\ N(n,\underline{d},\underline{i},a,j)\
\log\frac{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}{(P_{\tilde{C}}^{a})^{d_{a}}(j|i_{a})}$
$\displaystyle\leq
A\cdot\left(\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\
N(n,\underline{d},\underline{i},a,j)\right)$
$\displaystyle=A\cdot(n-K+1)\quad\text{almost surely},$ (108)

where

$A=\max\left\\{\log\frac{P_{a}^{d}(j|i)}{P_{a^{\prime}}^{d}(j|i)}:\
P_{a}^{d}(j|i)\neq 0,\ P_{a^{\prime}}^{d}(j|i)\neq 0,\ d\in\mathbb{N},\
i,j\in\mathcal{S},\ a,a^{\prime}\in\mathcal{A}\right\\}<\infty.$ (109)

Furthermore, suppose that $X_{0}^{a}\sim\phi$ for all $a\in\mathcal{A}$, where
$\phi$ is a probability distribution on $\mathcal{S}$ that is independent of
$a$ and the underlying assignment of the TPMs $C$. Without loss of generality,
let $\phi(i)>0$ for all $i\in\mathcal{S}$. Then, the first term in (107) may
be upper bounded as

$\displaystyle\sum_{a=1}^{K}\log\frac{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}{P_{\tilde{C}}^{\pi}(X_{a-1}^{a})}$
$\displaystyle=\log\frac{P_{C^{\prime}}^{\pi}(X_{0}^{1})}{P_{\tilde{C}}^{\pi}(X_{0}^{1})}+\sum_{a=2}^{K}\log\frac{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}{P_{\tilde{C}}^{\pi}(X_{a-1}^{a})}$
$\displaystyle=\sum_{a=2}^{K}\ \sum_{j\in\mathcal{S}}\
\mathbb{I}_{\\{X_{a-1}^{a}=j\\}}\
\log\frac{P_{C^{\prime}}^{\pi}(X_{a-1}^{a}=j)}{P_{\tilde{C}}^{\pi}(X_{a-1}^{a}=j)}$
$\displaystyle=\sum_{a=2}^{K}\ \sum_{j\in\mathcal{S}}\
\mathbb{I}_{\\{X_{a-1}^{a}=j\\}}\ \log\frac{\sum_{i\in\mathcal{S}}\
\phi(i)\cdot(P_{C^{\prime}}^{a})^{a-1}(j|i)}{\sum_{i\in\mathcal{S}}\
\phi(i)\cdot(P_{\tilde{C}}^{a})^{a-1}(j|i)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{a=2}^{K}\
\sum_{j\in\mathcal{S}}\ \mathbb{I}_{\\{X_{a-1}^{a}=j\\}}\
\sum_{i\in\mathcal{S}}\
\frac{\phi(i)\,(P_{C^{\prime}}^{a})^{a-1}(j|i)}{\sum_{i^{\prime}\in\mathcal{S}}\phi(i^{\prime})\,(P_{C^{\prime}}^{a})^{a-1}(j|i^{\prime})}\,\log\frac{(P_{C^{\prime}}^{a})^{a-1}(j|i)}{(P_{\tilde{C}}^{a})^{a-1}(j|i)}$
$\displaystyle\leq A\,(K-1)\quad\text{almost surely},$ (110)

where $(a)$ above follows from the log-sum inequality [29, Theorem 2.7.1].
Combining (108) and (110), we get

$Z_{C^{\prime}\tilde{C}}^{\pi}(n)\leq A\cdot n\quad\text{almost surely},$
(111)

from which it follows that
$\mathbb{E}_{C}^{\pi}[Z_{C^{\prime}\tilde{C}}^{\pi}(n)]\leq A\cdot n$.

##  Appendix G Proof of Lemma 5

By the definition of $\tau(\pi)$, we know that under the assignment of the
TPMs $C$,

$M_{C}^{\pi}(\tau(\pi)-1)<\log(L(K-1)(K-1)!).$

Therefore, almost surely,

$\displaystyle 1$ $\displaystyle=\limsup_{L\to\infty}\
\frac{\log(L(K-1)(K-1)!)}{\log L}$ $\displaystyle\geq\limsup_{L\to\infty}\
\frac{M_{C}^{\pi}(\tau(\pi)-1)}{\log L}$ $\displaystyle=\limsup_{L\to\infty}\
\frac{M_{C}^{\pi}(\tau(\pi)-1)}{\tau(\pi)-1}\cdot\frac{\tau(\pi)-1}{\log L}$
$\displaystyle\geq\left(\limsup_{L\to\infty}\ \frac{\tau(\pi)-1}{\log
L}\right)\cdot\left(\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{\eta,R,C}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))\right),$
(112)

where the last line above is due to (46) and the fact that the increment
$M_{C}^{\pi}(n)-M_{C}^{\pi}(n-1)$ is bounded for all $n\geq K$. We then note
that

$\displaystyle\min_{C^{\prime}\in\textsf{Alt}(C)}\
\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{\eta,R,C}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))$
$\displaystyle\geq\eta\ \min_{C^{\prime}\in\textsf{Alt}(C)}\
\left(\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{C,R}^{\textsf{unif}}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))\right)$
$\displaystyle\hskip 85.35826pt+(1-\eta)\ \min_{C^{\prime}\in\textsf{Alt}(C)}\
\left(\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\ \sum_{a=1}^{K}\
\nu_{C,R}^{\star}(\underline{d},\underline{i},a)\
D((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))\right)$
$\displaystyle\geq\eta\ T_{R}^{\textsf{unif}}(C)+(1-\eta)\ T_{R}^{\star}(C),$
(113)

thus establishing the desired result.

##  Appendix H Proof of Proposition 3

We prove here that the family $\\{\tau(\pi)/\log L:L>1\\}$, where
$\pi=\pi^{\star}(L,\eta,R)$, is uniformly integrable. Towards this, we show
that

$\limsup_{L\to\infty}\
\mathbb{E}_{C}^{\pi}\bigg{[}\bigg{(}\frac{\tau(\pi)}{\log
L}\bigg{)}^{2}\bigg{]}<\infty.$ (114)

Then, [30, Lemma 3, pp. 227] implies the desired uniform integrability result
from (114) (by using $G(t)=t^{2}$ in [30, Lemma 3, pp. 227]). Let

$\displaystyle\psi(L)\coloneqq\frac{\log(L(K-1)(K-1)!)}{\log L},$ (115)

and let $\pi^{\star}_{C}=\pi^{\star}_{C}(L,\eta,R)$ denote the version of the
policy $R$-DCR-BAI that stops only when the event

$M_{C}^{\pi^{\star}_{C}}(n)\geq\log(L(K-1)(K-1)!)$

occurs. Clearly, $\tau(\pi^{\star}_{C})\geq\tau(\pi)$ almost surely. Then,

$\displaystyle\limsup_{L\to\infty}\
\mathbb{E}_{C}^{\pi}\bigg{[}\bigg{(}\frac{\tau(\pi)}{\log
L}\bigg{)}^{2}\bigg{]}$
$\displaystyle=\limsup_{L\to\infty}\int_{0}^{\infty}P_{C}^{\pi}\bigg{(}\left(\frac{\tau(\pi)}{\log
L}\right)^{2}>x\bigg{)}\,dx$
$\displaystyle=\limsup_{L\to\infty}\int_{0}^{\infty}P_{C}^{\pi}\bigg{(}\tau(\pi)>(\sqrt{x})({\log
L})\bigg{)}\,dx$
$\displaystyle\leq\limsup_{L\to\infty}\int_{0}^{\infty}P_{C}^{\pi}\bigg{(}{\tau(\pi^{\star}_{C})}>(\sqrt{x})({\log
L})\bigg{)}\,dx$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\limsup_{L\to\infty}\bigg{\\{}\psi(L)+\int_{\psi(L)}^{\infty}P_{C}^{\pi}\bigg{(}{\tau(\pi^{\star}_{C})}>(\sqrt{x})({\log
L})\bigg{)}\,dx\bigg{\\}}$ $\displaystyle\leq\limsup_{L\to\infty}\
\psi(L)+\limsup_{L\to\infty}\sum_{n\geq\sqrt{\psi(L)}\,\log
L}^{\infty}\frac{2n+1}{(\log L)^{2}}\ P_{C}^{\pi}(\tau(\pi_{C}^{\star})>n)$
$\displaystyle\leq 1+\limsup_{L\to\infty}\sum_{n\geq\sqrt{\psi(L)}\,\log
L}^{\infty}\frac{2n+1}{(\log L)^{2}}\
P_{C}^{\pi}(M_{C}^{\pi}(n)<\log(L(K-1)(K-1)!)),$ (116)

where $(a)$ above follows by upper bounding the probability term by $1$ for
all $x\leq\psi(L)$. Below, we show that
$P_{C}^{\pi}(M_{C}^{\pi}(n)<\log(L(K-1)(K-1)!))$ is $O(1/n^{3})$, which
implies that the infinite sum in (116) is finite. This will then prove that
the right-hand side of (116) is finite. Note that

$\displaystyle P_{C}^{\pi}(M_{C}^{\pi}(n)<\log(L(K-1)(K-1)!))$
$\displaystyle=P_{C}^{\pi}\left(\min_{C^{\prime}\in\textsf{Alt}(C)}Z_{CC^{\prime}}^{\pi}(n)<\log(L(K-1)(K-1)!)\right)$
$\displaystyle\leq\sum_{C^{\prime}\in\textsf{Alt}(C)}\
P_{C}^{\pi}\left(Z_{CC^{\prime}}^{\pi}(n)<\log(L(K-1)(K-1)!)\right),$ (117)

where the last line above follows from the union bound.

We now show that each term inside the summation in (117) is $O(1/n^{3})$. Fix
$C^{\prime}\in\textsf{Alt}(C)$ and observe that

$\displaystyle
P_{C}^{\pi}\left(Z_{CC^{\prime}}^{\pi}(n)<\log(L(K-1)(K-1)!)\right)$
$\displaystyle=P_{C}^{\pi}\left(\frac{Z_{CC^{\prime}}^{\pi}(n)}{n}<\frac{\log(L(K-1)(K-1)!)}{n}\right)$
$\displaystyle=P_{C}^{\pi}\bigg{(}\frac{1}{n}\ \sum_{a=1}^{K}\
\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}$
$\displaystyle\hskip
56.9055pt+\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\
\frac{N(n,\underline{d},\underline{i},a,j)}{n}\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}<\frac{\log(L(K-1)(K-1)!)}{n}\bigg{)}$
$\displaystyle\leq P_{C}^{\pi}\left(\frac{1}{n}\ \sum_{a=1}^{K}\
\log\frac{P_{C}^{\pi}(X_{a-1}^{a})}{P_{C^{\prime}}^{\pi}(X_{a-1}^{a})}<-\varepsilon\right)$
(118)
$\displaystyle+P_{C}^{\pi}\bigg{(}\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\ \sum_{j\in\mathcal{S}}\
\frac{N(n,\underline{d},\underline{i},a,j)}{n}\
\log\frac{(P_{C}^{a})^{d_{a}}(j|i_{a})}{(P_{C^{\prime}}^{a})^{d_{a}}(j|i_{a})}$
$\displaystyle\hskip
85.35826pt-\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\
\frac{N(n,\underline{d},\underline{i},a)}{n}\,D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))<-\varepsilon\bigg{)}$
(119)
$\displaystyle+P_{C}^{\pi}\bigg{(}\sum_{(\underline{d},\underline{i})\in\mathbb{S}_{R}}\
\sum_{a=1}^{K}\
\frac{N(n,\underline{d},\underline{i},a)}{n}\,D_{\textsf{KL}}((P_{C}^{a})^{d_{a}}(\cdot|i_{a})\|(P_{C^{\prime}}^{a})^{d_{a}}(\cdot|i_{a}))-2\varepsilon<\frac{\log(L(K-1)(K-1)!)}{n}\bigg{)}$
(120)

for all $\varepsilon>0$. Fixing $\varepsilon$, we handle (118)-(120)
individually. We also show how to choose $\varepsilon$ (later in (130)).

  1. 1.

Handling (118): This term is equal to $0$ for all sufficiently large values of