TBD

Liu

Index Policy for Partially Observable RMAB

Relaxed Indexability and Index Policy for Partially Observable Restless
Bandits

Keqin Liu Department of Mathematics, Nanjing University, China, 210093,
<EMAIL_ADDRESS>
This paper addresses an important class of restless multi-armed bandit (RMAB)
problems that finds a broad application area in operations research,
stochastic optimization, and reinforcement learning. There are $N$ independent
Markov processes that may be operated, observed and offer rewards. Due to the
resource constraint, we can only choose a subset of $M~{}(M<N)$ processes to
operate and accrue reward determined by the states of selected processes. We
formulate the problem as a partially observable RMAB with an infinite state
space and design an algorithm that achieves a near-optimal performance with
low complexity. Our algorithm is based on a generalization of Whittle’s
original idea of indexability. Referred to as the relaxed indexability, the
extended definition leads to the efficient online verifications and
computations of the approximate Whittle index under the proposed algorithmic
framework.

restless multi-armed bandit, partial observation, infinite state space,
relaxed indexability and index policy This paper was first submitted on August
19, 2021 and resubmitted on September 12, 2022.

##  1 Introduction

The first multi-armed bandit (MAB) problem was proposed in 1933 in the context
of clinical trial for adaptively selecting the best treatment over time
(Thompson 1933). Specifically, given two new medicines just invented for
curing some disease, we want to find out which medicine has the better effect
in long-run. When a new patient arrives, the doctor needs to decide which
medicine to use based on past observations on the recovery processes of the
previous patients after being treated with one of the medicines. Because the
effect of each medicine is often modeled as a random variable, the decision
problem involves a famous dilemma between “Exploitation” and “Exploration”
often appeared in reinforcement learning: choosing the medicine that seems to
be the best versus choosing the one less frequently used. In other words, the
choice of the medicine determines not only the immediate effect of the
treatment but also which medicine to observe for better estimation in the
future. In the following subsection, we formally state the classical MAB under
the Bayesian framework.

###  1.1 The Classical MAB and Gittins Index

In the classical Bayesian model of MAB, there are $N$ arms and a single
player. At each discrete time (decision epoch), a player chooses one arm to
operate and accrues certain amount of reward determined by the state of the
arm. The state of the chosen arm transits to a new one according to a known
Markovian rule while the states of other arms remain frozen. The observation
model is assumed to be complete, i.e., the states of all arms can be observed
before deciding which arm to choose. The objective is to maximize the total
discounted reward over the infinite horizon (Gittins et al. 2011). About 40
years later, Gittins (1979) solved the problem by showing that the optimal
policy has an index structure, i.e., at each time one can compute an index (a
real number) solely based on the current state of an arm and choosing the arm
associated with the highest index is optimal. Besides Gittins’ original proof
of optimality based on an interchange argument, Whittle (1980) gave a proof by
introducing retirement option which was further generalized to the restless
MAB model. Weber (1992) gave a beautiful proof without any mathematical
equation by an argument of fair charge, while Bertsimas and Niño-Mora (1996)
took the achievable region approach for a proof based on linear programming
and the duality theory. These four classical proofs of the optimality of
Gittins index were elegantly summarized and extended by Frostig and Weiss
(2016).

###  1.2 Whittle’s Generalization to Restless MAB

Whittle (1988) generalized the classical MAB to the restless bandit model,
where each unselected arm can also change state (accordingly to another known
Markovian rule) and offer reward. Furthermore, the player is not restricted to
select only one arm but can choose $M~{}(M<N)$ of them at each time. Either
extension of the above makes Gittins index suboptimal in general. Whittle
introduced an index policy based on the idea of subsidy, i.e., by focusing on
a single-armed bandit one can attach a fixed amount of reward (subsidy) to the
arm when it is unselected (made passive) and Whittle index is defined as the
minimum subsidy that makes selecting (activating) the arm or not equally
optimal at its current state. This subsidy decouples arms for computing
Whittle index and is reduced to Gittins index in the classical MAB model.
Whittle showed that the subsidy is essentially the Lagrangian multiplier
associated with a relaxed constraint on the expected number of arms to
activate over the infinite horizon, thus providing an upper bound for the
original problem. However, there is a great challenge before we can apply
Whittle index policy, namely, the indexability condition. In other words, we
require that the subsidy that makes actions indifferent exists and is uniquely
defined for each state of each arm. In this case, we call the RMAB is
indexable in which the Whittle index is well-defined. However, proving
indexability is generally difficult even for RMAB with finite state spaces
(Niño-Mora 2001). Furthermore, even the indexability is proved to hold,
solving for the Whittle index in closed-form is again a difficult problem in
the design of an implementable policy (Liu and Zhao 2010, Liu et al. 2011).
See Sec. 1.5 for more details.

###  1.3 Resource Constraint and Partial Observability

The restless MAB (RMAB) is a special class of Markov Decision Processes (MDP)
where system state vector is completely observed at the beginning of each
decision epoch. However, many problems do not possess such a perfect
observation model. Instead, only the selected arms will reveal their states to
the player after arm selection is determined. This category of problems
belongs to the class of Partially Observable MDP (POMDP), which encompasses a
much wider application range than MDP (Sondik 1978). In this paper, the $N$
processes (arms) are modeled as Markov chains evolving over time, according to
potentially different rules for state transitions and reward offering. At each
time, the player chooses only $M~{}(M<N)$ arms to observe and obtain reward
determined by the observed states of chosen arms. The states of other unchosen
arms remain unknown. To formulate the problem as an RMAB, we can use
information state as a sufficient statistics for optimal control that
characterizes the probability distribution of arm states based on past
observations. For the case that each Markov chain has only $2$ states, the
problem was solved near-optimally by Whittle index policy (Liu and Zhao 2010,
Liu et al. 2011). This paper extends those results to the case of $K$-state
Markov chains for $K>2$. As shown in the rest of this paper, this extension
makes the problem fundamentally more complex. Our approach is to embrace a
family of threshold policies that significantly simplifies the system dynamics
while keeping the major benefits from the fundamental structure of Whittle’s
relaxation. We summarize the main results of this paper in the next
subsection.

###  1.4 Main Results

First, we formulate the problem as a partially observable RMAB with an
infinite state space. Second, we establish an equivalent condition for
indexability in our problem which further leads to a proof of indexability
when the discount factor $\beta\leq 0.5$. Third, we extend the classical
indexability proposed by Whittle to the relaxed indexability. With this
generalization, we propose a threshold policy on a single arm that linearizes
the original decision boundary and leads to a closed-form expression of the
approximate Whittle index under the relaxed indexability. Meanwhile we show
that the relaxed indexability relative to the linearized threshold function is
reduced to the classical indexability with zero approximation error of the
Whittle index for $K=2$. Fourth, we establish an efficient algorithm based on
the relaxed indexability and the approximate Whittle index for general $K>2$.
Last, we consider the special case of $K=3$ and further optimize the
implementation of our algorithm with its near-optimal performance demonstrated
by numerical experiments.

###  1.5 Related Work

By considering a large deviation theory applied on Markov jump processes under
the time-average reward criterion, Weber and Weiss (1990) showed that Whittle
index policy implemented under the strict constraint (i.e., choosing exactly
$M$ arms with the highest indices at each time) converges to the upper bound
with the relaxed constraint per-arm-wise as $N\rightarrow\infty$ with $M/N$
fixed under a sufficient condition. This sufficient condition requires the
global stability of a deterministic fluid dynamic system approximating the
stochastic state evolution processes of all arms. Weber and Weiss (1991)
further showed that the sufficient condition is satisfied when the cardinality
of arm states is $2$ or $3$. Verloop (2016) extended these results to a wider
class of indexable and also non-indexable restless bandits with finite state
spaces. However, verifying this sufficient condition is very difficult without
a general theoretical approach. The existence of such an index policy (i.e.,
indexability) is part of the sufficient condition and is itself without a
general way to verify. For RMAB with finite state spaces, some sufficient
conditions for indexability were established (see, e.g., Weber and Weiss 1990,
1991, Niño-Mora 2001) as well as some necessary ones (see, e.g., Weber and
Weiss 1990, Niño-Mora 2007). For the indexable RMAB problems studied so far,
Whittle index policy has been shown a near-optimal performance in different
application areas (see, e.g., Niño-Mora 2001, Glazebrook et al. 2009, Liu and
Zhao 2010, Hodge and Glazebrook 2011, Verloop 2016). Furthermore, based on
Whittle’s original idea of arm-decoupling, various index policies have been
proposed for restless bandits with finite state spaces with asymptotic
optimality proved under certain conditions and a strong performance
numerically demonstrated in finite regimes (see, e.g., Bertsimas and Niño-Mora
2000, Hu and Frazier 2017, Zayas-Cabán et al. 2019, Brown and Smith 2020, Gast
et al. 2021). It is worth noticing that the general restless MAB with a finite
state space is PSPACE-HARD (Papadimitriou and Tsitsiklis 1999), making it
unlikely to discover an efficient optimal algorithm in general.

The partially observable restless bandit for the case of $K=2$ was first
formulated in the context of communications networks by Liu and Zhao (2008)
and in the context of unmanned aerial vehicles by Le Ny et al. (2008), where
the indexability and the closed-form Whittle index function were established
under the total discounted reward criterion in both of the two independent
papers. Liu and Zhao (2010) extended these results to the time-average reward
criteria and proved the structure, optimality and equivalence of the Whittle
index policy to the myopic policy for homogeneous arms (i.e., arms with the
same $2\times 2$ transition probability matrix and reward function). Following
these results, various partial observation and state transition models for
$K=2$ were studied in different application areas with the strong performance
of such an index policy successfully demonstrated (see, e.g., Liu et-al. 2010,
Lapiccirella et al. 2011, Liu and Zhao 2012, Wang et al. 2014, Elmaghraby et
al. 2018, Zhao 2019, Liu et al. 2022). This motivates us to consider the
general case of $K>2$ in this paper.

##  2 RMAB Formulation and Classical Indexability

In this section, we will formulate the multi-armed bandit problem as a
partially observable Markov decision process and introduce the concept of
Whittle Index. Consider a bandit machine with totally $N$ independent arms,
each of which is modelled as a Markov process. For the $n$-th arm
$(n\in\\{1,...,N\\})$, let
$\textbf{P}^{(n)}=\\{p_{i,j}^{(n)}\\}_{i,j\in\\{0,1,2,\ldots,K_{n}-1\\}}$
denote its state transition matrix and
$B_{n,i}~{}(i\in\\{0,1,2,\ldots,K_{n}-1\\})$ the reward that can be obtained
when the arm is observed in state $i$. Let
$B_{n}=[B_{n,0},B_{n,1},B_{n,2},\ldots,B_{n,K_{n}-1}]$ be the reward vector
for arm $n$. At each discrete time $t$, $M$ arms will be selected for
observation (activated). Let $U(t)\subseteq\\{1,...,N\\}~{}(|U(t)|=M)$ be the
set of arms that are observed at time $t$. The (random) reward obtained at
time $t$ is given by

$R_{U(t)}(t)=\sum_{n\in U(t)}B_{n,S_{n}(t)},$ (1)

where $S_{n}(t)\in\\{0,1,2,\ldots,K_{n}-1\\}$ denotes the state of arm $n$ at
time $t$. Our objective is to decide an optimal policy $\pi^{*}$ of choosing
$M$ arms at each time such that the long-term reward is maximized in
expectation. In this paper, we will focus on the expected total discounted
reward objective function:

$\pi^{*}=\arg\max_{\pi\in\Pi}\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}R_{U(t)}(t)],$
(2)

where $\beta\in(0,1)$ is the discount factor for the convergence of the sum in
the right-hand side of (2) and $\Pi$ the set of all feasible policies
satisfying $|U(t)|=M$ at each time $t$.

###  2.1 Belief Vector as System State

Since no arm state is observable before $U(t)$ is decided at time $t$, we need
an alternative representation of information for decision making. According to
the general POMDP theory, the conditional probability distribution of the
Markovian state given all past knowledge is a sufficient statistics for
decision making (Sondik 1978). Specifically, in our problem, the past
knowledge consists of the initial (a prior) probability distribution of the
state of each arm at $t=1$, the time of last observation of each arm, and the
observed state at the last observation of each arm. Then the conditional
probability distribution of each arm’s state given the past knowledge can be
written in the following equation and is referred to as the belief state (or
belief vector) of the arm. The belief states from all arms thus form a
sufficient statistics for our decision making process and are fully
observable.

Denoted by $\omega_{n}(t)$ the belief vector of arm $n$ at time $t$, we have

$\omega_{n}(t)=\left(\begin{matrix}{\rm
Pr}(S_{n}(t)=0|\omega_{n}(1),\tau_{n},S_{n}(\tau_{n}))\\\ {\rm
Pr}(S_{n}(t)=1|\omega_{n}(1),\tau_{n},S_{n}(\tau_{n}))\\\ \vdots\\\ {\rm
Pr}(S_{n}(t)=K_{n}-1|\omega_{n}(1),\tau_{n},S_{n}(\tau_{n}))\end{matrix}\right)^{\prime},\quad\Omega(t)=\left(\begin{matrix}\omega_{1}(t)\\\
\vdots\\\ \omega_{N}(t)\end{matrix}\right),$

where $A^{\prime}$ denotes the transpose of $A$ and $\tau_{n}$ the time of
last observation on arm $n$. If the arm has never been observed, we can set
$\tau_{n}=-\infty$ and remove $S_{n}(\tau_{n})$ from the condition. Thus the
initial belief vector $\omega_{n}(1)$ can be set as the stationary
distribution $\bar{\omega}_{n}$ of the internal Markov chain (corresponding to
the case of $\tau_{n}=-\infty$)111Here we assume the Markov chain with
transition matrix $\textbf{P}^{(n)}$ is irreducible and aperiodic.:

$\displaystyle\omega_{n}(1)=\bar{\omega}_{n}=\lim_{k\rightarrow\infty}\textbf{p}(\textbf{P}^{(n)})^{k},$
(3)

where $\bar{\omega}_{n}$ is the unique solution to
$\omega\textbf{P}^{(n)}=\omega$ and p an arbitrary probability distribution of
the state of arm $n$. The limit in (3) can be taken under any norm since
belief vectors are in a finite-dimensional vector space. It is also convenient
to update the belief vector of each arm at each time according to the
following Markovian rule:

$\omega_{n}(t+1)=\begin{cases}[p^{(n)}_{S_{n}(t),0},p^{(n)}_{S_{n}(t),1},\ldots,p^{(n)}_{S_{n}(t),K_{n}-1}],&n\in
U(t)\\\ \omega_{n}(t)\textbf{P}^{(n)},&n\notin U(t)\end{cases}\quad.$ (4)

So the POMDP problem is reduced to an MDP one by treating all belief vectors
of all arms as the system state of the decision problem. However, the state
space becomes infinite as a function space (consisting of probability
measures).

Note that the belief update is deterministic if the arm is not chosen for
observation at the time. For the case where the arm is not being observed for
a consecutive sequence of time, we define the following operator for updating
the belief vector continuously over $k$ consecutive slots without any
observation:

$\displaystyle\mathcal{T}^{k}_{n}(\omega_{n}(t))$
$\displaystyle=\left(\begin{matrix}{\rm Pr}(S_{n}(t+k)=0|\omega_{n}(t))\\\
{\rm Pr}(S_{n}(t+k)=1|\omega_{n}(t))\\\ \vdots\\\ {\rm
Pr}(S_{n}(t+k)=K_{n}-1|\omega_{n}(t))\end{matrix}\right)^{\prime}$
$\displaystyle=\omega_{n}(t)(\textbf{P}^{(n)})^{k}.$ (5)

Now the decision problem has a countable state space as modelled by the belief
vector for a fixed initial $\Omega(1)$ and an uncountable  state space for an
arbitrarily chosen $\Omega(1)$. This infinite-dimensional optimization problem
can be formulated as

$\displaystyle\max_{\pi\in\Pi}$
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}\sum_{n=1}^{N}\mathbbm{1}(n\in
U(t))B_{n,S_{n}(t)}|\Omega(1)]$ (6) s. t.
$\displaystyle\sum_{n=1}^{N}\mathbbm{1}(n\in U(t))=M,\quad\forall~{}t\geq 1.$
(7)

It is clear that as the number of arms increases, the number of choices at
each time grows geometrically. Furthermore, different choices lead to
different updates of the belief vector, yielding a high complexity in solving
the problem. In the following, we will extend Whittle’s original idea of arm-
decoupling for an index policy to our model which has an infinite state space
consisting of belief vectors.

###  2.2 Definition of Indexability and Whittle Index

Whittle relaxed the strict constraint on the exact number of arms to choose at
each time to requiring only $M$ arms are chosen in expectation. Particularly,
we consider the following relaxed form of problem (6):

$\displaystyle\max_{\pi\in\Pi}$
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}\sum_{n=1}^{N}\mathbbm{1}(n\in
U(t))B_{n,S_{n}(t)}|\Omega(1)]$ (8) s. t.
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}\sum_{n=1}^{N}\mathbbm{1}(n\notin
U(t))|\Omega(1)]=\frac{N-M}{1-\beta}.$ (9)

Remark. For RMAB with finite state spaces and the time-average reward
criterion, Weber and Weiss (1990) showed that the performance gap from (7) to
(9) asymptotically tends to zero per-arm-wise as $N\rightarrow\infty$ with
$M/N$ fixed (Theorem 1 in Weber and Weiss 1990). They also showed that the
performance gap induced by the Whittle index policy is determined by the
stability of a high-dimensional nonlinear dynamic system (the fluid
approximation), which is still an open problem in general for arm state number
greater than $3$ (Weber and Weiss 1991, Verloop 2016). For RMAB with finite
state spaces and the discounted reward criterion, a general LP (linear
programming) relaxation with the performance region approach was proposed by
Bertsimas and Niño-Mora (2000) to numerically demonstrate the small
performance gap of the primal-dual index heuristic; while other index
heuristics under various relaxation methods for finite time horizons were
proposed with performance gap tending to zero (in the same sense as in Weber
and Weiss 1991) under certain conditions (Hu and Frazier 2017, Zayas-Cabán et
al. 2019, Brown and Smith 2020, Gast et al. 2021). However, these approaches
cannot be directly applied to analyze our problem which has an infinite state
space.

Whittle’s relaxation from (7) to (9) allows us to analyze the dual problem
with arms decoupled as detailed below. Applying the Lagrangian multiplier
$\lambda$ to (9), we arrive at the following unconstrained optimization
problem:

$\displaystyle\max_{\pi\in\Pi}$
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}\sum_{n=1}^{N}[\mathbbm{1}(n\in
U(t))B_{n,S_{n}(t)}+\lambda\mathbbm{1}(n\notin U(t))]|\Omega(1)].$ (10)

The above unconstrained optimization is equivalent to $N$ independent
optimization problem as shown below:

$\displaystyle\max_{\pi\in\Pi}$
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}[\mathbbm{1}(n\in
U(t))B_{n,S_{n}(t)}+\lambda\mathbbm{1}(n\notin U(t))]|\omega_{n}(1)],\quad
n=1,2,\ldots,N.$ (11)

Therefore, it is sufficient to consider a single arm for solving problem (10).
Note that the action applied on a single arm is either “selected (activated)”
or “unselected (made passive)” at each time. We can thus focus on the single-
armed problem (with Lagrangian multiplier $\lambda$) with state space
consisting of all probability measures on the Markov chain and a binary action
space.

For simplicity, we will drop the subscript $n$ in consideration of a single-
armed bandit without loss of generality. The Lagrangian multiplier $\lambda$
introduces a reward for passive actions on this arm. Referred to as the
subsidy for passivity by Whittle, we will denote it by $m$ as a variable
dependent only on this arm, in distinction to $\lambda$ shared by all arms in
the relaxed problem (10). Let $V_{\beta,m}(\omega)$ denote the value of (11)
with $\omega_{n}(1)=\omega$. It is straightforward to write out the dynamic
equation of the single-armed bandit problem as follows:

$V_{\beta,m}(\omega)=\max\\{V_{\beta,m}(\omega;u=1);V_{\beta,m}(\omega;u=0)\\},$
(12)

where $V_{\beta,m}(\omega;u=1)$ and $V_{\beta,m}(\omega;u=0)$ denote,
respectively, the maximum expected total discounted reward that can be
obtained if the arm is activated or made passive at the current belief state
$\omega$, followed by an optimal policy in subsequent slots. Since we consider
the infinite-horizon problem, a stationary optimal policy can be chosen and
the time index $t$ is not needed in (12). Let
$p_{i\cdot}=[p_{i0},p_{i1},\ldots,p_{i(K-1)}],(i=0,1,\ldots,K-1)$ denote the
$i$-th row of P, we have

$\displaystyle V_{\beta,m}(\omega;u=1)=\omega
B^{\prime}+\beta\omega\left(\begin{matrix}V_{\beta,m}(p_{0})\\\
V_{\beta,m}(p_{1})\\\ \vdots\\\ V_{\beta,m}(p_{K-1})\end{matrix}\right),$ (13)
$\displaystyle V_{\beta,m}(\omega;u=0)=m+\beta
V_{\beta,m}(\mathcal{T}^{1}(\omega)),$ (14)

where $\mathcal{T}^{1}(\omega)$ is the one-step belief update as defined in
(2.1). Without loss of generality, we assume $0=B_{0}\leq B_{1}\leq\cdots\leq
B_{K-1}$. Note that $V_{\beta,m}(\omega;u=1)$ is linear in $\omega$ while
$V_{\beta,m}(\omega;u=0)$ is convex in $\omega$ as shown by Lemma 2.2 in Sec.
2.3.

Define passive set $P(m)$ as the set of all belief states such that taking the
passive action $u=0$ is optimal:

$\displaystyle
P(m){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\\{\omega:~{}V_{\beta,m}(\omega;u=1)\leq
V_{\beta,m}(\omega;u=0)\\}.$ (15)

It is clear that $P(m)$ changes from the empty set to the whole space of
probability measures as $m$ increases from $-\infty$ to $\infty$. However,
such change may not be monotonic as $m$ increases (see Sec. 2.3 for more
discussions). If the passive set $P(m)$ increases monotonically with $m$, then
for each value $\omega$ of the belief state, one can define the unique $m$
that makes it join $P(m)$ and stay in the set forever. Intuitively, this $m$
measures how attractive it is to activate the arm at the belief state $\omega$
compared to other belief states in a well-ordered manner: the larger $m$
required for it to be passive, the more incentives to activate at the belief
state without $m$. This value of $m$ (if well-defined) thus yields a priority
index of the belief state. In the following, we present the formal definition
of indexability and Whittle index (Whittle 1988).

###### Definition 2.1

A restless multi-armed bandit is indexable if for each single-armed bandit
with subsidy, the passive set of arm states increases monotonically from
$\emptyset$ to the whole state space as $m$ increases from $-\infty$ to
$+\infty$. Under indexability, the Whittle index of an arm state is defined as
the infimum subsidy $m$ such that the state remains in the passive set.

Note that if the indexability condition is verified and the Whittle index
solved as a function of the state of each arm, the Lagrangian relaxation
problem (10) may be solved with the optimal $\lambda^{*}$: for each arm at
each time, we choose to activate the arm if its current Whittle index is
greater than $\lambda^{*}$ or make it passive otherwise. There is some
randomization technique involved to ensure the satisfaction of constraint (9)
when the Whittle index is equal to $\lambda^{*}$. But that is not the main
focus of this paper and we will give some brief discussions following Theorem
2.4 in Sec. 2.4.

###  2.3 Threshold Structure of The Optimal Policy

For our model in which the arm state is given by the belief vector, the
indexability is equivalent to the following:

$\displaystyle\mbox{If}~{}V_{\beta,m}(\omega;u=1)\leq
V_{\beta,m}(\omega;u=0),~{}\mbox{then}~{}\forall~{}m^{\prime}>m,~{}V_{\beta,m^{\prime}}(\omega;u=1)\leq
V_{\beta,m^{\prime}}(\omega;u=0).$ (16)

Under indexability, the Whittle index $W(\omega)$ of arm state $\omega$ is
defined as

$\displaystyle
W(\omega){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\inf\\{m:~{}V_{\beta,m}(\omega;u=1)\leq
V_{\beta,m}(\omega;u=0)\\}.$ (17)

Before we proceed, it helps to emphasize on the recursive nature in defining
the value functions given in (13) and (14) conditional on the active and
passive actions, respectively. We know that the indexability condition
essentially requires a once only rank change of the two value functions as $m$
increases. Although it is intuitive that the larger subsidy causes more states
to join the passive set, we cannot conclude this by merely comparing the
immediate rewards obtained by active and passive actions ($\omega B^{\prime}$
vs. $m$) respectively: the future total expected reward is again in the form
of value functions that are dependent on our current action (which affects the
belief update) and the subsidy $m$. To evaluate indexability, we need to have
sufficient knowledge about the value functions (13) and (14) to determine
their rank (as functions of the current belief state and the subsidy). In
general, the value functions are hard to solve due to the dilemma between
exploitation and exploration mentioned at the beginning of this paper.
However, for the problem at hand, we can show that the value function (12)
implies a threshold structure of the problem, which generalizes the case of
$K=2$ and further inspires for an efficient algorithm as detailed below.

Now we prove a crucial lemma that gives some fundamental properties of the
value function $V_{\beta,m}(\omega)$.

###### Lemma 2.2

The value function $V_{\beta,m}(\omega)$ for the single-armed bandit with
subsidy is convex and Lipschitz continuous in both $\omega$ and $m$.

The proof will be given in the e-companion to this paper.

Remark

  * •

Note that if $m\leq 0$, it is optimal to always activate the arm (since all
extreme points of a convex function under the passive action are below those
of a linear one under the active action) and $V_{\beta,m}(\omega)$ does not
depend on $m$ and is thus Lipschitz continuous in $m$. If $m\geq B_{K-1}$, it
is optimal to always make the arm passive so
$V_{\beta,m}(\omega)=\frac{m}{1-\beta}$ and is thus Lipschitz continuous as
well. The interesting case is when $0<m<B_{K-1}$ as focused in the rest of the
paper. The monotonic property of $V_{\beta,m}(\omega)$ as a nondecreasing
function of $m$ is clear.

  * •

Since $V_{\beta,m}(\omega)$ is Lipschitz continuous in $m$, it is also
absolutely continuous and differentiable almost everywhere in $m$. Assume
$m_{0}$ is a point where the derivative exists, a small increase to
$m_{0}+\Delta m$ should cause $V_{\beta,m_{0}}(\omega)$ to boost at a ratio at
least equal to the expected total discounted time of being passive, since the
subsidy $m_{0}$ for passivity is being paid for such a duration of time
(passive time in short). The passive time is not necessarily unique and we
will give a rigorous formulation of its relation to the (right) derivative of
$V_{\beta,m}(\omega)$ in Theorem 2.4 in Sec. 2.4.

  * •

Since $V_{\beta,m}(\omega)$ is also Lipschitz continuous in $\omega$, for
sufficiently small $\beta$, a change of $\omega$ that makes the immediate
reward $\omega B^{\prime}$ vary may play a dominating role in determining the
order of (13) and (14) as the value function $V_{\beta,m}(\omega)$ varies in
bounded ratios with $\omega$. This motivates us to consider the family of
linearized threshold policies: following the trajectory of
$\mathcal{T}^{k}(\omega)$ until some linear function
$r(\cdot):~{}\mathbb{R}^{K}\rightarrow\mathbb{R}$ (e.g., the projection
$r(\omega)=\omega B^{\prime}$) maps $\mathcal{T}^{k}(\omega)$ to a value
greater than a given one, we activate the arm and reset the value function to
one of $V_{\beta,m}(p_{0}),V_{\beta,m}(p_{1}),\cdots,V_{\beta,m}(p_{K-1})$
(See (13)). Linearized threshold policies are suboptimal in general,
especially when $\beta$ is large. However, they provide an efficient way in
solving the approximated value functions and leads to a computable Whittle
index function in low-complexity with the near-optimal performance even when
$\beta$ is close to $1$, as elaborated in Sec. 3.2 and Sec. 4.

Next, we show that the optimal single-arm policy has a general threshold
structure. Let $\mathbb{X}$ denote the belief state space as a
$(K-1)$-simplex. It is a $(K-1)$-dimensional space of probability measures.
For convenience, we still use the $K$-dimensional vector
$(\omega_{1},\omega_{2},\ldots,\omega_{K})$ to denote a point in $\mathbb{X}$
by keeping in mind that $\sum_{i=1}^{K}\omega_{k}=1$. Now consider an extreme
point $\omega=[0,0,\cdots,1,\cdots,0]$ of the belief state space where it is
known that the arm’s internal state is $k$ for some
$k\in\\{0,1,\cdots,K-1\\}$. In this case, the next belief state is
deterministically $p_{k}$, independent of the current action, i.e.,

$\displaystyle\arg\max\\{V_{\beta,m}(\omega;u=1);V_{\beta,m}(\omega;u=0)\\}$
$\displaystyle=$ $\displaystyle\arg\max\left\\{B_{k},~{}m\right\\}.$ (18)

From the above, each extreme point successively joins the passive set as $m$
increases from $0$ to $B_{K-1}$. Consider an $m\in(0,B_{K-1})$ such that
$0=B_{0}\leq\cdots\leq m<B_{j}\leq\cdots\leq B_{K-1}$. The first $j$ states
are in the passive set while states $j,\cdots,K-1$ are in the active set
defined as

$\displaystyle
A(m){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\mathbb{X}-P(m)=\\{\omega:~{}V_{\beta,m}(\omega;u=1)>V_{\beta,m}(\omega;u=0)\\}.$
(19)

The following lemma shows that the active set $A(m)$ is an open convex region
in $\mathbb{X}$ with a decision boundary $C(m)$ shared by the passive set
$P(m)$:

$\displaystyle
C(m){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\\{\omega:~{}V_{\beta,m}(\omega;u=1)=V_{\beta,m}(\omega;u=0)\\}.$
(20)

###### Lemma 2.3

The active set $A(m)$ is an open convex $(K-1)$-dimensional subspace of
$\mathbb{X}$. The decision boundary $C(m)$ is a compact and simply connected
$(K-2)$-dimensional subspace of $\mathbb{X}$ that partitions $\mathbb{X}$ into
two disjoint and connected subspaces: $A(m)$ and $P(m)$ with $C(m)\subset
P(m)$.

The proof will be given in the e-companion to this paper.

According to Lemma 2.3, we can treat $C(m)$ as a $(K-2)$-dimensional threshold
without any holes or discontinuities for the optimal decision making process.
One can visualize it as a curve for $K=3$ or a surface for $K=4$. Higher
dimensions are analogous to compact $(K-2)$-manifolds. If indexability holds,
the boundary $C(m)$ should (continuously) move in a direction such that $A(m)$
shrinks as $m$ increases. For each $\omega$, there exists an $m$ such that
$C(m)$ reaches $\omega$ for the first time and this $m$ is the Whittle index
$W(\omega)$ of $\omega$:

$\displaystyle
W(\omega){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\inf\\{m:V_{\beta,m}(\omega;u=1)\leq
V_{\beta,m}(\omega;u=0)\\}=\min\\{m:\omega\in C(m)\\}.$ (21)

In the above, we have used the minimization operator instead of the infimum by
observing that the closure of the nontrivial region $(0,B_{K-1})$ for the
subsidy $m$ is compact. A sufficient and necessary condition of indexability
for our model with an infinite state space is given in the next subsection.

###  2.4 An Equivalent Condition for Indexability

In this subsection, we establish a sufficient and necessary condition for
indexability by requiring the decision boundary $C(m)$ to satisfy certain
properties. Furthermore, we verify this equivalent condition to prove the
indexability of our problem when $\beta\leq 0.5$.

###### Theorem 2.4

Let $\Pi^{*}_{sa}(m)$ denote the set of all optimal single-arm policies
achieving $V_{\beta,m}(\omega)$ with initial belief state $\omega$. Define the
passive time

$\displaystyle
D_{\beta,m}(\omega){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\max_{\pi^{*}_{sa}(m)\in\Pi^{*}_{sa}(m)}\mathbb{E}_{\pi^{*}_{sa}(m)}[\sum_{t=1}^{\infty}\beta^{t-1}\mathbbm{1}(u(t)=0)|\omega(1)=\omega].$
(22)

The right derivative of the value function $V_{\beta,m}(\omega)$ with $m$,
denoted by $\frac{dV_{\beta,m}(\omega)}{(dm)^{+}}$, exists at every value of
$m$ and

$\displaystyle\left.\frac{dV_{\beta,m}(\omega)}{(dm)^{+}}\right|_{m=m_{0}}=D_{\beta,m_{0}}(\omega).$
(23)

Furthermore, the single-armed bandit is indexable if and only if for all
values of $\omega$ and $m_{\omega}$ such that $\omega\in C(m_{\omega})$, we
have

$\displaystyle\left.\frac{dV_{\beta,m}(\omega;u=0)}{(dm)^{+}}\right|_{m=m_{\omega}}\geq\left.\frac{dV_{\beta,m}(\omega;u=1)}{(dm)^{+}}\right|_{m=m_{\omega}},$
(24)

and for any $\omega\in C(m_{\omega})$ with the equality true in (24), there
exists a $\Delta m(\omega)>0$ such that

$\displaystyle V_{\beta,m}(\omega;u=0)\geq
V_{\beta,m}(\omega;u=1),~{}\quad\forall~{}m\in(m_{\omega}+\Delta m(\omega)).$
(25)

The proof will be given in the e-companion to this paper.

Remark

  * •

Theorem 2.4 establishes a crucial relation between the value function
$V_{\beta,m}(\omega)$ and the passive time $D_{\beta,m}(\omega)$ as its right
derivative. The convexity established in Lemma 2.2 then implies the monotonic
property of $D_{\beta,m}(\omega)$ as $m$ increases. However, the increase of
$D_{\beta,m}(\omega)$ needs not to be continuous. In the proof of Theorem 2.4,
we have shown the right continuity of $D_{\beta,m}(\omega)$ but not the left
one. These jumping points are essentially caused by the case where the points
in the belief state space may not join the passive set $P(m)$ in a continuous
sense. Specifically, if we fix the initial belief state $\omega$, the arm
state will move in a countable set as a discrete process. Under the optimal
policy that achieves the passive time defined in (22) and indexability, it is
possible that when $m$ increases by a sufficiently small amount, the policy
remains unchanged, i.e., the partition of active and passive sets for the
countable state space is the same. Consequently, the passive time
$D_{\beta,m}(\omega)$ remains a constant during this increasing period of the
subsidy. However, as $m$ keeps increasing, new states would join the passive
set and cause a jump in $D_{\beta,m}(\omega)$. The discontinuity of
$D_{\beta,m}(\omega)$ poses a question: how should one make the continuation
of $D_{\beta,m}(\omega)$ such that constraint (9) must be satisfied for the
relaxed version of the multi-armed bandit problem? The technique is to use
nondeterministic optimal policies: for believe states in the decision boundary
$C(m)$ that causes discontinuities in $D_{\beta,m}(\omega)$, we activate the
arm with certain probability $\rho\in[0,1]$ and make it passive with
probability $1-\rho$. As $\rho$ decreases from $1$ to $0$, the corresponding
policies provide a continuation of $D_{\beta,m}(\omega)$. For a detailed
exposition of this randomization technique in solving the original multi-armed
bandit problem under the relaxed constraint, see Liu 2020 that considers a
more general model of infinite arm state spaces.

###### Theorem 2.5

The restless bandit is indexable if $\beta\leq 0.5$.

The proof will be given in the e-companion to this paper.

However, it is difficult to verify $\eqref{eq:diffIdx}$ and
$\eqref{eq:diffIdx1}$ when $\beta>0.5$. This requires further analysis on the
passive time $D_{\beta,m}(\omega)$ as well as the value function
$V_{\beta,m}(\omega)$. If we can characterize the boundary function $C(m)$ of
subsidy $m$, then for each $\omega$, we may obtain the first crossing time
$L(\omega,C(m))$ when it enters the active set under consecutive passive
actions:

$\displaystyle
L(\omega,C(m)){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\min_{0\leq
k<\infty}\\{k:~{}~{}\mathcal{T}^{k}(\omega)\in A(m)\\}.$ (26)

Define
$\mathcal{T}^{0}(\omega){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\omega$ and
if $\mathcal{T}^{k}(\omega)\notin A(m)$ for all $k\geq 0$, we set
$L(\omega,C(m))=+\infty$. It is clear that for any $\omega\in C(m)$, we have

$\displaystyle V_{\beta,m}(\omega)$ $\displaystyle=\omega
B^{\prime}+\beta\omega(V_{\beta,m}(p_{0}),\cdots,V_{\beta,m}(p_{K-1}))^{\prime}{}$
(27)
$\displaystyle=\frac{1-\beta^{L(\omega,C(m))}}{1-\beta}m+\beta^{L(\omega,C(m))}V_{\beta,m}\left(\mathcal{T}^{L(\omega,C(m))}(\omega);u=1\right),$
$\displaystyle
V_{\beta,m}\left(\mathcal{T}^{L(\omega,C(m))}(\omega);u=1\right)$
$\displaystyle=\mathcal{T}^{L(\omega,C(m))}(\omega)B^{\prime}+\beta\mathcal{T}^{L(\omega,C(m))}(\omega)(V_{\beta,m}(p_{0}),\cdots,V_{\beta,m}(p_{K-1}))^{\prime},$
(30) $\displaystyle V_{\beta,m}(p_{k})$
$\displaystyle=\frac{1-\beta^{L(p_{k},C(m))}}{1-\beta}m+\beta^{L(p_{k},C(m))}V_{\beta,m}\left(\mathcal{T}^{L(p_{k},C(m))}(p_{k});u=1\right),{}$
$\displaystyle\quad\forall~{}k\in\\{0,\cdots,K-1\\},$ $\displaystyle
V_{\beta,m}\left(\mathcal{T}^{L(p_{k},C(m))}(p_{k});u=1\right)$
$\displaystyle=\mathcal{T}^{L(p_{k},C(m))}(p_{k})B^{\prime}+\beta\mathcal{T}^{L(p_{k},C(m))}(\omega)(V_{\beta,m}(p_{0}),\cdots,V_{\beta,m}(p_{K-1}))^{\prime},{}$
$\displaystyle\quad\forall~{}k\in\\{0,\cdots,K-1\\}.$

With both $\omega$ and $L(\cdot,C(m))$ fixed and known, the above equation set
is linear and has $2K+3$ equations with $2K+3$ unknowns (value functions and
$m$), so an exact solution for the value function $V_{\beta,m}(\omega)$ is
possible to obtain, as well as the passive time $D_{\beta,m}(\omega)$, and the
subsidy $m$, in terms of $\omega$ and $L(\cdot,C(m))$. However, even if
$L(\cdot,C(m))$ is solved for, such a way in checking indexability and solving
for Whittle index is complex since $L(\cdot,C(m))$ itself is a nonlinear
function and appears as an exponent in the expressions of the value functions.
Furthermore, the function $L(\cdot,C(m))$ may be solved only if $C(m)$ is
sufficiently analyzed which involves dynamic programming on an uncountable
state space. To circumvent these difficulties, we consider a family of
threshold policies that simplifies the analysis of the value functions and
establish an approximation of Whittle index under a relaxed requirement for
indexability, as detailed in Sec. 3.2.

Before concluding this subsection, let us have a brief review on the case of
$K=2$ as considered in Liu and Zhao (2010). In this case, our decision
boundary $C(m)$ is reduced to a single point ($0$-dimensional as also proven
in Lemma 2 in Liu and Zhao 2010)! Given any $\omega^{*}$ in the
$1$-dimensional belief space (i.e., homeomorphic to the interval $[0,1]$), the
solution to $L(\omega,\omega^{*})$ is straightforwardly obtained in closed-
form (Equations (16) and (17) in Liu and Zhao 2010). Consequently, the
indexability and closed-form Whittle index can be established with the closed-
form solutions of the value functions. But these proofs are highly nontrivial
even with the closed-form solutions of the value functions (Liu and Zhao
2010).

For the general case of $K>2$, we do not know $C(m)$ solely by fixing an
$\omega^{*}\in C(m)$ since $C(m)$ contains other (uncountable) points with
unknown locations. Henceforth the first-crossing time $L(\cdot,C(m))$ is not
solved. Nevertheless, we are free to impose some relations among the points in
$C(m)$ to approximate $L(\cdot,C(m))$. This is the key motivation for
generalizing the classical indexability to a relaxed one, as elaborated in the
next subsection.

##  3 Threshold Policies and Relaxed Indexability

As mentioned in Sec. 2.4, the key to analyze the indexability is to solve for
the first crossing time $L(\omega,C(m))$ and subsequently the set of linear
equations for every fixed $\omega$ and $L(\omega,C(m))$ (26–30). Note that the
linear equation set has a coefficient matrix nonlinearly dependent on
$L(\omega,C(m))$ and thus on the belief state. Therefore each belief state
requires a different set of linear equations to solve for its Whittle index,
i.e., the system of these equations is nonlinear over the belief space in
general. Nevertheless, the first step is still to solve for $L(\omega,C(m))$.
In this subsection, we approximate $C(m)$ by a family of linearized threshold
policies to solve for the approximate Whittle index under the framework of
relaxed indexability.

We first give a general definition of threshold policies. A threshold policy
is defined by a mapping $r(\cdot)$ from the belief state space $\mathbb{X}$ to
a space $\mathbb{Y}$ with the order topology such that the binary action
(activate or make passive) at any state $\omega\in\mathbb{X}$ depends only on
the order between $r(\omega)$ and $r(\omega^{*}_{\beta}(m))$ for a fixed
$\omega^{*}_{\beta}(m)\in\mathbb{X}$. This $\omega^{*}_{\beta}(m)$ is called
to be in the threshold of the belief state space with respect to $r(\cdot)$.
Furthermore, we require that the set
$\\{\omega\in\mathbb{X}:r(\omega)=r(\omega^{*}_{\beta}(m))\\}$ to be simply
connected, i.e., it is without any holes or disconnectedness but as a whole
solid piece. Then we call this set as the threshold and the mapping $r(\cdot)$
the threshold function that specifies the threshold policy. In our problem,
the optimal single-arm policy with a fixed subsidy $m$ is a threshold policy
with its threshold function given by
$V_{\beta,m}(\omega;u=1)-V_{\beta,m}(\omega;u=0)$, mapping the belief simplex
space $\mathbb{X}$ to the real line $\mathbb{R}$. Recall that the original
decision boundary $C(m)$ defined in (20) is thus a nonlinear
$(K-2)$-dimensional threshold as it is simply connected (Lemma 2.3).

To approximate the decision boundary $C(m)$, we consider the following linear
threshold function $r(\cdot)$ defined as

$\displaystyle r(\omega){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\omega
B^{\prime}.$ (31)

We immediately observe that the above threshold function linearizes the
original decision boundary $C(m)$: fixing any
$\omega^{*}_{\beta}(m)\in\mathbb{X}$ as a point in the threshold, the entire
threshold is specified by the $(K-2)$-dimensional hyperplane

$\displaystyle\\{\omega\in\mathbb{X}:~{}~{}\omega
B^{\prime}=\omega^{*}_{\beta}(m)B^{\prime}\\}.$ (32)

It is easy to see the hyperplane is reduced to a point when $K=2$ which is
just $\omega^{*}_{\beta}(m)$ itself. In this case, the linearized threshold
policy is equivalent to the optimal policy (Liu and Zhao 2010).

The threshold function $r(\cdot)$ defined in (31) is a simple and intuitive
definition which is identical to the immediate reward function by activating
the arm. As the belief state $\omega$ varies in the $(K-1)$-dimensional
probability space, we measure the attractiveness of activating the arm by the
expected reward that can be immediately obtained under activation. For the
original problem with multiple arms, if they share the same parameters
(homogeneous arms), i.e., the transition matrix $P$ and reward vector $B$ are
arm-independent, this threshold policy on a single arm with subsidy
corresponds to the myopic policy: at each time we activate the $M$ arms that
will yield the highest expected reward. However, for inhomogeneous arms, the
myopic policy may yield a significant performance loss (see Sec. 4.4). It is
thus important to precisely characterize the attractiveness of a state as a
function of the arm parameters. Our attempt is to solving for the subsidy $m$
that makes a belief state $\omega$ as a point in the threshold and define this
$m$ (if exists) as its approximate Whittle index $W(\omega)$. Given the
initial belief state $\omega$ as the threshold, the action
$u_{\beta,m}^{*}(\omega(t))$ to take at $t\geq 1$ is given by:

$u_{\beta,m}^{*}(\omega(t))=\begin{cases}1~{}\text{(active)},\quad\text{if
}r(\omega(t))>r(\omega^{*}_{\beta}(m))\\\ 0~{}\text{(passive)},\quad\text{if
}r(\omega(t))\leq r(\omega^{*}_{\beta}(m))\end{cases}.$ (33)

It is important to observe that when the current arm state is equal to the
threshold, e.g., at $t=1$, we always make the arm passive (for now). This is
because activating the arm does not necessarily yield the same performance
when confined in the family of linearized threshold policies. Nevertheless,
the suboptimality of this threshold policy is alleviated if the belief update
has a sharp slope projected into the real line by (31) and the discount factor
$\beta$ is small, in which case the comparison in (12) is dominated by the
order between the expected immediate reward $\omega B^{\prime}$ and the
subsidy $m$.

###  3.1 The Value Function

Consider the linearized threshold policy $\pi_{\beta,m}$ with
$\omega^{*}_{\beta}(m)$ fixed as a point in the threshold and the belief
points $p_{0},p_{1},\cdots p_{K-1}$. Define

$\displaystyle
L(\omega_{1},\omega^{*}_{\beta}(m)){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\min_{0\leq
k<\infty}\\{k:~{}~{}\mathcal{T}^{k}(\omega_{1})B^{\prime}>\omega^{*}_{\beta}(m)B^{\prime}\\}.$
(34)

The above is just a simplified expression by using $\omega^{*}_{\beta}(m)$ to
delegate the entire decision boundary (compare (26)) because the threshold
function is specified now. If
$\mathcal{T}^{k}(\omega_{1})B^{\prime}\leq\omega_{2}B^{\prime}$ for all $k\geq
0$, we set $L(\omega_{1},\omega_{2})=+\infty$. Under $\pi_{\beta,m}$, we have

$\displaystyle\hat{V}_{\beta,m}(p_{k})$
$\displaystyle=\frac{1-\beta^{L(p_{k},\omega)}}{1-\beta}m+\beta^{L(p_{k},\omega)}\hat{V}_{\beta,m}\left(\mathcal{T}^{L(p_{k},\omega)}(p_{k});u=1\right),{}$
(36) $\displaystyle\quad\forall~{}k\in\\{0,\cdots,K-1\\},$
$\displaystyle\hat{V}_{\beta,m}\left(\mathcal{T}^{L(p_{k},\omega)}(p_{k});u=1\right)$
$\displaystyle=\mathcal{T}^{L(p_{k},\omega)}(p_{k})B^{\prime}+\beta\mathcal{T}^{L(p_{k},\omega)}(\omega)(\hat{V}_{\beta,m}(p_{0}),\cdots,\hat{V}_{\beta,m}(p_{K-1}))^{\prime},{}$
$\displaystyle\quad\forall~{}k\in\\{0,\cdots,K-1\\},$

where the value function $\hat{V}_{\beta,m}(\omega_{1})$ denotes the expected
total discounted reward under $\pi_{\beta,m}$, starting from a belief state
$\omega_{1}$. If $L(\cdot,\omega)$ is solved, the above equation set is linear
and has $2K$ unknowns with $2K$ equations. In this case, we show (36) and (36)
yield a unique solution consisting of
$\\{\hat{V}_{\beta,m}(p_{k})\\}_{k=0}^{K-1}$.

###### Lemma 3.1

Given the first crossing time function $L(\cdot,\omega)$ with
$\omega^{*}_{\beta}(m)=\omega$ fixed as a point in the threshold, the linear
equation set (36) and (36) has a unique solution consisting of the value
functions $\\{\hat{V}_{\beta,m}(p_{k})\\}_{k=0}^{K-1}$ in terms of $\omega$
and $m$.

The proof will be given in the e-companion to this paper.

Remark

  * •

The proof of Lemma 3.1 does not require any particular form of
$L(\cdot,\cdot)$ so for any optimal single-arm policy, equations (30) and (30)
have a unique solution consisting of $\\{V_{\beta,m}(p_{k})\\}_{k=0}^{K-1}$ in
terms of $m$ and $\omega$. For equation (27) that solves for the Whittle index
$m$ for a given belief state $\omega$, the existence of the decision boundary
$C(m)$ under the optimal policy leads to its validity. For the linearized
threshold policy with $\omega^{*}_{\beta}(m)=\omega$ fixed as a point in the
threshold, if we add to (36) and (36) the following additional constraint
similar to (27), then the subsidy $m$ may be solved as an approximated Whittle
index under the threshold policy.

$\displaystyle\hat{V}_{\beta,m}(\omega)$ $\displaystyle=\omega
B^{\prime}+\beta\omega(\hat{V}_{\beta,m}(p_{0}),\cdots,\hat{V}_{\beta,m}(p_{K-1}))^{\prime}=m+\beta\hat{V}_{\beta,m}(\mathcal{T}^{1}(\omega)).$
(37)

Equation (37) essentially requires that there exists a subsidy $m$ such that
taking active and passive actions at the threshold $\omega$ achieve the same
performance by following the threshold policy. In general, this might not hold
and we need to redefine the approximated Whittle index as detailed in Sec.
3.2.

  * •

The value function $\hat{V}_{\beta,m}(\omega)$ with the fixed threshold
$\omega^{*}_{\beta}(m)=\omega$ is a linear function of $m$ as

$\displaystyle\hat{V}_{\beta,m}(\omega)$
$\displaystyle=\frac{1-\beta^{L(\omega,\omega)}}{1-\beta}m+\beta^{L(\omega,\omega)}(\mathcal{T}^{L(\omega,\omega)}(\omega)B^{\prime}+\beta\mathcal{T}^{L(\omega,\omega)}(\omega)(\hat{V}_{\beta,m}(p_{0}),\cdots,\hat{V}_{\beta,m}(p_{K-1}))^{\prime})$
(38)

and $\\{\hat{V}_{\beta,m}(p_{k})\\}_{k=0}^{K-1}$ are linear in $m$ as well,
since $L(\cdot,\omega)$ is independent of $m$ with $\omega$ fixed as a point
in the linearized threshold. Furthermore, the coefficient of $m$ in the linear
expression of $\hat{V}_{\beta,m}(\omega)$ is equal to the expected total
discounted passive time starting from $\omega$ under the threshold policy.
With the indifference at $\omega$ as given in (37), the passive time must be
unique and equal to the derivative of $\hat{V}_{\beta,m}(\omega)$ with $m$
under the threshold policy with $\omega^{*}_{\beta}(m)=\omega$ fixed as a
point in the threshold.

###  3.2 Relaxed Indexability and Approximate Whittle Index

To have a well-defined value function $\hat{V}_{\beta,m}(\omega)$ to calculate
the approximated Whittle index of a belief state $\omega$, we need one more
equation (that is, (37)) that makes active and passive actions
indistinguishable at $\omega$ fixed as a point in the threshold (Lemma 3.1).
Now we introduce the following definition of relaxed indexability:

###### Definition 3.2

A restless multi-armed bandit satisfies the relaxed indexability with respect
to a threshold policy if for each arm state there exists a unique subsidy $m$
such that, when making this state as a point in the threshold, then taking the
passive and active actions at this state followed by the threshold policy
achieve the same performance.

For our model, relaxed indexability is equivalent to the unique solution of
(36), (36) and (37). Recall the linearity of the value function
$\hat{V}_{\beta,m}(\omega_{1})$ with $m$ given a belief state $\omega_{1}$
fixed as a point in the threshold, we take the derivatives of the value
functions in (37) with $m$ and arrive at the following equivalent condition
for relaxed indexability.

###### Theorem 3.3

Define the passive time $\hat{D}_{\beta,m}(\omega_{1})$ under a threshold
policy $\pi_{\beta,m}$ as

$\displaystyle\hat{D}_{\beta,m}(\omega_{1}){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\mathbb{E}_{\pi_{\beta,m}}[\sum_{t=1}^{\infty}\beta^{t-1}\mathbbm{1}(u(t)=0)|\omega(1)=\omega_{1}]=\frac{d\hat{V}_{\beta,m}(\omega_{1})}{dm}.$
(39)

By fixing $\omega^{*}_{\beta}(m)=\omega$ as a point in the threshold and an
$m$-independent function $r(\cdot)$ in (31), the passive time starting from
any initial belief state $\omega_{1}$ is independent of $m$ and denoted by
$\hat{D}_{\beta}(\omega_{1})$. The restless bandit of POMDP satisfies the
relaxed indexability if and only if for any arm, the corresponding single-
armed bandit problem with subsidy $m$ and with any belief state $\omega$ fixed
as a point in the threshold on the arm state space, we have

$\displaystyle\beta\omega(\hat{D}_{\beta}(p_{0}),\cdots,\hat{D}_{\beta}(p_{K-1}))^{\prime}\neq
1+\beta\hat{D}_{\beta}(\mathcal{T}^{1}(\omega)).$ (40)

Under the relaxed indexability, the approximated Whittle index
$\hat{W}(\omega)$ for a belief state $\omega$ is given by

$\hat{W}(\omega)=\frac{\omega B^{\prime}-\beta
g(\omega\textbf{P})\biggl{[}\textbf{I}_{K}+\beta
H(\textbf{P})G(\textbf{P})\biggr{]}B^{\prime}+\beta\omega
H(\textbf{P})G(\textbf{P})B^{\prime}}{1+\beta
f(\omega\textbf{P})+\beta\biggl{[}\beta
g(\omega\textbf{P})-\omega\biggr{]}H(\textbf{P})F(\textbf{P})},$ (41)

where $L(\cdot):=L(\cdot,\omega),\
f(\cdot):=\frac{1-\beta^{L(\cdot)}}{1-\beta},\
g(\omega):=\beta^{L(\omega)}\mathcal{T}^{L(\omega)}(\omega)=\beta^{L(\omega)}\omega\textbf{P}^{L(\omega)}$,
and

$F(\textbf{P}):=\left(\begin{matrix}f(p_{0})\\\ f(p_{1})\\\ \cdots\\\
f(p_{K-1})\end{matrix}\right),\quad
G(\textbf{P}):=\left(\begin{matrix}g(p_{0})\\\ g(p_{1})\\\ \cdots\\\
g(p_{K-1})\end{matrix}\right),\quad
H(\textbf{P})=\biggl{(}\textbf{I}_{K}-\beta G(\textbf{P})\biggr{)}^{-1}.$

The proof will be given in the e-companion to this paper.

Remark

  * •

Fixing any $\omega$ as in the threshold and an initial $\omega_{1}$, Lemma 3
allows us to solve for $\hat{V}_{\beta,m}(\omega_{1})$ as a linear function of
$m$ and its coefficient (derivative) is just $\hat{D}_{\beta,m}(\omega_{1})$.
Thus the relaxed indexability condition (40) is equivalent to requiring that
the denominator of the Whittle index (41) obtained from (37) is nonzero. If
there exists a belief state $\omega$ such that (40) does not hold, we can
simply use $\omega B^{\prime}$ as a substitute for its Whittle index to
measure the attractiveness of activating the arm. For the original multi-armed
bandit problem (6) and (7), starting from the initial belief states for all
arms $\Omega(1)$, we only need to calculate the (approximate) Whittle index
for the state of each arm and select the $M$ arms with the highest Whittle
indices at each time. Since solving for the Whittle index as well as verifying
condition (40) for each arm has a complexity determined by the process of
solving the set of linear equations (36), (36) and (37), we have an efficient
online algorithm for arm selections with a polynomial running time of the arm
internal state size $K$ and a linear running time of the number of arms $N$ at
each time $t$. Specifically, our algorithm has complexity $O(K^{3}NT)$, given
that the first-crossing function $L(\cdot,\omega)$ is solved for any $\omega$
fixed as a point in the threshold.

  * •

Recall the definition of $L(\cdot,\omega)$ in (34). Since
$\mathcal{T}^{k}(\omega_{1})=\omega_{1}\textbf{P}^{k}=\omega_{1}QJ^{k}Q^{-1}$
with $\textbf{P}=QJQ^{-1}$ in its Jordan canonical form, it is possible to
have an analytical solution for $L(\cdot,\omega)$. In Sec 4, we focus on the
case of $K=3$ and obtain detailed forms of $L(\cdot,\omega)$ in various
scenarios. In general, one could use the exhaustion method to search for the
first crossing time with an upper bound on the number of steps. If the number
of search steps exceeds the upper bound, we simply set
$L(\cdot,\omega)=\infty$. As $\beta^{k}$ decreases geometrically with $k$ and
$\omega_{1}\textbf{P}^{k}$ with any belief state $\omega_{1}$ also converges
geometrically with $k$ for regular transition matrices, such a numerical
exhaustion has its practical convenience.

  * •

The relaxed indexability is reduced to the classical one given the threshold
function $V_{\beta,m}(\omega;u=1)-V_{\beta,m}(\omega;u=0)$. First, the
classical indexability implies the unique existence of the minimum $m$ for any
belief state $\omega$ at which the active and passive actions are
indifferent222In case of an interval, we choose the minimum $m$.. On the other
hand, the unique existence of $m$ under the relaxed indexability implies the
monotonic property of the passive set, for otherwise there will be two
different values of $m$ that pushes some $\omega$ to the passive set as $m$
increases from $-\infty$ to $+\infty$ due to the continuity of the value
functions. For $K=2$, the relaxed indexability relative to the linearized
threshold function is equivalent to the classical indexability as the
threshold consists of only one point.

###  3.3 The General Algorithm

In this subsection, we present the general algorithm based on the approximate
Whittle index under the relaxed indexability relative to the linearized
threshold function, as detailed in Algorithm 1.

Algorithm 1 Whittle Index Policy

Input: time period $T$, arm number $N$, active arm number $M$
Input: initial belief state $\omega_{n}(1)$, transition matrix
$\textbf{P}^{(n)}$, reward vector $B_{n},~{}n=1,...,N$
Input: discount factor $\beta$, first-crossing search maximum $l_{max}$

1:for $t=1,2,...,T$ do

2: for $n=1,...,N$ do

3: For each $i$, do a binary search for
$L\left(\omega_{n}(t)\textbf{P}^{(n)},\omega_{n}(t)\right)$ and
$L\left(p^{(n)}_{i},\omega_{n}(t)\right)$ in $\\{1,\ldots,l_{max}\\}$

4: For any value of $L(\cdot,\cdot)$ not found in $\\{1,\ldots,l_{max}\\}$,
set it to $+\infty$

5: Compute
$f(p^{(n)}_{i})=\frac{1-\beta^{L\left(p^{(n)}_{i},\omega_{n}(t)\right)}}{1-\beta},\quad
i=0,1,2,\cdots,K-1$

6: Set
$F(\textbf{P}^{(n)})=[f(p^{(n)}_{0}),f(p^{(n)}_{1}),f(p^{(n)}_{2}),\cdots,f(p^{(n)}_{K-1})]^{\prime}$

7: Compute
$g(p^{(n)}_{i})=\beta^{L\left(p^{(n)}_{i},\omega_{n}(t)\right)}\omega_{n}(t)(\textbf{P}^{(n)})^{L\left(p^{(n)}_{i},\omega_{n}(t)\right)},\quad
i=0,1,2,\cdots,K-1$

8: Set
$G(\textbf{P}^{(n)})=[g(p^{(n)}_{0}),g(p^{(n)}_{1}),g(p^{(n)}_{2}),\cdots,g(p^{(n)}_{K-1})]^{\prime}$
and $H(\textbf{P}^{(n)})=\left(\textbf{I}_{K}-\beta
G(\textbf{P}^{(n)})\right)^{-1}$

9: Compute
$f(\omega_{n}(t)\textbf{P}^{(n)})=\frac{1-\beta^{L\left(\omega_{n}(t)\textbf{P}^{(n)},\omega_{n}(t)\right)}}{1-\beta}$

10: Compute
$g(\omega_{n}(t)\textbf{P}^{(n)})=\beta^{L\left(\omega_{n}(t)\textbf{P}^{(n)},\omega_{n}(t)\right)}\omega_{n}(t)(\textbf{P}^{(n)})^{L\left(\omega_{n}(t)\textbf{P}^{(n)},\omega_{n}(t)\right)+1}$

11: Define $A{\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,1+\beta
f(\omega_{n}(t)\textbf{P}^{(n)})+\beta\biggl{[}\beta
g(\omega_{n}(t)\textbf{P}^{(n)})-\omega_{n}(t)\biggr{]}H(\textbf{P}^{(n)})F(\textbf{P}^{(n)})$

12: Set $W(\omega_{n}(t))=\omega_{n}(t)B_{n}^{\prime}$ and skip Step 13 if
$A=0$

13: Compute $W(\omega_{n}(t))=\frac{\omega_{n}(t)B_{n}^{\prime}-\beta
g(\omega_{n}(t)\textbf{P}^{(n)})\biggl{[}\textbf{I}_{K}+\beta
H(\textbf{P}^{(n)})G(\textbf{P}^{(n)})\biggr{]}B_{n}^{\prime}+\beta\omega_{n}(t)H(\textbf{P}^{(n)})G(\textbf{P}^{(n)})B_{n}^{\prime}}{1+\beta
f(\omega_{n}(t)\textbf{P}^{(n)})+\beta\biggl{[}\beta
g(\omega_{n}(t)\textbf{P}^{(n)})-\omega_{n}(t)\biggr{]}H(\textbf{P}^{(n)})F(\textbf{P}^{(n)})}$

14: Choose the top $M$ arms with the largest Whittle indices
$W(\omega_{n}(t))$

15: Observe the states $S_{n}(t)$ of the selected $M$ arms and accrue the
reward

16: for $n=1,...,N$ do

17: if arm $n$ is active then

18:
$\omega_{n}(t+1)=\left[p^{(n)}_{S_{n}(t),0},p^{(n)}_{S_{n}(t),1},p^{(n)}_{S_{n}(t),2},\cdots,p^{(n)}_{S_{n}(t),K-1}\right]$

19: else

20: $\omega_{n}(t+1)=\omega_{n}(t)\textbf{P}^{(n)}$

##  4 The Case of $K=3$

In this section, we consider the case that an arm has a $2$-dimensional belief
state space, i.e., the internal Markov chain has 3 states. For simplicity of
presentation, we assume that the Markov chain is irreducible and aperiodic,
thus having a unique stationary (limiting) distribution.

###  4.1 The Jordan Canonical Form

To compute $L(\cdot,\omega)$, it is crucial to analyze the form of
$\textbf{P}^{k}$ with $k$. A general approach is to use the Jordan canonical
form of the stochastic matrix when computing its power. It is well known that
any $K\times K$ square matrix P can be written in its Jordan form as

$\displaystyle\textbf{P}=QJQ^{-1}=Q\left(\begin{matrix}J_{0}&\\\ ~{}&\ddots\\\
~{}&~{}&J_{V-1}\end{matrix}\right)Q^{-1},\quad
J_{v}=\left(\begin{matrix}\lambda_{v}&~{}1&\\\ &~{}\lambda_{v}&~{}\ddots&\\\
&&~{}~{}\ddots&~{}1\\\ &&&~{}~{}\lambda_{v}\end{matrix}\right),$ (42)

where $Q$ is a square matrix of full rank $K$ and the upper diagonal
$K_{v}\times K_{v}$ matrix $J_{v}$ is the $v$-th Jordan block of size
$K_{v}~{}(1\leq K_{v}\leq K)$ with the eigenvalue $\lambda_{v}$ and
$\sum_{v=0}^{V-1}=K$. Note that if $K_{v}=1$ then the Jordan block is simply a
scalar $(\lambda_{v})$ and different blocks can have the same eigenvalue,
i.e., there may exist $0\leq v_{1}\neq v_{2}\leq V-1$ such that
$\lambda_{v_{1}}=\lambda_{v_{2}}$. The $k$th power of P can thus be computed
as

$\displaystyle\textbf{P}^{k}=Q\left(\begin{matrix}J_{0}^{k}&\\\ ~{}&\ddots\\\
~{}&~{}&J_{V-1}^{k}\end{matrix}\right)Q^{-1},\quad
J_{v}^{k}=\left(\begin{matrix}\lambda_{v}^{k}&\binom{k}{1}\lambda_{v}^{k-1}&\binom{k}{2}\lambda_{v}^{k-2}&\cdots&\binom{k}{K_{v}-1}\lambda_{v}^{k-K_{v}+1}\\\
0&\lambda_{v}^{k}&\binom{k}{1}\lambda_{v}^{k-1}&\cdots&\binom{k}{K_{v}-2}\lambda_{v}^{k-K_{v}+2}\\\
\vdots&\vdots&\ddots&\ddots&\vdots\\\
0&0&\cdots&\lambda_{v}^{k}&\binom{k}{1}\lambda_{v}^{k-1}\\\
0&0&\cdots&0&\lambda_{v}^{k}\\\ \end{matrix}\right).$ (43)

For a finite irreducible and aperiodic Markov chain, the transition matrix P
is regular, i.e., there exists an integer $k\geq 1$ such that
$\textbf{P}^{k}>0$ (element-wise). Therefore its Perron-Frobenius eigenvalue
$\lambda_{pf}=1$ has algebraic multiplicity $1$, i.e., the Jordan block
associated with the eigenvalue $1$ is unique and of size $1$. Furthermore, any
other eigenvalue $\lambda_{v}\neq 1~{}(1\leq v\leq K)$ of P satisfies
$|\lambda_{v}|<1$. In this case, the Markov chain has a unique stationary
distribution to which $\omega_{1}\textbf{P}^{k}$ converges at a geometric rate
as $k\rightarrow\infty$ for any belief sate $\omega_{1}$.

In the case of $K=3$, the Jordan canonical form of the transition matrix P
takes one of the following two forms (assuming irreducible and aperiodic
Markov chains):

  * 1.

P has $3$ linearly independent eigenvectors: there exist
$\lambda_{1},\lambda_{2}\in\mathbb{R}$ or
$\lambda_{1}=\overline{\lambda_{2}}\in\mathbb{C}$ with
$|\lambda_{1}|,|\lambda_{2}|\in[0,1)$,

$J_{(1)}=\left(\begin{matrix}1&0&0\\\ 0&\lambda_{1}&0\\\
0&0&\lambda_{2}\end{matrix}\right);$ (44)

  * 2.

P has $2$ linearly independent eigenvectors: there exists
$\lambda_{1}\in\mathbb{R},~{}|\lambda_{1}|\in[0,1)$,

$J_{(2)}=\left(\begin{matrix}1&0&0\\\ 0&\lambda_{1}&1\\\
0&0&\lambda_{1}\end{matrix}\right).$ (45)

Since the eigenvalue $1$ corresponds to a single Jordan block of size $1$
under our assumption, the matrix P has at least $2$ linearly independent
eigenvectors.

###  4.2 The $k$-Step Reward Function

Fix a belief state $\omega$. Define the $k$-step reward function as

$\displaystyle
h(k)=\mathcal{T}^{k}(\omega)B^{\prime}=\omega\textbf{P}^{k}B^{\prime},\quad
k\geq 0.$ (46)

To analyze $L(\omega,\omega^{*})$ for any threshold $\omega^{*}$, we only need
to find out the maximum of $h(k)$ and if it exceeds $\omega^{*}B^{\prime}$,
the first $k$ that makes $h(k)>\omega^{*}B^{\prime}$. In the following lemma,
we show that $h(k)$ can only take three forms and then establish a detailed
form of $L(\omega,\omega^{*})$ for the three cases respectively in Sec. 4.3.

###### Lemma 4.1

The $k$-step reward function $h(k)$ takes one of the following three forms:

  * 1.

P has only real eigenvalues and $3$ linearly independent eigenvectors:

$h(k)=a_{1}b_{1}^{k}+a_{2}b_{2}^{k}+c,\quad
a_{1},b_{1},a_{2},b_{2},c\in\mathbb{R},\ |b_{1}|,|b_{2}|<1;$

  * 2.

P has only real eigenvalues and $2$ linearly independent eigenvectors:

$h(k)=ab^{k}+ckb^{k-1}+d,\quad a,b,c,d\in\mathbb{R},\ |b|<1;$

  * 3.

P has a pair of conjugate complex eigenvalues:

$h(k)=a^{\prime}A^{k}\sin(k\theta+b^{\prime})+c^{\prime},\quad
a^{\prime},A,b^{\prime},c^{\prime},\theta\in\mathbb{R},\ A\in(0,1),\
a^{\prime}\geq 0,\ \theta\in(0,2\pi),\ b^{\prime}\in[0,2\pi).$

The proof will be given in the e-companion to this paper.

###  4.3 The Computation of $L(\omega,\omega^{*})$

In the following theorem, we give the forms of the first crossing time
$L(\omega,\omega^{*})$ for various cases mentioned in Lemma 4.1.

###### Theorem 4.2

Fix $\omega$ and $\omega^{*}$. Let
$r^{*}{\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\omega^{*}B^{\prime}$. The
first crossing time $L(\omega,\omega^{*})$ takes following forms:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}0,\quad\text{if}~{}h(0)>r^{*}\\\
1,\quad\text{if}~{}h(1)>r^{*}\geq h(0)\\\
2,\quad\text{if}~{}h(2)>r^{*}\geq\max\\{h(0),h(1)\\}\end{cases},$ (47)

where $h(k)$ is the $k$-step reward function that depends on $\omega$. The
other cases are summarized below.

  * 1.

P has only real eigenvalues and $3$ linearly independent eigenvectors:
$h(k)=a_{1}b_{1}^{k}+a_{2}b_{2}^{k}+c$.

    * 1.1

$b_{1}=b_{2}\neq 0~{}\&\&~{}b_{1}>0~{}\&\&~{}a_{1}+a_{2}<0$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\lfloor\log_{b_{1}}^{\frac{c-r^{*}}{-(a_{1}+a_{2})}}\rfloor+1,\quad\text{if}~{}h(0)\leq
r^{*}<c\\\ \infty,\quad\text{if}~{}r^{*}\geq c\end{cases};$ (48)

    * 1.2

$b_{1}=b_{2}\neq 0~{}\&\&~{}(b_{1}<0~{}||~{}a_{1}+a_{2}\geq 0)$:
$L(\omega,\omega^{*})=\infty$ if $r^{*}\geq\max\\{h(0),h(1)\\}$;

    * 1.3

$a_{1}b_{1}=0~{}\&\&~{}b_{2}>0~{}\&\&~{}a_{2}<0$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\lfloor\log_{b_{2}}^{\frac{c-r^{*}}{-a_{2}}}\rfloor+2,\quad\text{if}~{}\max\\{h(0),h(1)\\}\leq
r^{*}<c\\\ \infty,\quad\text{if}~{}r^{*}\geq\max\\{h(0),c\\}\end{cases};$ (49)

    * 1.4

$a_{1}b_{1}=0~{}\&\&~{}(b_{2}\leq 0~{}||~{}a_{2}\geq 0)$:
$L(\omega,\omega^{*})=\infty$ if $r^{*}\geq\max\\{h(0),h(1),h(2)\\}$;

    * 1.5

$a_{2}b_{2}=0~{}\&\&~{}b_{1}>0~{}\&\&~{}a_{1}<0$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\lfloor\log_{b_{1}}^{\frac{c-r^{*}}{-a_{1}}}\rfloor+2,\quad\text{if}~{}\max\\{h(0),h(1)\\}\leq
r^{*}<c\\\ \infty,\quad\text{if}~{}r^{*}\geq\max\\{h(0),c\\}\end{cases};$ (50)

    * 1.6

$a_{2}b_{2}=0~{}\&\&~{}(b_{1}\leq 0~{}||~{}a_{1}\geq 0)$:
$L(\omega,\omega^{*})=\infty$ if $r^{*}\geq\max\\{h(0),h(1),h(2)\\}$;

    * 1.7

$a_{1},a_{2},b_{1},b_{2}>0$: $L(\omega,\omega^{*})=\infty$ if $r^{*}\geq
h(0),h(1)$;

    * 1.8

$a_{1}<0,a_{2}>0,b_{1}>b_{2}>0$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}k>\max\\{\lceil\log_{\frac{b_{1}}{b_{2}}}^{-\frac{a_{2}(1-b_{2})}{a_{1}(1-b_{1})}}\rceil,0\\},~{}h(k)>r^{*}\\},\quad\text{if}~{}h(0)\leq
r^{*}<c\\\ \infty,\quad\text{if}~{}r^{*}\geq\max\\{h(0),c\\}\end{cases};$ (51)

    * 1.9

$a_{1}<0,a_{2}>0,b_{2}>b_{1}>0$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}0<k\leq\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{0}}\rfloor+1,~{}h(k)>r^{*}\\},\quad\text{if}~{}z_{0}<1~{}\&\&~{}h(\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{0}}\rfloor+1)>r^{*}\geq
h(0)\\\ \infty,\quad\text{if}~{}(z_{0}\geq 1\&\&r^{*}\geq
h(0))~{}||~{}(z_{0}<1~{}\&\&~{}h(\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{0}}\rfloor+1)\leq
r^{*})\end{cases}$ (52)

where $z_{0}=-\frac{a_{2}(1-b_{2})}{a_{1}(1-b_{1})}$;

    * 1.10

$b_{1}<0,a_{1},a_{2},b_{2}>0$: $L(\omega,\omega^{*})=\infty$ if $r^{*}\geq
h(0)$;

    * 1.11

$a_{1},b_{1}<0,a_{2},b_{2}>0$: $L(\omega,\omega^{*})=\infty$ if
$r^{*}\geq\max\\{h(0),h(1)\\}$;

    * 1.12

$a_{2},b_{1}<0,a_{1},b_{2}>0,|b_{1}|>b_{2}$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}0<k\leq\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor+2,~{}h(k)>r^{*}\\},\quad\text{if}~{}z_{1}\geq
1~{}\&\&~{}h(\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor+2)>r^{*}\geq
h(0)\\\ \infty,\quad\text{if}~{}(z_{1}<1\&\&r^{*}\geq h(0))~{}||~{}(z_{1}\geq
1~{}\&\&~{}h(\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor+2)\leq
r^{*})\end{cases}$ (53)

where $z_{1}=-\frac{a_{2}(1-b_{2}^{2})}{a_{1}(1-b_{1}^{2})}$;

    * 1.13

$a_{2},b_{1}<0,a_{1},b_{2}>0,|b_{1}|<b_{2}$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}k\geq\max\\{\lceil\log_{\frac{b_{1}}{b_{2}}}^{-\frac{a_{2}(1-b_{2}^{2})}{a_{1}(1-b_{1}^{2})}}\rceil,1\\},~{}h(k)>r^{*}\\},\quad\text{if}~{}h(0)\leq
r^{*}<c\\\ \infty,\quad\text{if}~{}\max\\{h(0),c\\}\leq r^{*}\end{cases};$
(54)

    * 1.14

$a_{2},b_{1}<0,a_{1},b_{2}>0,|b_{1}|=b_{2}$:

$\displaystyle L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}k\geq
1,~{}h(k)>r^{*}\\},\quad\text{if}~{}h(0)\leq r^{*}<c\\\
\infty,\quad\text{if}~{}\max\\{h(0),c\\}\leq r^{*}\end{cases};$ (55)

    * 1.15

