1

Multi-armed Bandits with Constrained Arms
and Hidden States

arXiv:1710.07115v1 [cs.SY] 19 Oct 2017

Varun Mehta, Rahul Meshram, Kesav Kaza and S. N. Merchant
Department of Electrical Engineering,
Indian Institute of Technology Bombay, India

Abstract
The problem of rested and restless multi-armed bandits with constrained availability of arms
is considered. The states of arms evolve in Markovian manner and the exact states are hidden from
the decision maker. First, some structural results on value functions are claimed. Following these
results, the optimal policy turns out to be a threshold policy. Further, indexability of rested bandits
is established and index formula is derived. The performance of index policy is illustrated and
compared with myopic policy using numerical examples.

I. I NTRODUCTION
Multi-armed bandits are among commonly used models for solving sequential decision
making problems, [1], [2]. In the multi-armed bandit problem, there are N arms and each
arm can be in one of a finite set of states. The decision maker plays M arms, (M < N)
at every time instant and collects rewards from the played arms. Reward from each played
arm depends on the state of that arm. The state of an arm changes according to a stochastic
process associated with that arm. The decision maker’s aim is to maximize the long-term
expected discounted reward. The state evolution may be action dependent and based on that
there are two types of bandits, rested and restless bandits. In a rested bandit, the state evolves
only for the arm which is played while states of other arms do not change. For a restless
bandit, the states of all arms evolve even when they are not played. In this setting, each arm
can be considered as a Markov decision process (MDP) with finite states and two actions
(play or not to play) in each state. As a model choice, states may assumed to be either
observable by decision maker or hidden to it. Now, the multi-armed bandit problem can be
looked as a set of MDPs coupled together with constraints.
A rested multi-armed bandit problem was first introduced in the seminal work of [1], where
the author proposed an index based policy. In such policies, state of each arm is mapped to
an index, i.e., real valued number. At each time instant arms with the highest indices are
played. This policy is known as Gittins index policy. Later, a generalization of the rested
multi-armed bandit problem was devised in [3], where a restless multi-armed bandit was
introduced and again index based policy proposed. The index policy for restless bandits is
now referred to as Whittle index policy.
Recently, restless bandits have been studied when state of the arms are not observable but
feedback signal is observable. The decision maker estimates the state from this feedback.
This is called the hidden Markov bandit. For a hidden Markov bandit, each arm can be
modeled using partially observable Markov decision processes (POMDP). An index policy
The work of Varun Mehta and Kesav Kaza was done in SPANN Lab at IIT Bombay. The work of Rahul Meshram was
carried out in the Bharti Centre for Communications at IIT Bombay.

2

