Approximation Algorithms for Restless Bandit Problems

Introduction

The celebrated multi-armed bandit problem (MAB) models the central trade-off in decision theory between exploration and exploitation, or in other words between learning about the state of a system and utilizing the system. In this problem, there are $n$ competing options, referred to as “arms,” yielding unknown rewards $\{r_{i}\}$. Playing an arm yields a reward drawn from an underlying distribution, and the information from the reward observed partially resolves its distribution. The goal is to sequentially play the arms in order to maximize reward obtained over some time horizon.

Typically, the multi-armed bandit problem is studied under one of two assumptions:

The underlying reward distribution for each arm is fixed but unknown, and a prior of this distribution is specified as input (stochastic multi-armed bandits ); or

The underlying rewards can vary with time in an adversarial fashion, and the comparison is against an optimal strategy that always plays one arm, albeit with the benefit of hindsight (adversarial multi-armed bandits ).

Relaxing both the assumptions simultaneously leads to the notorious restless bandit problem in decision theory, which in its ultimate generality, is PSPACE hard to even approximate . In the last two decades, in spite of the growth of approximation algorithms and the numerous applications of restless bandits , the approximability of these have remained unexplored. In this paper, we provide a general algorithmic technique that yields the first $O(1)$ approximations to a large class of these problems that are commonly studied in practice.

An important subclass of restless bandit problems are situations where the system is agnostic of the exploration – or the exploration gives us information about the state of the system but does not interfere with the evolution of the system. One such problem is the Feedback MAB which models opportunistic multi-channel access at a wireless node : The bandit corresponds to a wireless node with access to multiple noisy channels (arms). The state of the arm is the state (good/bad) of the channel, which varies according to a bursty $2$-state Markov process. Playing the arm corresponds to transmitting on the channel, yielding reward if the transmission is successful (good channel state), and at the same time revealing to the transmitter the current state of the channel. This corresponds to the Gilbert-Elliot model of channel evolution. The goal is to find a transmission policy of choosing one channel to transmit on every time step, that maximizes the long-term transmission rate. Feedback MAB also models Unmanned Aerial Vehicle (UAV) routing : the arms are locations of possibly interesting events, and whether a location is interesting or uninteresting follows a $2$-state Markov processes. Visiting a location by the UAV corresponds to playing the arm, and yields reward if an interesting event is detected. The goal is to find a routing policy that maximizes the long-term average reward from interesting events.

This problem is also a special case of Partially Observable Markov Decision Processes or POMDPs . The state of each arm evolves according to a Markov chain whose state is only observed when the arm is played. The player’s partial information, encapsulated by the last observed state and the number of steps since last playing, yields a belief on the current state. (This belief is simply a probability distribution for the arm being good or bad.) The player uses this partial information in making the decision about which arm to play next, which in turn affects the information at future times. While such POMDPs are widely used in control theory, they are in general notoriously intractable . In this paper we provide the first $O(1)$ approximation for the Feedback MAB and a number of its important extensions. This represents the first approximation guarantee for a POMDP, and the first guarantee for a MAB problem with time-varying rewards that compares to an optimal solution allowed to switch arms at will.

Before we present the problem statements formally, we survey literature on the stochastic multi-armed bandit problem. (We discuss adversarial MAB after we present our model and results.)

1 Background: Stochastic MAB and Restless Bandits

The stochastic MAB was first formulated by Arrow et al and Robbins . It resides under a Bayesian (or decision theoretic) setting: we successively choose between several options given some prior information (specified by distributions), and our beliefs are updated via Bayes’ rule conditioned on the results of our choices (observed rewards).

More formally, we are given a “bandit” with $n$ independent arms. Each arm $i$ can be in one of several states belonging to the set $\mathcal{S}_{i}$. At any time step, the player can play one arm. If arm $i$ in state $k\in\mathcal{S}_{i}$ is played, it transitions in a Markovian fashion to state $j\in\mathcal{S}_{i}$ w.p. $q^{i}_{kj}$, and yields reward $r^{i}_{k}\geq 0$. The states of arms that are not played stay the same. The initial state models the prior knowledge about the arm. The states in general capture the posterior conditioned on the observations from sequential plays. The problems is, given the initial states of the arms, find a policy for playing the arms in order to maximize one of the following infinite horizon quantities: $\sum_{t=0}^{\infty}R_{t}\beta^{t}$ (discounted reward), or $\lim_{t\rightarrow\infty}\frac{1}{t}\sum_{t=0}^{\infty}R_{t}$ (average reward), where $R_{t}$ is the expected reward of the policy at time step $t$ and $\beta\in(0,1)$ is a discount factor. A policy is a (possibly implicit) specification of fixing up front which arm (or distribution over arms) to play for every possible joint state of the arms.

It is well-known that Bellman’s equations yield the optimal policy by dynamic programming. The main issue in the stochastic setting is in efficiently computing and succinctly specifying the optimal policy: The input to an algorithm specifies the rewards and transition probabilities for each arm, and thus has size linear in $n$, but the state space is exponential in $n$. We seek polynomial-time algorithms (in terms of the input size) that compute (near-) optimal policies with poly-size specifications. Moreover, we require the policies to be executable each step in poly-time.

Note that since a policy is a fixed (possibly randomized) mapping from the exponential size joint state space to a set of actions, ensuring poly-time computation and execution often requires simplifying the description of the optimal policy using the problem structure. The stochastic MAB problem is the most well-known decision problem for which such a structure is known: The optimal policy is a greedy policy termed the Gittins index policy . In general, an index policy specifies a single number called “index” for each state $k\in\mathcal{S}_{i}$ for each arm $i$, and at every time step, plays the arm whose current state has the highest index. Index policies are desirable since they can be compactly represented, so they are the heuristic method of choice for several MDP problems. In addition, index policies are also optimal for several generalizations of the stochastic MAB, such as arm-acquiring bandits and branching bandits . In fact, a general characterization of problems for which index policies are optimal is now known .

On the positive side, Whittle presents a poly-size LP relaxation of the problem. In this relaxation, the constraint that exactly one arm is played per time step is replaced by the constraint that one arm on average is played per time step. In the LP, this is the only constraint connecting the arms. (Such decision problems have been termed weakly coupled systems .) Based on the Lagrangean of this relaxation, Whittle defines a heuristic index that generalizes the Gittins index. This is termed the Whittle Index (see Section 3). Though this index is widely used in practice and has excellent empirical performance , the known theoretical guarantees ( ) are very weak. In summary, despite being very well-motivated and extensively studied, there are almost no positive results on approximation guarantees for the restless bandit problems.

2 Results and Roadmap

We provide the first approximation algorithm for both a restless bandit problem and a partially observable Markov decision problem by providing a $2+\epsilon$-approximate index policy for the Feedback MAB problem which belongs to both classes. We show several other results; however, before presenting the specifics, we place our contribution in the context of existing techniques in control theory.

Our algorithmic technique for this problem (Section 2) involves solving (in polynomial time) the Lagrangean of Whittle’s LP relaxation for a suitable (and subtle) “balanced” choice of the Lagrange multiplier, converting this into a feasible index policy, and using an amortized accounting of the reward for the analysis. We show that this technique is closely related to the Whittle index , and in fact, provide the first approximation analysis of (a subtle variant of) the Whittle index which is widely used in control theory literature in the context of Feedback MAB problems (Section 3). We believe that analyzing the performance guarantees of the numerous indices used in the literature will increase and our analysis will provide an useful template.