$b_{1},b_{2}<0,a_{1},a_{2}>0$: $L(\omega,\omega^{*})=\infty$ if $r^{*}\geq
h(0)$;

    * 1.16

$b_{1},b_{2}>0,a_{1},a_{2}<0$:

$\displaystyle L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}k\geq
0,~{}h(k)>r^{*}\\},\quad\text{if}~{}r^{*}<c\\\ \infty,\quad\text{if}~{}c\leq
r^{*}\end{cases};$ (56)

    * 1.17

$a_{1},a_{2},b_{1}<0,b_{2}>0,|b_{1}|>b_{2}$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}0<k\leq\lfloor\log_{\frac{-b_{1}}{b_{2}}}^{z_{2}}\rfloor+2,~{}h(k)>r^{*}\\},\quad\text{if}~{}z_{2}>\frac{-b_{1}}{b_{2}}~{}\&\&~{}h(\lfloor\log_{\frac{-b_{1}}{b_{2}}}^{z_{2}}\rfloor+2)>r^{*}\geq
h(0)\\\ \infty,\quad\text{if}~{}(z_{2}\leq\frac{-b_{1}}{b_{2}}\&\&r^{*}\geq
h(1))~{}||~{}(z_{2}>\frac{-b_{1}}{b_{2}}~{}\&\&~{}h(\lfloor\log_{\frac{-b_{1}}{b_{2}}}^{z_{2}}\rfloor+2)\leq
r^{*})\end{cases}$ (57)

where $z_{2}=\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}$;

    * 1.18

$a_{1},a_{2},b_{1}<0,b_{2}>0,|b_{1}|<b_{2}$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}k\geq\max\\{\lceil\log_{\frac{-b_{1}}{b_{2}}}^{z_{2}}\rceil,1\\},~{}h(k)>r^{*}\\},\quad\text{if}~{}h(1)\leq
r^{*}<c\\\ \infty,\quad\text{if}~{}\max\\{h(1),c\\}\leq r^{*}\end{cases}$ (58)

where $z_{2}=\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}$;

    * 1.19

$a_{1},a_{2},b_{1}<0,b_{2}>0,|b_{1}|=b_{2}$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}k>1,~{}h(k)>\omega^{*}\\},\quad\text{if}~{}h(1)\leq
r^{*}<c\\\ \infty,\quad\text{if}~{}\max\\{h(1),c\\}\leq r^{*}\end{cases};$
(59)

    * 1.20

$a_{2},b_{1},b_{2}<0,a_{1}>0,|b_{1}|>|b_{2}|$:

$\displaystyle L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}1\leq
k\leq\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor_{e}+2,~{}h(k)>r^{*}\\},\quad\text{if}~{}z_{1}>1~{}\&\&~{}h(0)\leq
r^{*}<h(\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor_{e}+2)\\\
\infty,\quad\text{if}~{}(z_{1}>1~{}\&\&~{}\max\\{h(0),h(1),h(\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor_{e}+2)\\}\leq
r^{*})~{}||~{}(z_{1}\leq 1~{}\&\&~{}h(0)\leq r^{*})\end{cases}$ (60)

where $z_{1}=-\frac{a_{2}(1-b_{2}^{2})}{a_{1}(1-b_{1}^{2})}$ and $\lfloor
n\rfloor_{e}$ denotes the maximum even integer not exceeding $n$;

    * 1.21