for hidden Markov rested multi-armed bandit is suggested in [4]. Further, extension of this
to hidden Markov restless bandit is analysed in work of [5], [6], [7], [8].
To use index policy in rested and restless bandit, an approach is to first consider the singlearmed bandit problem and show that the optimal policy is of a threshold type. Using this
result one can show that arm is indexable and later index can be derived. While analyzing
a single-armed bandit model, structural results of POMDP can be used for hidden Markov
bandits. Some structural results for POMDP have been extensively studied in [9], [10], [11],
[12].
All of the above works on bandits assume that every arm is available for decision maker
at each time instant to play. The decision maker determines whether to play or not play the
arms using index policy. But this may not be feasible in some scenarios. For example, in a
machine-repair problem one may not able to schedule a task on some of the machines due
to machine breakdown. Such consideration has been made in [13]. In queuing systems, the
controller may not be able to schedule jobs to some servers due to server breakdown, [14],
[15]. In these examples a machine or server is available to the decision maker intermittently.
In this work, we consider rested and restless bandits with arm availability constraints where
arms may not be available to play at some time instants and these are called as constrained
bandits. It is a generalization of the classical rested and restless multi-armed bandit problems.
Usually when arm is not available, we consider a substitute arm which yield low reward
compare to the arm when it is available.
In constrained bandits [13], [14], [15], each state is defined as a pair (X(t), Y (t)), where
X(t) represents the state of arm and Y (t) represents availability of an arm at time t. Time is
discretized in [13] while it is continuous in the models of [14], [15]. The state (X(t), Y (t))
is assumed to be observable. Under some assumptions on model parameters the index policy
is analyzed in [13], [14], [15]. In this paper we consider a hidden Markov model, where
state X(t) of the arm is not observable but the availability of the arm is observable.
The paper is organized as follows. In next section, we describe the hidden Markov model
for multi-armed bandit with constraints. We later consider single armed bandit problem in
Section III. We analyze structural results for single-armed bandit in Section IV. Section V
we compute the index for hidden Markov rested bandit with availability constraints on arm.
We also illustrate the performance of the index policy and compare it with that of myopic
policy in Section VI. We finally conclude in Section VII and discuss some of open issues.
II. P RELIMINARIES AND M ODEL D ESCRIPTION
Consider a multi-armed bandit with N independent arms. Each arm can be in one of two
states, 0 and 1,. The system is time slotted and it is indexed by t. Let Xn (t) denote the state
of arm n at beginning of time slot t, Xn (t) ∈ {0, 1}. Each arm has availability constraints
i.e. it is intermittently available. Let Yn (t) ∈ {0, 1} represent the availability of arm n in
time slot t and
(
1 if arm n is available,
Yn (t) =
0 if arm n is not available.
When arm n is not available in slot t we will assume that , the arm n is replaced by substitute
arm which yield low reward after play. An (t) ∈ {0, 1} is the action in slot t with the following
interpretation.
(
1 if arm n is played in slot t,
An (t) =
0 otherwise.

3

Exactly one arm is to be played in each time slot. Arm n changes state at the end of time
slot t according to transition probabilities that depend on An (t), Yn (t) and it is defined as
follows.
Pr{Xn (t + 1) = j | Xn (t) = i, Yn (t) = y, An (t) = a} = Pijn (y, a)

In every slot t, a binary signal Zny (t) is observed from the arm n that is played. There is
no observation from the arms that are not played. Thus
(
1 play of arm n is successful
Zny (t) =
0 otherwise.
Let ρn (i, y) be the probability of success given that arm n is played An (t) = 1, and
Xn (t) = i, Yn (t) = y. We assume ρn (0, y) < ρn (1, y) for y ∈ {0, 1}.
Pr (Zny (t) = 1 | Xn (t) = i, Yn (t) = y, An (t) = 1) = ρn (i, y).
Also, Rna (i, y) is the reward obtained from playing arm n given that, Xn (t) = i, Yn (t) = y,
An (t) = a. Let
Rn1 (i, 1) = rn,i ,
Rn0 (i, 1) = 0,

Rn1 (i, 0) = ηn,i
Rn0 (i, 0) = 0.

Further, we will suppose that 0 ≤ ηn,0 < rn,0 < ηn,1 < rn,1 ≤ 1 for all n.
Remark 1:
y
• The observation variable Zn (t) may have different meanings in different applications.
In communication systems, Zny (t) = 1 may mean an acknowledgement (ACK) of a
successful transmission over a given link, [5]. For a recommendation system, it may
correspond to click or like by the user over a recommended item, see [6].
• Notice that ηn,i 6= 0; this means there is a non-zero reward for playing an arm even
when it is not available. This captures application scenarios where broken (not available)
arms can be repaired by playing them and paying a penalty from the reward.
The decision maker cannot directly observe states of the arms, and hence it does not know
the states at the beginning of each time slot. But decision maker knows the probability of
availability θna (i, y) of arm n, at the beginning of next time slot t + 1; it is as follows
θna (i, y) = Pr (Yn (t + 1) = 1|Xn (t) = i, Yn (t) = y, An (t) = a).

However, the decision maker maintains a belief πn (t) about the state of arm n. It is the
probability that the arm is in state 0 given all past availability, actions, observations. This is
given as follows.

πn (t) = Pr Xn (t) = 0 | (Yn (s) = ys , An (s), Znys (s))t−1
s=1 .

Let Ht denote the history,

Ht := (Yn (s) = ys , An (s), Znys (s))1≤n≤N,1≤s<t .
We can describe the state of arm n at time t by Sn (t) = (πn (t), Yn (t)) ∈ [0, 1] × {0, 1}.
(S1 (t), · · · SN (t)) is the state information of the arms at the beginning of time slot t. Further,
we can rewrite θna (i, y) as function of π in following form.
θna (π, y) = Pr(Yn (t + 1) = 1|πn (t) = π, Yn (t) = y, An (t) = a).

4

Hence the expected reward from playing arm n at time t given that Yn (t) = y is
en1 (πn (t), y) = πn (t)Rn1 (0, y) + (1 − πn (t)Rn1 (1, y).
R

In each slot, exactly one arm is to played. Let φ(t) is the policy by the decision maker such
that φ(t) : Ht → {1, · · · , N} maps the history to one of the arm at slot t. Let
(
1 if φ(t) = n,
Aφn (t) =
0 if φ(t) 6= n.
We are now ready to define the infinite horizon discounted reward under policy φ for initial
state information (π, y), π = (π1 (1), · · · , πN (1)) and y = (y1 (1), · · · , yN (1)). It is given by
" N
#!
∞
X
X
e1 (πn (t), Yn (t))
Vφ (π, y) = Eφ
β t−1
Aφ (t)R
.
(1)
n

t=1

n

n=1

Here, β is discount parameter, 0 < β < 1. The goal is to find a policy φ that maximizes
Vφ (π, y) for given π ∈ [0, 1]N , y ∈ {0, 1}N . The optimization problem (1) is a multiarmed bandit problem with availability constraints. This is generalized version of multi-armed
bandits, where it has partially observable states and availability constraints. In general, this
problem is known to be PSPACE-hard,[16]. Index based policies are developed in [2], [3] for
rested and restless multi-armed bandits. To study such index policies, a Lagrangian relaxed
version of problem (1) is analysed. In this relaxed problem, complexity of problem reduced as
it separates the solving one multi-armed bandit problem to N single-armed bandit problems.
Thus it reduces to calculating the index for each arm separately. The arm with highest index
is played in each time slot.
We next analyze the single-armed bandit problem in next section.
III. S INGLE - ARMED BANDIT PROBLEM
For notational convenience, we will drop the subscript n, i.e., the sequence number of the
arm. As a widely used method for solving the single arm bandit problem, a subsidy w is
assigned for not playing the arm [3]. In that case, optimization problem (1) can be rewritten
as follows.
Vφ (π, y) = Eφ

∞
X
t=1

!
h
i
e1 (π(t), Y (t)) + w(1 − Aφ (t)) ,
β t−1 Aφ (t)R

(2)

where action A(t) under policy φ is

(
1
Aφ (t) =
0

if φ(t) = 1,
if φ(t) = 0.

The objective is to find a policy φ that maximizes Vφ (π, y).
Recall that the state evolution of arms may be action dependent. Based on this, we can
have two different types of bandits, rested and restless single-armed bandit. In rested singlearmed bandit, state evolves for the arm that is played and state of other arms do not change.
For restless bandit model, state of all arms changes at each time slot.

5

To simplify the model further, we assume that P00 (y, a) = µ0 and P10 (y, a) = µ1 for
a, y ∈ {0, 1}.1 We will also assume that ρ(i, 1) = ρ(i, 0) = ri , i ∈ {0, 1}. Recall that
π(t) = Pr(X(t) = 0|Ht) and using Bayes rule, we can obtain the belief π(t + 1) as follows.
π(t + 1) =

(

if A(t) = 1, Y (t) = y, and Z y (t) = z,
if A(t) = 0, and Y (t) = y.

γz,y (π(t))
Γy (π(t))

Here,
1) If A(t) = 1, i.e., arm is played and Y (t) = 1, Z 1 (t) = 1 then
γ1,1 (π(t)) :=

π(t)r0 µ0 + (1 − π(t))r1 µ1
.
π(t)r0 + (1 − π(t))r1

2) if A(t) = 1, i.e., arm is played and Y (t) = 1, Z 1 (t) = 0 then
γ0,1 (π(t)) :=

π(t)(1 − r0 )µ0 + (1 − π(t))(1 − r1 )µ1
.
π(t)(1 − r0 ) + (1 − π(t))(1 − r1 )

3) if A(t) = 1, i.e., arm is played and Y (t) = 0, Z 1 (t) = 1 then
(
π(t)
for rested bandit,
γ1,0 (π(t)) :=
γ1,1 (π(t)) for restless bandit.
4) if A(t) = 1, i.e., arm is played and Y (t) = 0, Z 1 (t) = 0 then
(
π(t)
for rested bandit,
γ0,0 (π(t)) :=
γ0,1 (π(t)) for restless bandit.
5) if A(t) = 0, i.e., arm is not played and Y (t) = 1 then
Γ1 (π(t)) :=

(

π(t)
π(t)µ0 + (1 − π(t))µ1

for rested bandit,
for restless bandit.

6) if A(t) = 0, i.e., arm is not played and Y (t) = 0 then
Γ0 (π(t)) := π(t).
From [17], we know that the π(t) captures the information about the history Ht , and it is a
sufficient statistic. It suggests that the optimal policies can be restricted to stationary Markov
policies. In this, one can obtain the optimum value function by solving suitable dynamic
program, it will be given in later part of this section.
Let us define the value function under initial action A1 and availability Y1

1

VS := value
VeS := value
VN S := value
VeN S := value

function under A1 = 1, Y1 = 1
function under A1 = 1, Y1 = 0
function under A1 = 0, Y1 = 1
function under A1 = 0, Y1 = 0

But in general, transition probabilities for available and unavailable arms could be different.

6

We can write the following.
VS (π) = ρ(π) + β[ρ(π){θ1 (π, 1)V (γ1,1 (π)) + (1 − θ1 (π, 1))Ve (γ1,1 (π))}
+(1 − ρ(π){θ1 (π, 1)V (γ0,1 (π)) + (1 − θ1 (π, 1))Ve (γ0,1 (π))}],

VN S (π) = w + β[θ0 (π, 1)V (Γ1 (π)) + (1 − θ0 (π, 1))Ve (Γ1 (π))],
VeS (π) = ξ(π) + β[ρ(π){θ1 (π, 0)V (γ1,0 (π)) + (1 − θ1 (π, 0))Ve (γ1,0 (π))}
+(1 − ρ(π){θ1 (π, 0)V (γ0,0 (π)) + (1 − θ1 (π, 0))Ve (γ0,0 (π))}],

VeN S (π) = w + β[θ0 (π, 0)V (Γ0 (π)) + (1 − θ0 (π, 0))Ve (Γ0 (π))].

(3)

(4)

(5)

(6)

Here ξ(π) = πη0 + (1 − π)η1 , ρ(π) = πr0 + (1 − π)r1 . The optimal value function V (π, y),
is determined by solving the following dynamic program
V (π) = max{VS (π), VN S (π)},
Ve (π) = max{VeS (π), VeN S (π)}.

(7)

These are dynamic programs for single-armed rested as well as restless bandit problems.
Now, we proceed to present the main results of this work.
IV. S TRUCTURAL RESULTS
We now begin with some of structural results on value functions, showing convexity and
threshold type policy.
Lemma 1: (Convexity of value function)
1) For fixed w, V (π), VS (π), VN S (π), Ve (π), VeT (π) and VeN S (π) are convex functions of π.
2) For a fixed π, V (π), VS (π), VN S (π), Ve (π), VeT (π) and VeN S (π) are non decreasing and
convex in w.
A sketch of the proof is in Appendix VII-A. We first define a threshold or monotone policy
for the single armed bandit problem and then prove that the optimal policy is of this kind
under some restriction on model parameters.
Definition 1: (Threshold type policy) A policy is said to be threshold type, if one of the
following is true.
1) The optimal action is to play the arm ∀π.
2) The optimal action is to not play the arm ∀π.
3) There exists a threshold π ∗ such that ∀π ≤ π ∗ the optimal action is to play the arm
and not to play the arm otherwise.

7

A. Threshold structure of optimal policy (case µ0 > µ1 )
The following lemma provides sufficient conditions for monotonicity of the optimal value
function.
Lemma 2: (Monotone value functions) If
1) 0 ≤ η0 < r0 < η1 < r1 ≤ 1,
2) µ0 > µ1 ,
3) ρ1 > ρ0 ,
4) θa (π, 1) > θa (π, 0), and θa (π, y) > θa (π ′ , y), for π ′ > π,
then for π ′ ≥ π implies V (π) ≥ V (π ′ ) and Ve (π) ≥ Ve (π ′ ).
A sketch of the proof is given in Appendix VII-B.
Remark 2: The lemma says that if the rewards, observation and transition probabilities
follow certain order than the optimal value functions are monotone with belief π. This result
can be utilized to prove that optimal policy is a monotone policy. A monotone policy is one
where the actions are monotone over state space.
To have monotone optimal policy, we first prove that the difference between the value
functions VS (π) and VN S (π), is monotonic in π. Similarly, we prove this for VeS (π) and
VeN S (π).
Lemma 3: (Isotone difference property) For fixed w and conditions of Lemma 2
1) (VS (π) − VN S (π)) is decreasing in π,
2) (VeS (π) − VeN S (π)) is decreasing in π,
We describe the proof in Appendix VII-C.
Let S1 := [0, 1] × {1}, S0 := [0, 1] × {0}, a∗ (π) := arg max{VS (π), VN S (π)} and e
a∗ (π) :=
arg max{VeS (π), VeN S (π)}. Then the following theorem gives monotone optimal policy on
belief π.
Theorem 1: (Monotone optimal policy)
1) If the value function V : S1 × A → R has isotone difference on S1 × A then there
exists a non increasing optimal policy a∗ : S1 → A on belief S1 .
2) If the value function Ve : S0 × A → R has isotone difference on S0 × A then there
exists a non increasing optimal policy e
a∗ : S0 → A on belief S0 .
Proof: From Lemma 1, the value functions V (π), Ve (π) are convex and monotone in
π. From Lemma 2, V (π), Ve (π) has isotone difference property. This implies, there exists
a∗ (π) ∈ {0, 1} that is non increasing in π.
Remark 3: Here, we observe that the optimal actions are ordered on belief space. This
indeed is a threshold type policy by Definition 1. Note that a monotone policy is a threshold
policy for two actions. Thus isotone difference property implies a threshold policy result.
B. Threshold structure of optimal policy (case µ0 < µ1 )
For µ0 < µ1 , different proof technique is necessary to To claim a threshold type optimal
policy. Here, we will assume θa (π, y) = θa (y), i.e. independent of π.
We first argue that difference between the value functions VS (π) and VN S (π), is monotonic
in π for special cases. Similarly, difference between VeS (π) and VeN S (π) is monotone in π.
Lemma 4: For fixed w and β, and 0 ≤ µ1 − µ0 ≤ 31 ,
1) (VS (π) − VN S (π)) is decreasing in π,
2) (VeS (π) − VeN S (π)) is decreasing in π,