However, the key difference between Whittle’s index and our index policy is the following: The former chooses one Lagrange multiplier (or index) per state of each arm, with the policy playing the arm with the largest index. This has the advantage of separate efficient computations for different arms; and in addition, such a policy (the Gittins index policy ) is known to be optimal for the stochastic MAB. However, it is well-known that this intuition about playing the arm with the largest index being optimal becomes increasingly invalid when complicated side-constraints such as time-varying rewards (Feedback MAB), blocking plays, and switching costs are introduced. In fact, we show a concrete problem in Section 8 where the Whittle index has a $\Omega(n)$ performance gap.

In contrast to the Whittle index, our technique chooses a single global Lagrange multiplier via a careful accounting of the reward, and develops a feasible policy from it. Unlike the Whittle index, this technique is sufficiently robust to encompass a large number of often-used variants of Feedback MAB problems: Plays with varying duration (Section 5), switching costs (Section 6), and observation costs (Section 7). In fact, we identify a general Monotone condition in restless bandit problems under which our technique applies (Section 4). Furthermore, our technique provides $O(1)$ approximations to other classic restless bandit problems even when Whittle’s index is polynomially sub-optimal: We show an example in the non-preemptive machine replenishment problem (Section 8). Finally, since our technique is based on solving the LagrangeanThis aspect is explicit in Sections 2 and 3. However, in Sections 4–8, we have presented our algorithm in terms of first solving a linear program. However, it is easy to see that this is equivalent to solving the Lagrangean, and hence to the computation required for Whittle’s index. The details are quite standard and can be reconstructed from those in Sections 2 and 3. (just like the Whittle index), the computation time is comparable to that for such indices.

In summary, our technique succeeds in finding the first provably approximate policies for widely-studied control problems, without sacrificing efficiency in the process. We believe that the generality of this technique will be useful for exploring other useful variations of these problems as well as providing an alternate algorithm for practitioners.

In terms of specific results, the paper is organized as follows:

We begin by presenting a $2+\epsilon$-approximation for Feedback bandits in Section 2. We also provide a $e/(e-1)$ integrality gap instance showing that out analysis is nearly tight.

In Section 3 we show that our analysis technique can be used to prove that a thresholded variant of the Whittle index is a $2$ approximation. We also show instances where the reward of any index policy is at least $1+\Omega(1)$ factor from the reward of the optimal policy. Therefore although the Whittle index is not optimal, our result sheds light on its observed superior performance in this specific context.

In Section 4 we generalize the result in Section 2 to define a general sub-class of restless bandit problems based on a critical set of properties: Separability and monotonicity. For this subclass, termed Monotone bandits (which generalizes Feedback MAB), we provide a $2$ approximation by generalizing the technique in Section 2. Our technique now introduces a balance constraint in the dual of the natural LP relaxation, and constructs the index policy from the optimal dual solution. We further show that in the absence of monotonicity or separability, the problem is either NP-Hard to approximate, or has unbounded integrality gap respectively.

In Section 5 we extend Feedback MAB (as well as Monotone bandits) to consider multiple simultaneous blocking plays of varying durations.

In Section 6 we extend Feedback MAB (and Monotone bandits) to consider switching costs.

In Section 7 we extend Feedback MAB to a variant where the information acquisition is varied, namely, an arm has to be explicitly probed at some cost to obtain its state.

In Section 8, we derive a $2$-approximation for a classic, restless bandit problem called non-preemptive machine replenishment . We also show that the Whittle Index for this problem has a $\Omega(n)$ factor worse performance compared to the optimal policy. Thus the technique introduced in this paper can be superior to Whittle index or similar policies.

3 Related Work

Contrast with the Adversarial MAB Problem. While our problem formulations are based on the stochastic MAB problem, one might be interested in a formulation based on the adversarial MAB . Such a formulation might be to assume that rewards can vary adversarially, and that the objective is to compete with a restricted optimal solution that always plays the same arm but with the benefit of hindsight.

These different formulations result in fundamentally different problems. Under our formulation, the difficulty is computational: we want to compute policies for playing the arms, assuming stochastic models of how the system varies with time. under the adversarial formulation, the difficulty is informational: we would be interested in the regret of not having the benefit of hindsight. A sequence of papers show near-tight regret bounds in fairly general settings . However, applying this framework is not satisfying: It is straightforward to show that a policy for Feedback MAB that is allowed to switch arms can be $\Omega(n)$ times better than a policy that is not allowed to do so (even assuming hindsight). Another approach would be to define each policy as an “expert”, and use the low-regret experts algorithm ; however, the number of policies is super-exponentially large, which would lead to weak regret bounds, along with exponential-size policy descriptions and exponential per-step execution time.

We note that developing regret bounds in the presence of changing environments has received significant interest recently in computational learning ; however, this direction requires strong assumptions such as bounded switching between arms and slowly varying environments , both of which assumptions are inapplicable to Feedback MAB. In independent work, Slivkins and Upfal consider the modification of Feedback MAB where the underlying state of the arms vary according to a reflected Brownian motion with bounded variance. As discussed in , this problem is technically very different from ours, even requiring different performance metrics.

The results in consider variants of the stochastic MAB where the underlying reward distribution does not change and only a limited time is allotted to learning about this environment. Although several of these results use LP rounding, they have little connection to the duality based framework considered here.

Our duality based framework shows a $2$-approximate index policy for non-preemptive machine replenishment (Section 8). Elsewhere, Munagala and Shi considered the special case of preemptive machine replenishment problem, for which the Whittle index is equivalent to a simple greedy scheme. They show that this greedy policy, though not optimal, is a $1.51$ approximation. However, the techniques there are based on queuing analysis, and do not extend to the non-preemptive case where the Whittle index can be an arbitrarily poor approximation (as shown in Section 8).

Our solution technique differs from primal-dual approximation algorithms and online algorithms , which relax either the primal or the dual complementary slackness conditions using a careful dual-growing procedure. Our index policy and associated potential function analysis crucially exploit the structure of the optimal dual solution that is gleaned using both the exact primal as well as dual complementary slackness conditions. Furthermore, our notion of dual balancing is very different from that used by Levi et al for designing online algorithms for stochastic inventory management.

The Feedback MAB Problem

In this problem, first formulated independently in , there is a bandit with $n$ independent arms. Arm $i$ has two states: The good state $g_{i}$ yields reward $r_{i}$, and the bad state $b_{i}$ yields no reward. The evolution of state of the arm follows a bursty $2$-state Markov process which does not depend on whether the arm is played or not at a time slot. Let $s_{it}$ denote the state of arm $i$ at time $t$. Denote the transition probabilities of the Markov chain as follows: $\Pr[s_{i(t+1)}=g_{i}|s_{it}=b_{i}]=\alpha_{i}$ and $\Pr[s_{i(t+1)}=b_{i}|s_{it}=g_{i}]=\beta_{i}$. The $\alpha_{i},\beta_{i},r_{i}$ values are specified as input. The “burstiness” assumption simply means $\alpha_{i}+\beta_{i}\leq 1-\delta$ for some small $\delta>0$ specified as part of the input. The evolution of states for different arms are independent. Any policy chooses at most one arm to play every time slot. Each play is of unit duration, yields reward depending on the state of the arm, and reveals to the policy the current state of that arm. When an arm is not played, the true underlying state cannot be observed, which makes the problem a POMDP. The goal is to find a policy to play the arms in order to maximize the infinite horizon average reward.

