Multi-armed Bandits with Constrained Arms and Hidden States

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 \textit{threshold policy}. Further, \textit{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. INTRODUCTION
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.
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. PRELIMINARIES AND MODEL DESCRIPTION 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 X n (t) denote the state of arm n at beginning of time slot t, X n (t) ∈ {0, 1}. Each arm has availability constraints i.e. it is intermittently available. Let Y n (t) ∈ {0, 1} represent the availability of arm n in time slot t and Y n (t) = 1 if arm n is available, 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. A n (t) ∈ {0, 1} is the action in slot t with the following interpretation.
A n (t) = 1 if arm n is played in slot 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 A n (t), Y n (t) and it is defined as follows.
Pr{X n (t + 1) = j | X n (t) = i, Y n (t) = y, A n (t) = a} = P n ij (y, a) In every slot t, a binary signal Z y n (t) is observed from the arm n that is played. There is no observation from the arms that are not played. Thus Z y n (t) = 1 play of arm n is successful 0 otherwise.
Pr (Z y n (t) = 1 | X n (t) = i, Y n (t) = y, A n (t) = 1) = ρ n (i, y). Also, R a n (i, y) is the reward obtained from playing arm n given that, X n (t) = i, Y n (t) = y, A n (t) = a. Let Further, we will suppose that 0 ≤ η n,0 < r n,0 < η n,1 < r n,1 ≤ 1 for all n.
Remark 1: • The observation variable Z y n (t) may have different meanings in different applications. In communication systems, Z y n (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 = 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 θ a n (i, y) of arm n, at the beginning of next time slot t + 1; it is as follows θ a n (i, y) = Pr (Y n (t + 1) = 1|X n (t) = i, Y n (t) = y, A n (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 X n (t) = 0 | (Y n (s) = y s , A n (s), Z ys n (s)) t−1 s=1 . Let H t denote the history, H t := (Y n (s) = y s , A n (s), Z ys n (s)) 1≤n≤N,1≤s<t . We can describe the state of arm n at time t by S n (t) = (π n (t), Y n (t)) ∈ [0, 1] × {0, 1}. (S 1 (t), · · · S N (t)) is the state information of the arms at the beginning of time slot t. Further, we can rewrite θ a n (i, y) as function of π in following form.
Hence the expected reward from playing arm n at time t given that Y n (t) = y is R 1 n (π n (t), y) = π n (t)R 1 n (0, y) + (1 − π n (t)R 1 n (1, y). In each slot, exactly one arm is to played. Let φ(t) is the policy by the decision maker such that φ(t) : H t → {1, · · · , N} maps the history to one of the arm at slot t. Let We are now ready to define the infinite horizon discounted reward under policy φ for initial state information (π, y), π = (π 1 (1), · · · , π N (1)) and y = (y 1 (1), · · · , y N (1)). It is given by 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. SINGLE-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.
where action A(t) under policy φ is 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.
From [17], we know that the π(t) captures the information about the history H t , 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 A 1 and availability Y 1 1 But in general, transition probabilities for available and unavailable arms could be different.
We can write the following.
IV. STRUCTURAL RESULTS We now begin with some of structural results on value functions, showing convexity and threshold type policy.
2) For a fixed π, V (π), V S (π), V N S (π), V (π), V T (π) and V N 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.
A. Threshold structure of optimal policy (case µ 0 > µ 1 ) The following lemma provides sufficient conditions for monotonicity of the optimal value function.
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 V S (π) and V N S (π), is monotonic in π. Similarly, we prove this for V S (π) and V N S (π).
Lemma 3: (Isotone difference property) For fixed w and conditions of Lemma Then the following theorem gives monotone optimal policy on belief π.
Theorem 1: (Monotone optimal policy) 1) If the value function V : S 1 × A → R has isotone difference on S 1 × A then there exists a non increasing optimal policy a * : S 1 → A on belief S 1 . 2) If the value function V : S 0 × A → R has isotone difference on S 0 × A then there exists a non increasing optimal policy a * : S 0 → A on belief S 0 . Proof: From Lemma 1, the value functions V (π), V (π) are convex and monotone in π. From Lemma 2, V (π), V (π) 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 V S (π) and V N S (π), is monotonic in π for special cases. Similarly, difference between V S (π) and V N S (π) is monotone in π.
Lemma 4: For fixed w and β, and 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 (π), V (π) have following property Theorem 2: For fixed w and β, and 0 ≤ µ 1 − µ 0 ≤ 1 3 , 1) The optimal policy is threshold type for V T (π) and V N S (π). That is, either V (π) = V S (π) for all π ∈ [0, 1] or V (π) = V N S (π) for all π ∈ [0, 1] or there exists π * such that for π ≤ π * , V N S (π) for π ≥ π * .

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. INDEX 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.
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.,
Remark 6: • Note that we can rewrite definition of set G(w) in the following way.
where π L := min{π ∈ [0, 1] : V S (π) = V N S (π)}, and π L := min{π ∈ [0, 1] : V S (π) = V N S (π)}. • If the optimal policy is of threshold type, then π * = π L and π = π L . • To claim indexability, we require to show that as subsidy w increases, π L (w) and π L (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.
where δ ij equals to 1 if i = j and 0 otherwise. Also, p 00 = µ 0 , and p 10 = µ 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.
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 total discounted reward starting in state (π, 0) is V (π, w) = 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 the arm when it is in (π, 0). The expected total discounted reward for policy (a) is w 1−β and for policy (b) is given in (11).
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 for τ > 0. Proof: We first assume that (π, y) ∈ G(w). We want to prove Eqn. (13). We know from Lemma 5 that if (π, 0) ∈ G(w), then V (π, w) = w 1−β and if (π, 1) ∈ G(w), then V (π, w) = w 1−β . This is true for w ≥ R 1 (π, 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 This expected reward is upper bounded by w 1−β because not playing arm is always optimal for (π, y) ∈ G(w) as shown earlier. Hence 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 Here, τ is optimal stopping time, it is time until which arm is played.
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.
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. NUMERICAL RESULTS 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.
In Fig. 1-a), we plot V S (π) and V N S (π) as function of π. Similarly, in Fig. 1-b), we plot value functions V S (π) and V N 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 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 We also set ρ 0 = r 0 , ρ 1 = r 1 , initial belief and availability vector of arms is 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., θ a n (π, y) = θ a (π, y). In second set of examples, each arm has different probability of availability.
1) Arms with identical probability of availability: Here, θ a n (π, y) = θ a (π, y). But we assumed different reward and transition probabilities. We consider four examples as given below.
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.
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.