8

We describe sketch of the proof in Appendix VII-D.
Remark 4: The proof of this Lemma is different from the earlier Lemma 2 because here
we are not assuming monotonicity of value functions. Instead here we use the Lipschitz
properties of value functions with respect to π, i.e., the value functions, V (π), Ve (π) have
following property
|V (π1 ) − V (π2 )| ≤ κ|r1 − r0 ||π1 − π2 |,
|Ve (π1 ) − Ve (π2 )| ≤ κ|η1 − η0 ||π1 − π2 |,

(8)

where κ = 1−β(µ11 −µ0 ) . It is true for 0 < µ1 − µ0 ≤ 1/3. The Lipschitz-property proof is
given in [5, Appendix, Lemma 5].
Theorem 2: For fixed w and β, and 0 ≤ µ1 − µ0 ≤ 13 ,
1) The optimal policy is threshold type for VT (π) and VN S (π). That is, either V (π) =
VS (π) for all π ∈ [0, 1] or V (π) = VN S (π) for all π ∈ [0, 1] or there exists π ∗ such
that
(
VS (π)
for π ≤ π ∗ ,
V (π) =
VN S (π) for π ≥ π ∗ .
2) The optimal policy is threshold type for VeT (π) and VeN S (π). That is, either Ve (π) =
VeS (π) for all π ∈ [0, 1] or Ve (π) = VeN S (π) for all π ∈ [0, 1] or there exists π
e such that
(
VeS (π)
for π ≤ π
e,
Ve (π) = e
VN S (π) for π ≥ π
e.

Remark 5:
• The proof of Theorem 2 is analogous to the Theorem IV-A.
• In Section VI, we will present few numerical examples to illustarte a threshold-type
policy for general case, where we do not make any restriction on θ and model parameters
µs.

V. I NDEX POLICY FOR SINGLE - ARMED BANDIT
Recall that our interest here is to seek an index-type policy. We now define indexability
of an arm and then its index. Let G(w) be the subset of state space S = [0, 1] × {0, 1} in
which it is optimal to not play the arm with subsidy w, it is given as follows.
G(w) :={(π, y) ∈ [0, 1] × {0, 1} :
VS (π) ≤ VN S (π), VeS (π) ≤ VeN S (π)}.

(9)

Using set G(w), indexability and index are defined as follows.
Definition 2: An arm is indexable if G(w) is increasing in subsidy w, i.e.,
w2 ≤ w1 ⇒ G(w2 ) ⊆ G(w1 ).
Definition 3: The index of an indexable arm is defined as
w(π, y) := inf{w ∈ R : (π, y) ∈ G(w), ∀(π, y) ∈ S}.
Remark 6:

(10)

9

•

Note that we can rewrite definition of set G(w) in the following way.
G(w) = {[πL , 1] × {1}, [e
πL , 1] × {0}} ,

where πL := min{π ∈ [0, 1] : VS (π) = VN S (π)}, and π
eL := min{π ∈ [0, 1] : VeS (π) =
VeN S (π)}.
∗
• If the optimal policy is of threshold type, then π = πL and π
e=π
eL .
• To claim indexability, we require to show that as subsidy w increases, πL (w) and π
eL (w)
are non-increasing in w.
• In general, it is difficult to show indexability and obtain index because there is difficulty
in proving a threshold type policy.
We next show the indexability and compute the closed form expression for the index of a
single-armed rested bandit. The proof of index computation is along the lines of [13].
A. Rested single-armed bandit
We further simplify the rested single-armed bandit problem and make following assumptions on transition probabilities.
(
pij if y = a = 1,
Pij (y, a) =
δij if y = 0 or a = 0.
where δij equals to 1 if i = j and 0 otherwise. Also, p00 = µ0 , and p10 = µ1 . This indicates
that state of the arm changes if arm is available and does not change when arm is unavailable.
Further we assume θ0 (π, 0) = 0.
We now present a few preliminary results which are used to derive the index. These results
make use of the definition of set G(w) and obtain value function expressions.
Lemma 5:
w
1) For (π, 0) ∈ S, subsidy w ∈ R, if (π, 0) ∈ G(w) then Ve (π, w) = 1−β
with initial state
(π, 0).
2) For (π, 1) ∈ S, subsidy w ∈ R, if (π, 1) ∈ G(w) then
V (π, w) = max