First observe that we can change the reward structure of Feedback MAB so that when an arm is played, we obtain reward from the last-observed state instead of the currently observed state. This does not change the average reward of any policy. This allows us to encode all the state of each arm as follows.

From the perspective of any policy, the state of any arm can be encoded as $(s,t)$, which denotes that it was last observed $t\geq 1$ steps ago to be in state $s\in\{g_{i},b_{i}\}$.

Note that any policy maps each possible joint state of $n$ arms into an action of which arm to play. Such a mapping has size exponential in $n$. The standard heuristic is to consider index policies: Policies which define an “index” or number for each state $(s_{i},t)$ and play the arm with the highest current index. The following theorem shows that playing the arm with the highest myopic reward does not work, and that index policies in general are non-optimal. Therefore, our problem is interesting and the best we can hope for with index policies is a $O(1)$ approximation.

(Proved in Appendix A) For Feedback MAB, the reward of the optimal policy has an $\Omega(n)$ gap against that of the myopic index policy and an $\Omega(1)$ gap against that of the optimal index policy.

In this section, we show that a simple index policy is a $(2+\epsilon)$ approximation. This is based on a natural LP relaxation suggested by Whittle which we discuss in Section 2.1; this formulation will have infinitely many constraints. We then consider the Lagrangean of this formulation in Section 2.2, and analyze its structure via duality, which enables computing its optimal solution in polynomial time. At this point, we deviate significantly from previous literature, and present our main contribution in Section 2.3: A subtle and powerful “balanced” choice of the Lagrange multiplier, which enables the design of an intuitive index policy, BalancedIndex, along with an equally intuitive analysis. We use duality and potential function arguments to show that the policy is $(2+\epsilon)$ approximation. We conclude by showing that the gap of Whittle’s relaxation is $e/(e-1)\approx 1.58$, indicating that our analysis is reasonably tight. This analysis technique generalizes easily (explored in Sections 4 – 8) and has rich connections to other index policies, most notably the Whittle index (explored in Section 3).

1 Whittle’s LP

Whittle’s LP is obtained by effectively replacing the hard constraint of playing one arm per time step, with allowing multiple plays per step but requiring one play per step on average. Hence, the LP is a relaxation of the optimal policy.

Let $v_{it}$ be the probability of the arm $i$ being in state $g_{i}$ when it was last observed in state $b_{i}$ exactly $t$ steps ago. Let $u_{it}$ be the same probability when the last observed state was $g_{i}$. We have:

The functions $v_{it}$ and $1-u_{it}$ are monotonically increasing and concave functions of $t$.

We now present Whittle’s LP, and interpret it in the lemma that immediately follows.

The optimal objective to Whittle’s LP, $OPT$, is at least the value of the optimal policy.

Consider the optimal policy. In the execution of this policy, for each arm $i$ and state $(s,t)$ for $s\in\{g,b\}$, let the variable $x^{i}_{st}$ denote the probability (or fraction of time steps) of the event: Arm $i$ is in state $(s,t)$ and gets played. Let $y^{i}_{st}$ correspond to the probability of the event that the state is $(s,t)$ and the arm is not played. Since the underlying Markov chains are ergodic, the optimal policy when executed is ergodic, and the above probabilities are well-defined.

Now, at any time step, some arm $i$ in state $(s,t)$ is played, which implies the $x^{i}_{st}$ values are probabilities of mutually exclusive events. This implies they satisfy the first constraint in the LP. Similarly, for each arm $i$, at any step, this arm is in some state $(s,t)$ and is either played or not played, so that the $x^{i}_{st},y^{i}_{st}$ correspond to mutually exclusive events. This implies that for each $i$, they satisfy the second constraint. For any arm $i$ and state $(s,t)$, the LHS of the third constraint is the probability of being in this state, while the RHS is the probability of entering this state; these are clearly identical in the steady state. For arm $i$, the LHS of the fourth (resp. fifth) constraint is the probability of being in state $(g,1)$ (resp. $(b,1)$), and the RHS is the probability of entering this state; again, these are identical.

This shows that the probability values defined for the execution of the optimal policy are feasible for the constraints of the LP. The value of the optimal policy is precisely $\sum_{i=1}^{n}\sum_{t\geq 1}r_{i}x^{i}_{gt}$, which is at most $OPT$ – the maximum possible objective for the LP. ∎

The above LP encodes in one variable $x^{i}_{st}$ the probability the arm $i$ is in state $(s,t)$ and gets played; however, we note that in the optimal policy, this decision to play actually depends on the joint state of all arms. This separation of the joint probabilities into individual probabilities effectively relaxes the condition of having one play per step, to allowing multiple plays per step but requiring one play per step on average. While the policy generated by Whittle’s LP is infeasible, the relaxation allows us to compute an upper-bound on the value of the optimal feasible policy.

We note $y^{i}_{st}=\sum_{t^{\prime}>t}x^{i}_{st^{\prime}}$. It is convenient to eliminate the variables $y^{i}_{st}$ by substitution and the last two constraints collapse into the same constraint. Thus, we have the natural LP formulation shown in Figure 1. We note that the first constraint can either be an inequality ($\leq$) or an equality; w.l.o.g., we use equality, since we can add a dummy arm that does not yield any reward on playing.

From now on, let $OPT$ denote the value of the optimal solution to (Whittle). The LP in its current form has infinitely many constraints; we will now show that this LP can be solved in polynomial time to arbitrary precision by finding structure in the Lagrangean.

2 Decoupling Arms via the Lagrangean

In (Whittle), the only constraint connecting different arms is the constraint:

We absorb this constraint into the objective via Lagrange multiplier $\lambda\geq 0$ to obtain the following objective:

Through the Lagrangean, we have effectively removed the only constraint that connected multiple arms. LPLagrange$(\lambda)$ now yields $n$ disjoint maximization problems, one for each arm $i$: At any time step, arm $i$ can be played (and reward obtained from it), or not played. Whenever the arm is played, we incur a penalty $\lambda$ in addition to the reward. The goal is to maximize the expected reward minus cost. Note that if the penalty is zero, the arm is played every step, and if the penalty is sufficiently large, the optimal solution would be to never play the arm.

For each arm $i$, let $L_{i}(\lambda)$ denote the optimal policy, and let $H_{i}(\lambda)$ denote the optimal reward minus penalty. Note that the global reward minus penalty is the sum for each arm: $G(\lambda)=\sum_{i=1}^{n}H_{i}(\lambda)$.

We first show that the optimal policy $L_{i}(\lambda)$ for any arm $i$ belongs to the class of policies $\mathcal{P}_{i}(t)$ for $t\geq 1$, whose specification is presented in Figure 2. Intuitively, step (1) corresponds to exploitation, and step (2) to exploration. Set $\mathcal{P}_{i}(\infty)$ to be the policy that never plays the arm.

To show this, we take with the dual of LPLagrange$(\lambda)$:

The fact that the optimal single arm policy $L_{i}(\lambda)$ belongs to the class $\{P_{i}(t)\}$ comes from (5) of the following lemma.

For any $\lambda\geq 0$, in the optimal solution to Whittle-Dual$(\lambda)$, for any arm with $h_{i}>0$:

For some $t_{i}\geq 1$, $x^{i}_{bt_{i}}>0$ and $\lambda+t_{i}h_{i}=v_{it_{i}}p_{i}$.

$x^{i}_{g1}>0$ and $\lambda+h_{i}=r_{i}-\beta p_{i}$.