$a_{2},b_{1},b_{2}<0,a_{1}>0,|b_{1}|<|b_{2}|$:

$\displaystyle L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}1\leq
k\leq\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor_{o}+2,~{}h(k)>r^{*}\\},\quad\text{if}~{}z_{1}<\frac{b_{1}}{b_{2}}~{}\&\&~{}h(0)\leq
r^{*}<h(\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor_{o}+2)\\\
\infty,\quad\text{if}~{}(z_{1}\geq\frac{b_{1}}{b_{2}}~{}\&\&~{}\max\\{h(0),h(1)\\}\leq
r^{*})~{}||~{}(z_{1}<\frac{b_{1}}{b_{2}}~{}\&\&~{}\\{h(0),h(1),h(\lfloor\log_{\frac{b_{1}}{b_{2}}}^{z_{1}}\rfloor_{o}+2)\\}\leq
r^{*})\end{cases}$ (61)

where $z_{1}=-\frac{a_{2}(1-b_{2}^{2})}{a_{1}(1-b_{1}^{2})}$ and $\lfloor
n\rfloor_{o}$ denotes the maximum odd integer not exceeding $n$;

    * 1.22

$a_{2},b_{1},b_{2}<0,a_{1}<0$: $L(\omega,\omega^{*})=\infty$ if
$\omega^{*}\geq h(1)$;

    * 1.23

any other case, which is symmetric to one of the above and omitted here.

  * 2.

P has only real eigenvalues and $2$ linearly independent eigenvectors:
$h(k)=ab^{k}+ckb^{k-1}+d$.

    * 2.1

$b,c>0$:

$\displaystyle L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}0\leq k<\lceil
z_{3}\rceil+1,~{}h(k)>r^{*}\\},\quad\text{if}~{}z_{3}>0~{}\&\&~{}h(0)\leq
r^{*}<h(z_{3}+1)\\\ \infty,\quad\text{if}~{}(z_{3}>0~{}\&\&~{}h(z_{3}+1)\leq
r^{*})~{}||~{}(z_{3}\leq 0~{}\&\&~{}h(0)\leq r^{*})\end{cases}$ (62)

where $z_{3}=\frac{ab-ab^{2}-cb}{c(b-1)}$;

    * 2.2

$b>0,c<0$:

$\displaystyle
L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}k\geq\max\\{\lceil
z_{3}\rceil+1,0\\},~{}h(k)>r^{*}\\},\quad\text{if}~{}h(0)\leq r^{*}<d\\\
\infty,\quad\text{if}~{}\max\\{h(0),d\\}\leq r^{*}\end{cases}$ (63)

where $z_{3}=\frac{ab-ab^{2}-cb}{c(b-1)}$;

    * 2.3

$b<0,c<0$:

$\displaystyle L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}1\leq
k\leq\lfloor
z_{4}\rfloor_{e}+2,~{}h(k)>r^{*}\\},\quad\text{if}~{}z_{4}>0~{}\&\&~{}h(0)\leq
r^{*}<h(\lfloor z_{4}\rfloor_{e}+2)\\\
\infty,\quad\text{if}~{}(z_{4}>0~{}\&\&~{}\max\\{h(0),h(1),h(\lfloor
z_{4}\rfloor_{e}+2)\\}\leq r^{*})~{}||~{}(z_{4}\leq 0~{}\&\&~{}h(0)\leq
r^{*})\end{cases}$ (64)

where $z_{4}=\frac{ab-ab^{3}-2cb^{2}}{c(b^{2}-1)}$ and $\lfloor n\rfloor_{e}$
denotes the maximum even integer not exceeding $n$;

    * 2.4

$b<0,c>0$:

$\displaystyle L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}1\leq
k\leq\lfloor
z_{4}\rfloor_{o}+2,~{}h(k)>r^{*}\\},\quad\text{if}~{}z_{4}>1~{}\&\&~{}h(0)\leq
r^{*}<h(\lfloor z_{4}\rfloor_{o}+2)\\\ \infty,\quad\text{if}~{}(z_{4}\leq
1~{}\&\&~{}\max\\{h(0),h(1)\\}\leq
r^{*})~{}||~{}(z_{4}>1~{}\&\&~{}\\{h(0),h(1),h(\lfloor
z_{4}\rfloor_{o}+2)\\}\leq r^{*})\end{cases}$ (65)

where $z_{4}=\frac{ab-ab^{3}-2cb^{2}}{c(b^{2}-1)}$ and $\lfloor n\rfloor_{o}$
denotes the maximum odd integer not exceeding $n$;

    * 2.5

$bc=0$: $h(k)$ is reduced to forms similar to those in (1.1)-(1.6) so details
are omitted .

  * 3.

P has a pair of conjugate complex eigenvalues:
$h(k)=a^{\prime}A^{k}\sin(k\theta+b^{\prime})+c^{\prime}$.

    * 3.1

$d^{\prime}=\frac{r^{*}-c^{\prime}}{a^{\prime}}>0$:

$\displaystyle L(\omega,\omega^{*})=\begin{cases}\min\\{k:~{}0\leq
k<\lceil\log_{A}^{d^{\prime}}\rceil,~{}h(k)>r^{*}\\},\quad\text{if}~{}\log_{A}^{d^{\prime}}>0~{}\&\&~{}\max\\{h(k):~{}0\leq
k<\lceil\log_{A}^{d^{\prime}}\rceil\\}>r^{*}\\\
\infty,\quad\text{if}~{}\log_{A}^{d^{\prime}}\leq
0~{}||~{}(\log_{A}^{d^{\prime}}>0~{}\&\&~{}\max\\{h(k):~{}0\leq
k<\lceil\log_{A}^{d^{\prime}}\rceil\\}\leq r^{*})\end{cases}$ (66)

    * 3.2

$d^{\prime}=\frac{r^{*}-c^{\prime}}{a^{\prime}}<0$:
$L(\omega,\omega^{*})=\min\\{k:~{}k\geq 0,~{}h(k)>r^{*}\\}$;

    * 3.3

$d^{\prime}=\frac{r^{*}-c^{\prime}}{a^{\prime}}=0,b^{\prime}\in(0,\pi)$:
$L(\omega,\omega^{*})=0$;

    * 3.4

$d^{\prime}=\frac{r^{*}-c^{\prime}}{a^{\prime}}=0,\theta=\pi,b^{\prime}\in\\{0,\pi\\}$:
$L(\omega,\omega^{*})=\infty$;

    * 3.5

$d^{\prime}=\frac{r^{*}-c^{\prime}}{a^{\prime}}=0,\theta\neq\pi,b^{\prime}=0$:
$L(\omega,\omega^{*})=\lfloor\frac{\pi}{2\pi-\theta}\rfloor+1$;

    * 3.6

$d^{\prime}=\frac{r^{*}-c^{\prime}}{a^{\prime}}=0,\theta\neq\pi,b^{\prime}=\pi$:
$L(\omega,\omega^{*})=\lfloor\frac{\pi}{\theta}\rfloor+1$;

    * 3.7

$d^{\prime}=\frac{r^{*}-c^{\prime}}{a^{\prime}}=0,\theta\in(0,\pi],b^{\prime}\in(\pi,2\pi)$:
$L(\omega,\omega^{*})=\lfloor\frac{2\pi-b}{\theta}\rfloor+1$;

    * 3.8

$d^{\prime}=\frac{r^{*}-c^{\prime}}{a^{\prime}}=0,\theta\in(\pi,2\pi),b^{\prime}\in(\pi,2\pi)$:
$L(\omega,\omega^{*})=\lfloor\frac{b-\pi}{2\pi-\theta}\rfloor+1$.

The proof will be given in the e-companion to this paper.

###  4.4 Numerical Examples

In this section, we demonstrate the near-optimality of the (approximate)
Whittle index policy. Through extensive numerical examples, we compute the
performance of the optimal policy by dynamic programming and simulate the low-
complexity Whittle index policy by Monte-Carlo runs. The performance of
Whittle index policy has been observed to be quite close to the optimal one
from all these numerical trials. Here we list a few examples in Figures 2, 2,
4, 4, 6 and 6 with their system parameters shown in Tables 1, 2 and 3. The
comparison between the Whittle index policy and the myopic policy in Figures 6
and 6 demonstrates the superiority of the former.

To better illustrate the efficiency of the Whittle index policy, we further
plot its performance versus the myopic policy for large number of arms and
long time horizon. The optimal policy was not plotted due to the curse of
dimensionality for large systems. As observed in Figures 8, 8, 10, 10, 12, 12,
14, 14, 16 and 16 with time horizon $T=100$ and 1000 monte-carlo runs for
smoothing each curve, the Whittle index policy clearly shows a stronger
performance for arm number $N=20,~{}30,~{}40,50~{}\mbox{and}~{}60$,
respectively (two figures for each case). For larger systems or longer time
horizons in consideration, the Whittle index policy becomes more significant
since it has only a linear complexity with the number of arms (as well as with
the length of time horizon), while solving for the optimal policy has an
exponential complexity as the joint-state space grows geometrically with the
number of arms. As times goes, the (approximate) Whittle index policy
maintains a better balance between exploitation and exploration than the
myopic one which only maximizes the immediate reward.

##  5 Conclusion and Future Work

In this paper, we proposed an efficient algorithm to achieve a strong
performance for a class of restless multi-armed bandits arisen in the general
POMDP framework. By formulating the problem with a $(K-1)$-dimensional belief
state space, we extended the Whittle index policy previously studied for the
case of $K=2$ to $K>2$ by introducing the concept of relaxed indexability. An
interesting finding is that through the online computation process for the
first crossing time, all our numerical studies have shown that the relaxed
indexability relative to the linearized threshold function was satisfied.
Future work includes the extensions of Whittle index to more general POMDP
models, e.g., those with observation errors or different state transition
dynamics. Furthermore, the approximation of the decision boundary can be
readily implemented by the classical $t$-step lookahead approach in dynamic
programming with $t$ chosen to control the the tradeoff between the
approximation accuracy and the time complexity (Bertsekas 1987). Specifically,
the $t$-step threshold function is defined as