(

φ0
Eπ,1

"

∞
X
t=1

β

(t−1)

#

w
(w1{y(t)=1} + R (π, 0)1{y(t)=0} ) ,
1−β
1



.

(11)

φ0
Here Eπ,1
is the expectation under policy φ0 that plays the arm when it is unavailable and
otherwise keeps it rested.
Proof: 1. State of the arm does not change when arm is unavailable and not played.
Therefore if (π, 0) ∈ G(w), then it is always optimal to not play the arm and the expected
w
total discounted reward starting in state (π, 0) is Ve (π, w) = 1−β
.
2. If (π, 1) ∈ G(w), then, the arm may visit (π, 0) state if it goes unavailable in between.
Therefore, the arm is in either (π, 1) or (π, 0) state. In this case, two optimal policies are
possible (a) never play the arm, (b) do not play the arm when it is in state (π, 1) and play
w
the arm when it is in (π, 0). The expected total discounted reward for policy (a) is 1−β
and
for policy (b) is given in (11).
φ1
We now define Eπ,1
as the expectation under policy φ1 that always plays the arm. Then
we can evaluate the total expected discounted reward under φ1 for initial state (π, 1). It is
"∞
#
X
φ1
Ψ(π, 1) := Eπ,1
β (t−1) R1 (π(t), y(t)) .
t=1

10

We can derive lower bound on Ψ(π, 1) in terms of η0 ,
Ψ(π, 1) >

R1 (π, 0)
πη0 + (1 − π)η1
η0
=
>
.
1−β
1−β
1−β

(12)

Lemma 6: If subsidy w is smaller than η0 , then set G(w) = ∅.
Proof: The proof is by contradiction. We first consider case for y = 0. Suppose that
w
. We also
(π, 0) ∈ G(w), hence, G(w) 6= ∅. Then, from Lemma 5, we get Ve (π, w) = 1−β
w
1
e
obtain V (π, w) > 1−β because w < η0 < R (π, 0). This contradicts our assumption. Hence
claim follows.
Now we consider case for y = 1. We assume that (π, 1) ∈ G(w). Then using Lemma 5, we
1 (π,0)
have V (π, w) < R1−β
because w < R1 (π, 0). Further, we can derive lower bound V (π, w) ≥
R1 (π,0)
.
1−β

This contradicts the upper bound and hence our assumption. Thus G(w) = ∅. This
completes the proof.
If subsidy w is higher than η0 , then, set G(w) can be non-empty. We will provide sufficient
condition on subsidy w for G(w) to be non-empty. Also, if set G(w) is nonempty then we
give lower bound on subsidy w. This is given in the next Lemma.
Lemma 7: (π, y) ∈ G(w) if and only if

Pτ −1 (t−1) 1
φ1
β
R
(π(t),
y(t))
Eπ,y
t=1
(13)
w ≥ (1 − β)
φ1
1 − Eπ,y
[β τ ]
for τ > 0.
Proof: We first assume that (π, y) ∈ G(w). We want to prove Eqn. (13). We know
w
from Lemma 5 that if (π, 0) ∈ G(w), then Ve (π, w) = 1−β
and if (π, 1) ∈ G(w), then
w
1
V (π, w) = 1−β . This is true for w ≥ R (π, 0). This suggests that the optimal action is not to
play the arm for all time slots. The optimization problem in 2 reduces to optimal stopping
problem, where arm is played until stopping time τ − 1 and not played since τ. Thus the
expected discounted reward is
#
" τ −1
∞
X
X
φ1
βtw
Eπ,y
β (t−1) R1 (π(t), y(t)) +
t=τ

t=1

w
1−β

This expected reward is upper bounded by
because not playing arm is always optimal
for (π, y) ∈ G(w) as shown earlier. Hence
" τ −1
#
∞
X
X
w
φ1
≥ Eπ,y
β (t−1) R1 (π(t), y(t)) +
βtw .
(14)
1−β
t=1
t=τ
We assume that w is lower bounded and Eqn. (13) holds true. Then, it is easy to verify
that (π, y) ∈ G(w). To see this, make use of the optimal stopping time policy and Eqn. (14).
Theorem 3: The arm is indexable and index w(π, y) is
Pτ −1 (t−1) 1

φ1
Eπ,y
R (π(t), y(t))
t=1 β
w(π, y) := (1 − β) sup
φ1
τ ∈S
1 − Eπ,y
[β τ ]

Here, τ is optimal stopping time, it is time until which arm is played.

(15)

11

2.45

2.3

2.4

VeS (π)
VeNS (π)

2.2
2.35

VS (π)
2.1

VNS (π)

2.3

Ve (π)

V (π)

2.25

2.2

2

1.9

2.15

2.1

1.8

2.05

1.7
2

1.95
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

π

a) VS (π) and VN S (π)

