Low-Complexity Algorithm for Restless Bandits with Imperfect Observations

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

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

where $A(t)\subset\{1,2,\ldots,N\}$ is the set of arms chosen at time $t$ with $|A(t)|=M$, $S_{n}(t)$ and $O_{n}(t)$ are respectively the state and observation from arm $n$ at time $t$ if $n\in A(t)$, $\mathop{\text{ACK}}_{n}(t)$ the acknowledgement of successful utilization of arm $n$ for slot $t$, $\mathcal{T}_{n}(\cdot)$ the one-step belief update operator without observation, and $\textbf{P}^{(n)}=\{p^{(n)}_{ij},{i,j\in\{0,1\}}\}$ the transition matrix of the internal Markov chain of arm $n$. Note that when $\epsilon=0$, all three expressions of the next belief state in (4) become linear functions and the problem is reduced to that in Liu and Zhao (2010) for perfect observations where the value functions for dynamic programming can be directly solved in closed-form. Later, we will see that when $\epsilon\neq 0$, the value functions are very difficult to analyze except for a few general properties. Without a fine-grain analysis on the value functions, the indexability and Whittle index cannot be established for our model. Our approach is to start with a finite time horizon and then utilize the backward induction (on time horizon) methodology until we take limits of corresponding functions as the time horizon goes to infinity. The key idea is to obtain analytic bounds on the value functions and their derivatives as functions of the system parameters instead of just numerical computations of these functions. We will show that these bounds, together with some detailed properties of the value functions, are sufficient for our purpose. From (5), the $k$-step belief update of an unobserved arm for $k$ consecutive slots starting from any belief state $\omega$ is

For simplicity of notations, we denote $\mathcal{T}_{n}^{1}(\cdot)$ by $\mathcal{T}_{n}(\cdot)$.
       At time $t=1$, the initial belief state $\omega_{n}(1)$ of arm $n$ can be set as the stationary distribution $\omega_{n,o}$ of the internal Markov chain^***Here we assume the internal Markov chain with transition matrix $\textbf{P}^{(n)}$ is irreducible and aperiodic.:

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

Now the decision problem has a countable state space as modelled by the belief vector for a fixed initial $\boldsymbol{\omega}(1)$ and an uncountable state space for an arbitrarily chosen $\boldsymbol{\omega}(1)$. It is clear that fixing $\boldsymbol{\omega}(1)$, the action-dependent belief vector $\boldsymbol{\omega}(t)$ takes possible values growing geometrically with time $t$, leading to a high-complexity in solving the problem; this is the so-called curse of dimensionality. In the following, we adopt Whittle’s original idea of Lagrangian relaxation to decouple arms for an index policy and show some crucial properties of the value functions of a single arm.

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

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

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

where $V_{\beta,m}(\omega;u=1)$ and $V_{\beta,m}(\omega;u=0)$ denote, respectively, the maximum expected total discounted reward that can be obtained if the arm is activated or made passive at the current belief state $\omega$, followed by an optimal policy in subsequent slots. Since we consider the infinite-horizon problem, a stationary optimal policy can be chosen and the time index $t$ is not needed in (14). Define the nonlinear operator $\phi(\cdot)$ as

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

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

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

Notice that the immediate reward under the active action cannot exceed $1$ so it is optimal to always make the arm passive if the immediate reward under the passive action exceeds $1$ ($m\geq 1$). This is because we would obtain the maximum immediate reward equal to $m$ at each time step regardless of the state transitions in this case. On the other hand, if $m<-1/{(1-\beta)}$ then the optimal action must be to activate the arm. To see this, note that the total discounted reward by any policy consists of two parts: the reward under the active actions and the reward under the passive actions. If the optimal policy is to make the arm passive now when $m<-1/{(1-\beta)}$, then the reward obtained under the future active actions by this policy must be greater than $1/{(1-\beta)}$ otherwise the total discounted reward would be negative, contradicting the optimality of the policy since any policy that always activates the arm achieves a nonnegative total discounted reward so should the optimal policy. This is again a contradiction since the total discounted reward under the active actions is upper bounded by $1/{(1-\beta)}$. Consequently, the passive set $P(m)$ changes from the empty set to the closed interval $[0,1]$ as $m$ increases from $-\infty$ to $\infty$. However, such change may not be monotonic as $m$ increases. But if $P(m)$ does increase monotonically with $m$, then for each value $\omega$ of the belief state, one can define the unique $m$ that makes it join $P(m)$ and stay in the set forever. Intuitively, such $m$ measures in a well-ordered manner the attractiveness of activating the arm in belief state $\omega$ compared to other belief states: the larger is the $m$ that is required for it to be passive, the more is the incentive to activate the arm in belief state $\omega$, even in the problem without $m$. This Lagrangian multiplier $m$ is thus called ‘subsidy for passivity’ by Whittle who formalized the following definition of indexability and Whittle index (Whittle, 1988).

For our model in which the arm state is given by the belief vector, the indexability is equivalent to the following:

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

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

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

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

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

is piecewise linear and convex since the leading coefficient $(1-(1-\epsilon)\omega)$ also appears as the denominator of the argument of the linear operator $\mathcal{T}$ in $V_{1,T-1,\beta,m}(\cdot)$ assumed to be piecewise linear and convex by the induction hypothesis. Henceforth, the recursive equation set (25) and (26) shows that $V_{1,T,\beta,m}(\omega)$ is the maximum of two convex and piecewise linear functions and thus piecewise linear and convex for any $T>1$ (in both $\omega$ and $m$). Motivated by the Lipschitz continuity of $\mathcal{T}\circ\phi$, we show in Lemma 2 that $V_{1,T,\beta,m}(\omega)$ is also Lipschitz continuous under certain conditions. In the following, we first establish a monotonic property of $V_{1,T,\beta,m}(\omega)$ in the case of $p_{11}>p_{01}$ (positively correlated Markov chain).

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

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