remarkRemark hypothesisHypothesis claimClaim Whittle Index for Imperfect
ObservationsK. Liu and T. Wu ex_supplement

# Whittle Index for A Class of Restless Bandits with Imperfect
Observations††thanks: Submitted to the editors 08/09/2021.

Keqin Liu Department of Mathematics, Nanjing University, China (, ).
<EMAIL_ADDRESS><EMAIL_ADDRESS>Ting Wu22footnotemark: 2

###### Abstract

We consider a class of restless bandit problems that finds a broad application
area in stochastic optimization, reinforcement learning and operations
research. In our model, there are $N$ independent $2$-state Markov processes
that may be observed and accessed for accruing rewards. The observation is
error-prone, i.e., both false alarm and miss detection may happen.
Furthermore, the user can only choose a subset of $M~{}(M<N)$ processes to
observe at each discrete time. If a process in state $1$ is correctly
observed, then it will offer some reward. Due to the partial and imperfect
observation model, the system is formulated as a restless multi-armed bandit
problem with an information state space of uncountable cardinality. Restless
bandit problems with finite state spaces are PSPACE-HARD in general. In this
paper, we establish a low-complexity algorithm that achieves a strong
performance for this class of restless bandits. Under certain conditions, we
theoretically prove the existence (indexability) of Whittle index and its
equivalence to our algorithm. When those conditions do not hold, we show by
numerical experiments the near-optimal performance of our algorithm in
general.

###### keywords:

restless bandits, continuous state space, observation errors, Whittle index

65K05, 90C15, 90C40

##  1 Introduction

The exploration-exploitation (EE) dilemma is well posed in optimization-over-
time problems and mathematically modeled in various forms for reinforcement
learning, to which a major category, multi-armed bandits (MAB), belongs. In
the classical MAB model, a player chooses $1$ out of $N$ statistically
independent arms to pull and possibly accrues reward determined by the state
of the chosen arm which transits to a new state according to a known Markovian
rule [2]. The states of other arms remain frozen. The objective is to maximize
the expected total discounted reward over an infinite time horizon:

(1)
$\displaystyle\max_{\pi\in\Pi}\mathbb{E}_{\pi}\sum_{t=1}^{\infty}[\beta^{t-1}R(t)|S(t),A(t)],$

where $\Pi$ is the set of all feasible policies, $\beta\in(0,1)$ the discount
factor, $A(t)\in\\{1,2,\cdots,N\\}$ the arm chosen at time $t$ under a policy
$\pi\in\Pi$, $S(t)$ the joint state of all arms at time $t$ and $R(t)$ the
obtained reward determined by the state of the chosen arm. For the infinite-
horizon problem, there must exist an optimal stationary policy $\pi^{*}$,
independent of time $t$, that maps the joint arm state space to an arm to
choose. If each arm’s state space has cardinality of $K$, then the joint state
space has a size of $K^{N}$, leading to the geometric growth of the
algorithmic complexity with the number of arms. Gittins in 1970s solved the
problem by showing the optimality of an index policy, i.e., for each state of
each arm we can compute an index solely dependent on the parameters of the arm
and choosing the arm with a state of the highest index at each time is optimal
[1]. Gittins index policy clearly reduces the complexity of the problem to a
linear growth with the number of arms as they are decoupled when computing the
index function (of the states of each arm). Whittle in 1988 generalized
Gittins index to the restless MAB model where arms not chosen may also change
states or offer reward [9]. Whittle’s generalization, referred to as Whittle
index, has been demonstrated with a strong performance through numerical
studies [5]. However, establishing the existence of Whittle index
(indexability) and the computation of Whittle index if it exists are both
difficult in general. Papadimitriou and Tsitsiklis in 1999 have shown that the
restless MAB with a finite state space is PSPACE-HARD [7].

In this paper, we extend the work in [5] (for a perfect observation model) and
[6] (for the myopic policy on stochastically identical arms) to build a near-
optimal algorithm with low complexity for a class of restless bandits with an
infinite state space and an imperfect observation model. Our model also
belongs to the general framework of partially observable Markov decision
processes (POMDP) [8]. Consider $N$ processes each of which evolves on a
$2$-state Markov chain whose state is observed if and only if the process is
chosen. Furthermore, the observation is error-prone: state $1$ may be observed
as $0$ and vice versa. At time $t$, the player obtains reward of amount
$B_{n}$ if and only if channel $n$ is currently chosen and accurately observed
in state $1$. This observation model finds a broad application area in
communication networks [6]. Under resource constraints, the player’s goal is
to select $M~{}(M<N)$ channels at each time for maximizing the long-term
reward. By formulating the belief vector as the system state for decision
making, we show that the indexability is satisfied under certain conditions.
Furthermore, we propose an efficient algorithm to compute the approximated
Whittle index that achieves a near-optimal performance in general, even if the
conditions for indexability do not hold.

The paper is organized as follows. Our main results are in Section 2, our new
algorithm is in Section 3, experimental results are in Section 4, and the
conclusions follow in Section 5.

##  2 Main results

Consider a restless MAB with $N$ internal $2$-state Markov chains (arms) of
potentially different transition probabilities. At each time $t$, the player
chooses a subset consisting of $M~{}(M<N)$ arms to observe their states. Let
$\delta=\Pr(O=1|S=0)$ and $\epsilon=\Pr(O=0|S=1)$ denote, respectively, the
miss detection and false alarm probabilities in the observation model, where
$S\in\\{0~{}\text{(bad)},1~{}\text{(good)}\\}$ denotes the state of an arm and
$O$ the observation (detection outcome) of the state. Under the optimal
detector, the error probabilities $\delta$ and $\epsilon$ follow the curve of
receiver operating characteristics (ROC) [6]. Since one cannot minimize both
$\delta$ and $\epsilon$ simultaneously, we fix the constraint on miss
detection $\delta\leq\delta_{0}$ for some $\delta_{0}\in(0,1)$ which yields
the optimal false arm probability $\epsilon_{0}$, simply denoted by
$\epsilon$. If arm $n~{}(1\leq n\leq N)$ in state $S=1$ is observed in state
$1$ (i.e., $S=1$ and $O=1$), then the player accrues $B_{n}$ units of reward
from this arm. One application example of this observation model is cognitive
radios, where a secondary user aims to utilize a frequency band (channel/arm)
currently unused by the primary users. Due to energy and policy constraints on
the senor of the secondary user, only a subset of channels can be sensed at
each time and if any of them is sensed idle ($O=1$), the user can send certain
packets over it to its receiver and obtain an ACK in the end of the time slot
if the channel is indeed idle ($S=1$); otherwise no ACK from this channel
would be received. Then the reward $B_{n}$ is just the bandwidth of channel
$n$. Clearly, the hard constraint here should be on the miss detection
probability $\delta$ to guarantee the satisfaction of the primary users, i.e.,
the disturbance (when a secondary user senses a busy channel as idle and
subsequently sends data over it) to the primary users should be capped.

###  2.1 System Model and Belief Vector

At each discrete time $t$, the internal state ($0/1$) of an arm cannot be
observed before deciding whether or not to observe the arm. Therefore, we
cannot use the states of the Markov chains as the system state for decision
making. Applying the general POMDP theory to our model the belief state vector
consisting of probabilities that arms are in state $1$ given all past
observations is a sufficient statistics for making future decisions [8]:

(2) $\displaystyle\Omega(t)$ $\displaystyle=$
$\displaystyle(\omega_{1}(t),\omega_{2}(t),\cdots,\omega_{N}(t)),$ (3)
$\displaystyle\omega_{n}(t)$ $\displaystyle=$
$\displaystyle\Pr(S_{n}(t)=1|\text{past observations on
arm}~{}n),~{}~{}\forall\ n\in\\{1,\cdots,N\\},$

where $\omega_{n}(t)$ is the belief state of arm $n$ at time $t$ and
$S_{n}(t)$ its internal state. According to the Bayes’ rule, the belief state
(of any arm) itself evolves as a Markov chain with an infinite state space:

(4) $\displaystyle~{}~{}~{}~{}~{}~{}~{}\omega_{n}(t+1)$ $\displaystyle=$
$\displaystyle\begin{cases}p_{11}^{(n)},&n\in
A(t),ACK_{n}(t)~{}(S_{n}(t)=1,O_{n}(t)=1)\\\
\mathcal{T}_{n}(\frac{\epsilon\omega_{n}(t)}{\epsilon\omega_{n}(t)+1-\omega_{n}(t)}),&n\in
A(t),No\ ACK_{n}(t)\\\ \mathcal{T}_{n}(\omega_{n}(t)),&n\notin
A(t)\end{cases},$ (5) $\displaystyle\mathcal{T}_{n}(\omega_{n}(t))$
$\displaystyle=$
$\displaystyle\omega_{n}(t)p^{(n)}_{11}+(1-\omega_{n}(t))p^{(n)}_{01},$

where $A(t)\subset\\{1,2,\cdots,N\\}$ is the set of chosen arms at time $t$
with $|A(t)|=M$, $S_{n}(t)$ and $O_{n}(t)$ respectively the state and
observation from arm $n$ at time $t$ if $n\in A(t)$, $ACK_{n}(t)$ the
acknowledgement of successful utilization of arm $n$ for slot $t$,
$\mathcal{T}_{n}(\cdot)$ the one-step belief update operator without
observation, and $\textbf{P}^{(n)}=\\{p^{(n)}_{ij}\\}_{i,j\in\\{0,1\\}}$ the
transition matrix of the internal Markov chain of arm $n$. Furthermore, the
$k$-step belief update of an unobserved arm for $k$ consecutive slots starting
from any belief state $\omega$ is

(6)
$\displaystyle\mathcal{T}_{n}^{k}(\omega)=\frac{p^{(n)}_{01}-(p^{(n)}_{11}-p^{(n)}_{01})^{k}(p^{(n)}_{01}-(1+p^{(n)}_{01}-p^{(n)}_{11})\omega)}{1+p^{(n)}_{01}-p^{(n)}_{11}}.$

For simplicity of notations, we denote $\mathcal{T}_{n}^{1}(\cdot)$ by
$\mathcal{T}_{n}(\cdot)$.

At time $t=1$, the initial belief state $\omega_{n}(1)$ of arm $n$ can be set
as the stationary distribution $\omega_{n,o}$ of the internal Markov
chain111Here we assume the internal Markov chain with transition matrix
$\textbf{P}^{(n)}$ is irreducible and aperiodic.:

(7)
$\displaystyle\omega_{n}(1)=\omega_{n,o}=\lim_{k\rightarrow\infty}\mathcal{T}_{n}^{k}(\omega^{\prime})=\frac{p^{(n)}_{01}}{p^{(n)}_{01}+p^{(n)}_{10}},$