0.9

1

1.6
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

π

b) VeS (π) and VeN S (π)

Fig. 1. In a) VS (π) and VNS (π) plotted as function of π and b) VeS (π) and VeNS (π) plotted as function of π. This is
plotted for a single-armed restless bandit.

Proof: Note that Eqn. (13) is true for every stopping time τ > 0. That implies not
playing the arm is optimal. Further, the following is true.

Pτ −1 (t−1) 1
φ1
Eπ,y
β
R
(π(t),
y(t))
t=1
.
(16)
w ≥ (1 − β) sup
φ1
τ ∈S
1 − Eπ,y
[β τ ]
In order to show indexability, we need to prove that G(w) set is monotone in w. From
Lemma 6, we know that there is w for which set G(w) is empty. As w increases this set
becomes non-empty. This is clear from Lemma 7. As subsidy w increases, Eqn. (13) continues
to hold for larger subset of S = [0, 1] × {0, 1}. Thus indexability holds true by definition
and index can be computed using (16).
VI. N UMERICAL R ESULTS
We first present few numerical examples to illustrate threshold type optimal policy for a
restless single-armed bandit. We later demonstrate the performance of our index policy for
rested multi-armed bandit.
A. Examples for a threshold type result
To demonstrate the threshold type result for a single-armed bandit, we use the following
parameters. µ0 = 0.1, µ1 = 0.9, r0 = 0.4, η0 = 0.1, r1 = 0.95, η1 = 0.65, θa (π, y) = 0.5 for
any π ∈ [0, 1], a, y ∈ {0, 1}, and β = 0.7.
In Fig. 1-a), we plot VS (π) and VN S (π) as function of π. Similarly, in Fig. 1-b), we
plot value functions VeS (π) and VeN S (π). These plots suggest that the optimal policy is of a
threshold type.
In this case, we have µ1 − µ0 = 0.8. But to prove analytically a threshold policy result,
we have assumed 0 < µ1 − µ0 < 1/3, see Section IV-B. This is a limitation from analysis
because it is very difficult to evaluate closed form expressions for value functions or introduce
monotonicity of value functions.
B. Performance of index policy
We now present few numerical examples to illustrate the performance of index policy and
compare this with that of myopic policy. This is done for rested single-armed bandit. Note that
this is different from standard rested bandits because here arms are available probabilistically

12

