Two families of indexable partially observable restless bandits and Whittle index computation¹¹1This research was funded in part by Fonds de Recherche du Quebec-Nature et technologies (FRQNT).

We use uppercase letters to denote random variables; the corresponding lowercase letter to denote their realization and corresponding calligraphic letters to denote the set of realizations. Superscripts index arms and subscripts index time, e.g., $X^{i}_{t}$ denotes the state of arm $i$ at time $t$. The subscript $0{:}t$ denote the history of the variable from time $0$ to $t$, e.g., $X^{i}_{0:t}$ denotes $(X_{0},\ldots,X_{t})$. Bold letters denote the vector of variable for all arms, e.g., ${\boldsymbol{X}}_{t}$ denotes $(X^{1}_{t},\ldots,X^{n}_{t})$. Given a collection of real numbers $p^{1},\ldots,p^{n}$, we use $\prod_{i=1}^{n}p^{i}$ to denote their product $p^{1}\cdot p^{2}\cdot\dots\cdot p^{n}$. Given a collection of sets ${\cal X}^{1},\dots,{\cal X}^{n}$, we use $\prod_{i=1}^{n}{\cal X}^{i}$ to denote their Cartesian product ${\cal X}^{1}\times{\cal X}^{2}\times\dots\times{\cal X}^{n}$. For a finite set ${\cal X}$, ${\cal P}({\cal X})$ denote the set of probability mass functions (PMFs) on ${\cal X}$.

We use $\mathds{I}$ as the indicator function, $\mathds{E}$ as the expectation operator, $\mathds{P}$ as the probability function, $\mathds{R}$ as the set of real numbers, $\mathds{Z}$ as the set of integers and $\mathds{Z}_{\geq m}$ as the set of integers that are not lower than $m$.

Given ordered sets $\mathcal{X}$ and $\mathcal{Y}$, a function $f:\mathcal{X}\times\mathcal{Y}\to\mathds{R}$ is called submodular if for any $x_{1},x_{2}\in\mathcal{X}$ and $y_{1},y_{2}\in\mathcal{Y}$ such that $x_{2}\geq x_{1}$ and $y_{2}\geq y_{1}$, we have $f(x_{1},y_{2})-f(x_{1},y_{1})\geq f(x_{2},y_{2})-f(x_{2},y_{1})$. Furthermore, the transition probability matrix $P$ is stochastic monotone if for any $x,y\in\mathcal{X}$ such that $x<y$, we have $\sum_{w\in\mathcal{X}_{\geq z}}P_{xw}\leq\sum_{w\in\mathcal{X}_{\geq z}}P_{yw}$ for any $z\in\mathcal{X}$. For any function $f\colon\mathcal{Z}\to\mathbb{R}$, $\operatorname{span}(f)$ denotes the span semi-norm of $f$, i.e., $\operatorname{span}(f)=\sup_{z\in\mathcal{Z}}f(z)-\inf_{z\in\mathcal{Z}}f(z).$

A discrete-time restless bandit process (or arm) is a controlled Markov process $(\mathcal{X},\{0,1\},\allowbreak\{\bar{P}(a)\}_{a\in\{0,1\}},c,\pi_{0},\mathcal{Y})$ where $\mathcal{X}$ denotes the finite set of states; $\{0,1\}$ denotes the action space where the action $0$ is called the passive action and the action $1$ is the active action; $\bar{P}(a)$, $a\in\{0,1\}$, denotes the transition matrix when action $a$ is chosen; $c:\mathcal{X}\times\{0,1\}\to\mathbb{R}_{\geq 0}$ denotes the cost function; $\pi_{0}$ denotes the initial state distribution; $\mathcal{Y}$ denotes the finite set of observations.

For models which satisfy Assumption $1$, we denote $\bar{P}(0)$ by $P$ and denote each (identical) row of $\bar{P}(1)$ by $Q$. The term restart property is used following the terminology of [26], where $Q$ was a PMF on the state space (i.e., on taking active action, the state resets according to PMF $Q$). Note [26] considered fully observed models, while we are considering partially observable setups.