where $\omega_{n,o}$ is the unique solution to
$\mathcal{T}_{n}(\omega)=\omega$ and $\omega^{\prime}\in[0,1]$ an arbitrary
probability. Given the initial belief vector
$\Omega(1)=(\omega_{1}(1),\omega_{2}(1),\cdots,\omega_{N}(1))$, we arrive at
the following constrained optimization problem:

(8) $\displaystyle\max_{\pi:\Omega(t)\rightarrow
A(t)}\mathbb{E}_{\pi}\sum_{t=1}^{\infty}[\beta^{t-1}R(t)|\Omega(1)],$ (9)
$\displaystyle\quad\mbox{subject to}\quad|A(t)|=M,\quad t\geq 1.$

It is clear that fixing $\Omega(1)$, the action-dependent belief vector
$\Omega(t)$ takes possible values geometrically growing with time $t$, leading
to a high-complexity in solving the problem, i.e., curse of dimensionality. In
the following, we adopt Whittle’s original idea of Lagrangian relaxation to
decouple arms for an index policy and show some crucial properties of the
value functions of a single arm.

###  2.2 Arm Decoupling by Lagrangian Relaxation

Consider the following relaxed version of the restless MAB:

(10) $\displaystyle\max_{\pi:\Omega(t)\rightarrow A(t)}$
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}\sum_{n=1}^{N}\mathbbm{1}(n\in
A(t))\cdot S_{n}(t)\cdot O_{n}(t)\cdot B_{n}|\Omega(1)]$ (11) subject to
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}\sum_{n=1}^{N}\mathbbm{1}(n\notin
A(t))|\Omega(1)]=\frac{N-M}{1-\beta}.$

Clearly constraint (11) is a relaxation on the player’s action $A(t)$ from
(9). Applying the Lagrangian multiplier $\lambda$ to constraint (11), we
arrive at the following unconstrained optimization problem:

(12) $\displaystyle\max_{\pi:\Omega(t)\rightarrow A(t)}$
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}\sum_{n=1}^{N}[\mathbbm{1}(n\in
A(t))S_{n}(t)O_{n}(t)B_{n}+\lambda\cdot\mathbbm{1}(n\notin A(t))]|\Omega(1)].$

Fixing $\lambda$, the above optimization is equivalent to $N$ independent
unconstraint optimization problem as shown below: for each
$n\in\\{1,2,\cdots,N\\}$,

(13) $\displaystyle\max_{\pi:\omega_{n}(t)\rightarrow\\{0,1\\}}$
$\displaystyle\mathbb{E}_{\pi}[\sum_{t=1}^{\infty}\beta^{t-1}[\mathbbm{1}(n\in
A(t))S_{n}(t)O_{n}(t)B_{n}+\lambda\cdot\mathbbm{1}(n\notin
A(t))]|\omega_{n}(1)].$

Here $\pi$ is a single-arm policy that maps the belief state of the arm to the
binary action $u=1$ (chosen/activated) or $u=0$ (unchosen/made passive). It is
thus sufficient to consider a single arm for solving problem (12). For
simplicity, we will drop the subscript $n$ in consideration of a single-armed
bandit problem without loss of generality. Let $V_{\beta,m}(\omega)$ denote
the value of (13) with $\lambda=m$ and $\omega_{n}(1)=\omega$, it is
straightforward to write out the dynamic equation of the single-armed bandit
problem as follows:

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

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 (14). Define the nonlinear operator
$\phi(\cdot)$ as

(15)
$\displaystyle\phi(\omega)=\frac{\epsilon\omega}{\epsilon\omega+1-\omega}.$

It is easy to see that $\mathcal{T}\circ\phi(\cdot)$ is Lipschitz continuous
on $[0,1]$:

(16) $\displaystyle\begin{aligned}
|\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega})-\mathcal{T}(\frac{\epsilon\omega^{\prime}}{\epsilon\omega^{\prime}+1-\omega^{\prime}})|&=|\frac{p_{11}\epsilon\omega+(1-\omega)p_{01}}{\epsilon\omega+1-\omega}-\frac{p_{11}\epsilon\omega^{\prime}+(1-\omega^{\prime})p_{01}}{\epsilon\omega^{\prime}+1-\omega^{\prime}}|\\\
&=|\frac{\epsilon(p_{11}-p_{01})(\omega-\omega^{\prime})}{(1-(1-\epsilon)\omega)(1-(1-\epsilon)\omega^{\prime})}|\\\
&\leq\frac{|p_{11}-p_{01}|}{\epsilon}|\omega-\omega^{\prime}|.\end{aligned}$

We assume that $\epsilon\neq 0$ (otherwise the problem is reduced to that
considered in [5]) and $p_{11}\neq p_{01}$ (otherwise the belief update is
independent of observations or actions and the problem becomes trivial).
Without loss of generality, set $B=1$. We have

(20)
$\displaystyle\left\\{\begin{array}[]{ll}&V_{\beta,m}(\omega;u=1)=(1-\epsilon)\omega+\beta\big{[}(1-\epsilon)\omega
V_{\beta,m}(p_{11})\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+(1-(1-\epsilon)\omega)V_{\beta,m}(\mathcal{T}(\phi(\omega)))\big{]},\\\
&V_{\beta,m}(\omega;u=0)=m+\beta
V_{\beta,m}(\mathcal{T}(\omega)).\end{array}\right.$

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

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

It is clear that $P(m)$ changes from the empty set to the closed interval
$[0,1]$ as $m$ increases from $-\infty$ to $\infty$. However, such change may
not be monotonic as $m$ increases. 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, such $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 $\omega$ without $m$. This
Lagrangian multiplier $m$ is thus called ’subsidy for passivity’ by Whittle
who formalized the following definition of indexability and Whittle index [9].

######  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.

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),{}$ (22)
$\displaystyle\mbox{then}~{}\forall~{}m^{\prime}>m,~{}V_{\beta,m^{\prime}}(\omega;u=1)\leq
V_{\beta,m^{\prime}}(\omega;u=0).$

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

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

In the following we give some useful properties of the value functions
$V_{\beta,m}(\omega;u=1),\ V_{\beta,m}(\omega;u=0)$ and $V_{\beta,m}(\omega)$.
Our strategy is to first establish those properties for finite horizons and
then extend them to the infinite horizon by the uniform convergence of the
value functions of the former to the latter. Define the $T$-horizon value
function $V_{1,T,\beta,m}(\omega)$ as the maximum expected total discounted
reward achievable over the next $T$ time slots starting from the initial
belief state $\omega$. Then

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

where $V_{1,T,\beta,m}(\omega;u=1)$ and $V_{1,T,\beta,m}(\omega;u=0)$ denote,
respectively, the maximum expected total discounted reward achievable given
the initial active and passive actions over the next $T$ time slots starting
from the initial belief state $\omega$:

(25) $\displaystyle V_{1,T,\beta,m}(\omega;u=1)$ $\displaystyle=$
$\displaystyle(1-\epsilon)\omega+(1-\epsilon)\omega\beta
V_{1,T-1,\beta,m}(p_{11}){}$ $\displaystyle+(1-(1-\epsilon)\omega)\beta
V_{1,T-1,\beta,m}(\mathcal{T}(\frac{\epsilon\omega}{1-(1-\epsilon)\omega})),$
(26) $\displaystyle V_{1,T,\beta,m}(\omega;u=0)$ $\displaystyle=$
$\displaystyle m+\beta V_{1,T-1,\beta,m}(\mathcal{T}(\omega)),$ (27)
$\displaystyle V_{1,0,\beta,m}(\cdot)$ $\displaystyle\equiv$ $\displaystyle
0.$

From the above recursive equations, we can analyze $V_{1,T,\beta,m}(\omega)$
by backward induction on $T$. It is easy to see that for any $\omega$,

(28) $\displaystyle V_{1,1,\beta,m}(\omega;u=1)=(1-\epsilon)\omega,\quad
V_{1,1,\beta,m}(\omega;u=0)=m.$

Therefore $V_{1,T,\beta,m}(\omega)$ is the maximum of two linear equations and
thus piecewise linear and convex for $T=1$ (in both $\omega$ and $m$).
Exploiting the Bayes’ rule that leads to the following term

(29) $\displaystyle(1-(1-\epsilon)\omega)\beta
V_{1,T-1,\beta,m}(\mathcal{T}(\frac{\epsilon\omega}{1-(1-\epsilon)\omega})),$

which has a coefficient $(1-(1-\epsilon)\omega)$ also appeared as the
denominator of the expression inside the linear operator $\mathcal{T}$, the
recursive equation set (25) and (26) shows that $V_{1,T,\beta,m}(\omega)$ is
the maximum of two convex and piecewise linear functions and thus piecewise
linear and convex for any $T>1$ (in both $\omega$ and $m$). Motivated by the
Lipschitz continouity of $\mathcal{T}\circ\phi$, we show in Lemma 2.4 that
$V_{1,T,\beta,m}(\omega)$ is also Lipschitz continuous under certain
conditions. In the following, we first establish a monotonic property of
$V_{1,T,\beta,m}(\omega)$ in the case of $p_{11}>p_{01}$ (positively
correlated Markov chain).

######  Lemma 2.2.

If $p_{11}>p_{01}$, then $V_{1,T,\beta,m}(\omega)$ is monotonically increasing
with $\omega\in[0,1]$ for any $T\geq 1$.

######  Proof 2.3.

Since $V_{1,T,\beta,m}(\omega)$ is piecewise linear, it is differentiable
almost everywhere except on a null set (under the Lebesgue measure on
$\mathbb{R}$) consisting of finite points among which both the left and right
derivatives at any point exist but not equal. To prove that the continuous
function $V_{1,T,\beta,m}(\omega)$ is monotonically increasing with $\omega$,
we only need to show

(30) $\displaystyle V^{\prime}_{1,T,\beta,m}(\omega)\geq
0,\quad\forall\omega\in(0,1),$

where $V^{\prime}_{1,T,\beta,m}(\omega)$ denotes the right derivative of
$V_{1,T,\beta,m}(\cdot)$ as a function of the belief state with $m$ fixed.
From (28), the value function
$V_{1,1,\beta,m}(\omega)=\max\\{(1-\epsilon)\omega,m\\}$ is monotonically
increasing with nonnegative right derivative $1-\epsilon$ or $0$. Assume (30)
is true for $T\geq 1$, then for $T+1$ we have
$V_{1,T+1,\beta,m}(\omega)=\max\\{f_{T}(\omega),g_{T}(\omega)\\}$ with:

(31) $\displaystyle\left\\{\begin{aligned}
f_{T}(\omega)&=(1-\epsilon)\omega+(1-\epsilon)\omega\beta
V_{1,T,\beta,m}(p_{11})\\\ &~{}~{}~{}+(1-(1-\epsilon)\omega)\beta
V_{1,T,\beta,m}(\mathcal{T}\circ\phi(\omega)),\\\ g_{T}(\omega)&=m+\beta
V_{1,T,\beta,m}(\mathcal{T}(\omega)).\end{aligned}\right.$

From the above, we have

(32) $\displaystyle\left\\{\begin{aligned}
f_{T}^{\prime}(\omega)&=(1-\epsilon)+(1-\epsilon)\beta
V_{1,T,\beta,m}(p_{11})-(1-\epsilon)\beta
V_{1,T,\beta,m}(\mathcal{T}\circ\phi(\omega))\\\
&~{}~{}~{}+V_{1,T,\beta,m}^{\prime}(\mathcal{T}\circ\phi(\omega))\frac{\epsilon\beta(p_{11}-p_{01})}{1-(1-\epsilon)\omega},\\\
g_{T}^{\prime}(\omega)&=\beta(p_{11}-p_{01})V_{1,T,\beta,m}^{\prime}(\mathcal{T}(\omega)),\end{aligned}\right.$

where $f_{T}^{\prime}(\cdot),\ g^{\prime}_{T}$ and
$V_{1,T,\beta,m}^{\prime}(\cdot)$ denote the right derivatives of the
corresponding functions. We have used the fact that $\phi(\cdot)$ is
monotonically increasing and when $p_{11}>p_{01}$, $\mathcal{T}(\cdot)$ is
also monotonically increasing and that

(33)
$\displaystyle\phi^{\prime}(\omega)=\frac{\epsilon}{(1-(1-\epsilon)\omega)^{2}}.$

By the induction hypothesis and (32), if $p_{11}>p_{01}$ then $g_{T}(\omega)$
is monotonically increasing (since $g^{\prime}_{T}(\omega)\geq 0$) and

(34) $\displaystyle\begin{aligned}
f_{T}^{\prime}(\omega)&=(1-\epsilon)+(1-\epsilon)\beta
V_{1,T,\beta,m}(p_{11})-(1-\epsilon)\beta
V_{1,T,\beta,m}(\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega}))\\\
&~{}~{}~{}+(1-(1-\epsilon)\omega)\beta
V_{1,T,\beta,m}^{\prime}(\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega}))(\mathcal{T}\circ\phi)^{\prime}(\omega)\\\
&\geq(1-\epsilon)+\frac{\epsilon\beta(p_{11}-p_{01})}{1-(1-\epsilon)\omega}V_{1,T,\beta,m}^{\prime}(\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega}))\\\
&>0,\end{aligned}$

where both the first and second inequalities are due to the monotonically
increasing property of $V_{1,T,\beta,m}(\cdot)$ under the assumption that
$p_{11}>p_{01}$ by our induction hypothesis and

(35) $\displaystyle p_{01}\leq\mathcal{T}(\omega)\leq p_{11},\
0\leq\phi(\omega)\leq 1,\quad\forall~{}\omega\in[0,1].$

This proves the monotonically increasing property of $f_{T}(\omega)$. Hence
$V_{1,T+1,\beta,m}(\omega)=\max\\{f_{T}(\omega),g_{T}(\omega)\\}$ is also
monotonically increasing and the proof by induction is finished.

Now we show that under a constraint on the discount factor $\beta\in(0,1)$,
the value function $V_{1,T,\beta,m}(\omega)$ is a Lipschitz function:

######  Lemma 2.4.

Suppose that the discount factor $\beta\in(0,1)$ satisfies

(36) $\displaystyle\beta<\frac{1}{(2-\epsilon)|p_{11}-p_{01}|}.$

Then $\forall T\geq 1$ and $\forall\omega,\omega^{\prime}\in[0,1]$,

(37)
$\displaystyle|V_{1,T,\beta,m}(\omega)-V_{1,T,\beta,m}(\omega^{\prime})|\leq
C|\omega-\omega^{\prime}|,\ \text{where}$ (38) $\displaystyle
C=\frac{1-\epsilon}{1-(2-\epsilon)\beta|p_{11}-p_{01}|}.$

######  Proof 2.5.

We prove this lemma by induction. Without loss of generality, assume
$\omega<\omega^{\prime}$. For the case of $T=1$,

$|V_{1,1,\beta,m}(\omega)-V_{1,1,\beta,m}(\omega^{\prime})|=\begin{cases}0,&m\geq(1-\epsilon)\omega^{\prime};\\\
(1-\epsilon)\omega^{\prime}-m,&\text{if }(1-\epsilon)\omega\leq
m<(1-\epsilon)\omega^{\prime};\\\
(1-\epsilon)|\omega-\omega^{\prime}|,&\text{if
}m<(1-\epsilon)\omega.\end{cases}$

Thus
$|V_{1,1,\beta,m}(\omega)-V_{1,1,\beta,m}(\omega^{\prime})|\leq(1-\epsilon)|\omega-\omega^{\prime}|\leq
C|\omega-\omega^{\prime}|.$

Assume that for $T\geq
1,|V_{1,T,\beta,m}(\omega)-V_{1,T,\beta,m}(\omega^{\prime})|\leq
C|\omega-\omega^{\prime}|$ holds, i.e., neither the left nor the right
derivative of $V_{1,T,\beta,m}(\cdot)$ can exceed $C$. To prove
$|V_{1,T+1,\beta,m}(\omega)-V_{1,T+1,\beta,m}(\omega^{\prime})|\leq
C|\omega-\omega^{\prime}|$, recall the definitions of $f_{T}(\omega)$ and
$g_{T}(\omega)$ in (31) and their right derivatives $f_{T}^{\prime}(\omega)$
and $g_{T}^{\prime}(\omega)$ in (32) and observe the following inequalities:

(39) $\displaystyle\left\\{\begin{aligned}
|V_{1,T,\beta,m}(p_{11})-V_{1,T,\beta,m}(\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega}))|&\leq
C|p_{11}-\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega})|\\\ &\leq
C|p_{11}-p_{01}|,\\\
\frac{\epsilon}{1-(1-\epsilon)\omega}|V_{1,T,\beta,m}^{\prime}(\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega}))|&\leq
C.\end{aligned}\right.$

Thus we have the following lower and upper bounds on $f^{\prime}_{T}(\omega)$
and $g^{\prime}_{T}(\omega)$:

(40) $\displaystyle~{}~{}\left\\{\begin{aligned}
(1-\epsilon)-(2-\epsilon)\beta C|p_{11}-p_{01}|\leq
f_{T}^{\prime}(\omega)&\leq(1-\epsilon)+(2-\epsilon)\beta C|p_{11}-p_{01}|,\\\
-C\beta|p_{11}-p_{01}|\leq g_{T}^{\prime}(\omega)&\leq
C\beta|p_{11}-p_{01}|.\end{aligned}\right.$

Note that for the case of $p_{11}<p_{01}$, the left derivative of
$V_{1,T,\beta,m}(\cdot)$ has been used due to the monotonically decreasing
property of $\mathcal{T}(\cdot)$. From (32) and (40), we have

$\displaystyle|V_{1,T+1,\beta,m}^{\prime}(\omega)|$
$\displaystyle\leq(1-\epsilon)+(2-\epsilon)\beta C|p_{11}-p_{01}|$
$\displaystyle=(1-\epsilon)+(2-\epsilon)\beta|p_{11}-p_{01}|\frac{1-\epsilon}{1-(2-\epsilon)\beta|p_{11}-p_{01}|}$
$\displaystyle=\frac{1-\epsilon}{1-(2-\epsilon)\beta|p_{11}-p_{01}|}$
$\displaystyle=C.$

Since $V_{1,T+1,\beta,m}(\omega)$ is absolutely continuous, the above implies
that

$|V_{1,T+1,\beta,m}(\omega)-V_{1,T+1,\beta,m}(\omega^{\prime})|\leq
C|\omega-\omega^{\prime}|.$

The proof is thus finished by the induction process.

Last, we give a lemma establishing the order of
$V^{\prime}_{1,T,\beta,m}(\cdot;u=1)$ and
$V^{\prime}_{1,T,\beta,m}(\cdot;u=0)$ under certain conditions which further
leads to a threshold structure of the optimal single-arm policy as detailed in
Sec 2.3.

######  Lemma 2.6.

Suppose that $p_{11}>p_{01}$ and
$\beta\leq\frac{1}{(3-\epsilon)(p_{11}-p_{01})}$, we have

(41) $\displaystyle V_{1,T,\beta,m}^{\prime}(\omega;u=1)\geq
V_{1,T,\beta,m}^{\prime}(\omega;u=0),$

where $V_{1,T,\beta,m}^{\prime}(\omega;u=i)$ denotes the right derivative of
$V_{1,T,\beta,m}(\cdot;u=i)$ at $\omega$ for $i\in\\{0,1\\}$. The above
inequality is also true if $p_{01}>p_{11}$ and
$\beta\leq\frac{1}{(5-2\epsilon)(p_{01}-p_{11})}$.

######  Proof 2.7.

Again, we prove by induction on the time horizon $T$. When $T=1$, it is clear
that $V_{1,1,\beta,m}(\omega;u=1)=(1-\epsilon)\omega$ and
$V_{1,1,\beta,m}(\omega;u=0)=m$:

(42) $\displaystyle
V_{1,1,\beta,m}^{\prime}(\omega;u=1)=1-\epsilon>V_{1,1,\beta,m}^{\prime}(\omega;u=0)=0.$

Assume that $V_{1,1,\beta,m}^{\prime}(\omega;u=1)\geq
V_{1,T,\beta,m}^{\prime}(\omega;u=0)$ for $T\geq 1$. From (40), we have, in
case of $p_{01}>p_{11}$ and $\beta\leq\frac{1}{(5-2\epsilon)(p_{01}-p_{11})}$,

$C\beta(p_{01}-p_{11})\leq(1-\epsilon)-(2-\epsilon)\beta C(p_{01}-p_{11}),$

which shows that $f_{T}^{\prime}(\omega)\geq g_{T}^{\prime}(\omega)$.
When $p_{11}>p_{01}$, $V_{1,T,\beta,m}(\omega)$ is increasing with $\omega$
with nonnegative right derivatives by Lemma 2.2. We can thus obtain tighter
bounds on $f_{T}^{\prime}(\omega)$ and $g_{T}^{\prime}(\omega)$:

$\left\\{\begin{aligned} (1-\epsilon)\leq
f_{T}^{\prime}(\omega)&\leq(1-\epsilon)+(2-\epsilon)\beta C(p_{11}-p_{01}),\\\
0\leq g_{T}^{\prime}(\omega)&\leq C\beta(p_{11}-p_{01}).\end{aligned}\right.$

If $\beta\leq\frac{1}{(3-\epsilon)(p_{11}-p_{01})}$, we have

$C\beta(p_{11}-p_{01})\leq(1-\epsilon),$

which shows that $f_{T}^{\prime}(\omega)\geq g_{T}^{\prime}(\omega)$. The
proof is thus complete.

###  2.3 Threshold Policy and Indexability

In this section, we show that the optimal single-arm policy is a threshold
policy under the constraints on the discount factor $\beta$ specified in Sec.
2.2 and analyze the conditions for indexability. First, for a finite-horizon
single-armed bandit, a threshold policy $\pi$ is defined by a time-dependent
real number $\omega_{T,\beta}(m)$ such that

(43) $u_{T,m}(\omega)=\begin{cases}1,&\text{if }\omega>\omega_{T,\beta}(m);\\\
0,&\text{if }\omega\leq\omega_{T,\beta}(m).\end{cases}$

In the above $u_{T,m}(\omega)\in\\{0,1\\}$ is the action taken under $\pi$ at
the current state $\omega$ with $T$ slots remaining. Intuitively, the larger
$\omega$ is, the larger expected immediate reward to accrue and thus more
attractive to activate the arm. We formally prove this statement under certain
conditions in the following theorem.

######  Theorem 2.8.

Suppose that $p_{11}>p_{01}$ and
$\beta\leq\frac{1}{(3-\epsilon)(p_{11}-p_{01})}$. For any $T\geq 1$, the
optimal single-arm policy $\pi^{*}$ is a threshold policy, i.e., there exists
$\omega_{T,\beta}^{*}(m)\in\mathbb{R}$ such that under $\pi^{*}$, the optimal
action is

$u_{T,m}^{*}(\omega)=\begin{cases}1,&\text{if
}\omega>\omega_{T,\beta}^{*}(m);\\\ 0,&\text{if
}\omega\leq\omega_{T,\beta}^{*}(m).\end{cases}$

Furthermore, at the threshold $\omega_{T,\beta}^{*}(m)$,

(44) $\displaystyle
V_{1,T,\beta,m}(\omega_{T,\beta}^{*}(m);u=0)=V_{1,T,\beta,m}(\omega_{T,\beta}^{*}(m);u=1).$

The conclusion is also true for the case of $p_{01}>p_{11}$ and
$\beta\leq\frac{1}{(5-2\epsilon)(p_{01}-p_{11})}$.

######  Proof 2.9.

At $T=1$,
$V_{1,1,\beta,m}(\omega;u=1)=(1-\epsilon)\omega,V_{1,1,\beta,m}(\omega;u=0)=m$.
Thus we can choose $\omega_{1,\beta}^{*}(m)$ as follows:

$\omega_{1,\beta}^{*}(m)=\begin{cases}c,&\text{if }m\geq 1-\epsilon;\\\
\frac{m}{1-\epsilon},&\text{if }0\leq m<1-\epsilon;\\\ b,&\text{if
}m<0,\end{cases}$

where $b<0,c>1$ are arbitrary constants.

For $T\geq 1$, when the condition on $\beta$ is satisfied, Lemma 2.6 shows
that

(45) $\displaystyle
h_{T}(\omega){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,V_{1,T,\beta,m}(1;u=1)-V_{1,T,\beta,m}(1;u=0),$
(46) $\displaystyle h^{\prime}_{T}(\omega)\geq
0,\quad\forall~{}\omega\in(0,1).$

This shows that $h_{T}(\cdot)$ is monotonically increasing and either has no
zeros in the interval $[0,1]$ or intersects with it over a closed interval
(which can be a single point) only. Specially,

$\left\\{\begin{aligned} V_{1,T,\beta,m}(0;u=1)&=\beta
V_{1,T-1,\beta,m}(p_{01}),\\\ V_{1,T,\beta,m}(0;u=0)&=m+\beta
V_{1,T-1,\beta,m}(p_{01}),\\\ V_{1,T,\beta,m}(1;u=1)&=(1-\epsilon)+\beta
V_{1,T-1,\beta,m}(p_{11}),\\\ V_{1,T,\beta,m}(1;u=0)&=m+\beta
V_{1,T-1,\beta,m}(p_{11}).\end{aligned}\right.$

Consider the following three regions of $m$.
i) $0\leq m<1-\epsilon$. In this case, $V_{1,T,\beta,m}(0;u=1)\leq
V_{1,T,\beta,m}(0;u=0)$ and $V_{1,T,\beta,m}(1;u=1)>V_{1,T,\beta,m}(1;u=0)$.
Therefore $h_{T}(\cdot)$ intersects over (at least) one point in $[0,1]$. This
point can thus be chosen as $\omega_{T,\beta}^{*}(m)$.
ii) $m<0$. In this case, $V_{1,T,\beta,m}(0;u=1)>V_{1,T,\beta,m}(0;u=0)$ and
$V_{1,T,\beta,m}(1;u=1)>V_{1,T,\beta,m}(1;u=0)$. So $h_{T}(\cdot)$ is strictly
positive over $[0,1]$ and we can choose $\omega_{T,\beta}^{*}(m)=b$ with any
$b<0$.
iii) $m\geq(1-\epsilon)$. In this case, always choosing the passive action is
clearly optimal as the expected immediate reward is uniformly upper-bounded by
$m$ over the whole belief state space. We can thus choose
$\omega_{T,\beta}^{*}(m)=c$ with any $c>1$.

In conclusion, when the conditions in the theorem are satisfied, the optimal
finite-horizon single-arm policy is a threshold policy for any horizon length
$T\geq 1$.

In the next theorem, we show that the optimal single-arm policy over the
infinite horizon is also a threshold policy under the same conditions.

######  Theorem 2.10.

Fix the subsidy $m$. The finite-horizon value functions
$V_{1,T\beta,m}(\cdot)$,
$V_{1,T,\beta,m}(\cdot;u=1)\text{~{}and~{}}V_{1,T,\beta,m}(\cdot;u=0)$
uniformly converge to the infinite-horizon value functions
$V_{\beta,m}(\cdot)$,
$V_{\beta,m}(\cdot;u=1)\text{~{}and~{}}V_{\beta,m}(\cdot;u=0)$ which are
consequently obedient to the same properties established in Lemmas 2.2 and 2.4
and Theorem 2.8.

######  Proof 2.11.

Consider the single-armed bandit with subsidy. We will apply two different
scenarios to analyze the relation between $V_{1,T,\beta,m}(\omega)$ and
$V_{\beta,m}(\omega)$. First, we apply a $T$-horizon optimal policy to the
first $T$ time slots and the infinite-horizon optimal policy to the future
slots. Suppose that the initial belief state is $\omega$ and after $T$ slots
the belief state becomes to a policy-dependent random variable $\omega(T+1)$.
Then the maximum expected total discounted reward under this policy is
$V_{1,T,\beta,m}(\omega)+\beta^{T}\mathbb{E}[V_{\beta,m}(\omega(T+1))]$ where
the expectation is taken w.r.t. $\omega(T+1)$. By the definition of
$V_{\beta,m}(\omega)$, we have

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

In the second scenario, we apply the infinite-horizon optimal policy to the
RMAB and the expected total discounted reward over the first $T$ slots is
$V_{\beta,m}(\omega)-\beta^{T}\mathbb{E}[V_{\beta,m}(\omega(T\\\ +1))]$. By
the definition of $V_{1,T,\beta,m}(\omega)$, we have

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

Combining the two inequalities above, we obtain

$0\leq
V_{\beta,m}(\omega)-V_{1,T,\beta,m}(\omega)\leq\beta^{T}\frac{\max\\{1,m\\}}{1-\beta}\rightarrow
0~{}(\text{as}~{}T\rightarrow\infty).$

Thus $V_{1,T,\beta,m}(\cdot)$ uniformly converges to $V_{\beta.m}(\cdot)$ as
$T\rightarrow\infty$. The uniform convergence of
$V_{1,T,\beta,m}(\cdot;u=1)\text{~{}and~{}}V_{1,T,\beta,m}(\cdot;u=0)$ to
$V_{\beta,m}(\cdot;u=1)\text{~{}and~{}}V_{\beta,m}(\cdot;u=0)$ respectively
can be shown similarly.

For any $\epsilon>0$, there exists a $T_{0}\geq 1$ such that
$|V_{\beta,m}(\omega)-V_{1,T,\beta,m}(\omega)|<\epsilon$ for any $T\geq T_{0}$
and any $\omega\in[0,1]$. Therefore the properties of monotonicity and
Lipschitz-continuity of $V_{1,T,\beta,m}(\omega)$ established under certain
conditions in Lemmas 2.2 and 2.4 and the convexity of the finite-horizon value
functions also hold for $V_{\beta,m}(\omega)$. Recall the definition of
$h_{T}(\omega)$ in (45) and define the continuous function (as the difference
of two convex functions $V_{\beta,m}(\cdot;u=1)$ and $V_{\beta,m}(\cdot;u=0)$)

(47) $\displaystyle
h(\cdot)=V_{\beta,m}(\cdot;u=1)-V_{\beta,m}(\cdot;u=0)=\lim_{T\rightarrow\infty}h_{T}(\cdot).$

The above limit is well defined due to the uniform convergence of
$V_{1,T,\beta,m}(\cdot;u=i)$ to $V_{\beta,m}(\cdot;u=i)$ as
$T\rightarrow\infty$ (for $i\in\\{0,1\\}$). Since $h_{T}(\omega)$ is
monotonically increasing with $\omega$ for any $T\geq 1$ according to Lemma
2.6, $h(\omega)$ is also monotonically increasing which shows that the
infinite-horizon optimal policy is a threshold policy.

By far we have established the threshold structure of the optimal single-arm
policy with subsidy based on the analysis of $V_{\beta,m}(\omega)$ as a
function of the belief state $\omega$ with $m$ fixed. To study the
indexability condition, we now analyze the properties of $V_{\beta,m}(\omega)$
as a function of the subsidy $m$ with the starting belief $\omega$ fixed. From
Definition 2.1 and the threshold structure of the optimal policy, the
indexability of our model is reduced to requiring that the threshold
$\omega^{*}_{\beta}(m)$ is monotonically increasing with $m$ (if the threshold
is a closed interval then the right end is selected). Note that for the
infinite-horizon problem, the threshold $\omega^{*}_{\beta}(m)$ is independent
of time. Furthermore, $V_{\beta,m}(\omega)$ is also convex in $m$ as for any
$m_{1},m_{2}\in\mathbb{R}$ and $\lambda\in(0,1)$ the optimal policy
$\pi_{\beta}^{*}(\lambda m_{1}+(1-\lambda)m_{2})$ achieving $V_{\beta,\lambda
m_{1}+(1-\lambda)m_{2}}(\omega)$ applied respectively on the problem with
subsides $m_{1}$ and $m_{2}$ cannot outperform those achieving
$V_{\beta,m_{1}}(\omega)$ and $V_{\beta,m_{2}}(\omega)$. Specifically, let
$r_{a}$ be the expected total discounted reward from the active action and
$r_{p}(m)$ that from the passive action under $\pi_{\beta}^{*}(\lambda
m_{1}+(1-\lambda)m_{2})$ applied to the problem with subsidy $m$, then

(48) $\displaystyle\lambda
V_{\beta,m_{1}}(\omega)+(1-\lambda)V_{\beta,m_{2}}(\omega)$
$\displaystyle\geq$ $\displaystyle r_{a}+\lambda
r_{p}(m_{1})+(1-\lambda)r_{p}(m_{2})$ (49) $\displaystyle=$ $\displaystyle
r_{a}+r_{p}(\lambda m_{1}+(1-\lambda)m_{2})$ (50) $\displaystyle=$
$\displaystyle V_{\beta,\lambda m_{1}+(1-\lambda)m_{2}}(\omega).$

Since $V_{\beta,m}(\omega)$ is convex in $m$, its left and right derivatives
with $m$ exist at every point $m_{0}\in\mathbb{R}$. Furthermore, consider two
policies $\pi_{\beta}^{*}(m_{1})$ and $\pi_{\beta}^{*}(m_{2})$ achieving
$V_{\beta,m_{1}}(\omega)$ and $V_{\beta,m_{2}}(\omega)$ for any
$m_{1},m_{2}\in\mathbb{R}$, respectively. With a similar interchange argument
of $\pi_{\beta}^{*}(m_{1})$ and $\pi_{\beta}^{*}(m_{2})$ as above, we have

(51) $\displaystyle V_{\beta,m_{1}}(\omega)\geq
V_{\beta,m_{2}}(\omega)-\frac{|m_{1}-m_{2}|}{1-\beta},$ (52) $\displaystyle
V_{\beta,m_{2}}(\omega)\geq
V_{\beta,m_{1}}(\omega)-\frac{|m_{1}-m_{2}|}{1-\beta}.$

Therefore
$|V_{\beta,m_{1}}(\omega)-V_{\beta,m_{2}}(\omega)|\leq\frac{1}{1-\beta}|m_{1}-m_{2}|$
and $V_{\beta,m}(\omega)$ is Lipschitz continuous in $m$. By the Rademacher
theorem, $V_{\beta,m}(\omega)$ is differentiable almost everywhere in $m$. For
a small increase of $m$, the rate at which $V_{\beta,m}(\omega)$ increases is
at least the expected total discounted passive time under any optimal policy
for the problem with subsidy $m$ starting from the belief state $\omega$. In
the following theorem, we formalize this relation between the value function
and the passive time as well as a sufficient condition for the indexability of
our model.

######  Theorem 2.12.

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

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

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

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

Furthermore, the single-armed bandit is indexable if at least one of the
following condition is satisfied:

  * i.

for any $m_{0}\in[0,1-\epsilon)$ the optimal policy is a threshold policy with
threshold $\omega^{*}_{\beta}(m_{0})\in[0,1)$ (if the threshold is a closed
interval then the right end is selected) and

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

  * ii.

for any $m_{0}\in\mathbb{R}$ and $\omega\in P(m_{0})$, we have

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

######  Proof 2.13.

The proof of (54) follows directly from the argument in Theorem 1 in [3] and
is omitted here. To prove the sufficiency of (55), we note that if it is true
then there exists a $\Delta m>0$ such that

$\displaystyle
V_{\beta,m}(\omega^{*}_{\beta}(m_{0});u=0)-V_{\beta,m_{0}}(\omega^{*}_{\beta}(m_{0});u=0){}$
(57)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}>V_{\beta,m}(\omega^{*}_{\beta}(m_{0});u=1)-V_{\beta,m_{0}}(\omega^{*}_{\beta}(m_{0});u=1),\forall~{}m\in(m_{0},m_{0}+\Delta
m).$