in each time slot. Recall that in an index policy, the arm with highest index is played in
given time slot. In myopic policy, the arm with highest immediate expected reward is played
at each time slot.
We consider number of arms, N = 5 and use the following set of parameters in all
examples.
µ0 = [0.1, 0.9, 0.3, 0.9, 0.3], µ1 = [0.9, 0.1, 0.9, 0.3, 0.9],
r0 = [0.2, 0.3, 0.25, 0.4, 0.35], r1 = [0.9, 0.95, 0.8, 0.9, 0.6],
η0 = [0.1, 0.2, 0.15, 0.3, 0.25], η1 = [0.6, 0.65, 0.5, 0.6, 0.3].
We also set ρ0 = r0 , ρ1 = r1 , initial belief and availability vector of arms is
π(1) = [0.2, 0.4, 0.3, 0.7, 0.5], y(1) = [1, 1, 1, 1, 1].
We further have two sets of examples, in first set of examples we assume that the probability
of availability is identical for all the arms, i.e., θna (π, y) = θa (π, y). In second set of examples,
each arm has different probability of availability.
1) Arms with identical probability of availability: Here, θna (π, y) = θa (π, y). But we
assumed different reward and transition probabilities. We consider four examples as given
below.
1) θ1 (π, 1) = 1, θ1 (π, 0) = 0 and θ0 (π, 1) = 1
2) θ1 (π, 1) = 0.8, θ1 (π, 0) = 0 and θ0 (π, 1) = 0.7
3) θ1 (π, 1) = 0.8, θ1 (π, 0) = 0.4 and θ0 (π, 1) = 0.7.
4) θ1 (π, 1) = 0.35, θ1 (π, 0) = 0.75 and θ0 (π, 1) = 0.9.
From value function equations (3)–(6), we can observe the influence of V (π) and Ve (π) on
each other, that is based on different value of θa (π, y).
TABLE I
W E USE θ1 (π, 1) = 1, θ1 (π, 0) = 0 AND θ0 (π, 1) = 1
β
0.95
0.8
0.6

Total discounted cumulative reward
Myopic policy Index policy
% Gain in
index policy
15
17
13.33
3
3.18
6.3
1.9
1.8
-4.2

The first example captures the scenario, where there is no influence of V (π) and Ve (π)
on each other. In Tables I, we show a detailed comparison of discounted cumulative reward
using index based policy and myopic policy. Also, we observe that the index policy performs
better than myopic policy for large values of discount parameters β, i.e., β closer to 1. In
this example, myopic policy gives better peformance over index policy for β = 0.6.
TABLE II
W E SET θ1 (π, 1) = 0.8, θ1 (π, 0) = 0 AND θ0 (π, 1) = 0.7
β
0.95
0.8
0.6

Total discounted cumulative reward
Myopic policy Index policy
% Gain in
index policy
8.33
10
20
1.97
2.5
26.9
1
1.35
25

13

In our second example, we consider θ1 (π, 0) = 0, i.e., no influence from V (π) on Ve (π) but
θ1 (π, 1) = 0.8, and θ0 (π, 1) = 0.7, i.e., there is influence from Ve (π) on V (π), see Eqn. (5).
The performance is given in Table II. It suggests that the index policy yields up to 20% gain
in discounted cumulative reward compared to myopic policy. In this example, index policy
gives better performance compared to myopic policy even for β = 0.6.
TABLE III
W E USE θ1 (π, 1) = 0.8, θ1 (π, 0) = 0.4 AND θ0 (π, 1) = 0.7.
β
0.95
0.8
0.6

Total discounted cumulative reward
Myopic policy Index policy
% Gain in
index policy
13.4
15
11.94
3.5
3.56
1.71
1.82
1.74
-4.12

In third example, we use θ1 (π, 0) = 0.4, θ1 (π, 1) = 0.8, and θ0 (π, 1) = 0.7. The
performance is illustrated in Table III. This example captures a scenario with some influence
from V (π) and Ve (π) on each other. We notice that index policy provides gain in cumulative
discounted reward compared to myopic polic for β = 0.8, 0.95. The index policy yields up
to 12% gain in discounted reward over myopic policy for β = 0.95. But it does not provide
any gain for β = 0.6.
In above first 3 examples we considered θ1 (π, 1) > θ1 (π, 0), see Table I—III. This implies
that the probability that the arm is available in next slot given that it is not available and
played in current time slot is smaller that the probability of availability in next slot given the
arm is available and played. On the other hand we consider example of θ1 (π, 1) < θ1 (π, 0)
in Table IV, which means playing an arm when it is not available leads to better chance
of it being available in the next slot than playing when it is available. we observe similar
performance to that of example 3.
TABLE IV
W E USE θ1 (π, 1) = 0.35, θ1 (π, 0) = 0.75 AND θ0 (π, 1) = 0.9.
β
0.95
0.8
0.6

Total discounted cumulative reward
Myopic Policy Index Policy
% Gain in
index policy
12.3
13.82
12.35
3.3
3.25
-1.3
1.7
1.6
-5.88

2) Arms with non identical probability of availability: In next set of examples we have
considered the scenario where arms have same rewards and transition probabilities but
different probabilities of availability. The transition probabilities are, µ0 = 0.9, µ1 = 0.3
and rewards, η0 = 0.1, η1 = 0.6 and r0 = 0.2, r1 = 0.9. The initial belief and availability
vector for arms are
π(1) = [0.2, 0.4, 0.3, 0.7, 0.5], y(1) = [1, 0, 1, 0, 1].
Example illustrating two possible scenarios were considered with parameters shown in Table V. From Table VI we can see that index policy performs better compared to myopic policy.
The index policy gives upto 16 to 18% gain over myopic policy. The authors observed that,
in both examples, myopic policy chose arms 1,3 and 5 in initial time slots and later on kept
choosing arm 5. The index policy chose arm 5 from the beginning. This again suggests the
“far-sightedness” of the index policy in accounting for future states and availability of arms.

14

TABLE V
S ECOND SET OF EXAMPLES - PROBABILITIES OF AVAILABILITY
Arm
Example
θ1 (π, 1)
θ1 (π, 0)
θ0 (π, 1)