$\displaystyle
r_{t}(\omega){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,V_{\beta,m,[1,\cdots,t]}(\omega;u=1)-V_{\beta,m,[1,\cdots,t]}(\omega;u=0),$
(67)

where $V_{\beta,m,[1,\cdots,t]}(\cdot)$ denotes the maximum expected reward
obtained over $t$ steps. Obviously our linearized threshold function is
equivalent to the case of $t=1$. The larger $t$ is, the better approximation
to the optimal threshold function since

$\displaystyle r_{t}(\cdot)\rightarrow
V_{\beta,m}(\omega;u=1)-V_{\beta,m}(\omega;u=0),\
\mbox{as}~{}t\rightarrow\infty.$ (68)

So the approximation error to the original decision boundary $C(m)$ converges
to zero as $t\rightarrow\infty$. Nevertheless, the algorithmic complexity
definitely increases with $t$.

Future work also includes a theoretical verification of the relaxed
indexability relative to the linearized threshold function (i.e., $t=1$), the
systematic categorization of threshold functions to build efficient algorithms
for general partially observable RMAB problems, and the analysis on the
duality gap introduced by the relaxation for arm-decoupling (the relaxation to
the expected number of arms to activate).

Figure 1: Experiment 1: machine 1

Figure 2: Experiment 1: machine 2

Figure 3: Experiment 2: machine 1

Figure 4: Experiment 2: machine 2

Figure 5: Experiment 2: machine 3

Figure 6: Experiment 2: machine 4

Figure 7: Large System 1: $N=20$

Figure 8: Large System 2: $N=20$

Figure 9: Large System 3: $N=30$

Figure 10: Large System 4: $N=30$

Figure 11: Large System 5: $N=40$

Figure 12: Large System 6: $N=40$

Figure 13: Large System 7: $N=50$

Figure 14: Large System 8: $N=50$

Figure 15: Large System 7: $N=60$

Figure 16: Large System 8: $N=60$

Table 1: Experiment setting 1 ($\beta=0.9999,B_{i}=[0,2,3],i=1,...,7$) arm machine | 1 | 2
---|---|---
1 | $\textbf{P}^{(1)}=\left(\begin{matrix}0.514&0.321&0.165\\\ 0.123&0.159&0.718\\\ 0.420&0.195&0.385\end{matrix}\right)$ | $\textbf{P}^{(1)}=\left(\begin{matrix}0.519&0.445&0.036\\\ 0.188&0.292&0.520\\\ 0.043&0.292&0.665\end{matrix}\right)$
|  $\omega_{1}(1)=$(0.279, 0.618, 0.103) |  $\omega_{1}(1)=$(0.354, 0.164, 0.482)
2 | $\textbf{P}^{(2)}=\left(\begin{matrix}0.372&0.543&0.085\\\ 0.103&0.633&0.264\\\ 0.417&0.301&0.282\end{matrix}\right)$ | $\textbf{P}^{(2)}=\left(\begin{matrix}0.193&0.534&0.273\\\ 0.275&0.485&0.240\\\ 0.234&0.694&0.072\end{matrix}\right)$
|  $\omega_{2}(1)=$(0.688, 0.024, 0.288) |  $\omega_{2}(1)=$(0.426, 0.188, 0.386)
3 | $\textbf{P}^{(3)}=\left(\begin{matrix}0.405&0.129&0.466\\\ 0.413&0.328&0.259\\\ 0.327&0.502&0.171\end{matrix}\right)$ | $\textbf{P}^{(3)}=\left(\begin{matrix}0.250&0.274&0.476\\\ 0.600&0.242&0.158\\\ 0.271&0.199&0.530\end{matrix}\right)$
|  $\omega_{3}(1)=$(0.489, 0.408, 0.103) |  $\omega_{3}(1)=$(0.333, 0.498, 0.169)
4 | $\textbf{P}^{(4)}=\left(\begin{matrix}0.461&0.272&0.267\\\ 0.555&0.431&0.014\\\ 0.058&0.689&0.253\end{matrix}\right)$ | $\textbf{P}^{(4)}=\left(\begin{matrix}0.721&0.203&0.076\\\ 0.201&0.621&0.178\\\ 0.444&0.319&0.237\end{matrix}\right)$
|  $\omega_{4}(1)=$(0.554, 0.061 , 0.385) |  $\omega_{4}(1)=$(0.455, 0.285, 0.260)
5 | $\textbf{P}^{(5)}=\left(\begin{matrix}0.339&0.427&0.234\\\ 0.161&0.469&0.370\\\ 0.265&0.296&0.439\end{matrix}\right)$ | $\textbf{P}^{(5)}=\left(\begin{matrix}0.161&0.445&0.394\\\ 0.249&0.394&0.357\\\ 0.164&0.363&0.473\end{matrix}\right)$
|  $\omega_{5}(1)=$(0.313, 0.297, 0.390) |  $\omega_{5}(1)=$(0.352, 0.424, 0.224)
6 | $\textbf{P}^{(6)}=\left(\begin{matrix}0.071&0.556&0.373\\\ 0.158&0.308&0.534\\\ 0.412&0.459&0.129\end{matrix}\right)$ | $\textbf{P}^{(6)}=\left(\begin{matrix}0.080&0.279&0.641\\\ 0.027&0.780&0.193\\\ 0.418&0.265&0.317\end{matrix}\right)$
|  $\omega_{6}(1)=$(0.332, 0.305, 0.363) |  $\omega_{6}(1)=$(0.102, 0.893, 0.005)
7 | $\textbf{P}^{(7)}=\left(\begin{matrix}0.427&0.324&0.249\\\ 0.478&0.356&0.166\\\ 0.326&0.490&0.184\end{matrix}\right)$ | $\textbf{P}^{(7)}=\left(\begin{matrix}0.130&0.536&0.334\\\ 0.377&.253&0.370\\\ 0.334&0.120&0.546\end{matrix}\right)$
|  $\omega_{7}(1)=$(0.234, 0.722, 0.044) |  $\omega_{7}(1)=$(0.367, 0.276, 0.357)
Table 2:  Experiment setting 2-1 ($\beta=0.9999$) arm machine | 1 | 2
---|---|---
1 | $\textbf{P}^{(1)}=\left(\begin{matrix}0.036&0.607&0.357\\\ 0.053&0.126&0.821\\\ 0.579&0.359&0.062\end{matrix}\right)$ | $\textbf{P}^{(1)}=\left(\begin{matrix}0.538&0.305&0.157\\\ 0.575&0.097&0.328\\\ 0.346&0.168&0.486\end{matrix}\right)$
|  $\omega_{1}(1)=$(0.284, 0.404, 0.312) |  $\omega_{1}(1)=$(0.462, 0.418, 0.120)
|  $B_{1}=$(0, 1.004, 2.186) |  $B_{1}=$(0, 2.422, 2.698)
2 | $\textbf{P}^{(2)}=\left(\begin{matrix}0.447&0.021&0.532\\\ 0.485&0.164&0.351\\\ 0.461&0.409&0.130\end{matrix}\right)$ | $\textbf{P}^{(2)}=\left(\begin{matrix}0.367&0.114&0.519\\\ 0.798&0.089&0.113\\\ 0.367&0.354&0.279\end{matrix}\right)$
|  $\omega_{2}(1)=$(0.297, 0.361, 0.342) |  $\omega_{2}(1)=$(0.459, 0.528, 0.013)
|  $B_{2}=$(0, 1.155, 2.761) |  $B_{2}=$(0, 2.745, 2.754)
3 | $\textbf{P}^{(3)}=\left(\begin{matrix}0.407&0.200&0.393\\\ 0.435&0.180&0.385\\\ 0.245&0.465&0.290\end{matrix}\right)$ | $\textbf{P}^{(3)}=\left(\begin{matrix}0.218&.015&0.767\\\ 0.849&0.129&0.022\\\ 0.405&0.151&0.444\end{matrix}\right)$
|  $\omega_{3}(1)=$(0.043, 0.421, 0.536) |  $\omega_{3}(1)=$(0.519, 0.413, 0.068)
|  $B_{3}=$(0, 0.437, 0.7826) |  $B_{3}=$(0, 2.917, 2.916)
4 | $\textbf{P}^{(4)}=\left(\begin{matrix}0.087&0.454&0.459\\\ 0.181&0.672&0.147\\\ 0.462&0.492&0.046\end{matrix}\right)$ | $\textbf{P}^{(4)}=\left(\begin{matrix}0.428&0.294&0.278\\\ 0.431&0.022&0.547\\\ 0.011&0.511&0.478\end{matrix}\right)$
|  $\omega_{4}(1)=$(0.642, 0.026, 0.332) |  $\omega_{4}(1)=$(0.113, 0.499, 0.388)
|  $B_{4}=$(0, 0.568, 0.619) |  $B_{4}=$(0, 0.051, 0.503)
5 | $\textbf{P}^{(5)}=\left(\begin{matrix}0.331&0.181&0.488\\\ 0.347&0.117&0.536\\\ 0.245&0.197&0.558\end{matrix}\right)$ | $\textbf{P}^{(5)}=\left(\begin{matrix}0.317&0.413&0.270\\\ 0.376&0.333&0.291\\\ 0.351&0.203&0.446\end{matrix}\right)$
|  $\omega_{5}(1)=$(0.606, 0.017, 0.377) |  $\omega_{5}(1)=$(0.555, 0.400, 0.045)
|  $B_{5}=$(0, 2.448, 2.63 ) |  $B_{5}=$(0, 1.51 , 2.688)
6 | $\textbf{P}^{(6)}=\left(\begin{matrix}0.449&0.008&0.543\\\ 0.782&0.198&0.020\\\ 0.338&0.614&0.048\end{matrix}\right)$ | $\textbf{P}^{(6)}=\left(\begin{matrix}0.320&0.649&0.031\\\ 0.112&0.037&0.851\\\ 0.377&0.364&0.259\end{matrix}\right)$
|  $\omega_{6}(1)=$(0.362, 0.560, 0.078) |  $\omega_{6}(1)=$(0.348, 0.212, 0.440)
|  $B_{6}=$(0, 1.327, 1.945) |  $B_{6}=$(0, 1.623, 1.777)
7 | $\textbf{P}^{(7)}=\left(\begin{matrix}0.067&0.435&0.498\\\ 0.334&0.290&0.376\\\ 0.258&0.483&0.259\end{matrix}\right)$ | $\textbf{P}^{(7)}=\left(\begin{matrix}0.046&0.213&0.741\\\ 0.031&0.430&0.539\\\ 0.238&0.238&0.524\end{matrix}\right)$
|  $\omega_{7}(1)=$(0.296, 0.298, 0.406) |  $\omega_{7}(1)=$(0.483, 0.050, 0.467)
|  $B_{7}=$(0, 1.858, 2.033) |  $B_{7}=$(0, 0.897, 2.443)
Table 3: Experiment setting 2-2 ($\beta=0.9999$) arm machine | 3 | 4
---|---|---
1 | $\textbf{P}^{(1)}=\left(\begin{matrix}0.488&0.258&0.254\\\ 0.012&0.790&0.198\\\ 0.681&0.208&0.111\end{matrix}\right)$ | $\textbf{P}^{(1)}=\left(\begin{matrix}0.413&0.329&0.258\\\ 0.089&0.511&0.400\\\ 0.086&0.309&0.605\end{matrix}\right)$
|  $\omega_{1}(1)=$(0.405,0.415,0.180) |  $\omega_{1}(1)=$(0.486, 0.028, 0.486)
|  $B_{1}=$(0, 2.146, 2.491) |  $B_{1}=$(0, 0.233, 2.853)
2 | $\textbf{P}^{(2)}=\left(\begin{matrix}0.354&0.311&0.335\\\ 0.278&0.027&0.695\\\ 0.502&0.341&0.157\end{matrix}\right)$ | $\textbf{P}^{(2)}=\left(\begin{matrix}0.031&0.171&0.798\\\ 0.678&0.134&0.188\\\ 0.597&0.358&0.045\end{matrix}\right)$
|  $\omega_{2}(1)=$(0.551,0.328,0.121) |  $\omega_{2}(1)=$(0.408, 0.496, 0.096)
|  $B_{2}=$(0, 1.579, 2.444) |  $B_{2}=$(0, 2.358, 2.632)
3 | $\textbf{P}^{(3)}=\left(\begin{matrix}0.342&0.036&0.622\\\ 0.451&0.219&0.330\\\ 0.471&0.073&0.456\end{matrix}\right)$ | $\textbf{P}^{(3)}=\left(\begin{matrix}0.358&0.263&0.379\\\ 0.264&0.249&0.487\\\ 0.400&0.364&0.236\end{matrix}\right)$
|  $\omega_{3}(1)=$(0.555,0.315,0.130) |  $\omega_{3}(1)=$(0.014, 0.247, 0.739)
|  $B_{3}=$(0, 0.286, 0.644) |  $B_{3}=$(0, 0.378, 1.241)
4 | $\textbf{P}^{(4)}=\left(\begin{matrix}0.304&0.639&0.057\\\ 0.457&0.380&0.163\\\ 0.262&0.357&0.381\end{matrix}\right)$ | $\textbf{P}^{(4)}=\left(\begin{matrix}0.598&0.028&0.374\\\ 0.762&0.109&0.129\\\ 0.313&0.391&0.296\end{matrix}\right)$
|  $\omega_{4}(1)=$(0.495,0.117,0.388) |  $\omega_{4}(1)=$(0.490, 0.256, 0.254)
|  $B_{4}=$(0, 2.391, 2.852) |  $B_{4}=$(0, 2.002, 2.374)
5 | $\textbf{P}^{(5)}=\left(\begin{matrix}0.404&0.282&0.314\\\ 0.621&0.106&0.273\\\ 0.204&0.657&0.14\end{matrix}\right)$ | $\textbf{P}^{(5)}=\left(\begin{matrix}0.323&0.177&0.500\\\ 0.174&0.138&0.688\\\ 0.416&0.310&0.274\par\end{matrix}\right)$
|  $\omega_{5}(1)=$(0.474,0.239,0.287) |  $\omega_{5}(1)=$(0.358, 0.501, 0.141)
|  $B_{5}=$(0, 0.111, 1.420) |  $B_{5}=$(0, 1.502, 2.258)
6 | $\textbf{P}^{(6)}=\left(\begin{matrix}0.586&0.024&0.390\\\ 0.455&0.027&0.518\\\ 0.365&0.464&0.171\end{matrix}\right)$ | $\textbf{P}^{(6)}=\left(\begin{matrix}0.424&0.442&0.134\\\ 0.301&0.182&0.517\\\ 0.164&0.360&0.476\end{matrix}\right)$
|  $\omega_{6}(1)=$(0.413,0.388,0.199) |  $\omega_{6}(1)=$(0.263, 0.502, 0.235)
|  $B_{6}=$(0, 0.324, 0.755) |  $B_{6}=$(0, 0.715, 1.022)
7 | $\textbf{P}^{(7)}=\left(\begin{matrix}0.612&0.335&0.053\\\ 0.333&0.486&0.181\\\ 0.483&0.513&0.004\end{matrix}\right)$ | $\textbf{P}^{(7)}=\left(\begin{matrix}0.613&0.136&0.251\\\ 0.454&0.383&0.163\\\ 0.287&0.693&0.020\end{matrix}\right)$
|  $\omega_{7}(1)=$(0.369,0.262,0.369) |  $\omega_{7}(1)=$(0.707, 0.226, 0.067)
|  $B_{7}=$(0, 0.491, 0.797) |  $B_{7}=$(0, 2.013, 2.436)

The author gratefully acknowledges the help from his students, Jiale Zha and
Chengzhong Zhang, for the numerical analysis and figures. The author’s
colleague, Prof. Ting Wu, provided very helpful comments for improving this
paper.

## References

  * Bertsekas (1987) Bertsekas DP (1987) Dynamic Programming: Deterministic and Stochastic Models (Prentice Hall).
  * Bertsimas and Niño-Mora (1996) Bertsimas D, Niño-Mora J (1996) Conservation laws, extended polymatroids and multi-armed bandit problems. Mathematics of Operations Research 21:257–306.
  * Bertsimas and Niño-Mora (2000) Bertsimas D, Niño-Mora J (2000) Restless bandits, linear programming relaxations, and a primal-dual index heuristic. Operations Research 48(1):80–90.
  * Brown and Smith (2020) Brown DB, Simth JE (2020) Index policies and performance bounds for dynamic selection problems. Management Science 66(7):3029–3050.
  * Elmaghraby et al. (2018) Elmaghraby HM, Liu K, Ding Z (2008) Femtocell scheduling as a restless multiarmed bandit problem using partial channel state observation. Proc. of IEEE International Conference on Communications (ICC) 1–6.
  * Frostig and Weiss (2016) Frostig E, Weiss G (2016) Four proofs of Gittins’ multiarmed bandit theorem. Ann. Oper. Res. 241:127–165.
  * Gast et al. (2021) Gast N, Gaujal B, Yan C (2021, working paper) (Close to) Optimal policies for finite horizon restless bandits. https://hal.inria.fr/hal-03262307/file/LP_paper.pdf.
  * Ges (2012) Geschke S (2012) Convex open subsets of $\mathbb{R}^{n}$ are homeomorphic to $n$-dimensional open balls. http://relaunch.hcm.uni-bonn.de/fileadmin/geschke/papers/ConvexOpen.pdf
  * Gittins (1979) Gittins JC (1979) Bandit processes and dynamic allocation indices. J. R. Stat. Soc. 41(2):148–177.
  * Gittins et al. (2011) Gittins JC, Glazebrook KD, Weber RR (2011) Multi-Armed Bandit Allocation Indices (Wiley, Chichester).
  * Gittins and Jones (1974) Gittins JC, Jones DM (1974) A dynamic allocation index for the sequential design of experiments. Progr. Stat. 241–266.
  * Glazebrook et al. (2009) Glazebrook KD, Kirkbride C, Ouenniche J (2009) Index policies for the admission control and routing of impatient customers to heterogeneous service stations. Operations Research 57:975–989.
  * Hodge and Glazebrook (2011) Hodge DJ, Glazebrook KD (2011) Dynamic resource allocation in a multi-product make-to-stock production system, Queueing Syst 67:333–364.
  * Hu and Frazier (2017) Hu W, Frazier PI (2017, working paper) An asymptotically optimal index policy for finite-horizon restless bandits. arXiv preprint https://arxiv.org/abs/1707.00205.
  * Lapiccirella et al. (2011) Lapiccirella FE, Liu K, Ding Z (2011) Multi-channel opportunistic access based on primary ARQ messages overhearing. Proc. of IEEE International Conference on Communications (ICC) 1–5.
  * Le Ny et al. (2008) Le Ny J, Dahleh M, Feron E (2008) Multi-UAV dynamic routing with partial observations using restless bandit allocation indices. Proc. Amer. Control Conf. 4220–4225.
  * Liu (2020) Liu K (2020) Whittle index for restless bandits with expanding state spaces. Numerical Mathematics: A Journal of Chinese Universities 42(4):372–384.
  * Liu et al. (2022) Liu K, Weber RR, Wu T, Zhang C (2022) Low-complexity algorithm for restless bandits with imperfect observations. arXiv preprint https://arxiv.org/abs/2108.03812.
  * Liu et al. (2011) Liu K, Weber RR, Zhao Q (2011) Indexability and Whittle index for restless bandit problems involving reset processes. Proc. of the 50th IEEE Conference on Decision and Control 7690–7696.
  * Liu and Zhao (2008) Liu K, Zhao Q (2008) A restless bandit formulation of opportunistic access: indexability and index Policy. Proc. of IEEE Workshop on Networking Technologies for Software Defined Radio (SDR) Networks 1–5.
  * Liu and Zhao (2010) Liu K, Zhao Q (2010) Indexability of restless bandit problems and optimality of Whittle index for dynamic multichannel access. IEEE Trans. Inform. Theory 56(11):5547–5567.
  * Liu and Zhao (2012) Liu K, Zhao Q (2012) Dynamic intrusion detection in resource-constrained cyber networks. IEEE International Symposium on Information Theory Proceedings 970–974.
  * Liu et-al. (2010) Liu K, Zhao Q, Krishnamachari B (2010) Dynamic multichannel access with imperfect channel state detection. IEEE Trans. Signal Process. 58(5):2795–2808.
  * Munkres (2003) Munkres JR (2003) Topology (Pearson).
  * Niño-Mora (2001) Niño-Mora J (2001) Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab., 33:76–98.
  * Niño-Mora (2007) Niño-Mora J (2007) Dynamic priority allocation via restless bandit marginal productivity indices. TOP, 15:161–198.
  * Papadimitriou and Tsitsiklis (1999) Papadimitriou CH, Tsitsiklis JN (1999) The complexity of optimal queueing network control. Math. Oper. Res. 24(2):293–305.
  * Sondik (1978) Sondik EJ (1978) The optimal control of partially observable Markov processes over the infinite horizon: discounted costs. Operations Research 26(2):282–304.
  * Thompson (1933) Thompson WR (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3/4):275–294.
  * Verloop (2016) Verloop IM (2016) Asymptotically optimal priority policies for indexable and nonindexable restless bandits. The Annals of Applied Probability 26(4):1947-1995.
  * Wang et al. (2014) Wang K, Chen L, Liu Q (2014) On optimality of myopic policy for opportunistic access with nonidentical channels and imperfect sensing. IEEE Trans. Veh. Technol. 63(5):2478–2483.
  * Weber (1992) Weber RR (1992) On the Gittins index for multiarmed bandits. Annals of Probability 2:1024–1033.
  * Weber and Weiss (1990) Weber RR, Weiss G (1990) On an index policy for restless bandits. J. Appl. Probab. 27:637–648.
  * Weber and Weiss (1991) Weber RR, Weiss G (1991) Addendum to ‘On an index policy for restless bandits’. Adv. Appl. Prob. 23:429–430.
  * Whittle (1980) Whittle P (1980) Multi-armed bandits and the Gittins index. J. R. Stat. Soc., Series B 42:143–149.
  * Whittle (1988) Whittle P (1988) Restless bandits: Activity allocation in a changing world. J. Appl. Probab. 25:287–298.
  * Zayas-Cabán et al. (2019) Zayas-Cabán G, Jasin S, Wang G (2019) An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits. Advanced in Applied Probability 51:745–772.
  * Zhao (2019) Zhao Q (2019) Multi-Armed Bandits: Theory and Applications to Online Learning in Networks (Morgan & Claypool publishers).
  * Zhao et al. (2008) Zhao Q, Krishnamachari B, Liu K (2008) On myopic sensing for multichannel opportunistic access: structure, optimality, and performance. IEEE Trans. Wireless Commun. 7(3):5413–5440.

Proofs of Lemmas and Theorems

##  6 Proof of Lemma 2.2.

###### Proof 6.1

Consider a horizon of $T~{}(T\geq 1)$ time slots and define
$V_{\beta,m,1}(\omega)$ as the maximum expected total discounted reward over
$T$ slots that can be obtained starting from initial state $\omega$ at $t=1$:

$\displaystyle V_{\beta,m,1}(\omega)=\max_{\pi\in\Pi_{sa}(T)}$
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{T}\beta^{t-1}\sum_{n=1}^{N}\\{B_{n,S_{n}(t)}\mathbbm{1}(u(t)=1)+m\mathbbm{1}(u(t)=0)\\}],$
(69)

where $\Pi_{sa}(T)$ is the set of single-arm policies that map the belief
state $\omega(t)$ to the action
$u(t)\in\\{1~{}\mbox{(active)},~{}0~{}\mbox{(passive)}\\}$ for
$t=1,2,\cdots,T$. Note that $\omega(1)=\omega$ and an optimal policy
$\pi^{*}_{sa}(T)$ achieving $V_{\beta,m,T}(\omega)$ is generally non-
stationary, i.e., the mapping from $\omega(t)$ to $u(t)$ is dependent on $t$.
Especially when $t=T$, we have only one more step to go and the myopic policy
that maximizes the immediate reward is obviously optimal:

$\displaystyle
u^{*}(T)=\arg\max_{u\in\\{0,1\\}}\\{u\cdot\omega(T)B^{\prime}+(1-u)\cdot
m\\}.$ (70)

Let $V_{\beta,m,t}(\cdot)$ denote the maximum expected total discounted reward
accumulated from slot $t$ to $T$ under $\pi^{*}_{sa}(T)$. We have the
following dynamic equations:

$\displaystyle V_{\beta,m,t}(\omega(t))$ $\displaystyle=$
$\displaystyle\max\left\\{\omega
B^{\prime}+\beta\omega\left(\begin{matrix}V_{\beta,m,t+1}(p_{0})\\\
V_{\beta,m,t+1}(p_{1})\\\ \vdots\\\
V_{\beta,m,t+1}(p_{K-1})\end{matrix}\right),~{}m+V_{\beta,m,t+1}(\mathcal{T}^{1}(\omega(t)))\right\\},\
t\leq T,$ (71) $\displaystyle V_{\beta,m,T+1}(\cdot)$ $\displaystyle\equiv$
$\displaystyle 0.$ (72)

We first prove the properties of $V_{\beta,m}(\omega)$ regarding to $\omega$
with $m$ fixed. Our approach is based on backward induction on $t$ with $T$
fixed and then taking the limit $T\rightarrow\infty$. When $t=T$, it is clear
that $V_{\beta,m,T}(\omega)$ is the maximum of a linear function of $\omega$
and a constant function ($m$), and is thus continuous, convex and piecewise
linear. By the induction hypothesis that $V_{\beta,m,t+1}(\omega)$ is
continuous, convex and piecewise linear, we again have that
$V_{\beta,m,t}(\omega)$ is the maximum of two continuous, convex and piecewise
linear functions and is thus continuous, convex and piecewise linear.
Therefore $V_{\beta,m,t}(\omega)$ is continuous, convex and piecewise linear
in $\omega$ for all $t\in\\{1,2,\cdots,T\\}$. Using
$\|\cdot\|{\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\|\cdot\|_{1}$ norm on
$\mathbb{R}^{K}$ and consider two states $\omega_{1},\omega_{2}$ such that
$\|\omega_{1}-\omega_{2}\|>0$. At $t=T$, we have

$\displaystyle|V_{\beta,m,T}(\omega_{1})-V_{\beta,m,T}(\omega_{2})|$
$\displaystyle=$
$\displaystyle\max\\{\omega_{1}B^{\prime},m\\}-\max\\{\omega_{2}B^{\prime},m\\}.$
(73)

Without loss of generality, assume
$\omega_{1}B^{\prime}\leq\omega_{2}B^{\prime}$. We consider the following 3
cases:
i) if $m<\omega_{1}B^{\prime}$, then

$|V_{\beta,m,T}(\omega_{1})-V_{\beta,m,T}(\omega_{2})|=|\omega_{1}B^{\prime}-\omega_{2}B^{\prime}|\leq
B_{K}\|\omega_{1}-\omega_{2}\|;$

ii) if $\omega_{1}B^{\prime}\leq m\leq\omega_{2}B^{\prime}$, then

$|V_{\beta,m,T}(\omega_{1})-V_{\beta,m,T}(\omega_{2})|\leq
B_{K}\|\omega_{1}-\omega_{2}\|;$

iii) if $m>\omega_{2}B^{\prime}$, then

$|V_{\beta,m,T}(\omega_{1})-V_{\beta,m,T}(\omega_{2})|=0.$

From the above, we have that

$\displaystyle|V_{\beta,m,T}(\omega_{1})-V_{\beta,m,T}(\omega_{2})|$
$\displaystyle\leq$ $\displaystyle B_{K}\|\omega_{1}-\omega_{2}\|.$ (74)

At time $t+1$, we make the following induction hypothesis that

$|V_{\beta,m,t+1}(\omega_{1})-V_{\beta,m,t+1}(\omega_{2})|\leq\frac{1-\beta^{T-t}}{1-\beta}B_{K}\|\omega_{1}-\omega_{2}\|.$

At time $t$, we have, by a similar case analysis as above, that

$\displaystyle|V_{\beta,m,t}(\omega_{1})-V_{\beta,m,t}(\omega_{2})|\leq\frac{1-\beta^{T-t+1}}{1-\beta}B_{K}\|\omega_{1}-\omega_{2}\|.$
(75)

Note that we have used the fact that
$\|\mathcal{T}^{1}(\omega_{1})-\mathcal{T}^{1}(\omega_{2})\|\leq\|\omega_{1}-\omega_{2}\|$.
Therefore, we have that

$\displaystyle|V_{\beta,m,1}(\omega_{1})-V_{\beta,m,1}(\omega_{2})|\leq\frac{1-\beta^{T}}{1-\beta}B_{K}\|\omega_{1}-\omega_{2}\|\leq\frac{1}{1-\beta}B_{K}\|\omega_{1}-\omega_{2}\|.$
(76)

Furthermore, for all $t\in\\{1,2,\cdots,T\\}$, we have that

$\displaystyle|V_{\beta,m,t}(\omega_{1})-V_{\beta,m,t}(\omega_{2})|\leq\frac{1}{1-\beta}B_{K}\|\omega_{1}-\omega_{2}\|.$
(77)

This proves that the finite-horizon value function $V_{\beta,m,t}(\omega)$ is
Lipschitz continuous in $\omega$ with constant $\frac{1}{1-\beta}B_{K}$,
independent of horizon length $T$ and starting point $t$. Fix $t=1$, if we can
show as $T$ goes to infinity $V_{\beta,m,1}(\cdot)$ converges to
$V_{\beta,m}(\cdot)$ pointwise, then $V_{\beta,m}(\cdot)$ must be Lipschitz
continuous with the same constant. This is because that given any two states
$\omega_{1},\omega_{2}$ and any $\epsilon>0$, there exists a positive integer
$T_{0}$ such that