An operator has to select $m<n$ arms at each time but does not observe the state of the arms. We consider two observation models.

• 1.

  Model A: In model A, the operator does not observe anything. We denote this by $Y_{t}=\mathfrak{E}$, where $\mathfrak{E}$ denotes a blank symbol.

• 2.

  Model B: In model B, the operator observes the state of the arm after it has been reset, i.e.,

  $$Y_{t+1}=\begin{cases}\mathfrak{E}\leavevmode\nobreak\ &\text{ if }\leavevmode\nobreak\ A_{t}=0\\ X_{t+1}\leavevmode\nobreak\ &\text{ if }\leavevmode\nobreak\ A_{t}=1\end{cases},$$

  (1)

For model A, $\mathcal{Y}=\{\mathfrak{E}\}$ and for model B, $\mathcal{Y}={\cal X}\cup\{\mathfrak{E}\}$.

A partially-observable restless multi-armed bandit (PO-RMAB) problem is a collection of $n$ independent restless bandits $(\mathcal{X}^{i},\{0,1\},\allowbreak\{P^{i}(a)\}_{a\in\{0,1\}},c^{i},\pi^{i}_{0},{\mathcal{Y}}^{i})$, $i\in{\cal N}\coloneqq\{1,\ldots,n\}$.

Let $\boldsymbol{\mathcal{X}}\coloneqq\prod_{i\in{\cal N}}{\mathcal{X}}^{i}$, ${\mathbfcal A}(m)\coloneqq\biggl{\{}(a^{1},\ldots,a^{n})\in\{0,1\}^{n}:\sum_{i\in{\cal N}}a^{i}=m\biggr{\}}$, and $\boldsymbol{\mathcal{Y}}\coloneqq\prod_{i\in{\cal N}}{\mathcal{Y}}^{i}$ denote the combined state, action, and observation spaces, respectively. Also, let $\boldsymbol{X}_{t}=(X^{1}_{t},\dots X^{n}_{t})\in\boldsymbol{\mathcal{X}}$, $\boldsymbol{A}_{t}=(A^{1}_{t},\dots,A^{n}_{t})\in{\mathbfcal A}(m)$, and $\boldsymbol{Y}_{t}=(Y^{1}_{t},\dots Y^{n}_{t})\in\boldsymbol{\mathcal{Y}}$ denote the combined states, actions taken, and observations made by the operator at time $t\geq 0$. Due to the independent evolution of each arm, for each realization ${\boldsymbol{x}}_{0:t}$ of ${\boldsymbol{X}}_{0:t}$ and ${\boldsymbol{a}}_{0:t}$ of ${\boldsymbol{A}}_{0:t}$, we have

Let ${\boldsymbol{\pi}}_{0}=\prod_{i\in{\cal N}}\pi^{i}_{0}$ denote the initial state distribution of all arms.

When the system is in state ${\boldsymbol{x}}_{t}$ and action ${\boldsymbol{a}}_{t}$ is taken, the system incurs a cost ${\boldsymbol{c}}({\boldsymbol{x}}_{t},{\boldsymbol{a}}_{t})\coloneqq\sum_{i\in{\cal N}}c^{i}(x^{i}_{t},a^{i}_{t}).$ The action at time $t$ is chosen according to

where ${\boldsymbol{g}}_{t}$ is a history-dependent policy at time $t$. Let ${\boldsymbol{g}}=(g_{1},g_{2},\ldots)$ denote the policy for infinite time horizon and let ${\mathbfcal G}$ denote the family of all such policies. Then, the performance of policy ${\boldsymbol{g}}$ is given by

where $\beta\in(0,1)$ denotes the discount factor.

Formally, the optimization problem of interest is as follows:

In this section, we present some examples corresponding to the model presented above.