1
1
0.5
0.7
0.9

2
2
0.5
0.7
0.9

1
0.5
0.5
0.5

3
2
0.3
0.5
0.6

1
0.8
0.9
0.7

4
2
0.8
0.9
0.7

1
0.5
0.5
0.5

5
2
0.5
0.5
0.5

1
1
0
1

2
1
0.2
1

TABLE VI
A RMS WITH DIFFERENT AVAILABILITY PROBABILITY
Example
1
2

Total discounted cumulative reward
Myopic Policy Index Policy
% Gain in
index policy
54.12
64
18.2
54
63
16.6

VII. C ONCLUDING REMARKS
In this paper we presented monotonicity results and showed that the optimal policy is of
threshold type under some model restrictions. Though this is generally true, it is difficult to
prove without any restriction on model parameters. We have demonstrated this via numerical
examples. Hidden states and interdependence between V (π) and Ve (π) makes it difficult to
get closed form expression for the threshold.
For a rested single-armed bandit with availability constraints, we have shown that the arm
is indexable and derived a formula for index. The index can also be calculated by the value
iteration algorithm. From numerical examples, we observed that index policy performs better
than myopic policy for some cases. This suggests that, index policy accounts for the future
availability of arms and hence gives better performance. In future we seek to obtain some
numerical scheme to compute the index for restless bandits with constrained arms.
R EFERENCES
[1] J. C. Gittins, Bandit processes and dynamic allocation indices, Journal of the Royal Statistical Society. Series B
(Methodological) (1979) 148–177.
[2] J. Gittins, K. Glazebrook, R. Weber, Multi-armed Bandit Allocation Indices, Wiley, 2011.
[3] P. Whittle, Restless bandits: activity allocation in a changing world, Journal of Applied Probability 25 (A) (1988)
287–298.
[4] V. Krishnamurthy, B. Wahlberg, Partially observed Markov decision process multiarmed banditsstructural results,
Mathematics of Operations Research 34 (2) (2009) 287–302.
[5] R. Meshram, D. Manjunath, A. Gopalan, On the Whittle index for restless multi-armed hidden Markov bandits, ArXiv
e-printsarXiv:1603.047309v1.
[6] R. Meshram, A. Gopalan, D. Manjunath, A hidden Markov restless multi-armed bandit model for playout recommendation systems, ArXiv e-printsarXiv:1704.02894.
[7] V. S. Borkar, Whittle index for partially observed binary Markov decision processes, IEEE Transactions on Automatic
Control PP (99) (2017) 1–1.
[8] K. Liu, Q. Zhao, Indexability of restless bandit problems and optimality of Whittle index for dynamic multichannel
access, IEEE Transactions on Information Theory 56 (11) (2010) 5547–5567.
[9] W. S. Lovejoy, Ordered solutions for dynamic programs, Mathematics of Operations Research 12 (2) (1987) 269–276.
[10] W. S. Lovejoy, Some monotonicity results for partially observed markov decision processes, Operations Research
35 (5) (1987) 736–743.
[11] S. C. Albright, Structural results for partially observable Markov decision processes, Operations Research 27 (5)
(1979) 1041–1053.
[12] C. C. White, Optimal control-limit strategies for a partially observed replacement problem, International Journal of
Systems Science 10 (3) (1979) 321–332.
[13] S. Dayanik, W. Powell, K. Yamazaki, Index policies for discounted bandit problems with availability constraints,
Advances in Applied Probability 40 (02) (2002) 377–400.

15

[14] S. Martin, I. Mitrani, K. D. Glazebrook, Dynamic routing among several intermittently available servers, in: Next
Generation Internet Networks, 2005, IEEE, 2005, pp. 1–8.
[15] K. D. Glazebrook, C. Kirkbride, Dynamic routing to heterogeneous collections of unreliable servers, Queueing System
55 (2007) 9–25.
[16] C. H. Papadimitriou, J. N. Tsitsiklis, The complexity of optimal queuing network control, Mathematics of Operations
Research 24 (2) (1999) 293–305.
[17] D. P. Bertsekas, Bertsekas, Dynamic programming and optimal control, 2nd Edition, Vol. 1-2, Athena Scientific
Belmont, MA, 1995.
[18] K. J. Aström, Optimal control of Markov processes with incomplete state information ii: The convexity of loss function,
J. Math. Ann. Appl 26 (1969) 403–406.
[19] D. P. Bertsekas, Bertsekas, Dynamic programming and optimal control, 2nd Edition, Vol. 2, Athena Scientific Belmont,
MA, 1995.