$|V_{\beta,m}(\omega_{1})-V_{\beta,m}(\omega_{2})|\leq
2\epsilon+|V_{\beta,m,1}(\omega_{1})-V_{\beta,m,1}(\omega_{2})|\leq
2\epsilon+\frac{1}{1-\beta}B_{K}\|\omega_{1}-\omega_{2}\|.$

Since $\epsilon>0$ is arbitrary, the Lipschitz continuity of
$V_{\beta,m}(\cdot)$ follows. To prove the convergence of
$V_{\beta,m,1}(\cdot)$ with $T$, we first apply the optimal policy
$\pi_{sa}^{*}(T)$ to the first $T$ slots followed by an (stationary) optimal
policy $\pi^{*}_{sa}$ for the infinite-horizon problem in subsequent time
slots $t>T$, then

$\displaystyle V_{\beta,m}(\omega)\geq
V_{\beta,m,1}(\omega)+\beta^{T}\mathbb{E}[V_{\beta,m}(\omega(T+1))],$ (78)

where the expectation is taken with respect to $\omega(T+1)$ which is
determined by the past observations and actions in the first $T$ slots. It is
clear that $V_{\beta,m}(\cdot)$ is bounded:

$\displaystyle 0\leq V_{\beta,m}(\cdot)\leq\frac{\max\\{B_{K},m\\}}{1-\beta}.$
(79)

From (78) and (79), we know that

$\displaystyle V_{\beta,m,1}(\omega)-V_{\beta,m}(\omega)\leq 0.$ (80)

Now we apply $\pi^{*}_{sa}$ to the finite-horizon problem with length $T$ and
compare the reward accumulated in the $T$ slots:

$\displaystyle V_{\beta,m,1}(\omega)\geq
V_{\beta,m}(\omega)-\beta^{T}\mathbb{E}[V_{\beta,m}(\omega(T+1))].$ (81)

From (79), (80) and (81), we have, for any initial value of $\omega$ at $t=1$,

$\displaystyle-\beta^{T}\frac{\max\\{B_{K},m\\}}{1-\beta}\leq
V_{\beta,m,1}(\omega)-V_{\beta,m}(\omega)\leq 0.$ (82)

Taking the limit $T\rightarrow\infty$, we proved the (uniform) convergence of
$V_{\beta,m,1}(\cdot)$ to $V_{\beta,m}(\cdot)$. Consequently
$V_{\beta,m}(\cdot)$ is Lipschitz continuous. Its convexity is clear as a
limiting function of convex functions.

Now we consider the properties of $V_{\beta,m}(\omega)$ regarding to $m$ with
$\omega$ fixed. By a similar argument as above, we have that
$V_{\beta,m,1}(\omega)$ is convex, continuous and piecewise linear in $m$.
Furthermore, it is Lipschitz continuous in $m$ with constant
$\frac{1}{1-\beta}$, i.e., , for any $m_{1}$ and $m_{2}$,

$|V_{\beta,m_{1},1}(\omega)-V_{\beta,m_{2},1}(\omega)|\leq\frac{1}{1-\beta}|m_{1}-m_{2}|.$

It remains to show the pointwise convergence of $V_{\beta,m,1}(\omega)$ to
$V_{\beta,m}(\omega)$ for every fixed $m$ as $T\rightarrow\infty$. However, it
is a direct result of (82).

##  7 Proof of Lemma 2.3.

###### Proof 7.1

We prove the lemma step-by-step.

Step 1. We first show that $A(m)$ is convex. From (12), (13), (14) and Lemma
2.2, given any $\omega_{1},\omega_{2}\in A(m)$ and $\lambda\in(0,1)$, we have

$\displaystyle V_{\beta,m}(\lambda\omega_{1}+(1-\lambda)\omega_{2};u=1)$
$\displaystyle=$ $\displaystyle\lambda
V_{\beta,m}(\omega_{1};u=1)+(1-\lambda)V_{\beta,m}(\omega_{2};u=1)$ (83)
$\displaystyle>$ $\displaystyle\lambda
V_{\beta,m}(\omega_{1};u=0)+(1-\lambda)V_{\beta,m}(\omega_{2};u=0)$ (84)
$\displaystyle\geq$ $\displaystyle
V_{\beta,m}(\lambda\omega_{1}+(1-\lambda)\omega_{2};u=0).$ (85)

The first equality in the above is due to the linearity of
$V_{\beta,m}(\cdot;u=1)$ by (13), the second last inequality is by Definition
(19), and the last inequality is due to the convexity of $V_{\beta,m}(\cdot)$
established in Lemma 2.2 and the linearity of $\mathcal{T}^{1}(\cdot)$ by (4).
Therefore, the active set $A(m)$ is convex.

Step 2. The openness of $A(m)$ is due to the strict inequality in (19) and the
continuity of the value function established in Lemma 2.2. Since every point
in $A(m)$ has an $\epsilon$-neighborhood as a $(K-1)$-dimensional ball of
$\mathbb{R}^{K-1}$ in $A(m)$, the dimension of $A(m)$ is $K-1$.

Step 3. It is obvious that the closure $\overline{A(m)}$ of the open convex
set $A(m)$ in $\mathbb{X}$ is formed by the linear boundaries of the simplex
space $X$ and $C(m)$. Therefore $C(m)$ is closed and bounded and thus compact
as a subspace of $\mathbb{R}^{K-1}$. The proof that $C(m)$ is a simply
connected $(K-2)$-dimensional subspace of $X$ requires familiarity to the
theory of algebraic topology and is concisely sketched as follows. Since
$\overline{A(m)}$ is also convex, it is homeomorphic to the open
$(K-1)$-dimensional unit ball in $\mathbb{R}^{K-1}$ (Ges 2012). Let $h$ denote
this homeomorphism. Choose the extreme point
$x_{0}=(0,0,\ldots,1)\in\overline{A(m)}-C(m)$. Note that the boundary of
$A(m)$ consists of parts of the $(K-2)$-dimensional linear boundaries
(hyperplanes) of $X$ and $C(m)$. Let $P$ be any of such hyperplanes that
intersect with $C(m)$. Then there is a deformation retract from $P-x_{0}$ to
the intersection $P\cap C(m)$ (i.e., a continuous map from $P-x_{0}$ to $P\cap
C(m)$ that is homotopic to the identity map on $P-x_{0}$ with $P\cap C(m)$
fixed during the homotopy). Followed by $h$, this induces a deformation
retract from the punctured $(K-2)$-sphere $\mathbb{S}^{K-2}-h(x_{0})$ to
$h(C(m))$. Therefore the fundamental group of $C(m)$ is isomorphic to that of
$\mathbb{S}^{K-2}-h(x_{0})$ by the deformation retract (Theorem 58.3 on
Munkres 2003). Since the punctured sphere $\mathbb{S}^{K-2}-h(x_{0})$ is
homeomorphic to $\mathbb{R}^{K-2}$ (by the stereographic projection) which is
simply connected, we proved that $C(m)$ is also simply connected. Finally, the
homeomorphism $h$ shows that $C(m)$ is a $(K-2)$-dimensional subspace of
$\mathbb{X}$ with $h(C(m))$ as a subset with a nonempty interior in
$\mathbb{S}^{K-2}$.

Step 4. Now it should be clear that $C(m)$ and the linear boundaries of the
simplex space $X$ containing the extreme points in $A(m)$ form the closure of
the active set. While $C(m)$ and the linear boundaries of $X$ containing the
rest of extreme points in $P(m)$ form the passive set. Therefore $C(m)$
partitions $X$ into two disjoint and connected subspaces: the active set and
the passive set.

Step 5. There is a small point in the above argument worth a little more
discussion. Since we include $C(m)$ in the passive set $P(m)$ by definition,
is it possible that $C(m)$ is a thick boundary as a $(K-1)$-dimensional space
(bulged in the direction to the interior of the passive set)? The answer is
no. Because in this case the convex value function conditional on $u=0$ will
always lie above the linear value function conditional on $u=1$, then the
problem is reduced to the trivial scenario.

##  8 Proof of Theorem 2.4.

###### Proof 8.1

The existence of the right (or left) derivative follows directly from the
convexity of $V_{\beta,m}(\omega)$. Fix an $m_{0}$ and apply a change $\Delta
m$ to the single-armed bandit, we have

$\displaystyle V_{\beta,m_{0}+\Delta m}(\omega)\geq
V_{\beta,m_{0}}(\omega)+D_{\beta,m}(\omega){\Delta m}.$ (86)

Now if we apply an optimal policy for the arm with subsidy $m=m_{0}+\Delta m$
to the case of $m=m_{0}$, we have

$\displaystyle V_{\beta,m_{0}}(\omega)\geq V_{\beta,m_{0}+\Delta
m}(\omega)-D_{\beta,m+\Delta m}(\omega){\Delta m}.$ (87)

From (86) and (87), it is clear that

$\displaystyle D_{\beta,m}(\omega)\leq\frac{V_{\beta,m_{0}+\Delta
m}(\omega)-V_{\beta,m_{0}}(\omega)}{\Delta m}\leq D_{\beta,m+\Delta
m}(\omega),~{}\quad\forall~{}\Delta m>0.$ (88)

Note that the above implies the monotonically nondecreasing property of
$D_{\beta,m}(\omega)$ with $m$. To prove (23), we only need to show that
$D_{\beta,m}(\omega)$ is right continuous in $m$. Assume this is not true so
there exists a decreasing sequence $\\{m_{k}\\}$ converging to $m_{0}$ and an
$\epsilon>0$ such that

$\displaystyle D_{\beta,m_{k}}(\omega)-D_{\beta,m_{0}}(\omega)>\epsilon.$ (89)

Since $D_{\beta,m_{k}}(\omega)$ has a value ranging in the compact set
$[0,\frac{1}{1-\beta}]$, we can find a convergent subsequence
$\\{m_{k_{i}}\\}$ of $\\{m_{k}\\}$ such that

$\displaystyle\lim_{i\rightarrow\infty}D_{\beta,m_{k_{i}}}(\omega)=D>D_{\beta,m_{0}}(\omega),$
(90)

where $D\in(0,\frac{1}{1-\beta}]$ is the limit of the passive time as
$m_{k_{i}}\rightarrow m_{0}$. If we can show that $D$ can be achieved by a
policy $\pi^{*}\in\Pi^{*}_{sa}(m_{0})$, then we have a contradiction to (22).

To construct $\pi^{*}$ with passive time $D$ and achieving
$V_{\beta,m_{0}}(\omega)$, we look at a finite horizon $T$. Starting from the
initial belief state $\omega$, the possible belief states within $T$ must be
finite, leading to a finite set of possible policies. Specifically, if the
number of possible states to observe is $h(T)$, the number of policies up to
time $T$ is at most $2^{h(T)}$ as each state is applied with either $u=0$ or
$u=1$. We can thus choose a subsequence $\\{m_{j}(T)\\}$ of $\\{m_{k_{i}}\\}$
such that the optimal policy achieving $D_{\beta,m_{m_{j}(T)}}$ under
$m_{j}(T)$ is the same for all $j$ within the first $T$ slots. Repeat the
process for slots $T+1$ up to $2T$ and keep doubling the time horizon, we
arrive at a policy for all states that may happen at any time. For any time
horizon $T^{\prime}$, this policy coincides with the optimal policies for a
subsequence $\\{m_{j}(T^{\prime\prime})\\}$ of $\\{m_{k_{i}}\\}$ for some
$T^{\prime\prime}>T^{\prime}$ and by taking $T^{\prime}$ large enough, this
policy achieves a passive time at least $D-\epsilon_{1}$ and a total reward
$V_{\beta,m_{0}}(\omega)-\epsilon_{1}$ for any arbitrarily small
$\epsilon_{1}>0$ due to (90) and the continuity of $V_{\beta,\cdot}(\omega)$.
This policy is thus optimal for the infinite-horizon single-armed bandit
problem with subsidy $m_{0}$ with passive time $D$, as desired for $\pi^{*}$.

To prove the sufficiency of (24) and (25), we assume that the arm is not
indexable, i.e., there exists $m_{0}$ and $\omega\in C(m_{0})\subset P(m_{0})$
such that for any $\epsilon>0$, we can find an
$m_{1}~{}(m_{0}<m_{1}<m_{0}+\epsilon)$ with $\omega\in A(m_{1})$. This means
that as the boundary $C(m)$ moves (continuously) as $m$ increases, some belief
state moves from the passive set to the active set. Under this scenario, we
have

$\displaystyle V_{\beta,m_{0}}(\omega;u=1)=V_{\beta,m_{0}}(\omega;u=0).$ (91)
$\displaystyle V_{\beta,m_{1}}(\omega;u=1)>V_{\beta,m_{1}}(\omega;u=0).$ (92)

According to (13) and (14), both $V_{\beta,m}(\omega;u=1)$ and
$V_{\beta,m}(\omega;u=0)$ are right differentiable with $m$ for any belief
state $\omega$, so is their difference. Therefore, by (91) and (92),

$\displaystyle\left.\frac{dV_{\beta,m}(\omega;u=1)}{(dm)^{+}}\right|_{m=m_{0}}$
$\displaystyle=$ $\displaystyle\lim_{m_{1}\rightarrow
m_{0}}\frac{V_{\beta,m_{1}}(\omega;u=1)-V_{\beta,m_{0}}(\omega;u=1)}{m_{1}-m_{0}}$
(93) $\displaystyle\geq$ $\displaystyle\lim_{m_{1}\rightarrow
m_{0}}\frac{V_{\beta,m_{1}}(\omega;u=0)-V_{\beta,m_{0}}(\omega;u=0)}{m_{1}-m_{0}}=\left.\frac{dV_{\beta,m}(\omega;u=0)}{(dm)^{+}}\right|_{m=m_{0}}.$
(94)

This would contradict (24) unless the equality in (94) holds, which would
contradict (25) given (92) and that $\epsilon$ can be chosen arbitrarily
small.

To prove the necessity of (24) and (25), assume there exists an $\omega\in
C(m_{\omega})$ such that

$\displaystyle\left.\frac{dV_{\beta,m}(\omega;u=0)}{(dm)^{+}}\right|_{m=m_{\omega}}<\left.\frac{dV_{\beta,m}(\omega;u=1)}{(dm)^{+}}\right|_{m=m_{\omega}},$
(95)

and when

$\displaystyle\left.\frac{dV_{\beta,m}(\omega;u=0)}{(dm)^{+}}\right|_{m=m_{\omega}}=\left.\frac{dV_{\beta,m}(\omega;u=1)}{(dm)^{+}}\right|_{m=m_{\omega}},$
(96)

for any $\epsilon_{1}>0$, there exists an
$m_{2}~{}(m_{\omega}<m_{2}<m_{\omega}+\epsilon_{1})$ such that

$\displaystyle V_{\beta,m_{2}}(\omega;u=0)<V_{\beta,m_{2}}(\omega;u=1).$ (97)

By (95), there exists $\Delta m>0$ such that

$\displaystyle V_{\beta,m(\omega)+\Delta
m}(\omega;u=0)-V_{\beta,m(\omega)}(\omega;u=0)<V_{\beta,m(\omega)+\Delta
m}(\omega;u=1)-V_{\beta,m(\omega)}(\omega;u=1).$ (98)

Together with the fact that

$\displaystyle
V_{\beta,m(\omega)}(\omega;u=0)=V_{\beta,m(\omega)}(\omega;u=1),$ (99)

we have that $\omega\in A(m(\omega)+\Delta m)$ and obtained a contradiction to
indexability as $\omega\in C(\omega)\subset P(m(\omega))$. Furthermore, when
(96) holds, it is straightforward that (97) contradicts (25).

##  9 Proof of Theorem 2.5.

###### Proof 9.1

Note that (24) is equivalent to

$\displaystyle\beta\sum_{k=0}^{K-1}\omega_{k}D_{\beta,m}(p_{k})\leq 1+\beta
D_{\beta,m}(\mathcal{T}^{1}(\omega)),~{}\quad\forall~{}\omega\in C(m).$ (100)

The above clearly holds if $\beta\leq 0.5$ as $D_{\beta,m}(\cdot)$ is lower
and upper bounded by $0$ and $1-\beta$, respectively. The strict inequality in
(100) holds if $\beta<0.5$, satisfying $\eqref{eq:diffIdx}$. When $\beta=0.5$,
the equality in (100) holds if
$\beta\sum_{k=0}^{K-1}\omega_{k}D_{\beta,m}(p_{k})=\frac{\beta}{1-\beta}=1$
and $D_{\beta,m}(\mathcal{T}^{1}(\omega))=0$. In this case, as $m$ keeps
increasing, the left-hand side of (100) can not increase while the right-hand
side cannot decrease. Apply any $\Delta m>0$ to $\omega\in C(m)$, we have

$\displaystyle V_{\beta,m+\Delta m}(\omega;u=0)$ $\displaystyle\geq$
$\displaystyle\Delta m(1+\beta
D_{\beta,m}(\mathcal{T}^{1}(\omega)))+V_{\beta,m}(\omega;u=0)$ (101)
$\displaystyle=$ $\displaystyle\Delta m(1+\beta
D_{\beta,m}(\mathcal{T}^{1}(\omega)))+V_{\beta,m}(\omega;u=1)$ (102)
$\displaystyle=$ $\displaystyle\Delta m(1+\beta
D_{\beta,m}(\mathcal{T}^{1}(\omega)))+\omega
B^{\prime}+\beta\frac{m}{1-\beta}$ (103) $\displaystyle=$ $\displaystyle\omega
B^{\prime}+\beta\frac{m+\Delta m}{1-\beta}$ (104) $\displaystyle=$
$\displaystyle V_{\beta,m+\Delta m}(\omega;u=1),$ (105)

where the second last equality is due to that
$D_{\beta,m}(\mathcal{T}^{1}(\omega))=0$ and $\beta=0.5$. The last equality is
due to the fact that any future state $p_{k}$ after activating at $\omega$
must remain in the passive set as $m$ increases due to the monotonic
nondecreasing property of $D_{\beta,m}(p_{k})$ with $m$ and that
$D_{\beta,m}(p_{k})$ is already equal to the upper bound $\frac{1}{1-\beta}$.
Therefore $\eqref{eq:diffIdx1}$ is satisfied as well.

##  10 Proof of Lemma 3.1.

###### Proof 10.1

It is helpful to rewrite (36) and (36) in the following matrix form $AX=b$:

$\displaystyle\left[\begin{matrix}\textbf{I}_{K}-\beta\left(\begin{matrix}\beta^{L(p_{0},\omega)}p_{0}\textbf{P}^{L(p_{0},\omega)}\\\
\beta^{L(p_{1},\omega)}p_{1}\textbf{P}^{L(p_{1},\omega)}\\\ \vdots\\\
\beta^{L(p_{K-1},\omega)}p_{K}\textbf{P}^{L(p_{K-1},\omega)}\\\
\end{matrix}\right)\end{matrix}\right]\times\left(\begin{matrix}V_{\beta,m}(p_{0})\\\
V_{\beta,m}(p_{1})\\\ \vdots\\\
V_{\beta,m}(p_{K-1})\end{matrix}\right)=\left[\left(\begin{matrix}\frac{1-\beta^{L(p_{0},\omega)}}{1-\beta}\\\
\frac{1-\beta^{L(p_{1},\omega)}}{1-\beta}\\\ \vdots\\\
\frac{1-\beta^{L(p_{K-1},\omega)}}{1-\beta}\\\
\end{matrix}\right)m+\left(\begin{matrix}\beta^{L(p_{0},\omega)}p_{0}\textbf{P}^{L(p_{0},\omega)}\\\
\beta^{L(p_{1},\omega)}p_{1}\textbf{P}^{L(p_{1},\omega)}\\\ \vdots\\\
\beta^{L(p_{K-1},\omega)}p_{K-1}\textbf{P}^{L(p_{K-1},\omega)}\\\
\end{matrix}\right)B^{\prime}\right]$ (106)