The optimal single-arm policy for arm $i$ is $L_{i}(\lambda)=\mathcal{P}_{i}(t_{i})$.

The first part follows the definition of strong duality. The problem LPLagrange$(\lambda)$, ignoring the constant $\lambda$ in the objective, separates into $n$ separate LPs, one for each arm. The dual objective for arm $i$ is precisely $h_{i}$, which must be the same as the primal objective, $H_{i}(\lambda)$.

If $h_{i}=H_{i}(\lambda)>0$, the solution to the LP for arm $i$ is the policy $L_{i}(\lambda)$. In order to have non-zero $H_{i}(\lambda)$, such a policy must play the arm first in some state $(b,t_{i})$ and state $(g,t^{\prime}_{i})$. Since $x^{i}_{st}$ is the probability this policy plays in state $(s,t)$, this implies $x^{i}_{bt_{i}}>0$ and $x^{i}_{gt^{\prime}_{i}}>0$.

Since $x^{i}_{bt_{i}}>0$, by complementary slackness, we have $\lambda+t_{i}h_{i}=v_{it_{i}}p_{i}$. Since the LHS is at least zero, this implies $p_{i}\geq 0$. This proves parts (2) and (3).

To see part (4), observe that for the set of constraints $\lambda+th_{i}\geq r_{i}-(1-u_{it})p_{i}$, since $1-u_{it}$ is a monotonically increasing function of $t$, the RHS is monotonically decreasing in $t$. Since the LHS is monotonically increasing, if the LHS and RHS are equal, they have to be so for $t=1$. Now, since $x^{i}_{gt^{\prime}_{i}}>0$, by complementary slackness, $\lambda+t^{\prime}_{i}h_{i}=r_{i}-(1-u_{it^{\prime}_{i}})p_{i}$. By the above argument, $t^{\prime}_{i}=1$, which completes the proof of part (4).

Since $x^{i}_{g1}>0$ and $x^{i}_{bt_{i}}>0$, the optimal policy for $L_{i}(\lambda)$ plays the arm in state $(g,1)$ and in state $(b,t_{i})$, which is precisely the description of $\mathcal{P}_{i}(t_{i})$. This proves part (5). ∎

It will be instructive to interpret the problem $L_{i}(\lambda)$ as follows: Amortize the reward so that for each play, the arm $i$ yields a steady reward of $\lambda$. The goal is to find the single-arm policy that optimizes the excess reward per step over and above the amortized reward $\lambda$ per play. As we have shown above, the optimal value for this problem is precisely $H_{i}(\lambda)$, and the policy $L_{i}(\lambda)$ that achieves this belongs to the class $\{\mathcal{P}_{i}(t),t\geq 1\}$.

2.2 Solving LPLagrange(λ)𝜆(\lambda)

Having decomposed the program LPLagrange$(\lambda)$ into independent maximization problems for each arm, and having characterized the optimal single-arm policies, we can now solve the program in polynomial time. It will turn out this can be solved by simple function maximization via closed form expressions.

For policy $\mathcal{P}_{i}(t)$, let $R_{i}(t)$ denote the expected per-step reward, and let $Q_{i}(t)$ denote the expected rate of play. Let $F_{i}(\lambda,t)=R_{i}(t)-\lambda Q_{i}(t)$ denote the value of $\mathcal{P}_{i}(t)$. Also define:

Finally, let $R_{i}(\lambda)=R_{i}(t_{i}(\lambda))$ and $Q_{i}(\lambda)=Q_{i}(t_{i}(\lambda))$

Note that the optimal reward minus cost for arm $i$ is simply $H_{i}(\lambda)=\max_{t\geq 1}R_{i}(t)-\lambda Q_{i}(t)=R_{i}(t_{i})-\lambda Q_{i}(t_{i})$. Since each $\mathcal{P}_{i}(t)$ corresponds to a Markov Chain, it is straightforward to obtain closed form expressions for $R_{i}(t)$ and $Q_{i}(t)$.

In playing an arm with reward $r$, transition probabilities $\alpha$ and $\beta$, the policy $\mathcal{P}(t)$ yields average reward $R(t)=r\frac{v_{t}}{v_{t}+t\beta}$, and expected rate of play $Q(t)=\frac{v_{t}+\beta}{v_{t}+t\beta}\geq\frac{1}{t}$. Recall that $v_{t}=\frac{\alpha}{\alpha+\beta}(1-(1-\alpha-\beta)^{t})$ is the probability the arm is good given it was observed to be bad $t$ steps ago.

The Markov chain describing the policy $\mathcal{P}(t)$ is shown in Figure 3, and has $t+1$ states which we denote $s,0,1,2,\ldots,t-1$. The state $s$ corresponds to the arm being observed to be in state $g$, and the state $j$ corresponds to the arm being observed in state $b$ exactly $j$ steps ago. The transition probability from state $j$ to state $j+1$ is $1$, from state $s$ to state is $\beta$, from state $t-1$ to state $s$ is $v_{t}$, and from state $t$ to state is $1-v_{t}$. Let $\pi_{s},\pi_{0},\pi_{1},\ldots,\pi_{t-1}$ denote the steady state probabilities of being in states $s,0,1,\ldots,t-1$ respectively. This Markov chain is easy to solve. We have $\pi_{0}=\pi_{1}\ldots=\pi_{t-1}$, so that the first identity is: $\pi_{s}+t\pi_{0}=1$. Furthermore, by considering transitions into and out of $s$, we obtain: $\beta\pi_{s}=v_{t}\pi_{t-1}=v_{t}\pi_{0}$. Combining these, we obtain: $\pi_{s}=\frac{v_{t}}{v_{t}+t\beta}$, and $\pi_{0}=\frac{\beta}{v_{t}+t\beta}$. Now we have:

(Proved in Appendix A) For each arm $i$, the optimal reward minus penalty of the single arm policy for arm $i$ is

The maximum value $t_{i}(\lambda)=\mbox{argmax}_{t\geq 1}F_{i}(\lambda,t)$ satisfies the following:

If $\lambda\geq r_{i}\left(\frac{\alpha_{i}}{\alpha_{i}+\beta_{i}(\alpha_{i}+\beta_{i})}\right)$, then $t_{i}(\lambda)=\infty$, and $H_{i}(\lambda)=0$.

If $\lambda=r_{i}\left(\frac{\alpha_{i}}{\alpha_{i}+\beta_{i}(\alpha_{i}+\beta_{i})}\right)-\rho$ for some $\rho>0$, then $t_{i}(\lambda)$ (and hence $H_{i}(\lambda)$) can be computed in time polynomial in the input size and in $\log(1/\rho)$ by binary search.

3 The BalancedIndex Policy

Though we could now use LPLagrange$(\lambda)$ to solve Whittle’s LP by finding the $\lambda$ so that $\sum_{i=1}^{n}Q_{i}(\lambda)\approx 1$ (refer Appendix A.3 for details), our $2$-approximation policy will not be based this approach. For our analysis to work, we must make a subtle but crucial modification: We will instead set $\lambda$ to be the sum of the excess reward for all single-arm policies $\sum_{i=1}^{n}H_{i}(\lambda)$. (Recall that we can interpret $\lambda$ to be a penalty per play, so in the optimal single-arm policy for arm $i$, $H_{i}(\lambda)$ is the average reward minus penalty.) Note that by Lemma 2.7, this implies $\lambda\geq OPT/2$ and $\sum_{i=1}^{n}H_{i}(\lambda)\geq OPT/2$. Intuitively, we are forcing the Lagrangean to balance short-term reward (represented by $\lambda$) with long-term average reward (represented by $\sum_{i=1}^{n}H_{i}(\lambda)$). Our balance technique can be generalizes to many other restless bandit problems (see Sections 4 – 8).