Since
$V_{\beta,m_{0}}(\omega^{*}_{\beta}(m_{0});u=0)=V_{\beta,m_{0}}(\omega^{*}_{\beta}(m_{0});u=1)$,
we have
$V_{\beta,m}(\omega^{*}_{\beta}(m_{0});u=0)>V_{\beta,m}(\omega^{*}_{\beta}(m_{0});u=1)$
which implies that the threshold $\omega^{*}_{\beta}(m_{0})$ remains in the
passive set as $m$ continuously increases so $P(m)$ is monotonically
increasing with $m$. This conclusion is clearly true for the trivial case of
$m<0$ or $m\geq 1-\epsilon$. The sufficiency of (56) is obvious as any
$\omega\in P(m)$ is impossible to escape from $P(m)$ as $m$ increases due to
the nondereasing property of $V_{\beta,m}(\omega;u=0)-V_{\beta,m}(\omega;u=1)$
enforced by (56).

Theorem 2.12 essentially provides a way for checking the indexability
condition in terms of the passive times. For example, equation (55) is
equivalent to for any $m\in[0,1-\epsilon)$,

(58) $\displaystyle\beta[(1-\epsilon)\omega_{\beta}^{*}(m)D_{\beta,m}(p_{11})$
$\displaystyle+$
$\displaystyle(1-(1-\epsilon)\omega_{\beta}^{*}(m))D_{\beta,m}(\mathcal{T}(\frac{\epsilon\omega_{\beta}^{*}(m)}{\epsilon\omega_{\beta}^{*}(m)+1-\omega_{\beta}^{*}(m)}))]{}$
$\displaystyle<$ $\displaystyle 1+\beta
D_{\beta,m}(\mathcal{T}(\omega_{\beta}^{*}(m))).$

The above strict inequality clearly holds if $\beta<0.5$ since
$D_{\beta,m}(\cdot)\in[0,\frac{1}{1-\beta}]$ for any $m\in\mathbb{R}$. When
$\beta=0.5$, we prove by contradiction that the strict inequality (58) must
hold under the threshold structure of the optimal policy. If
$\omega_{\beta}^{*}(m)=0$ then (58) is clearly true. Assume that the left and
right sides of (58) are equal and $\omega_{\beta}^{*}(m)\neq 0$. In this case,
we have

(59) $\displaystyle D_{\beta,m}(p_{11})=\frac{1}{1-\beta},$ (60)
$\displaystyle D_{\beta,m}(\mathcal{T}(\omega_{\beta}^{*}(m)))=0.$

Equation (60) implies that starting from $\mathcal{T}(\omega_{\beta}^{*}(m))$,
always activating the arm is strictly optimal. This means that the threshold
$\omega_{\beta}^{*}(m)$ is strictly below $p_{11}$ and we have a contradiction
to (59). Another easier way to see that the bandit is indexable if $\beta\leq
0.5$ is that (56) would be satisfied since no strict inequality is required.
However, condition (58) provides a convenient way for approximately computing
the passive times as well as the value functions which leads to an efficient
algorithm for evaluating the indexability and solving for the Whittle index
function for any $\beta\in(0,1)$, as detailed in the next section.

######  Corollary 2.14.

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

###  2.4 The Approximated Whittle Index

The threshold structure of the optimal single-arm policy under certain
conditions yields the following iterative nature of the dynamic equations for
both $D_{\beta,m}(\omega)$ and $V_{\beta,m}(\omega)$. Define the first
crossing time

(61) $L(\omega,\omega^{\prime})=\min_{0\leq
k<\infty}\\{k:\mathcal{T}^{k}(\omega)>\omega^{\prime}\\}.$

In the above
$\mathcal{T}^{0}(\omega){\,\stackrel{{\scriptstyle\Delta}}{{=}}}\,\omega$ and
we set $L(\omega,\omega^{\prime})=+\infty$ if
$\mathcal{T}^{k}(\omega)\leq\omega$ for all $k\geq 0$. Clearly
$L(\omega,\omega^{\prime})$ is the minimum time slots required for a belief
state $\omega$ to stay in the passive set $P(m)$ before the arm is activated
given a threshold $\omega^{\prime}\in[0,1)$. Consider the nontrivial case
where $p_{01},p_{11}\in(0,1)$ and $p_{01}\neq p_{11}$ such that the Markov
chain of the internal arm states is aperiodic and irreducible and that the
belief update is action-dependent. From (6), if $p_{11}>p_{01}$ then

(62) $L(\omega,\omega^{\prime})=\begin{cases}0,&\omega>\omega^{\prime}\\\
\bigg{\lfloor}\log_{p_{11}-p_{01}}^{\frac{p_{01}-\omega^{\prime}(1-p_{11}+p_{01})}{p_{01}-\omega(1-p_{11}+p_{01})}}\bigg{\rfloor}+1,&\omega\leq\omega^{\prime}<\omega_{o}\\\
\infty,&\omega\leq\omega^{\prime},\omega^{\prime}\geq\omega_{o}\end{cases};$

or if $p_{11}<p_{01}$ then

(63) $L(\omega,\omega^{\prime})=\begin{cases}0,&\omega>\omega^{\prime}\\\
1,&\omega\leq\omega^{\prime},\mathcal{T}(\omega)>\omega^{\prime}\\\
\infty,&\omega\leq\omega^{\prime},\mathcal{T}(\omega)\leq\omega^{\prime}\end{cases}.$

Suppose that the following conditions are satisfied such that the optimal
single-arm policy is a threshold policy and the indexability holds:

(64)
$\beta\leq\begin{cases}\min\\{\frac{1}{(3-\epsilon)(p_{11}-p_{01})},0.5\\},&\text{if}~{}p_{11}>p_{01}\\\
\min\\{\frac{1}{(5-2\epsilon)(p_{01}-p_{11})},0.5\\},&\text{if}~{}p_{11}<p_{01}\end{cases}.$

To solve for the Whittle index function $W(\omega)$, given the current arm
state $\omega$, we aim to find out the minimum subsidy $m$ that makes it as a
threshold:

(65) $\displaystyle
V_{\beta,m}(\omega)=V_{\beta,m}(\omega;u=1)=V_{\beta,m}(\omega;u=0),$
$\displaystyle
V_{\beta,m}(\omega;u=1)=(1-\epsilon)\omega+\beta[(1-\epsilon)\omega
V_{\beta,m}(p_{11}){}$ (66)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+(1-(1-\epsilon)\omega)V_{\beta,m}(\mathcal{T}\circ\phi(\omega))],$
(67) $\displaystyle V_{\beta,m}(\omega;u=0)=m+\beta
V_{\beta,m}(\mathcal{T}(\omega)).$