To prove the claim, we only need to show the coefficient matrix is invertible.
By the Perron-Frobenius theorem, the eigenvalues $\\{\lambda_{i}\\}_{i=1}^{h}$
of the following matrix satisfy $|\lambda_{i}|\leq 1$ for all
$i\in\\{1,\cdots,h\\}$ since it is a transition matrix with nonnegative
elements and the sum of each row is equal to $1$:

$\displaystyle\left(\begin{matrix}p_{0}\textbf{P}^{L(p_{0},\omega)}\\\
p_{1}\textbf{P}^{L(p_{1},\omega)}\\\ \vdots\\\
p_{K-1}\textbf{P}^{L(p_{K-1},\omega)}\\\
\end{matrix}\right)=Q\left(\begin{matrix}\lambda_{1}&\\\ &~{}\ddots\\\
&~{}&~{}~{}~{}\lambda_{i}&~{}~{}1\\\ &~{}&~{}&~{}~{}~{}~{}\lambda_{i}\\\
&~{}&~{}&~{}&~{}&~{}~{}\ddots\\\
&~{}&~{}&~{}&~{}&~{}&~{}~{}~{}~{}\lambda_{h}\end{matrix}\right)Q^{-1},$ (107)

where the above equation shows the Jordan canonical form of the matrix and the
square matrix $Q$ has full rank $K$. Therefore we can rewrite the coefficient
matrix $A$ as

$\displaystyle A$
$\displaystyle=\left[\begin{matrix}\textbf{I}_{K}-\beta\left(\begin{matrix}\beta^{L(p_{0},\omega)}p_{0}\textbf{P}^{L(p_{0},\omega)}\\\
\beta^{L(p_{1},\omega)}p_{1}\textbf{P}^{L(p_{1},\omega)}\\\ \vdots\\\
\beta^{L(p_{K-1},\omega)}p_{K}\textbf{P}^{L(p_{K-1},\omega)}\\\
\end{matrix}\right)\end{matrix}\right]{}$
$\displaystyle=Q\left(\begin{matrix}1-\beta^{L(p_{0},\omega)+1}\lambda_{1}&\\\
&\ddots\\\
&~{}&1-\beta^{L(p_{j},\omega)+1}\lambda_{i}&-\beta^{L(p_{i},\omega)+1}\\\
&~{}&~{}&1-\beta^{L(p_{j},\omega)+1}\lambda_{i}\\\ &~{}&~{}&~{}&~{}&\ddots\\\
&~{}&~{}&~{}&~{}&~{}&1-\beta^{L(p_{K-1},\omega)+1}\lambda_{h}\end{matrix}\right)Q^{-1}{}$
$\displaystyle=QJQ^{-1}.$ (108)

It is easy to see that no eigenvalue of $J$ can be zero so it has a full rank,
leading to the full rank of $A$ as it is similar to $J$.

##  11 Proof of Theorem 3.3.

###### Proof 11.1

According to the remark following Lemma 3.1, the value function
$\hat{V}_{\beta,m}(\omega_{1})$ is linear in $m$ for any $\omega_{1}$ because
the threshold policy is independent of $m$ if $\omega^{*}_{\beta}(m)$ is
fixed. Since the subsidy $m$ is paid if and only if the arm is made passive,
the linear coefficient of $m$ in $\hat{V}_{\beta,m}(\omega_{1})$ is simply
$\hat{D}_{\beta}(\omega_{1})$. The passive time $\hat{D}_{\beta}(\omega_{1})$
is clearly independent of $m$ conditional on the fixed threshold. Since (37)
has a unique solution for $m$ if and only if its left and right hand sides
have different coefficients of $m$, we proved the equivalence of (40) to the
relaxed indexability. The expression (41) of the approximated Whittle index
follows directly from the unique solution of (36), (36) and (37) under the
relaxed indexability.

##  12 Proof of Lemma 4.1.

###### Proof 12.1

Case $1$ and $2$ follow directly from the power of Jordan matrices with
$b_{1}=\lambda_{1}$, $b_{2}=\lambda_{2}$, or $b=\lambda_{1}=\lambda_{2}$:

$J_{(1)}^{k}=\left(\begin{matrix}1&0&0\\\ 0&\lambda_{1}^{k}&0\\\
0&0&\lambda_{2}^{k}\end{matrix}\right),\quad
J_{(2)}^{k}=\left(\begin{matrix}1&0&0\\\
0&\lambda_{1}^{k}&k\lambda_{1}^{k-1}\\\
0&0&\lambda_{1}^{k}\end{matrix}\right).$

For Case $3$, write $\textbf{P}=QJ_{(1)}Q^{-1}$. We have that
$\lambda_{2}=\overline{\lambda_{1}}$. Let $Q=\\{q_{ij}\\}_{i,j=0,1,2},\
Q^{-1}=\\{\tilde{q}_{ij}\\}_{i,j=0,1,2}$ and
$Q_{i}=(q_{0i},q_{1i},q_{2i})^{\prime},\
\tilde{Q}_{i}=(\tilde{q}_{i0},\tilde{q}_{i1},\tilde{q}_{i2}),\ i=0,1,2$. Then
$Q_{2}=\overline{Q}_{1},~{}\tilde{Q}_{2}=\overline{\tilde{Q}_{1}}$ and
$Q_{0},\tilde{Q}^{\prime}_{0}\in\mathbb{R}^{3}$ (since they are respectively
the right and left eigenvectors of P corresponding to the eigenvalue $1$):

$\displaystyle h(k)$
$\displaystyle=\omega\left(Q_{0}\tilde{Q}_{0}+\lambda_{1}^{k}Q_{1}\tilde{Q}_{1}+\overline{\lambda_{1}^{k}}Q_{2}\tilde{Q}_{2}\right)B^{\prime}$
$\displaystyle=\omega Q_{0}\tilde{Q}_{0}B^{\prime}+2Re(\lambda_{1}^{k}\omega
Q_{1}\tilde{Q}_{1}B^{\prime})\quad(\mbox{Let}~{}r+si=\omega
Q_{1}\tilde{Q}_{1}B^{\prime},~{}\lambda_{1}=Ae^{i\theta})$
$\displaystyle=\omega Q_{0}\tilde{Q}_{0}B^{\prime}+2A^{k}(r\cos k\theta-s\sin
k\theta)\quad(\mbox{Let}~{}a^{\prime}\sin(k\theta+b^{\prime})=2(r\cos
k\theta-s\sin k\theta),~{}c^{\prime}=\omega Q_{0}\tilde{Q}_{0}B^{\prime})$
$\displaystyle=a^{\prime}A^{k}\sin(k\theta+b^{\prime})+c^{\prime},$

where $\lambda_{1}=Ae^{i\theta},\ A\in(0,1),\ \theta\in(0,2\pi)$. Without loss
of generality, we choose $a^{\prime}\geq 0,\ b^{\prime}\in[0,2\pi)$.

##  13 Proof of Theorem 4.2.

###### Proof 13.1

The base case (47) is clear. We prove the rest case by case in the same order
as appeared in the theorem.

  * 1.

P has only real eigenvalues and $3$ linearly independent eigenvectors:
$h(k)=a_{1}b_{1}^{k}+a_{2}b_{2}^{k}+c$.

    * 1.1

$b_{1}=b_{2}\neq 0~{}\&\&~{}b_{1}>0~{}\&~{}a_{1}+a_{2}<0$:
$h(k)=(a_{1}+a_{2})b_{1}^{k}+c$ is monotonically increasing over $k\geq 0$ and
the result follows.

    * 1.2

$b_{1}=b_{2}\neq 0~{}\&\&~{}(b_{1}<0~{}||~{}a_{1}+a_{2}\geq 0)$:
$L(\omega,\omega^{*})$ achieves the maximum value at either $h(0)$ or $h(1)$
and the result follows.

    * 1.3

$a_{1}b_{1}=0~{}\&\&~{}b_{2}>0~{}\&\&~{}a_{2}<0$: $h(k)=a_{2}b_{2}^{k}+c$
which is monotonically increasing over $k\geq 1$ and the result follows.

    * 1.4

$a_{1}b_{1}=0~{}\&\&~{}(b_{2}\leq 0~{}||~{}a_{2}\geq 0)$:
$L(\omega,\omega^{*})$ achieves the maximum value at one of
$\\{h(0),h(1),h(2)\\}$ and the result follows.

    * 1.5

$a_{2}b_{2}=0~{}\&\&~{}b_{1}>0~{}\&~{}a_{1}<0$: similar to (1.3).

    * 1.6

$a_{2}b_{2}=0~{}\&\&~{}(b_{1}\leq 0~{}||~{}a_{1}\geq 0)$: similar to (1.4).

    * 1.7

$a_{1},a_{2},b_{1},b_{2}>0$: $h(k)$ achieves the maximum value at $h(0)$ and
the result follows.

    * 1.8

$a_{1}<0,a_{2}>0,b_{1}>b_{2}>0$: observe that

$h(k+1)-h(k)>0\Leftrightarrow
z(k){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\left(\frac{b_{1}}{b_{2}}\right)^{k}>-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}(>0).$

If there exists a $k_{1}\geq 0$ satisfying the above, then $h(k)$ is
monotonically decreasing until $k_{1}$ after which it increases. So the
supremum of $h(k)$ is achieved at either $0$ or $\infty$. If such $k_{1}$ does
not exist, $h(k)$ is monotonically increasing for all $k\geq 0$ and achieves
its supremum at $\infty$. The result thus follows.

    * 1.9

$a_{1}<0,a_{2}>0,b_{2}>b_{1}>0$: contrary to (1.8), if there exists a
$k_{1}\geq 0$ such that $h(k_{1}+1)-h(k_{1})>0$, then $h(k)$ is monotonically
increasing until $k_{1}+1$ after which it decreases to the stationary reward
$c$ (see Fig. 17). So the maximum of $h(k)$ is achieved at either $0$ or
$k_{1}+1$. If such $k_{1}$ does not exist, $h(k)$ is monotonically decreasing
for all $k\geq 0$ and achieves its maximum at $0$. The result thus follows.

Figure 17: $h(k)=-0.5\times 0.5^{k}+0.4\times 0.7^{k}$,
$z(k)=\left(\frac{0.5}{0.7}\right)^{k}$

    * 1.10

$b_{1}<0,a_{1},a_{2},b_{2}>0$: since

$h(k+1)<h(k),\ h(k+2)<h(k),\quad\forall\text{even number }k\geq 0,$

so $h(k)$ achieves its maximum at $0$ and the result follows.

    * 1.11

$a_{1},b_{1}<0,a_{2},b_{2}>0$: observe that

$h(k+1)-h(k)>0\Leftrightarrow
z(k)=\left(\frac{b_{1}}{b_{2}}\right)^{k}>-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}(>0)$
$h(k+2)-h(k)>0\Leftrightarrow
z(k)=\left(\frac{b_{1}}{b_{2}}\right)^{k}>-\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}(>0)$

which directly lead to the following properties:

$f(k+1)<f(k),\ f(k+2)<f(k),\quad\forall\text{odd number }k\geq 1.$

So $h(k)$ achieves its maximum at $0$ or $1$ and the result follows. See Fig.
18 for an example.

Figure 18: $h(k)=-0.5\times(-0.5)^{k}+0.4\times 0.7^{k}$

    * 1.12

$a_{2},b_{1}<0,a_{1},b_{2}>0,|b_{1}|>b_{2}$: observe that

$h(k+1)-h(k)>0\Leftrightarrow
z(k)=\left(\frac{b_{1}}{b_{2}}\right)^{k}<-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}(>0),$
$h(k+2)-h(k)>0\Leftrightarrow
z(k)=\left(\frac{b_{1}}{b_{2}}\right)^{k}<-\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}(>0).$

Let $k_{1}$ and $k_{2}$ be the maximum even integers achieving the above
inequalities, respectively. Note that $k_{2}\geq k_{1}$. If both of them are
nonnegative, then $h(k)$ is monotonically increasing until $k_{1}+2$, then
moving up with oscillations until $k_{2}+2$ and finally moving downward to
converge to $c$. If $k_{1}<0\leq k_{2}$, then $h(k)$ still achieves its
maximum $k_{2}+2$. Finally, if $k_{2}<0$, $h(k)$ has its maximum at $0$. The
result thus follows. See Figs. 19 and 20 for an example.

Figure 19: $h(k)=0.2\times(-0.7)^{k}-2\times 0.4^{k}$ Figure 20:
$z(k)=\left(-\frac{0,7}{0.4}\right)^{k}$

    * 1.13

$a_{2},b_{1}<0,a_{1},b_{2}>0,|b_{1}|<b_{2}$: this case is sort of the reversed
version to (1.12). Let $k_{1}\geq 0$ and $k_{2}\geq 0$ be the minimum even
integers achieving the two inequalities in (1.12), respectively. In this case,
$h(k)$ moves down with oscillations until $k_{2}$, then it moves up with
oscillations until $k_{1}$ and finally increases to the stationary reward $c$.
Therefore $h(k)$ achieves its supremum at $0$ or $\infty$. The result thus
follows.

    * 1.14

$a_{2},b_{1}<0,a_{1},b_{2}>0,|b_{1}|=b_{2}$: under this case, the following
holds

$h(k+1)-h(k)>0\Leftrightarrow(-1)^{k}<-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}(>0),$
$h(k+2)-h(k)>0\Leftrightarrow(-1)^{k}<-\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}(>0).$

If $-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}\geq 1$, then $h(k)$ is
monotonically increasing to the stationary reward $c$. If
$-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}<1$ and
$-\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}\leq 1$, then $h(k)$ oscillates
but its maximum value cannot exceed $h(0)$. If
$-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}<1$ and
$-\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}>1$, then $h(k)$ moves up with
oscillations to its supremum $c$. The result thus follows.

    * 1.15

$b_{1},b_{2}<0,a_{1},a_{2}>0$: the maximum of $h(k)$ clearly happens at $0$
and the result thus follows.

    * 1.16

$b_{1},b_{2}>0,a_{1},a_{2}<0$: $h(k)$ monotonically converges to $c$ from
below and the result thus follows.

    * 1.17

$a_{1},a_{2},b_{1}<0,b_{2}>0,|b_{1}|>b_{2}$: under this case, the following
holds

$h(k+1)-h(k)>0\Leftrightarrow
z(k)=\left(\frac{b_{1}}{b_{2}}\right)^{k}>-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}(<0),$
$h(k+2)-h(k)>0\Leftrightarrow
z(k)=\left(\frac{b_{1}}{b_{2}}\right)^{k}>-\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}(<0).$

Any even $k$ clear satisfies the above two inequalities. Let $k_{1}\geq 1$ and
$k_{2}\geq 1$ be the maximum odd integers achieving the above, respectively.
If $k_{1},k_{2}$ exist, then $k_{1}\leq k_{2}$ and $h(k)$ monotonically
increases until $k_{1}+2$ after which it goes up with oscillations until
$k_{2}+2$, and finally it falls with oscillations and converges to $c$. As
long as $k_{2}$ exists, $h(k)$ has its maximum at $k_{2}+2$. When $k_{2}$ does
not exist, it is clear that $h(k)$ achieves its maximum at $1$ and the result
follows.

    * 1.18

$a_{1},a_{2},b_{1}<0,b_{2}>0,|b_{1}|<b_{2}$: let $k_{1}\geq 1$ and $k_{2}\geq
1$ be the minimum odd integers achieving the two inequalities in (1.17),
respectively. Note that $k_{2}\leq k_{1}$. Then $h(k)$ moves down with
oscillations until $k_{2}$ after which it goes up with oscillations until
$k_{1}$ and finally $h(k)$ monotonically increases to $c$. The result thus
follows.

    * 1.19

$a_{1},a_{2},b_{1}<0,b_{2}>0,|b_{1}|=b_{2}$: similar to (1.14), if
$-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}\leq-1$, then $h(k)$ is monotonically
increasing to the stationary reward $c$. If
$-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}>-1$ and
$-\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}<-1$, then $h(k)$ moves up with
oscillations to $c$. If $-\frac{a_{2}(b_{2}-1)}{a_{1}(b_{1}-1)}>-1$ and
$-\frac{a_{2}(b_{2}^{2}-1)}{a_{1}(b_{1}^{2}-1)}\geq-1$, then $h(k)$ achieves
its maximum at $1$. The result thus follows.

    * 1.20

$a_{2},b_{1},b_{2}<0,a_{1}>0,|b_{1}|>|b_{2}|$: let

$\displaystyle k_{o1}$ $\displaystyle=$
$\displaystyle\min\\{k:h(k+1)>h(k),k\text{ is positive and odd}\\}-2,{}$
$\displaystyle k_{o2}$ $\displaystyle=$
$\displaystyle\min\\{k:h(k+2)>h(k),k\text{ is positive and odd}\\}-2,{}$
$\displaystyle k_{e1}$ $\displaystyle=$
$\displaystyle\max\\{k:h(k+1)>h(k),k\text{ is nonnegative and even}\\},{}$
$\displaystyle k_{e2}$ $\displaystyle=$
$\displaystyle\max\\{k:h(k+2)>h(k),k\text{ is nonnegative and even}\\}.{}$

If $k_{e1}$ exists, then $|k_{o1}-k_{e1}|=1$ and $|k_{o2}-k_{e2}|=1$.
Furthermore, we have that $k_{o1}\leq k_{o2}$ and $k_{e1}\leq k_{e2}$ (see
Fig. 21 for an example). Let $k_{1}=\max\\{k_{o1},k_{e1}\\}$. From the origin
$0$ to $k_{1}+1$, we have that $\max_{0\leq k\leq k_{1}+1}h(k)=h(1)$. Then
from $k_{1}+1$ to $k_{e2}+2$, it reaches a local maximum
$\max_{k>k_{1}}h(k)=h(k_{e2}+2)$ after which it moves down to the stationary
reward $c$ (see Fig. 22 for an example). If $k_{e1}$ does not exist but
$k_{e2}$ does, $h(k)$ attains its maximum value at either $0$ or
$h(k_{e2}+2)$. If $k_{e2}$ does not exist, then $h(k)$ attains its maximum
value at $0$. The result thus follows.

Figure 21: $z(k)=\left(\frac{-0.8}{-0.4}\right)^{k}$

Figure 22: $h(k)=0.2\times(-0.8)^{k}-2\times(-0.4)^{k}$

    * 1.21

$a_{2},b_{1},b_{2}<0,a_{1}>0,|b_{1}|<|b_{2}|$: let

$\displaystyle k_{o1}$ $\displaystyle=$
$\displaystyle\max\\{k:h(k+1)>h(k),k\text{ is positive and odd}\\},{}$
$\displaystyle k_{o2}$ $\displaystyle=$
$\displaystyle\max\\{k:h(k+2)>h(k),k\text{ is positive and odd}\\},{}$
$\displaystyle k_{e1}$ $\displaystyle=$
$\displaystyle\min\\{k:h(k+1)>h(k),k\text{ is nonnegative and even}\\}-2,{}$
$\displaystyle k_{e2}$ $\displaystyle=$
$\displaystyle\min\\{k:h(k+2)>h(k),k\text{ is nonnegative and even}\\}-2.{}$

Similar to (1.20), if $k_{o1}$ exists, then $|k_{o1}-k_{e1}|=1$,
$|k_{o2}-k_{e2}|=1$, $k_{o1}\leq k_{o2}$, and $k_{e1}\leq k_{e2}$. Let
$k_{1}=\max\\{k_{o1},k_{e1}\\}$. We have that $h(0)=\max_{0\leq k\leq
k_{1}+1}h(k)$ and $\max_{k\geq k_{1}+2}h(k)=h(k_{o2})$. If $k_{o1}$ does not