Using standard results from Markov decision theory, the partially observable restless bandit problem can be converted to a fully observable restless bandit problem with belief (or posterior distribution) as states. We present the details in this section. Let define the operator’s belief $\Pi^{i}_{t}\in\mathcal{P}({\cal X}^{i})$ on the state of arm $i$ at time $t$ as follows: for any, $x^{i}_{t}\in{\cal X}^{i}$, let $\Pi^{i}_{t}(x^{i}_{t})\coloneqq\mathds{P}(X^{i}_{t}=x^{i}_{t}\,|\,Y^{i}_{0:t-1},A^{i}_{0:t-1}).$ Note that $\Pi^{i}_{t}$ is a distribution-valued random variable. Also, define $\boldsymbol{\Pi}_{t}\coloneqq(\Pi^{1}_{t},\dots,\Pi^{n}_{t})$.

Then, for arm $i$, the evolution of the belief state is as follows: for model A, the belief update rule is

and for model B, the belief update rule is

where $\delta_{x}$ is the Dirac delta distribution over the discrete state space ${\cal X}$ with the value of one only for state $x$. The per-step cost function of the belief state $\Pi^{i}_{t}$ when action $A^{i}_{t}$ is taken is

Define the combined belief state $\Theta_{t}\in\mathcal{P}(\boldsymbol{\cal X})$ of the system as follows: for any $\boldsymbol{x}\in\boldsymbol{\cal X}$,

Note that $\Theta_{t}$ is a random variable that takes values in $\mathcal{P}(\boldsymbol{\cal X})$. Using standard results in POMDPs [39], we have the following.

Next, we present our first simplification for the structure of optimal decision policy as follows.

In Propositions 1 and 2, we do not present the dynamic programs because they suffer from the curse of dimensionality. In particular, obtaining the optimal policy for PO-RMAB is PSPACE-hard [16]. So, we focus on the Whittle index heuristics to solve the problem.

For models A and B, define ${\cal R}_{A}=\bigl{\{}QP^{k}:k\in\mathds{Z}_{\geq 0}\bigr{\}},\leavevmode\nobreak\ {\cal R}_{B}=\bigl{\{}\delta_{s}P^{k}:s\in{\cal X},k\in\mathds{Z}_{\geq 0}\bigr{\}}.$

For model A, define a process $\{K_{t}\}_{t\geq 0}$ as follows. The initial state $k_{0}$ is such that $\pi_{0}=QP^{k_{0}}$ and for $t>0$, $K_{t}$ is given by

Similarly, for model B, define a process $\{S_{t},K_{t}\}_{t\geq 0}$ as follows. The initial state $(s_{0},k_{0})$ is such that $\pi_{0}=\delta_{s_{0}}P^{k_{0}}$ and for $t>0$, $K_{t}$ evolves according to (14) and $S_{t}$ evolves according to

Note that once the first observation has been taken in both models, $K_{t}$ denotes the time elapsed since the last observation of arm $i$ and, in addition in model B, $S_{t}$ denotes the last observed states of arm $i$. Let $\boldsymbol{S}_{t}\coloneqq(S^{1}_{t},\dots S^{n}_{t})$ and $\boldsymbol{K}_{t}\coloneqq(K^{1}_{t},\dots K^{n}_{t})$. The relation between the belief state $\Pi_{t}$ and variables $S_{t}$ and $K_{t}$ is characterized in the following lemma.

For model A, the expected per-step cost at time $t$ may be written as

Similarly, for model B, the expected per-step cost at time $t$ may be written as

We assume that the model satisfies the following condition.

Under Assumption 3, we derive structural properties of the optimal policies for models A and B. Then, we show how $J^{(g)}_{\lambda}$ can be decomposed and computed.

In the following theorem, we show that the optimal policy for model A has a threshold structure and the optimal policy for model B has a threshold structure with respect to the second dimension of the information state.

See Section 6 for the proof.

We use ${\boldsymbol{\theta}}^{B}$ to denote the vector $(\theta^{B}_{s})_{s\in{\cal X}}$.

We simplify the notation and denote the policy corresponding to thresholds $\theta^{A}$ and ${\boldsymbol{\theta}}^{B}$ by simply $\theta^{A}$ and $\boldsymbol{\theta}^{B}$ instead of $g^{(\theta^{A})}$ and $g^{(\boldsymbol{\theta}^{B})}$.