Given a threshold $\omega^{*}_{\beta}(m)\in[0,1)$ and any $\omega\in[0,1]$,
the value function $V_{\beta,m}(\omega)$ can be expanded by the first crossing
time as

$\displaystyle~{}~{}~{}~{}V_{\beta,m}(\omega)$ $\displaystyle=$
$\displaystyle\frac{1-\beta^{L(\omega,\omega^{*}_{\beta}(m))}}{1-\beta}m+\beta^{L(\omega,\omega^{*}_{\beta}(m))}V_{\beta,m}(\mathcal{T}^{L(\omega,\omega^{*}_{\beta}(m))}(\omega);u=1){}$
$\displaystyle=$
$\displaystyle\frac{1-\beta^{L(\omega,\omega^{*}_{\beta}(m))}}{1-\beta}m+\beta^{L(\omega,\omega^{*}_{\beta}(m))}\bigg{\\{}(1-\epsilon)\mathcal{T}^{L(\omega,\omega^{*}_{\beta}(m))}(\omega){}$
$\displaystyle+$
$\displaystyle\beta\bigg{[}(1-\epsilon)\mathcal{T}^{L(\omega,\omega^{*}_{\beta}(m))}(\omega)V_{\beta,m}(p_{11})+(1-(1-\epsilon)\mathcal{T}^{L(\omega,\omega^{*}_{\beta}(m))}(\omega)){}$
$\displaystyle~{}~{}~{}~{}\cdot
V_{\beta,m}\bigg{(}\mathcal{T}\bigg{(}\frac{\epsilon\mathcal{T}^{L(\omega,\omega^{*}_{\beta}(m))}(\omega)}{\epsilon\mathcal{T}^{L(\omega,\omega^{*}_{\beta}(m))}(\omega)+1-\mathcal{T}^{L(\omega,\omega^{*}_{\beta}(m))}(\omega)}\bigg{)}\bigg{)}\bigg{]}\bigg{\\}}.{}$

There is no doubt that the last item of the above equation has caused us
trouble in solving for $V_{\beta,m}(\omega)$. However, if we let

(69)
$\displaystyle\begin{split}f(\omega,\omega_{\beta}^{*}(m))&=\mathcal{T}\bigg{(}\frac{\epsilon\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega)}{\epsilon\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega)+1-\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega)}\bigg{)}\\\
&=\frac{p_{11}\epsilon\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega)+p_{01}(1-\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega))}{\epsilon\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega)+1-\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega)}\end{split}$

and construct iteratively the sequence $\\{k_{n}\\}$ as
$k_{n+1}=f(k_{n},\omega_{\beta}^{*}(m))$ with $k_{0}=\omega$. We then get the
following sequence of equations:

$\left\\{\begin{aligned}
V_{\beta,m}(k_{0})&=\frac{1-\beta^{L(k_{0},\omega_{\beta}^{*}(m))}}{1-\beta}m+\beta^{L(k_{0},\omega_{\beta}^{*}(m))}\big{\\{}(1-\epsilon)\mathcal{T}^{L(k_{0},\omega_{\beta}^{*}(m))}(k_{0})+\beta\big{[}(1-\epsilon)\\\
&~{}~{}\cdot\mathcal{T}^{L(k_{0},\omega_{\beta}^{*}(m))}(k_{0})V_{\beta,m}(p_{11})+(1-(1-\epsilon)\mathcal{T}^{L(k_{0},\omega_{\beta}^{*}(m))}(k_{0}))V_{\beta,m}(k_{1})\big{]}\big{\\}}\\\
V_{\beta,m}(k_{1})&=\frac{1-\beta^{L(k_{1},\omega_{\beta}^{*}(m))}}{1-\beta}m+\beta^{L(k_{1},\omega_{\beta}^{*}(m))}\big{\\{}(1-\epsilon)\mathcal{T}^{L(k_{1},\omega_{\beta}^{*}(m))}(k_{1})+\beta\big{[}(1-\epsilon)\\\
&~{}~{}\cdot\mathcal{T}^{L(k_{1},\omega_{\beta}^{*}(m))}(k_{1})V_{\beta,m}(p_{11})+(1-(1-\epsilon)\mathcal{T}^{L(k_{1},\omega_{\beta}^{*}(m))}(k_{1}))V_{\beta,m}(k_{2})\big{]}\big{\\}}\\\
\cdots\\\
V_{\beta,m}(k_{n})&=\frac{1-\beta^{L(k_{n},\omega_{\beta}^{*}(m))}}{1-\beta}m+\beta^{L(k_{n},\omega_{\beta}^{*}(m))}\big{\\{}(1-\epsilon)\mathcal{T}^{L(k_{n},\omega_{\beta}^{*}(m))}(k_{n})\\\
&~{}~{}+\beta\big{[}(1-\epsilon)\cdot\mathcal{T}^{L(k_{n},\omega_{\beta}^{*}(m))}(k_{n})V_{\beta,m}(p_{11})+(1-(1-\epsilon)\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}\cdot\mathcal{T}^{L(k_{n},\omega_{\beta}^{*}(m))}(k_{n}))V_{\beta,m}(k_{n+1})\big{]}\big{\\}}\\\
\cdots\end{aligned}\right.$

For sufficiently large $n$, we can get an estimation of
$V_{\beta,m}(\omega)=V_{\beta,m}(k_{0})$ with an arbitrarily small error by
setting $V_{\beta,m}(k_{n+1})=0$ whose error is discounted by $\beta$ in
computing $V_{\beta,m}(k_{n})$ thus causing a geometrically decreasing error
propagation in the backward computation process for $V_{\beta,m}(k_{0})$. Note
that we first compute $V_{\beta,m}(p_{11})$ in the same way by setting
$k_{0}=p_{11}$ in the above equation set. Therefore we can have an estimation
of $V_{\beta,m}(\omega)$ with arbitrarily high precision for any
$\omega\in[0,1]$. Interestingly, extensive numerical results found that
$\\{k_{n}\\}$ quickly converges to a limit belief state $k$ (independent of
$k_{0}$) or oscillates within a small neighborhood of $k$. Specifically, after
$4$ iterations, the difference $|k_{4}-k|$ becomes quite small so we can set
$V_{\beta,m}(k_{5})=V_{\beta,m}(k_{4})$ and efficiently solve the finite
linear equation set (up to $V_{\beta,m}(k_{4})$). In general, the
$n$-iteration Whittle index is based on the solution of the following
equations:

$\displaystyle{}\left\\{\begin{aligned}
V_{\beta,m}(p_{11})&=\frac{1-\beta^{L(p_{11},\omega_{\beta}^{*}(m))}}{1-\beta}m+\beta^{L(p_{11},\omega_{\beta}^{*}(m))}\big{\\{}(1-\epsilon)\mathcal{T}^{L(p_{11},\omega_{\beta}^{*}(m))}(p_{11})\\\
&~{}+\beta\big{[}(1-\epsilon)\mathcal{T}^{L(p_{11},\omega_{\beta}^{*}(m))}(p_{11})V_{\beta,m}(p_{11})+(1-(1-\epsilon)\\\
&~{}~{}~{}~{}~{}~{}~{}~{}\cdot\mathcal{T}^{L(p_{11},\omega_{\beta}^{*}(m))}(p_{11}))V_{\beta,m}(k_{1})\big{]}\big{\\}}\\\
V_{\beta,m}(k_{1})&=\frac{1-\beta^{L(k_{1},\omega_{\beta}^{*}(m))}}{1-\beta}m+\beta^{L(k_{1},\omega_{\beta}^{*}(m))}\big{\\{}(1-\epsilon)\mathcal{T}^{L(k_{1},\omega_{\beta}^{*}(m))}(k_{1})+\beta\big{[}(1-\epsilon)\\\
&~{}\cdot\mathcal{T}^{L(k_{1},\omega_{\beta}^{*}(m))}(k_{1})V_{\beta,m}(p_{11})+(1-(1-\epsilon)\mathcal{T}^{L(k_{1},\omega_{\beta}^{*}(m))}(k_{1}))V_{\beta,m}(k_{2})\big{]}\big{\\}}\\\
\cdots\\\
V_{\beta,m}(k_{n})&=\frac{1-\beta^{L(k_{n},\omega_{\beta}^{*}(m))}}{1-\beta}m+\beta^{L(k_{n},\omega_{\beta}^{*}(m))}\big{\\{}(1-\epsilon)\mathcal{T}^{L(k_{n},\omega_{\beta}^{*}(m))}(k_{n})\\\
&~{}+\beta\big{[}(1-\epsilon)\mathcal{T}^{L(k_{n},\omega_{\beta}^{*}(m))}(k_{n})V_{\beta,m}(p_{11})+(1-(1-\epsilon)\\\
&~{}~{}~{}~{}~{}~{}~{}~{}\cdot\mathcal{T}^{L(k_{n},\omega_{\beta}^{*}(m))}(k_{n}))V_{\beta,m}(k_{n})\big{]}\big{\\}}\end{aligned}\right..$

According to Theorem 2.12, the passive time $D_{\beta,m}(\omega)$ can also be
approximately solved based on the following equations:

$\left\\{\begin{aligned}
D_{\beta,m}(p_{11})&=\frac{1-\beta^{L(p_{11},\omega_{\beta}^{*}(m))}}{1-\beta}+\beta^{L(p_{11},\omega_{\beta}^{*}(m))+1}\big{\\{}(1-\epsilon)\mathcal{T}^{L(p_{11},\omega_{\beta}^{*}(m))}(p_{11})\\\
&~{}\cdot
D_{\beta,m}(p_{11})+(1-(1-\epsilon)\mathcal{T}^{L(p_{11},\omega_{\beta}^{*}(m))}(p_{11}))D_{\beta,m}(k_{1})\big{\\}}\\\
D_{\beta,m}(k_{1})&=\frac{1-\beta^{L(k_{1},\omega_{\beta}^{*}(m))}}{1-\beta}+\beta^{L(k_{1},\omega_{\beta}^{*}(m))+1}\big{\\{}(1-\epsilon)\mathcal{T}^{L(k_{1},\omega_{\beta}^{*}(m))}(k_{1})\\\
&\cdot
D_{\beta,m}(p_{11})+(1-(1-\epsilon)\mathcal{T}^{L(k_{1},\omega_{\beta}^{*}(m))}(k_{1}))D_{\beta,m}(k_{2})\big{\\}}\\\
\cdots\\\
D_{\beta,m}(k_{n})&=\frac{1-\beta^{L(k_{n},\omega_{\beta}^{*}(m))}}{1-\beta}+\beta^{L(k_{n},\omega_{\beta}^{*}(m))+1}\big{\\{}(1-\epsilon)\mathcal{T}^{L(k_{n},\omega_{\beta}^{*}(m))}(k_{n})\\\
&\cdot
D_{\beta,m}(p_{11})+(1-(1-\epsilon)\mathcal{T}^{L(k_{n},\omega_{\beta}^{*}(m))}(k_{n}))D_{\beta,m}(k_{n})\big{\\}}\end{aligned}\right..$

Substituting $\omega$ for $\omega^{*}_{\beta}(m)$ in the above $n+1$ linear
equations with $n+1$ unknowns (first solving for $\omega=p_{11}$), we can
obtain $V_{\beta,m}(\omega^{\prime})$ and $D_{\beta,m}(\omega^{\prime})$ for
any $\omega^{\prime}\in[0,1]$ according to the linear equation sets. The
indexability condition (55) in Theorem 2.12 can be checked online: for the
original multi-armed bandit problem and for each arm at state $\omega(t)$ at
time $t$, we compute its approximated Whittle index $W(\omega(t))$ by solving
a set of linear equations, which has a polynomial complexity of the iteration
number $n$, independent of the decision time $t$. At time $t$, for each arm,
if $W(\cdot)$ is found to be nondecreasing with the arm states
$(\omega(1),\omega(2),\cdots,\omega(t))$ appeared so far starting from the
initial belief vector $\Omega(1)$ defined in (2), then the indexability has
not been violated. Interestingly, extensive numerical studies have shown that
the indexability is always satisfied as illustrated in Sec. 4.

For large $\beta\in(0,1)$ where the threshold structure of the optimal policy
or the indexability may not hold (i.e., condition (64) is not satisfied), we
can still use the above process to solve for the subsidy $m$ that makes (65)
true if it exists. Note that after computing the value functions appeared in
(65) in terms of $m$, both $V_{\beta,m}(\omega;u=1)$ and
$V_{\beta,m}(\omega;u=0)$ are linear (affine) in $m$ and their equality gives
a unique solution of $m$ if their linear coefficients are not equal. This $m$,
if exists, can thus be used as the approximated Whittle index $W(\omega)$
without requiring indexability or threshold-based optimal policy. If it does
not exist, we can simply set $W(\omega)=\omega B$. The existence of such an
$m$ is defined as the relaxed indexability in [3]. Note that extensive
numerical studies have shown that the relaxed indexability of our model with
imperfect state observations is always satisfied as well. Before summarizing
our general algorithm for all $\beta\in(0,1)$ in Sec. 3, we solve for the
approximated Whittle index function in closed-form for the simplest case of
$0$-iteration, which is referred to as the imperfect Whittle index. Note that
if $\epsilon\rightarrow 0$ then
$\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega})\rightarrow
p_{01}$. Thus when $\epsilon$ is sufficiently small, we can approximate
$V_{\beta,m}(\mathcal{T}(\frac{\epsilon\omega}{\epsilon\omega+1-\omega}))$ by
$V_{\beta,m}(p_{01})$. Under this approximation, we have, for any
$\omega\in[0,1]$,