A PPENDIX
A. Proof of Lemma 1
1. In this part, We prove V (π) is convex by induction and use that to show other value
functions are also convex.
Let
V1 (π) = max{πr0 + (1 − π)r1 , w}
Vn+1,S (π) = ρ(π) + β[ρ(π){θ1 (π, 1)Vn (γ1,1 (π)) + (1 − θ1 (π, 1))Ven (γ1,1 (π))}
+ (1 − ρ(π){θ1 (π, 1)Vn (γ0,1(π)) + (1 − θ1 (π, 1))Ven (γ0,1 (π))}]
Vn+1,N S (π) = w + β[θ0 (π, 1)Vn (Γ1 (π)) + (1 − θ0 (π, 1))Ven (Γ1 (π))]
Vn+1 (π) = max{Vn+1,S (π), Vn+1,N S (π)}

(17)

Now define
b0 :=[πµ0 (1 − r0 ) + (1 − π)µ1 (1 − r1 ),
π(1 − µ0 )(1 − r0 ) + (1 − π)(1 − µ1 )(1 − r1 )]T
b1 :=[πµ0 r0 + (1 − π)µ1 r1 ,
π(1 − µ0 )r0 + (1 − π)(1 − µ1 )r1 ]T
b̂0 =θ1 (π, 1)b0
b̂1 =θ1 (π, 1)b1
clearly, V1 (π) is linear and hence convex. If Vn (π), Ven (π) is convex in π then we can write

Vn+1,S (π) = kb1 k1 + β b̂1

1





 b̂1 
Vn 
 + β b̂1
b̂1
1

1





 b̂1 
Ven 
 + β b̂0
b̂1
1

1





 b̂0 
Vn 
 + β b̂0
b̂0
1

1





 b̂0 
Ven 
.
b̂0
1

From [18][Lemma 2], we can argue that Vn+1,S (π) is convex in π. Similarly, we can show
this for other value functions.
2. In this part, We can rewrite (17), in form of Vn+1,S (π, w) and Vn+1,N S (π, w) as function
of w. We can see that V1 (π, w) is monotone non decreasing and convex in w. Vn+1,S (π, w)
is constant plus a convex sum of four non decreasing convex function of w. Vn+1,N S (π, w)
is the sum of three non decreasing function of w. The convexity is preserved under max
operation so Vn+1 (π, w) is also non decreasing and convex in w and using induction, all
Vn (π, w) follows the same. As Vn (π, w) → V (π, w) and this complete the proof for V (π).
Similarly, we can show this for other value functions.

16

B. Proof of Lemma 2
The proof can be done via induction technique. The basic intuition behind ordering rewards,
transition and observation probabilities on belief π is to get monotone decreasing value
functions over π.
Assume that Vn (π) and Ven (π) is non increasing in π. Lets take π ′ ≥ π and playing an
arm is optimal. Then induction step

Vn+1 (π) = ρ(π) + β[ρ(π){θ1 (π, 1)Vn (γ1,1 (π)) + (1 − θ1 (π, 1))Ven (γ1,1 (π))}
+ (1 − ρ(π){θ1 (π, 1)Vn (γ0,1(π)) + (1 − θ1 (π, 1))Ven (γ0,1 (π))}]

Here ρ(π) is decresing in π, i.e. ρ(π ′ ) < ρ(π) for π ′ > π. Hence

Vn+1 (π) ≥ ρ(π ′ ) + β[ρ(π){θ1 (π, 1)Vn (γ1,1(π)) + (1 − θ1 (π, 1))Ven (γ1,1 (π))}
+ (1 − ρ(π){θ1 (π, 1)Vn (γ0,1(π)) + (1 − θ1 (π, 1))Ven (γ0,1 (π))}]

From our assumptions µ0 > µ1 , ρ1 > ρ0 and θa (π, y) > θa (π ′ , y), we get stochastic ordering
on obervation and availability probability, i.e., [ρ(π), 1 − ρ(π)]T ≤s [ρ(π ′ ), 1 − ρ(π ′ )]T and
[θa (π, y), 1 − θa (π, y)]T ≤s [θa (π ′ , y), 1 − θa (π ′ , y)]T . Then

′1
Vn+1 (π) ≥ ρ(π ′ ) + β[ρ(π ′ ){θ (π, 1)Vn (γ1,1 (π)) + (1 − θ1 (π, 1))Ven (γ1,1 (π))}
′1
′1
+ (1 − ρ′ (π){θ (π, 1)Vn (γ0,1 (π)) + (1 − θ (π, 1))Ven (γ0,1 (π))}]

Now γ1,1 (π), γ0,1(π) are increasing in π and Vn (π), Ve (π) are decreasing in π, then we have
Vn+1 (π) ≥ ρ(π ′ ) + β[ρ(π ′ ){θ1 (π ′ , 1)Vn (γ1,1 (π ′ )) + (1 − θ1 (π ′ , 1))Ven (γ1,1 (π ′ ))}
+ (1 − ρ(π ′ ){θ1 (π ′ , 1)Vn (γ0,1 (π ′ )) + (1 − θ1 (π ′ , 1))Ven (γ0,1 (π ′ ))}]
Vn+1 (π) ≥ Vn+1 (π ′ ).

Similarly we can show that Ven+1 (π) ≥ Ven+1 (π ′ ). This is true for every n ≥ 1. From Chapter 7
of [17] and Proposition 2.1 of Chapter 2 of [19], Vn (π) → V (π), uniformly and similarly
Ven (π) → Ve (π). Hence V (π) ≥ V (π ′ ) and Ve (π) ≥ Ve (π ′ ) for π ′ ≥ π.
C. Proof of Lemma 3
From Lemma 2 VS (π) is strictly decreasing in π and VN S (π) is nonincreasing in π.
Let f (π) = VS (π) − VN S (π) and f (π) is decreasing in π, i.e f (π) < f (π ′ ) for π > π ′ .
This implies that we need to show
VS (π) − VN S (π) < VS (π ′ ) − VN S (π ′ )

(18)

Rearranging 18 we need to show
VS (π) − VS (π ′ ) < VN S (π) − VN S (π ′ )

(19)

Rested bandit: Right hand side of (19) is 0. We know VS (π) is decreasing, hence our claim
follows.
Restless bandit: When ρ0 = 0, ρ1 = 1 similar argument holds and claim follows. But in other
cases, the claim holds under some restrictions on β and to prove this one required to use
Lipschitz properties (8) of value functions.

17

D. Proof of Lemma 4
As before f (π) = VS (π) − VN S (π). In order to prove that f (π) is decreasing, we need to
show that its partial derivative w.r.t. π is negative.
Taking partial derivative of f (π) w.r.t. π, we obtain
∂f (π)
∂VS (π) ∂VN S (π)
(20)
=
−
∂π
∂π
∂π
Next using Lipschitz property of value function 8, we can obtain following upper bound
on the sampling value function
∂VS (π)
≤ (ρ1 − ρ0 )κ{−1 + 2β(µ1 − µ0 )},
∂π
and lower bound on non sampling value function
∂VN S (π)
≥ −κ(ρ1 − ρ0 )|µ1 − µ0 |.
∂π
Hence

∂f (π)
≤ (ρ1 − ρ0 )κ{−1 + 2β(µ1 − µ0 ) + β|µ1 − µ0 |}
(21)
∂π
We want {−1 + 2β(µ1 − µ0 ) + β|µ1 − µ0 |} < 0 for the derivative of f (π) to be negative.
This holds true when 0 < µ1 − µ0 < 13 .
It is possible that VS (π), VN S (π) is not differential w.r.t π. In that case right partial
derivative should be taken. Such partial derivative exists because VS (π), VN S (π) are convex
and bounded.

