Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy

In this paper, we study finite state restless multi-armed bandit problem. We analyze the single-armed restless bandit problem. Our goal here is to show that the restless bandit is indexable. First, we provide structural results by making modeling assumption on transition probability and reward matrices and prove the indexability analytically.

Second contribution in this paper is to study single-armed restless bandit using the value-iteration algorithm with fixed subsidy (Lagrangian parameter) and obtain the optimal decision rule for each state. In this, the optimal decision can be either passive action or active action. Next, we vary subsidy over a fixed-size grid of subsidies and we compute the optimal decision rule for each state and for each value of subsidy from the fixed-size grid and it is referred to as the policy matrix. By analyzing this matrix, we provide an alternative approach to verify the indexability condition. It also provides an index value for each state. The advantages of our approach is that is easy to verify the indexability condition using value iteration scheme. We present the analysis of indexability using policy matrix with few examples. Best of our knowledge, this viewpoint is not taken into study in earlier works.

Third, we discuss different numerical examples from [28, 29, 16, 15] and present examples of non-indexable bandits. We give insight on conditions for the non-indexability of restless bandits using numerical examples. We observe that when the reward is monotone (non-decreasing/non-increasing) for both actions in same direction, then bandit is indexable. When the reward for passive action is increasing in state, the reward for active action is decreasing in state and there is sufficient difference between the rewards of passive and active action and some structure on transition probability matrices, then the bandit is shown to be non-indexable. This example is motivated from [15]. However, for most of applications in communication systems opportunistic scheduling problem [17] and recommendation systems [6, 7], the rewards are monotone for both actions in the same direction, thus the bandit is indexable.

Fourth, we compare the performance of Whittle index policy, myopic policy and online rollout policy. Numerical examples illustrate that the discounted cumulative reward under index policy and rollout policy is higher than that of myopic policy for non-identical restless bandits.

The rest of the paper is organized as follows. RMAB problem is formulated in Section II. Indexability and our approach of indexability for a single armed restless bandit is discussed in Section III. Different algorithms for RMAB are presented in Section IV. Numerical examples for indexability of single-armed restless bandit are given in Section V. Numerical examples for RMAB are illustrated in Section VI. We make concluding remarks in Section VII.

For notation simplicity, we omit superscript $n$ and introduce explicit dependence of value function on $\lambda.$ Then, the optimization problem from starting state $s$ under policy $\pi$ is as follows.

The optimal dynamic program is given by

for all $s\in\mathcal{S}.$ We use these ideas to define the indexability of single-armed restless bandit in next section. The analysis is done in the next section.

We now describe a single threshold type policy for MDP having action space $\mathcal{A}=\{0,1\}$ in $s$ assuming a fixed subsidy $\lambda$ as follows. We consider the deterministic Markov policy. The policy is called a single threshold type when the decision rule $\pi_{\lambda}(s)$ for $s\in\mathcal{S}$ is of the following form.

and $s^{*}$ is a threshold state. This is also referred to as control limit policy in [30]. The conditions required on transition probability and reward matrices for a single threshold policy are discussed below.

Proof of lemma follows from induction method and it is given in Appendix -A.

This implies that $Q(s,1,\lambda)-Q(s,0,\lambda)$ is non-decreasing in $s.$ This is also referred to as Monotone non-decreasing difference property in $s.$ This implies that the decision rule $\pi_{\lambda}(s)$ is non-decreasing in $s.$ We now state the following result from [30].

These assumptions imply that one requires stronger conditions on transition probability matrices $P^{0},$ $P^{1}$ and reward matrix $R.$

From Theorem 1, it is clear that optimal policy is of a single threshold type in $s$ for a fixed $\lambda.$

We next prove that $Q(s,a,\lambda)$ is subadditive on $\{0,1\}\times\mathbb{R}$ for all values of $s\in\mathcal{S}.$ That is, $Q(s,a=1,\lambda)-Q(s,a=0,\lambda)$ is non-increasing in $\lambda$ for each $s\in\mathcal{S}.$ Observe that $Q(s,a=0,\lambda)$ is strictly increasing in $\lambda$ and $Q(s,a=1,\lambda)$ is non-decreasing in $\lambda$ for fixed $s.$ For assumptions in Theorem 1, $Q(s,a=1,\lambda)-Q(s,a=0,\lambda)$ is non-increasing in $\lambda.$ Hence the policy $\pi_{\lambda}(s)$ is non-increasing in $\lambda$ for each $s\in\mathcal{S}.$