$\left\\{\begin{aligned}
&V_{\beta,m}(\omega;u=1)=(1-\epsilon)\omega+\beta\big{[}(1-\epsilon)\omega
V_{\beta,m}(p_{11})+(1-(1-\epsilon)\omega)V_{\beta,m}(p_{01})\big{]}\\\
&V_{\beta,m}(\omega;u=0)=m+\beta V_{\beta,m}(\mathcal{T}(\omega))\\\
&V_{\beta,m}(\omega)=\frac{1-\beta^{L(\omega,\omega_{\beta}^{*}(m))}}{1-\beta}m+\beta^{L(\omega,\omega_{\beta}^{*}(m))}\big{\\{}(1-\epsilon)\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega)\\\
&+\beta\big{[}(1-\epsilon)\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega)V_{\beta,m}(p_{11})+(1-(1-\epsilon)\mathcal{T}^{L(\omega,\omega_{\beta}^{*}(m))}(\omega))V_{\beta,m}(p_{01})\big{]}\big{\\}}\end{aligned}\right..$

By using the above three equations, we can directly solve for
$V_{\beta,m}(p_{01})$ and $V_{\beta,m}(p_{11})$ in closed-form.
When $p_{11}>p_{01}$, $V_{\beta,m}(p_{01})=$

$\begin{cases}\frac{(1-\epsilon)p_{01}}{(1-\beta)(1-\beta(1-\epsilon)p_{11}+\beta(1-\epsilon)p_{01})},\
\text{if }\omega_{\beta}^{*}(m)<p_{01}&\\\
\frac{(1-\beta(1-\epsilon)p_{11})(1-\beta^{L(p_{01},\omega_{\beta}^{*}(m))})m+(1-\epsilon)(1-\beta)\beta^{L(p_{01},\omega_{\beta}^{*}(m))}\mathcal{T}^{L(p_{01},\omega_{\beta}^{*}(m))}(p_{01})}{(1-\beta(1-\epsilon)p_{11})(1-\beta)(1-\beta^{L(p_{01},\omega_{\beta}^{*}(m))+1})+(1-\epsilon)(1-\beta)^{2}\beta^{L(p_{01},\omega_{\beta}^{*}(m))+1}\mathcal{T}^{L(p_{01},\omega_{\beta}^{*}(m))}(p_{01})},\\\
\quad\quad\quad\quad\quad\quad\quad\quad\text{if
}p_{01}\leq\omega_{\beta}^{*}(m)<\omega_{0}&\\\ \frac{m}{1-\beta},\ \text{if
}\omega_{\beta}^{*}(m)\geq\omega_{0}&\end{cases}$
$V_{\beta,m}(p_{11})=\begin{cases}\frac{(1-\epsilon)p_{11}+\beta(1-(1-\epsilon)p_{11})V_{\beta,m}(p_{01})}{1-\beta(1-\epsilon)p_{11}},&\text{if
}\omega_{\beta}^{*}(m)<p_{11}\\\ \frac{m}{1-\beta},&\text{if
}\omega_{\beta}^{*}(m)\geq p_{11}\end{cases}.$

The approximate Whittle index is given by

$W(\omega)=\begin{cases}\frac{\omega(1-\epsilon)(1-\beta p_{11}+\beta
p_{01})}{1-\beta(1-\epsilon)p_{11}+\beta(1-\epsilon)p_{01}},&\text{if
}\omega\leq p_{01}\\\
\frac{(1-\epsilon)(\omega-\beta\mathcal{T}(\omega))+C_{2}(1-\beta)\beta[(1-\beta(1-\epsilon)p_{11})-(1-\epsilon)(\omega-\beta\mathcal{T}(\omega))]}{1-\beta(1-\epsilon)p_{11}-C_{1}\beta[(1-\beta(1-\epsilon)p_{11})-(1-\epsilon)(\omega-\beta\mathcal{T}(\omega))]},&\text{if
}p_{01}<\omega<\omega_{0}\\\
\frac{(1-\epsilon)\omega}{1-\beta(1-\epsilon)p_{11}+\beta(1-\epsilon)\omega},&\text{if
}\omega_{0}\leq\omega<p_{11}\\\ (1-\epsilon)\omega,&\text{if }\omega\geq
p_{11}\end{cases},$

where

$\displaystyle
C_{1}=\frac{(1-\beta(1-\epsilon)p_{11})(1-\beta^{L(p_{01},\omega)})}{(1-\beta(1-\epsilon)p_{11})(1-\beta^{L(p_{01},\omega)+1})+(1-\epsilon)(1-\beta)\beta^{L(p_{01},\omega)+1}\mathcal{T}^{L(p_{01},\omega)}(p_{01})},$
$\displaystyle
C_{2}=\frac{(1-\epsilon)\beta^{L(p_{01},\omega)}\mathcal{T}^{L(p_{01},\omega)}(p_{01})}{(1-\beta(1-\epsilon)p_{11})(1-\beta^{L(p_{01},\omega)+1})+(1-\epsilon)(1-\beta)\beta^{L(p_{01},\omega)+1}\mathcal{T}^{L(p_{01},\omega)}(p_{01})}.$

Similarly, when $p_{01}>p_{11}$, we have

$V_{\beta,m}(p_{11})=\begin{cases}\frac{(1-\epsilon)(p_{11}(1-\beta)+\beta
p_{01})}{(1-\beta)(1-\beta(1-\epsilon)p_{11}+\beta(1-\epsilon)p_{01})},\
\text{if }\omega_{\beta}^{*}(m)<p_{11}&\\\
\frac{(1-\beta(1-(1-\epsilon)p_{01}))m+\beta(1-\epsilon)\mathcal{T}(p_{11})(1-\beta)+\beta^{2}(1-\epsilon)p_{01}}{(1-\beta)(1+\beta(1+\beta)(1-\epsilon)p_{01}-\beta^{2}(1-\epsilon)\mathcal{T}(p_{11}))},\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{if
}p_{11}\leq\omega_{\beta}^{*}(m)<\mathcal{T}(p_{11})&\\\ \frac{m}{1-\beta},\
\text{if }\omega_{\beta}^{*}(m)\geq\mathcal{T}(p_{11})&\end{cases}$
$V_{\beta,m}(p_{01})=\begin{cases}\frac{(1-\epsilon)p_{01}+\beta(1-\epsilon)p_{01}V_{\beta,m}(p_{11})}{1-\beta(1-(1-\epsilon)p_{01})},&\text{if
}\omega_{\beta}^{*}(m)<p_{01}\\\ \frac{m}{1-\beta},&\text{if
}\omega_{\beta}^{*}(m)\geq p_{01}\end{cases}.$

The approximate Whittle index is given by

$W(\omega)=\begin{cases}\frac{\omega(1-\epsilon)(1-\beta p_{11}+\beta
p_{01})}{1-\beta(1-\epsilon)p_{11}+\beta(1-\epsilon)p_{01}},&\text{if
}\omega\leq p_{11}\\\ \frac{(1-\epsilon)(1-\beta+C_{4}\beta)(\beta
p_{01}+\omega-\beta\mathcal{T}(\omega))}{1-\beta(1-(1-\epsilon)p_{01})+(1-\epsilon)C_{3}\beta(\beta\mathcal{T}(\omega)-\beta
p_{01}-\omega)},&\text{if }p_{11}<\omega<\omega_{0}\\\
\frac{(1-\epsilon)(1-\beta+\beta C_{4})(\beta
p_{01}+\omega(1-\beta))}{1-\beta(1-(1-\epsilon)p_{01})-(1-\epsilon)\beta
C_{3}(\beta p_{01}+\omega-\beta\omega)},&\text{if
}\omega_{0}\leq\omega<\mathcal{T}(p_{11})\\\ \frac{(1-\epsilon)(\beta
p_{01}+(1-\beta)\omega)}{1+(1-\epsilon)\beta(p_{01}-\omega)},&\text{if
}\mathcal{T}(p_{11})\leq\omega<p_{01}\\\ (1-\epsilon)\omega,&\text{if
}\omega\geq p_{01}\end{cases},$