APPENDIX
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 Now define clearly, V 1 (π) is linear and hence convex. If V n (π), V n (π) is convex in π then we can write From [18][Lemma 2], we can argue that V n+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 V n+1,S (π, w) and V n+1,N S (π, w) as function of w. We can see that V 1 (π, w) is monotone non decreasing and convex in w. V n+1,S (π, w) is constant plus a convex sum of four non decreasing convex function of w. V n+1,N S (π, w) is the sum of three non decreasing function of w. The convexity is preserved under max operation so V n+1 (π, w) is also non decreasing and convex in w and using induction, all V n (π, w) follows the same. As V n (π, w) → V (π, w) and this complete the proof for V (π). Similarly, we can show this for other value functions.

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

C. Proof of Lemma 3
From Lemma 2 V S (π) is strictly decreasing in π and V N S (π) is nonincreasing in π. Let f (π) = V S (π) − V N S (π) and f (π) is decreasing in π, i.e f (π) < f (π ′ ) for π > π ′ . This implies that we need to show Rearranging 18 we need to show Rested bandit: Right hand side of (19) is 0. We know V S (π) 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.

D. Proof of Lemma 4
As before f (π) = V S (π) − V N S (π). In order to prove that f (π) is decreasing, we need to show that its partial derivative w.r.t. π is negative.