We first show how to compute this value of $\lambda$ in polynomial time. We begin by presenting the connection between $G(\lambda=\sum_{i=1}^{n}H_{i}(\lambda)$ and $OPT$, the value of the optimal solution to (Whittle).

For any $\lambda$, we have: $\lambda+G(\lambda)=\lambda+\sum_{i=1}^{n}H_{i}(\lambda)\geq OPT$.

By Lemma 2.4, part (1), we have: $\lambda+\sum_{i=1}^{n}H_{i}(\lambda)=\lambda+\sum_{i=1}^{n}h_{i}$. The latter is the objective of the dual of (Whittle), which implies the lemma by weak duality. ∎

$h_{i}=H_{i}(\lambda)$ is a non-increasing function of $\lambda$.

Recall from Lemma 2.4 that $h_{i}=H_{i}(\lambda)$. For any $\lambda$, consider the value $F_{i}(\lambda,t)=R_{i}(t)-\lambda Q_{i}(t)$ of the policy $\mathcal{P}_{i}(t)$. Since this decreases as $\lambda$ increases, $H_{i}(\lambda)=\max_{t}F_{i}(\lambda,t)$ is also a non-increasing function of $\lambda$. ∎

In polynomial time, we can find a $\lambda$ so that $\lambda\geq(1-\epsilon)OPT/2$, and $G(\lambda)=\sum_{i=1}^{n}H_{i}(\lambda)=\sum_{i=1}^{n}h_{i}\geq OPT/2$.

First note by Lemma 2.8 that $G(\lambda)=\sum_{i=1}^{n}H_{i}(\lambda)$ is monotonically non-increasing in $\lambda$. Therefore, start with $\lambda=\sum_{i=1}^{n}r_{i}$, and $\lambda$ scale down by by a factor of $(1+\epsilon)$ until $\lambda<G(\lambda)$. Note that for any $\lambda$, the value of $G(\lambda)$ can be computed in poly-time by Lemma 2.6. At this point, let $\lambda^{\prime}=\lambda(1+\epsilon)$. Since $G(\lambda^{\prime})\leq\lambda^{\prime}$, by Lemma 2.7, we have $\lambda^{\prime}\geq OPT/2$, which implies $\lambda\geq(1-\epsilon)OPT/2$. Further, since $\lambda<G(\lambda)$, again by Lemma 2.7, we have $G(\lambda)\geq OPT/2$. ∎

We start with the value of $\lambda$ from Lemma 2.9. The policy only works with the subset of arms $S$ so that for $i\in S$, we have $H_{i}(\lambda)>0$. For this $\lambda$, the solution to LPLagrange$(\lambda)$ yields one policy $\mathcal{P}_{i}(t_{i}(\lambda))$ of value $H_{i}(\lambda)$ for each arm $i\in S$ (see Lemma 2.4). Let $t_{i}=t_{i}(\lambda)$. Recall that if an arm was last observed in state $s\in\{g,b\}$ some $t\geq 1$ steps ago, then its state is denoted $(s,t)$. We call an arm $i$ in state $(g,1)$ as good; in state $(b,t)$ for $t\geq t_{i}$ as ready, and in state $(b,t)$ for $t<t_{i}$ as bad. The policy is shown in Figure 4.

Note that the way the scheme works, at most one arm can be in state $(g,1)$ at any time step, and if such an arm exists, this arm is played at the current step (and in the future until it switches out of this state). The above can be thought of as executing the policies $\mathcal{P}_{i}(t_{i})$ for arms $i\in S$ independently and in case of simultaneous attempts to play, resolving conflicts according to the above priority scheme.

Though the above policy is not written as an index policy, it is equivalent to the following index: There is a dummy arm with index that does not yield reward on playing. If $h_{i}=H_{i}(\lambda)=0$, the index for all states of this arm is $-1$. For arms with $h_{i}>0$, the index for state $(g,1)$ is $2$; that for states $(b,t)$ with $t\geq t_{i}$ is $1$, and that for states $(b,t)$ with $t<t_{i}$ is $-1$.

3.2 Analysis

We now prove that the BalancedIndex policy is in fact a 2-approximation. The proof is based on the fact that the Lagragean $\lambda$ and the excess rewards $h_{i}=H_{i}(\lambda)$ give us a way of accounting for the average reward. And by Lemma 2.7, $\lambda\geq OPT/2$ and $\sum h_{i}\geq OPT/2$, which gives us a way of linking the rewards from our policy to the LP optimum.

The BalancedIndex policy is a $2+\epsilon$ approximation to Feedback MAB. Furthermore, this policy can be computed in polynomial time.

Recall that the reward of optimal single arm policy $\mathcal{P}_{i}(t_{i})$ is $R_{i}(\lambda)=H_{i}(\lambda)+\lambda Q_{i}(\lambda)$, so that this reward can be accounted as $H_{i}(\lambda)=h_{i}$ per step plus $\lambda$ per play. We use this amortization of rewards to show that the average reward of our index policy is at least $OPT/2$.

Focus on any arm $i$, we call a step blocked for the arm if the arm is ready for play–the state is $(b,t)$ where $t\geq t_{i}$–but some other arm is played at the current step. Consider only the time steps which are not blocked for arm $i$. For these time steps, the arm behaves as follows: It is continuously played in state $(g,1)$. Then it transitions to state $(b,1)$ and moves in $t_{i}-1$ time steps to state $(b,t_{i}-1)$. After this the arm might be blocked, and the next state that is not blocked is $(b,t)$ for some $t\geq t_{i}$, at which point the arm is played. Using the formula for $R(t)$ from Lemma 2.5, and since $v_{it}\geq v_{it_{i}}$ for $t\geq t_{i}$, we have

which implies that the per-step reward of this single arm policy for arm $i$ restricted to the non-blocked time steps is at least the per-step reward $R_{i}(t_{i})$ of the optimal single-arm policy $\mathcal{P}_{i}(t_{i})$. Therefore, for these non-blocked steps, the reward we get is at least $h_{i}=H_{i}(\lambda)$ per step, and at least $\lambda$ per play.

Now, on steps where no arm is played, none of the arms is blocked by definition, so our amortization yields a per-step reward of at least $\sum_{i\in S}h_{i}\geq OPT/2$. On steps when some arm is played, the arm that is played by definition cannot not blocked, so we get a reward of at least $\lambda\geq(1-\epsilon)OPT/2$ for this step. This completes the proof. ∎

3.3 Alternate Analysis

The above analysis is very intuitive. We now present an alternative way to analyze the policy, that leads to a more generalizable technique. This uses a Lyapunov (potential) function argument. Recall from Lemma 2.4 that $h_{i}=H_{i}(\lambda)$; further that $t_{i}=t_{i}(\lambda)$. Define the potential $\Phi_{i}$ for each arm $i$ at any time as follows:

If arm $i$ moved to state $b$ some $y$ steps ago ($y\geq 1$), the potential $\Phi_{i}$ is $h_{i}(\min(y,t_{i})-1)$. In the state $g_{i}$ the potential is $p_{i}$. Recall that $p_{i}$ is the optimal dual variable in Whittle-Dual$(\lambda)$.

Let $\Phi_{T}$ denote the total potential, $\sum_{i=1}^{n}\Phi_{i}$, at any step $T$ and let $R_{T}$ denote the total reward accrued until that step. Define the function $\mathcal{L}_{T}=t\cdot OPT/2-R_{T}-\Phi_{T}$. Let $\Delta R_{T}=R_{T+1}-R_{T}$ and $\Delta\Phi_{T}=\Phi_{T+1}-\Phi_{T}$.

$\mathcal{L}_{T}$ is a Lyapunov function. i.e., $\mathbf{E}[\mathcal{L}_{T+1}|\mathcal{L}_{T}]\leq\mathcal{L}_{T}$. Equivalently, at any step:

At a given step, suppose the policy does nothing, then all arms are “not ready”. The total increase in potential is precisely

On the other hand, suppose that the policy plays arm $i$, which has last been observed in state $b$ and has been in that state for $y\geq t_{i}$ steps. With probability $q\geq v_{it_{i}}$ the observed state is $g_{i}$ and the change in reward $\Delta R_{T}=r_{i}$ and the change in potential is $p_{i}-h_{i}(t_{i}-1)$. With probability $1-q$ the observed state is $b$ and the change in potential is $-h_{i}(t_{i}-1)$ (and there is no change in reward). Thus in this case since $q\geq v_{it_{i}}$, and $p_{i}\geq 0$, we have:

The penultimate inequality follows from Lemma 2.4, part (3). Note that the potentials of arms not played cannot decrease, so that the first inequality is valid.

Finally supposing the policy plays an arm $i$ which was last observed in state $g_{i}$ and played in the last step, with probability $1-\beta_{i}$ the increase in reward is $r_{i}$ and the potential is unchanged. With probability $\beta_{i}$ the potential will decrease by $-p_{i}$. Therefore in this case, by Lemma 2.4, part (4).

By their definition, the potentials $\Phi_{T}$ are bounded independent of the time horizon, by telescoping summation, the above lemma implies that $\lim_{T\rightarrow\infty}\frac{\mathbf{E}[R_{T}]}{T}\geq(1-\epsilon)OPT/2$. This proves Theorem 2.10.

The following theorem shows that our analysis is almost tight (considering that our $2$-approximation is against Whittle’s LP).

(Proved in Appendix A) The gap of Whittle’s LP is arbitrarily close to $e/(e-1)\approx 1.58$.

Analyzing the Whittle Index for Feedback MAB

Before generalizing our $2$-approximation algorithm to a larger subclass of restless bandit problems, we explore the connection between our analysis and the well-known Whittle Index used in practice. This section can be skipped without losing continuity of the paper.

A well-studied index policy for restless bandit problems is the Whittle Index . In the context of Feedback MAB, this index has been independently studied by Le Ny et al and subsequently by Liu and Zhao . Both these works give a closed form expressions for this index and show near-optimal empirical performance. Our main result in this section is to justify the empirical performance by showing that a simple but very natural modification of this index in order to favor myopic exploitation yields a $2$-approximation. The modification simply involves giving additional priority to arms in state $(g,1)$ if their myopic expected next step reward $r_{i}(1-\beta_{i})$ is at least a threshold value.

Defined in general, the Whittle’s index for each state $x$ is the largest penalty-per-play $\lambda$ such that the optimal policy is indifferent between playing in $x$ and not playing. In our specific problem, the current state for each arm $i$ is captured by the tuple $(s,t)$– the arm was last seen to be $s\in\{g,b\}$ (good or bad) $t$ steps ago. The Whittle index $\Pi_{i}(s,t)$ is a non-negative real numbers computed as follows: using the notation from Section 2.2., for any penalty per play $\lambda$, there is a single-arm policy $L_{i}(\lambda)$ that maximizes the average reward minus penalty (excess reward) $H_{i}(\lambda)$ over the infinite horizon. When $\lambda=\infty$, the optimal policy never plays; when $\lambda=0$, the optimal policy would play in any state. As $\lambda$ is decreased from $\infty$, at some value $\lambda^{*}$, the decision in state $(s,t)$ changes from “not play” to “play”. The Whittle index $\Pi_{i}(s,t)$ is precisely this value of $\lambda^{*}$. The Whittle index policy always plays the arm with the highest Whittle’s index (Fig. 5).

The Whittle index is strongly decomposable, i.e., can be computed separately for each arm. Further, we have defined $\lambda$ as a penalty (or amortized reward) per play, while Whittle defines it as a reward for not playing (which he terms the subsidy for passivity); it is easy to see that both these formulations are equivalent. Finally, for Feedback MAB, it can be shown that for any state $(s,t)$, there is a unique $\lambda\in(-\infty,\infty)$ where the decision switches between “play” and “not play”, i.e., the decision is monotone in $\lambda$. Strictly speaking, the Whittle index is defined only for such systems (termed indexable by Whittle ); we will define this aspect away by insisting that the index $\lambda^{*}$ is the largest value where a switch happens.

We present an explicit connection of Whittle’s index to LPLagrange$(\lambda)$.

(Proved in Appendix A) Recall the notation $L_{i}(\lambda)$ and $\mathcal{P}_{i}(t)$ from Section 2.2. The following hold for $\Pi_{i}(s,t)$:

$\Pi_{i}(s,t)\geq 0$ for all states $(s,t)$ where $s\in\{g,b\}$ and $t\in\mathbf{Z}^{+}$.

$\Pi_{i}(g,1)=r_{i}(1-\beta_{i})$, and $\Pi_{i}(b,t)\leq\Pi_{i}(g,1)$ for all $t\geq 1$.

$\Pi_{i}(b,t)=\max\{\lambda|L_{i}(\lambda)=\mathcal{P}_{i}(t)\}$, and is a monotonically non-decreasing function of $t$.

Though Whittle’s index is widely used, it is not clear how to analyze it since it leads to complicated priorities between arms. We now show that our balancing technique also implies an analysis for a slight but non-trivial modification to Whittle’s index.

2 The Threshold-Whittle Policy

We now show that modifying the index slightly to exploit the myopic next step reward in good states $g$ yields a $2$ approximation. Note that the myopic next step reward of an arm $i$ in state $g$ is precisely $\Pi_{i}(g,1)=r_{i}(1-\beta_{i})$. The modification essentially favors exploiting such a “good” state if the myopic reward is at least a certain threshold value. In particular, we analyze the policy Threshold-Whittle$(\lambda)$ shown in Figure 6, where we set $\lambda=\lambda^{*}$, where $\lambda^{*}$ is the value where $\lambda^{*}=\sum_{i=1}^{n}H_{i}(\lambda^{*})$ (refer Section 2.3).

Note that the above policy can be restated as playing the arm with the highest modified index, which is computed as follows: For arm $i$, if $\Pi_{i}(g,1)=r_{i}(1-\beta_{i})\geq\lambda$, the modified index for state $(g,1)$ is $\infty$, else the modified index is the same as the Whittle index.

Threshold-Whittle$(\lambda^{*})$ is a $2$ approximation for Feedback MAB. Here, $\lambda^{*}$ satisfies $\lambda^{*}=\sum_{i=1}^{n}H_{i}(\lambda^{*})$ (refer Section 2.3).

3 Proof of Theorem 3.2

We now prove the above result by modifying our analysis of the BalancedIndex policy (from Figure 4). Recall that $S$ is the set of arms with $h_{i}>0$ in the optimal solution to Whittle-Dual$(\lambda^{*})$. For such arms, $t=t_{i}$ is the first time instant when $\lambda+th_{i}\geq p_{i}v_{it}$ is tight. For arm $i\in S$, state $(s,t)$ is good if $s=g$ and $t=1$; ready if $s=b$ and $t\geq t_{i}$; and bad otherwise. The index policy from Figure 4 favors good over ready states, and does not play any arm in bad states.

For any arm $i$, exactly one of the following is true for Whittle-Dual$(\lambda^{*})$ and LPLagrange$(\lambda^{*})$.

The constraint $\lambda^{*}+th_{i}\geq v_{it}p_{i}$ is first tight at $t=t_{i}$. Then, $\Pi_{i}(b,t_{i}-1)<\lambda^{*}$ and $\Pi_{i}(b,t_{i})\geq\lambda^{*}$. Further, $\Pi_{i}(g,1)=r_{i}(1-\beta_{i})\geq\lambda^{*}$ and $h_{i}>0$.

The constraint $\lambda^{*}+th_{i}\geq v_{it}p_{i}$ is not tight for any $t$. Then, $\Pi_{i}(b,t)\leq\lambda^{*}$ for all $t\geq 1$, and $h_{i}=0$.

The optimal solution to LPLagrange$(\lambda^{*})$ finds the policy $\mathcal{P}_{i}(t_{i})$ for every arm $i$ with $h_{i}>0$. Therefore, by Lemma 3.1, we must have $\Pi_{i}(b,t_{i})\geq\lambda^{*}$, and $\Pi_{i}(b,t)<\lambda^{*}$ for all $t<t_{i}$. Furthermore, since the variable $x^{i}_{bt}$ in the optimal solution to LPLagrange$(\lambda^{*})$ is first non-zero at $t=t_{i}$, this implies the constraint $\lambda^{*}+th_{i}\geq v_{it}p_{i}$ is first tight at $t=t_{i}$ by complementary slackness (Lemma 2.4). Further, if this constraint is tight at $t=t_{i}$, since $v_{it}$ is monotonically increasing, the constraint is feasible for all $t\geq t_{i}$ only if $h_{i}>0$. Finally, $\Pi_{i}(g,1)=r_{i}(1-\beta_{i})\geq\Pi_{i}(b,t_{i})\geq\lambda^{*}$ follows from Lemma 3.1.

Suppose now that $\lambda^{*}+th_{i}\geq v_{it}p_{i}$ is not tight for any $t\geq 1$. Then, by complementary slackness, we have $x^{i}_{bt}=0$ for all $t\geq 1$, which implies $x^{i}_{gt}=0$ for all $t\geq 1$. Therefore, the policy $L_{i}(\lambda^{*})$ never plays arm $i$. This implies $\Pi_{i}(b,t)\leq\lambda^{*}$ for all $t\geq 1$. Since the excess reward of $L_{i}(\lambda^{*})$ is zero, we have $h_{i}=0$. (This can also be shown by complementary slackness.) ∎

We next classify the arms as follows. In Claim 3.3, let the arms satisfying the first condition ($h_{i}>0$) of the Claim be denoted Type (1), and the remaining arms satisfying $h_{i}=0$ be denoted Type (2). Note that type (1) arms are precisely the set $S$ of arms in Fig. 4, so the BalancedIndex policy only plays type (1) arms.

We consider the behavior of Threshold-Whittle$(\lambda^{*})$ restricted to just these arms. Since $\Pi_{i}(b,t)$ is monotonically increasing in $t$, by Claim 3.3, we have the following for the policy of Fig. 4: If the arm is ready, the Whittle index is at least $\lambda^{*}$; if the arm is bad, the index is at most $\lambda^{*}$; and finally, if the arm is good, then the modified Whittle index is infinity.

Therefore, Threshold-Whittle$(\lambda^{*})$ confined to these arms gives priority to good over ready over bad arms. The only difference with the policy in Fig. 4 is that instead of idling when all arms are bad, the policy Threshold-Whittle$(\lambda^{*})$ will play some bad arm. We now show that this is better than idling.

Threshold-Whittle$(\lambda^{*})$ executed just over Type (1) arms yields reward at least $OPT/2$.

Consider the alternate analysis presented in Section 2.3.3. The Index policy from Fig. 4 does not play an arm $i$ in bad state, and achieves change in potential $\Delta\Phi$ of exactly $h_{i}$. All we need to show is that if the arm is played instead, the expected change in potential is still at least $h_{i}$. The rest of the proof is the same as that of Lemma 2.11. Suppose the arm is played after $t\geq 1$ steps. The expected change in potential is: $\mathbf{E}[\Delta\Phi_{t}]=v_{it}p_{i}-h_{i}(t-1)$. We further have by definition of $t_{i}$ that $\lambda+t_{i}h_{i}=v_{it_{i}}p_{i}$. We therefore have $p_{i}v_{it_{i}}\geq t_{i}h_{i}$. Since $v_{it}$ is a concave function of $t$ with $v_{i0}=0$, the above implies that for every $t\leq t_{i}$, we must have $p_{i}v_{it}\geq th_{i}$. Therefore, $\mathbf{E}[\Delta\Phi_{t}]=v_{it}p_{i}-h_{i}(t-1)\geq th_{i}-h_{i}(t-1)=h_{i}$. ∎

The only catch now is that Threshold-Whittle$(\lambda^{*})$ can sometimes play a type (2) arm whose $h_{i}=0$. For such arms, we count their reward and ignore the change in potential.

In Threshold-Whittle$(\lambda^{*})$, if a type (2) arm $j$ preempts the play of a type (1) arm $i$, either the reward from the former is at least $\lambda^{*}$ or the increase in potential of the later $\Delta\Phi$ is at least $h_{i}$.

Suppose that for type (2) arm $j$, $\Pi_{j}(g,1)=r_{j}(1-\beta_{j})\geq\lambda^{*}$. Denote such a state $(g,1)$ as nice, and a nice type (2) arm has modified index of $\infty$. When $j$ was last observed to be good, the arm can be played continuously even if type (1) arms become ready. However, for every time step such an event happens, the current reward of playing this nice type (2) arm is precisely $r_{j}(1-\beta_{j})$, which is at least $\lambda^{*}$, and the type (1) arms only get better from waiting. When the type (2) arm $j$ was last observed to be bad, preemption can only happen if all type (1) arms are bad, since the Whittle’s index of a type (2) arm $\Pi_{j}(b,\infty)<\lambda^{*}$. But in this case the increase in potential of arm $i$ is $h_{i}$.

Finally, if $\Pi_{j}(g,1)<\lambda^{*}$, then by Lemma 3.1, we have $\Pi_{j}(s,t)<\lambda^{*}$ for all $s=b,g$ and $t\geq 1$. This implies that such an arm in any state can only preempt type (1) arms that are bad; in that case, the potential $\Phi$ of the latter rises by $h_{i}$ by idling. This completes the proof. ∎

3.2 Completing the Proof of Theorem 3.2

To complete the analysis, there are two cases: First, if a nice type (2) arm, or a ready or good type (1) arm is played, then the above discussion implies that the reward plus change in potential ($\Delta\Phi$) of this arm is at least $\lambda^{*}\geq OPT/2$. In the other case, all type (1) arms are bad, and focusing on just these arms, each yields increase in potential for each arm is at least $h_{i}$, so that the total reward plus change in potential of these system is at least $\sum_{i}h_{i}\geq OPT/2$. This completes the proof, and shows that Threshold-Whittle$(\lambda^{*})$ is a $2$ approximation. We note that the above analysis extends easily to the variant where $M\geq 1$ arms are simultaneously played per step.

The General Technique: Monotone Bandits

In this section, we present a general and non-trivial sub-class of restless bandits for which a generalization of the above balancing technique yields a $2$-approximate index policy. We term this class Monotone bandits, and this captures both the stochastic MAB, as well as the Feedback MAB as special cases.

In Monotone bandits, there are $n$ bandit arms. Each arm $i$ can be in one of $K$ states denoted $\mathcal{S}_{i}=\{\sigma^{i}_{1},\sigma^{i}_{2},\ldots,\sigma^{i}_{K}\}$. When the arm is not played, its state remains the same and it does not fetch reward. Suppose the arm is in state $\sigma_{k}^{i}$ and is played next after $t\geq 1$ steps. Then, it gains reward $r_{k}^{i}\geq 0$, and transitions to one of the states $\sigma_{j}^{i}\neq\sigma_{k}^{i}$ w.p. $g^{i}(k,j,t)$, and with the remaining probability stays in state $\sigma^{i}_{k}$. (For notational convenience, we denote $\sigma^{i}_{k}$ simply as $k$; the arm it refers to will be clear from the context.) The transition probabilities for different arms are independent. At most one arm is played per step. The goal is to find a policy for playing the arms so that the infinite horizon time-average reward is maximized.

In addition, we have the following key properties about the transition probabilities:

We assume that $g^{i}(k,j,t)$ is of the form $f^{i}_{k}(t)q^{i}(k,j)$. The function $f^{i}_{k}(t)\in$ for positive integers $t$ can be thought of as an “escape probability” from the state $\sigma_{k}\in\mathcal{S}_{i}$. Conditioned of the escape, the state changes to $\sigma_{j}\in\mathcal{S}_{i}$ with probability $q^{i}(k,j)$, thus $\sum_{j\neq k}q^{i}(k,j)\leq 1$.

For every arm $i$ and state $k\in\mathcal{S}_{i}$, we have: $f_{k}^{i}(t)\leq f_{k}^{i}(t+1)$ for every $t$.

The above properties are necessary in some sense: We show in Section 4.5 that when the monotone property is relaxed, the problem becomes $n^{\epsilon}$-hard to approximate. Further, if the separability property is not satisfied, then Whittle’s LP on which the analysis of this section is based, has $\Omega(n)$ gap.

Intuitively, Monotone bandit models optimization scenarios in which uncertainty increases: when an arm is just played and we observe its state, we are most certain that our observation still holds true the next time step. However, the non-decreasing nature of $f$ implies that as time goes on, the “escape probability” increases and the previous observation becomes less and less reliable. This serves as a model for certain POMDPs, such as the Feedback MAB.

Observe that the Monotone bandits generalizes the Feedback MAB. For the states $\mathcal{S}_{i}=\{g,b\}$, set $q^{i}(g,b)=q^{i}(b,g)=1$ and $f^{i}_{g}(t)=1-u_{it}$ and $f^{i}_{b}(t)=v_{it}$. Recall from Fact 2.2 that $u_{it},v_{it}$ are respectively the probabilities of observing the state $g$ when the state last observed $t$ steps ago was $g$ and $b$, and that $1-u_{it},v_{it}$ are both monotonically increasing. We also note that Monotone bandits generalizes the stochastic MAB by setting $f^{i}_{k}(t)=1$ for all $t$.

1 High Level Idea

Unlike the Feedback MAB problem, in Monotone bandits, there is no longer a clear distinction between “good” and “bad” states. Note however that an equivalent way of finding $\lambda$ such that $\lambda=\sum_{i=1}^{n}H_{i}(\lambda)$ is to treat $\lambda$ as a variable and enforce $\lambda=\sum_{i=1}^{n}h_{i}$ as a constraint in the dual of Whittle’s LP. By taking this approach, the variables $p^{i}_{k}$ (now one for each state $k\in\mathcal{S}_{i}$) can be interpreted as dual potentials, and the dual constraints are in terms of the expected potential change of playing in state $k\in\mathcal{S}_{i}$. Based on the sign of this potential change, we can classify the states into “good” and “bad” via complementary slackness. Our index policy continuously exploits arms in “good” states, and waits until the dual constraint goes tight (i.e., the arm becomes “ready”) before playing in “bad” states. We formalize the previous potential-based argument using a Lyapunov function and show a $2$-approximation. We note that the LP-duality approach is entirely equivalent to the Lagrangean approach; however, it leads to a different interpretation of variables which is more generalizable.

For simplicity of the exposition, we assume the monotone functions in this section are piece-wise linear with poly-size specification – see definition 5 for a formal definition. As shown in the previous section, these results do extend to a wider class of differentiable functions, such as those in Feedback MAB.

We also assume that for each arm $i$, the graph, where the vertices are $k\in\mathcal{S}_{i}$ and a directed edge $(j,k)$ exists if $q^{i}(j,k)>0$, is strongly connected. Since we consider the infinite horizon time average reward, assume that the policy is ergodic and can choose the start state of each arm. These assumptions do not simplify the problem, as it remains NP-Hard (see Section 4.5).

2 Whittle’s LP and its Dual

As with Feedback MAB, for each arm $i$ and $k\in\mathcal{S}_{i}$, we have variables $\{x^{i}_{kt},t\geq 1\}$. These variables capture the probabilities (in the execution of the optimal policy) of the event: Arm $i$ is in state $k$, was last played $t$ steps ago, and is played at the current step. These quantities are well-defined for ergodic policies. Whittle’s LP is presented in Figure 7. Let its optimal value be denoted $OPT$. The LP effectively encodes the constraints on the evolution of the state of each arm separately, connecting them only by the constraint that at most one arm is played in expectation every step. The first constraint simply states that the at any step, at most one arm is played; the second constraint encodes that each arm can be in at most one possible state at any time step; and the final constraint encodes that the rate of entering state $k\in\mathcal{S}_{i}$ is the same as the rate of exiting this state. This LP will clearly be a relaxation of the optimal policy; the details are the same as the proof of Lemma 2.3.

This LP has infinite size, and we will fix that aspect in this section. In particular, we now show that the LP has polynomial size when the $f^{i}_{k}$ are piece-wise linear with poly-size specification.

Given $i$, $k\in S_{i}$, $f^{i}_{k}(t)$ is specified as the piece-wise linear function that passes through breakpoints $(t_{1}=1,f^{i}_{k}(1)),(t_{2},f^{i}_{k}(t_{2})),\ldots,(t_{m},f^{i}_{k}(t_{m}))$. Denote the set $\{t_{1},t_{2},\ldots,t_{m}\}$ as $\mathcal{W}^{i}_{k}$. Therefore, for two consecutive points $t_{1},t_{2}\in\mathcal{W}^{i}_{k}$ with $t_{1}<t_{2}$, the function $f^{i}_{k}$ is specified at $t_{1}$ and $t_{2}$. For $t\in(t_{1},t_{2})$, we have $f^{i}_{k}(t)=((t_{2}-t)f^{i}_{k}(t_{1})+(t-t_{1})f^{i}_{k}(t_{2}))/(t_{2}-t_{1})$. For $t\geq t_{m}$, we have $f^{i}_{k}(t)=f^{i}_{k}(t_{m})$. We assume that $\mathcal{W}^{i}_{k}$ has poly-size specification.