In this section, we study the value iteration algorithm and compute the optimal policy $\pi_{\lambda}(s)$ for each state $s\in\mathcal{S}$ for fixed value of subsidy $\lambda.$ We define the grid of subsidy $\Lambda$ which is of finite size, say $J.$ We perform the value iteration for each $\lambda\in\Lambda$ and compute the policy $\pi_{\lambda}(s)$ for $s\in\mathcal{S}.$ Size of policy matrix $\Phi=[[\pi_{\lambda}(s)]]$ is $K\times J.$ We next verify the indexability criteria in Remark 1 using policy matrix $\Phi=[[\pi_{\lambda}(s)]],$ that is, there exist $\lambda^{*}$ such that

for each $s\in\mathcal{S}.$ If this condition does not meet, we verify the non-indexable bandit condition in Remark 1. The value iteration algorithm for computation of policy matrix $\Phi$ is described in Algorithm 1.

We now discuss the structure of matrix $\Phi$ with examples and this can depend on transition probability and reward matrices.

In the following examples we consider state space $\mathcal{S}=\{1,2,3,4\}$ and $8$ values of $\lambda\in\Lambda.$ Here $\Lambda=\{\lambda_{1},\lambda_{2},\cdots,\lambda_{8}\}$ and $\lambda_{i}<\lambda_{j}$ for $1\leq i<j\leq 8.$

RMABs are known to be a PSPACE hard problem,[10, Theorem $4$]. However, the Lagrangian relaxed RMAB problem is solved by the index policy, where we analyze a single-armed restless bandit. Each bandit is a MDP with finite number of states and two actions. From [31], MDP with finite state-space and finite action space can be solved in polynomial in time (P-complete). Thus, the computational complexity of indexability and index computation is polynomial in time. Note that we have used the value iteration algorithm for computation of policy matrix with fixed grid size of subsidy, $|\Lambda|=J.$ From [32], the sample complexity of value iteration algorithm is $O\left(\frac{K^{2}\log(1/(1-\beta)\epsilon)}{1-\beta}\right).$ The value iteration algorithm is performed for each $\lambda\in\Lambda.$ Thus, the sample complexity of computing policy matrix $\Phi$ is $O\left(\frac{K^{2}J\log(1/(1-\beta)\epsilon)}{1-\beta}\right).$ The verification of indexability from matrix $\Phi$ requires additional time $KJ.$ This is due to the fact that one has to verify for each $s,$ $\Phi(s,\lambda)$ is non-increasing in $\lambda$ for all $\lambda\in\Lambda.$ Hence, indexability verification criteria and the index computation require sample complexity of $O\left(KJ+\frac{K^{2}J\log(1/(1-\beta)\epsilon)}{1-\beta}\right).$ There are many variants of value iteration algorithm which have improved the sample complexity in terms of its dependence on number of states $K,$ see [33]. Therefore, one can improve the complexities of indexability verification and index computation.

We now discuss a simulation-based approach referred to as online rollout policy. Here, many trajectories are ‘rolled out’ using a simulator and the value of each action is estimated based on the cumulative reward along these trajectories. Trajectories of length $H$ are generated using a fixed base policy, say, $\phi,$ which might choose arms according to a deterministic rule (for instance, myopic decision) at each time-step. The information obtained from a trajectory is

under policy $\phi.$ Here, $l$ denotes a trajectory, $h$ denotes time-step and $X^{n}_{h,l}$ denotes the state about arm $n.$ The action of playing or not playing arm $n$ at time-step $h$ in trajectory $l$ is denoted by $b^{n,\phi}_{h,l}\in\{0,1\}.$ Reward obtained from arm $n$ is $r^{n,\phi}_{h,l}.$

We now describe the rollout policy for $M=1$. We compute the value estimate for trajectory $l$ with starting belief $X=(X^{1},\cdots,X^{N}),$ and initial action $\xi\in\{1,2,\cdots,N\}$. Here, $\xi_{h,l}=n$ means arm $n$ is played at time-step $h$ in trajectory $l$, so $b^{n,\phi}_{h,l}=1$, and $b^{i,\phi}_{h,l}=0$ for $\forall i\neq n$. The value estimate for initial action $\xi$ along trajectory $l$ is given by