where

$\displaystyle
C_{3}=\frac{1-\beta(1-(1-\epsilon)p_{01})}{1+\beta(1+\beta)(1-\epsilon)p_{01}-\beta^{2}(1-\epsilon)\mathcal{T}(p_{11})},$
$\displaystyle
C_{4}=\frac{\beta(1-\epsilon)\mathcal{T}(p_{11})(1-\beta)+\beta^{2}(1-\epsilon)p_{01}}{1+\beta(1+\beta)(1-\epsilon)p_{01}-\beta^{2}(1-\epsilon)\mathcal{T}(p_{11})}.$

##  3 Algorithm

Our analysis leads to the algorithm for the RMAB model with imperfect
observations in Algorithm 1 for all $\beta\in(0,1)$.

Algorithm 1 Whittle Index Policy

Input: $\beta\in(0,1)$, $T\geq 1$,$N\geq 2$, $1\leq M<N$, iteration number $k$
Input: initial belief state $\omega_{n}(1)$, $\textbf{P}^{(n)}$, $B_{n}$,
$n=1,...,N$

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

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

3: Set the threshold $\omega^{*}_{\beta}(m)=\omega_{n}(t)$ in (2.4)

4: Compute $L\left(p_{11},\omega_{n}(t)\right)$ and set $\omega=p_{11}$ in
(2.4)

5: Expand (2.4) to the $k$th step and solve for $V_{\beta,m}(p_{11})$

6: Compute $L\left(\mathcal{T}\circ\phi(\omega),\omega_{n}(t)\right)$ and set
$\omega=\mathcal{T}\circ\phi(\omega)$ in (2.4)

7: Expand (2.4) to the $k$th step and solve for
$V_{\beta,m}(\mathcal{T}\circ\phi(\omega))$ from $V_{\beta,m}(p_{11})$

8: Compute $L\left(\mathcal{T}(\omega),\omega_{n}(t)\right)$ and set
$\omega=\mathcal{T}(\omega)$ in (2.4)

9: Expand (2.4) to the $k$th step and solve for
$V_{\beta,m}(\mathcal{T}(\omega))$ from $V_{\beta,m}(p_{11})$

10: Solve for $V_{\beta,m}(\omega;u=1)$ by $V_{\beta,m}(p_{11})$ and
$V_{\beta,m}(\mathcal{T}\circ\phi(\omega))$ as in (66)

11: Solve for $V_{\beta,m}(\omega;u=0)$ by $V_{\beta,m}(\mathcal{T}(\omega))$
as in (67)

12: Evaluate the solvability of the linear equation of $m$:
$V_{\beta,m}(\omega;u=1)=V_{\beta,m}(\omega;u=0)$

13: Set $W(\omega_{n}(t))=\omega_{n}(t)B_{n}$ and skip Step 14 if the above is
unsolvable

14: Compute $W(\omega_{n}(t))$ as the solution to
$V_{\beta,m}(\omega;u=1)=V_{\beta,m}(\omega;u=0)$

15: end for

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

17: Observe the selected $K$ arms and accrue reward $O_{n}(t)S_{n}(t)B_{n}$
from each observed arm

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

19: Update the belief state $\omega_{n}(t)$ according to (4)

20: end for

21: end for

##  4 Experimental results

We use the $4$-iteration approximation algorithm to plot the approximated
Whittle index function $W(\omega)$ for the following parameters: in Fig. 2
$p_{11}=0.2,p_{01}=0.9,\beta=0.9,\epsilon=0.1,B=1$; in Fig. 2
$p_{11}=0.6,p_{01}=0.3,\beta=0.9,\epsilon=0.1,B=1$. Note that the monotonic
increasing property of $W(\omega)$ implies the indexability numerically while
the nonlinearity of $W(\omega)$ illustrates its difference to the myopic
policy (with index $\omega B$).

We further compare the performance of Whittle index policy with the optimal
policy which is computed by dynamic programming over a finite horizon (thus an
upper bound of the optimal infinite-horizon optimal policy for this horizon).
The performance of the myopic policy that chooses the $M$ arms with the
largest $\omega_{n}B_{n}$ is also illustrated. From Figures 3-18, we observe
that Algorithm 1 with iteration number $k=4$ achieves a near-optimal
performance and outperforms the myopic policy.

##  5 Conclusions

In this paper, we proposed a low-complexity algorithm based on the idea of
Whittle index to achieve a near-optimal performance for a class of RMAB with
an infinite state space and an imperfect observation model. Future work
includes the extension of the construction of linear equation sets by the idea
of threshold-based first crossing time and the computation of Whittle index
functions under the relaxed indexability to more general state and observation
models (see, e.g., the non-Markovian state model considered in [4]).

## Acknowledgments

We gratefully acknowledge the assistance of our student, Chengzhong Zhang, on
the numerical analysis and figures.

Figure 1: Approximated $W(\omega)$ ($p_{11}<p_{01}$)

Figure 2: Approximated $W(\omega)$ ($p_{11}>p_{01}$)

Table 1: Experiment Setting System-1 | $\\{p_{11}^{(i)}\\}_{i=1}^{7}$ | $\\{0.3,0.6,0.4,0.7,0.2,0.6,0.8\\}$
---|---|---
$\\{p_{01}^{(i)}\\}_{i=1}^{7}$ | $\\{0.1,0.4,0.3,0.4,0.1,0.3,0.5\\}$
$\\{B_{i}\\}_{i=1}^{7}$ | $\\{0.8800,0.2200,0.3300,0.1930,1.0000,0.2558,0.1549\\}$
System-2 | $\\{p_{11}^{(i)}\\}_{i=1}^{7}$ | $\\{0.6,0.4,0.2,0.2,0.4,0.1,0.3\\}$
$\\{p_{01}^{(i)}\\}_{i=1}^{7}$ | $\\{0.8,0.6,0.4,0.9,0.8,0.6,0.7\\}$
$\\{B_{i}\\}_{i=1}^{7}$ | $\\{0.5150,0.6666,1.0000,0.6296,0.5833,0.8100,0.6700\\}$
System-3 | $\\{p_{11}^{(i)}\\}_{i=1}^{7}$ | $\\{0.1,0.4,0.3,0.4,0.1,0.3,0.5\\}$
$\\{p_{01}^{(i)}\\}_{i=1}^{7}$ | $\\{0.3,0.6,0.4,0.7,0.2,0.6,0.8\\}$
$\\{B_{i}\\}_{i=1}^{7}$ | $\\{0.7273,0.3636,0.5000,0.3377,1.0000,0.3939,0.2955\\}$
System-4 | $\\{p_{11}^{(i)}\\}_{i=1}^{7}$ | $\\{0.6,0.7,0.2,0.6,0.4,0.5,0.3\\}$
$\\{p_{01}^{(i)}\\}_{i=1}^{7}$ | $\\{0.8,0.4,0.9,0.5,0.7,0.2,0.6\\}$
$\\{B_{i}\\}_{i=1}^{7}$ | $\\{0.4286,0.5000,0.5397,0.5143,0.5306,1.0000,0.6190\\}$
Table 2: Experiment Setting (continued) System | Example | $\epsilon$ | $\beta$ | Meet threshold | Meet indexability
---|---|---|---|---|---
|  |  |  | conditions? | conditions?
System-1 | 1 | 0.3 | 0.999 | yes | no
2 | 0.1 | 0.999 | yes | no
System-2 | 3 | 0.3 | 0.29 | yes | yes
4 | 0.1 | 0.29 | yes | yes
5 | 0.3 | 0.48 | no | yes
6 | 0.1 | 0.48 | no | yes
System-3 | 7 | 0.3 | 0.69 | yes | no
8 | 0.1 | 0.69 | yes | no
9 | 0.3 | 0.48 | yes | yes
10 | 0.1 | 0.48 | yes | yes
System-4 | 11 | 0.3 | 0.29 | yes | yes
12 | 0.1 | 0.29 | yes | yes
13 | 0.3 | 0.48 | no | yes
14 | 0.1 | 0.48 | no | yes
15 | 0.3 | 0.999 | no | no
16 | 0.1 | 0.999 | no | no

Figure 3: Example-1

Figure 4: Example-2

Figure 5: Example-3

Figure 6: Example-4

Figure 7: Example-5

Figure 8: Example-6

Figure 9: Example-7

Figure 10: Example-8

Figure 11: Example-9

Figure 12: Example-10

Figure 13: Example-11

Figure 14: Example-12

Figure 15: Example-13

Figure 16: Example-14

Figure 17: Example-15

Figure 18: Example-16

## References

  * [1] J. C. Gittins, Bandit processes and dynamic allocation indices, Journal of the Royal Statistical Society: Series B, 41 (1979), pp. 148–177.
  * [2] J. C. Gittins, K. D. Glazebrook, and R. R. Weber, Multi-Armed Bandit Allocation Indices, Wiley, Chichester, 2nd ed., 2011.
  * [3] K. Liu, Index policy for a class of partially observable markov decision processes, (2021), https://arxiv.org/abs/2107.11939.
  * [4] K. Liu, R. R. Weber, and Q. Zhao, Indexability and whittle index for restless bandit problems involving reset processes, Proc. of the 50th IEEE Conference on Decision and Control, (2011), pp. 7690–7696.
  * [5] K. Liu and Q. Zhao, Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access, IEEE Transactions on Information Theory, 56 (2010), pp. 5547–5567.
  * [6] K. Liu, Q. Zhao, and B. Krishnamachari, Dynamic multichannel access with imperfect channel state detection, IEEE Transactions on Signal Processing, 58 (2010), pp. 2795–2808.
  * [7] C. H. Papadimitriou and J. N. Tsitsiklis, The complexity of optimal queueing network control, Mathematics of Operations Research, 24 (1999), pp. 293–305.
  * [8] E. J. Sondik, The optimal control of partially observable markov processes over the infinite horizon: discounted costs, Operations Research, 26 (1978), pp. 282–304.
  * [9] P. Whittle, Restless bandits: Activity allocation in a changing world, Journal of Applied Probability, 25 (1988), pp. 287–298.