Then, averaging over $L$ trajectories, the value estimate for action $\xi$ in state $X$ under policy $\phi$ is

where, the base policy $\phi$ is myopic (greedy), i.e., it chooses the arm with the highest immediate reward, along each trajectory. Now, we perform one-step policy improvement, and the optimal action is selected as,

and $\widetilde{r}(X,\xi)=\sum_{n=1}^{N}r^{n}(X^{n},b^{n}).$ In each time-step $t$ with $X_{t}=\{X^{1}_{t},\cdots,X^{n}_{t}\},$ online rollout policy plays the arm $j^{*}(X_{t})$ obtained according to Eqn. (9). This can be extended to multiple play of arms.

We now discuss the computational complexity of online rollout policy. As rollout policy is a heuristic (look-ahead) policy, it does not require convergence analysis. In the Whittle index policy, index computation is done offline, where we compute and store the index values for each element on the grid $G,$ for all arms ($N$). During online implementation, when state $X=\{X^{1},...,X^{N}\}$ is observed, the corresponding index values are drawn from the stored data. On the other hand, rollout policy is implemented online and its computational complexity is stated in the following Theorem.

The proof is given in Appendix -C. Here $T$ is dependent on $\beta$ and $T=1/(1-\beta).$

For large state space, $K=1000,$ one requires grid of subsidy $\Lambda$ to be large, that is, $J=O(K).$ Thus the sample complexity of index computation is $O\left(K^{2}+\frac{K^{3}\log(1/(1-\beta)\epsilon)}{1-\beta}\right).$ The computational complexity of online rollout policy is dependent on horizon length $H$ and number of trajectories $L$ and it is $O(N(HL+2)/(1-\beta)).$ For large state space model, rollout policy can have lower computational complexity compared to index policy.

In the following example, we illustrate that the optimal policy is not a single threshold type but it is indexable. This example is taken from [28], [29], where indexability of the bandit is assumed, and author studied learning algorithm. In this example, we claim indexability using our approach.

The example has four states and the dynamics are circulant: when an arm is passive ($a=0$), resp. active ($a=1$), the state evolves according to the transition probability matrices.

The reward matrix is given as follows.

We consider different values of subsidy $\lambda\in[-1,1]$ and compute the optimal policy for $s\in\mathcal{S}$ using dynamic programming algorithm and obtain the policy matrix $\Phi,$ which is given in Fig. 1. We observe that the optimal policy has more than two threshold for some values of subsidy $\lambda.$ This is clear for subsidy $\lambda=-0.4,$ the optimal policy $\pi_{\lambda=-0.4}=\{0,1,1,0\}$ and there are two switches in decision rule. But it is indexable because as $\lambda$ increases from $-1$ to $+1,$ then the set $B(\lambda)$ is non-decreasing, where $B(\lambda)=\{s\in\mathcal{S}:\pi_{\lambda}(s)=0\}.$ Note that $B(-0.9)=\emptyset,$ $B(-0.8)=\{4\},$ $B(-0.4)=\{1,4\},$ $B(0.5)=\{1,2,4\},$ $B(0.9)=\{1,2,3,4\}.$

We illustrate the structure of policy matrix $\Phi$ for restart model, where action $1$ is taken, then $p^{1}_{s,1}=1$ for all $s\in\mathcal{S}.$ We consider $K=5$ states.

This example is taken from [28], where authors assumed indexability. The transition probability matrices are as follows.

The rewards for passive action $(a=0)$ with state $k,$ $r(k,0)=0.9^{k}$ and the rewards for active action $(a=1)$, $r(k,1)=0$ for all $k\in\mathcal{S}.$ We observe from Fig. 2 that the optimal policy is of a single threshold type for fixed subsidy $\lambda.$ Moreover, as subsidy increases from $-1$ to $+1,$ an optimal policy changes monotonically from active action to passive action for all states. Thus, the bandit is indexable.

We consider following parameters.

We make no structural assumption on transition probability matrices. But the reward is decreasing in $s$ for $a=1$ and increasing in $s$ for $a=0.$ From Fig. 3, we notice that $\pi_{\lambda}(s)$ is not monotone in $\lambda$ for $s=3.$ Thus, the bandit is non-indexable.