The Non-Bayesian Restless Multi-Armed Bandit: a Case of Near-Logarithmic Regret

Introduction

Multi-armed bandit (MAB) problems are fundamental tools for optimal decision making in dynamic, uncertain environments. In a multi-armed bandit problem, there are $N$ arms each generating stochastic rewards, and a player seeks a policy to activate $K\geq 1$ arms at each time in order to maximize the expected total reward obtained over multiple plays. MAB problems can be broadly classified as Bayesian (if player knows the statistical model/parameters of the reward process for each arm) or non-Bayesian (if the model for the reward process is a priori unknown to the user). In the case of non-Bayesian MAB problems, the objective is to design an arm selection policy that minimizes regret, defined as the gap between the expected reward that can be achieved by a genie that knows the parameters, and that obtained by the given policy. It is desirable to have a regret that grows as slowly as possible over time (if the regret is sub-linear, the average regret per slot tends to zero over time, and the policy achieves the maximum average reward that can be achieved under a known model).

A particularly challenging variant of these problems is the restless multi-armed bandit problem (RMAB) , in which the rewards on all arms evolve at each time as Markov chains. Even in the Baysian case, where the parameters of the Markov chains are known, this problem is difficult to solve, and has been proved to be PSPACE hard . One approach to this problem has been Whittle’s index, which is asymptotically optimal under certain regimes; however it does not always exist, and even when it does, it is not easy to compute. It is only in very recent work that non-trivial tractable classes of RMAB where Whittle’s index exists and is computable have been identified .

We consider in this work the even harder non-Bayesian RMAB, in which the parameters of the Markov chain are further assumed to be unknown a priori. Our main contribution in this work is a novel approach to this problem that is applicable whenever the corresponding Bayesian RMAB problem has the structure that the parameter space can be partitioned into a finite number of sets, for each of which there is a single optimal policy. Our approach essentially develops a meta-policy that treats these policies as arms in a different non-Bayesian multi-armed bandit problem for which a single arm selection policy is optimal for the genie, and tries to learn which policy from this finite set gives the best performance.

We demonstrate our approach on a practical problem pertaining to dynamic spectrum sensing. In this problem, we consider a scenario where a secondary user must select one of $N$ channels to sense at each time to maximize its expected reward from transmission opportunities. If the primary user occupancy on each channel is modeled to be an identical but independent Markov chain with unknown parameters, we obtain a non-Bayesian RMAB with the requisite structure. We develop an efficient new multi-channel cognitive sensing algorithm for unknown dynamic channels based on the above approach. We prove for $N=2,3$ that this algorithm achieves regret (the gap between the expected optimal reward obtained by a model-aware genie and that obtained by the given policy) that is bounded uniformly over time $n$ by a function that grows as $O(G(n)\cdot\log n)$, where $G(n)$ can be any arbitrarily slowly diverging non-decreasing sequence. This is the first non-Bayesian RMAB policy that achieves the maximum average reward defined by the optimal policy under a known model.

There are two parallel investigations on non-Bayesian RMAB problems given in , where a more general RMAB model is considered but under a much weaker definition of regret. Specifically, in , regret is defined with respect to the maximum reward that can be offered by a single arm/channel. Note that for RMAB with a known model, staying with the best arm is suboptimal. Thus, a sublinear regret under this definition does not imply the maximum average reward, and the deviation from the maximum average reward can be arbitrarily large.

A New Approach for non-Bayesian RMAB

We first describe a structured class of finite-option Bayesian RMAB problems that we will refer to as $\Psi_{m}$. Let $\mathcal{B}(P)$ be a Bayesian RMAB problem with the Markovian evolution of arms described by the transition matrix $P$. We say that $\mathcal{B}(P)\in\Psi_{m}$ if and only if there exists a partition of the parameter values $P$ into a finite number of $m$ sets $\{S_{1},S_{2},...S_{m}\}$ and a set of policies $\pi_{i}$ $(\forall i=1\ldots m)$ that do not assume knowledge of $P$ and are optimal whenever $P\in S_{i}$. Despite the general hardness of the RMAB problem, problems with such structure do indeed exist, as has been shown in .

We propose a solution to the non-Bayesian version of the problem that leverages the finite solution option structure when we have that the corresponding Bayesian version $\mathcal{B}(P)\in\Psi_{m}$. In this case, although the player does not know the exact parameter $P$, it must be true that one of the $m$ policies $\pi_{i}$ will yield the highest expected reward (corresponding to the set $S_{i}$ that contains the true, unknown $P$). These policies can thus be treated as arms in a different non-Bayesian multi-armed bandit problem for which a single-arm selection policy is optimal for the genie. Then, a suitable meta-policy that sequentially operates these policies while trying to minimize regret can be adopted. This can be done with an algorithm based on the well-known schemes proposed by Lai and Robbins , and Auer et al .

One subtle issue that must be handled in adopting such an algorithm as a meta-policy is how long to play each policy. An ideal constant length of play could be determined only with knowledge of the underlying unknown parameters $P$, so our approach is to have the duration for which each policy is operated slowly increase over time.

In the following, we demonstrate this novel meta-policy approach to the dynamic spectrum access problem discussed in where the Bayesian version of the RMAB has been shown to belong to the class $\Psi_{2}$. For this problem, we show that our approach yields an algorithm with provably near-logarithmic regret, thus achieving the same average reward offered by the optimal RMAB policy under a known model.

A Dynamic Spectrum Access Problem

We consider a slotted system where a secondary user is trying to access $N$ independent channels, with the availability of each channel evolving as a two-state Markov chain with identical transition matrix $\mathbf{P}$ that is a priori unknown to the user. The user can only see the state of the sensed channel. If the user selects channel $i$ at time $t$, and upon sensing finds the state of the channel $S_{i}(t)$ to be 1, it receives a unit reward for transmitting. If it instead finds the channel to be busy, i.e., $S_{i}(t)=0$, it gets no reward at that time. The user aims to maximize its expected total reward (throughput) over some time horizon by choosing judiciously a sensing policy that governs the channel selection in each slot. We are interested in designing policies that perform well with respect to regret, which is defined as the difference between the expected reward that could be obtained using the omniscient policy $\pi^{*}$ that knows the transition matrix $\mathbf{P}$, and that obtained by the given policy $\pi$. The regret at time $n$ can be expressed as:

where $\omega_{i}$ is the initial probability that $S_{i}(1)=1$, $\mathbf{P}$ is the transition matrix of each channel, $Y_{\pi^{*}}(\mathbf{P},\Omega(1),t)]$ is the reward obtained in time $t$ with the optimal policy, $Y_{\pi}(\mathbf{P},\Omega(1),t)$ is the reward obtained in time $t$ with the given policy. We denote $\Omega(t)\triangleq[\omega_{1}(t),\ldots,\omega_{N}(t)]$ as the belief vector where $\omega_{i}(t)$ is the conditional probability that $S_{i}(t)=1$ (and let $\Omega(1)=[\omega_{1}(1),\ldots,\omega_{N}(1)]$ denote the initial belief vector used in myopic sensing algorithm ).

Sensing Unknown Dynamic Channels

As has been shown in , the myopic policy has a simple structure for switching between channels that depends only on the correlation sign of the transition matrix $\mathbf{P}$, i.e. whether $p_{11}\geq p_{01}$ (positively correlated) or $p_{11}<p_{01}$ (negatively correlated).

In particular, if the channel is positively correlated, then the myopic policy corresponds to

Policy $\pi_{1}$: stay on a channel whenever it shows a “1” and switch on a “0” to the channel visited the longest ago.

If the channel is negatively correlated, then it corresponds to

Policy $\pi_{2}$: staying on a channel when it shows a “0”, and switching as soon as “1” is observed, to either the channel most recently visited among those visited an even number of steps before, or if there are no such channels, to the one visited the longest ago.

Furthermore, it has been shown in that the myopic policy is optimal for $N=2,3$, and for any $N$ in the case of positively correlated channels (the optimality of the myopic policy for $N>3$ negatively correlated channels is conjectured for the infinite-horizon case). As a consequence, this special class of RMAB has the required finite dependence on its model as described in Sec. 2; specifically, it belongs to $\Psi_{2}$. We can thus apply the general approach based on the concept of meta-policy. Specifically, the algorithm treats these two policies as arms in a classic non-Bayesian multi-armed bandit problem, with the goal of learning which one gives the higher reward.

A key question is how long to operate each arm at each step. It turns out from the analysis we present in the next section that it is desirable to slowly increase the duration of each step using any (arbitrarily slowly) divergent non-decreasing sequence of positive integers $\{K_{n}\}_{n=1}^{\infty}$.

The channel sensing policy we thus construct is shown in Algorithm 1.

Regret Analysis

We first define the discrete function $G(n)$ which represents the value of $K_{i}$ at the $n^{th}$ time step in Algorithm 1:

Note that since $K_{i}$ can be any arbitrarily slow non-decreasing diverging sequence $G(n)$ can also grow arbitrarily slowly.

The following theorem states that the regret of our algorithm grows close to logarithmically with time.

For the dynamic spectrum access problem with $N=2,3$ i.i.d. channels with unknown transition matrix $\mathbf{P}$, the expected regret with Algorithm 1 after $n$ time steps is at most $Z_{1}G(n)\ln(n)+Z_{2}\ln(n)+Z_{3}G(n)+Z_{4}$, where $Z_{1},Z_{2},Z_{3},Z_{4}$ are constants only related to $\mathbf{P}$.

The proof of Theorem 1, presented in the appendix, uses two interesting lemmas we have developed that we present here without proof. The first lemma is a non-trivial variant of the Chernoff-Hoeffding bound, that allows for bounded differences between the conditional expectations of sequence of random variables that are revealed sequentially:

Let $X_{1},\cdots,X_{n}$ be random variables with range $[0,b]$ and such that $|E[X_{t}|X_{1},\cdots,X_{t-1}]-\mu|\leq C$. $C$ is a constant number such that $0<C<\mu$. Let $S_{n}=X_{1}+\cdots+X_{n}$. Then for all $a\geq 0$,

The second lemma states that the expected loss of reward for either policy due to starting with an arbitrary initial belief vector compared to the reward $U_{i}(P)$ that would obtained by playing the policy at steady state is bounded by a constant $C_{i}(P)$ that depends only on the policy used and the transition matrix. These constants can be calculated explicitly, but we omit the details for brevity.

For any initial belief vector $\Omega(1)$ and any positive integer $L$, if we use policy $\pi_{i}$ ($i=1,2$) for $L$ times, and the summed expectation of the rewards for these $L$ steps is denoted as $E^{\pi_{i}}[\Sigma_{t=1}^{L}Y^{\pi_{i}}(\mathbf{P},\Omega(1),t)]$, then

Remark: Theorem 1 has been stated for the cases $N=2,3$, which are the only cases when the Myopic policy has been proved to be optimal for the known-parameter case for all values of $P$. In fact, our proof shows something even stronger than this: that Algorithm 1 yields the claimed near-logarithmic regret with respect to the Myopic policy for any $N$. The Myopic policy is known to be always optimal for $N=2,3$, and for any $N$ so long as the Markov chain is positively correlated. In case it is negatively correlated, it is an open question whether it is optimal for an infinite horizon case. If this were to be true, the algorithm we have presented would also offer near-logarithmic regret asymptotically as the time variable $n$ increases, for any $N$.

References

Appendix

We first derive a bound on the regret for the case when $p_{01}<p_{11}$. In this case, policy $\pi_{1}$ would be the optimal. Based on Lemma 2, the difference of $E^{\pi_{1}}[\Sigma_{t=1}^{n}Y^{\pi_{1}}(\mathbf{P},\Omega(1),t)]$ and $U_{1}\cdot n$ is no more than $C_{1}$, therefore we only need to prove $R^{\prime}(\mathbf{P},\Omega(1),n)$, the regret in the case when policy $\pi_{1}$ is optimal, which is defined as $R^{\prime}(\mathbf{P},\Omega(1),n)\triangleq U_{1}\cdot n-E^{\pi_{1}}[\Sigma_{t=1}^{n}Y_{\pi_{1}}(\mathbf{P},\Omega(1),t)]$, is at most $Z_{1}G(n)\ln(n)+Z_{2}\ln(n)+Z_{3}G(n)+Z_{4}$, $Z_{1},Z_{2},Z_{3},Z_{4}$ are constants only related to $\mathbf{P}$.

The regret comes from two parts: the regret when using policy $\pi_{2}$; the regret between $U_{1}$ and $E^{\pi_{1}}[Y_{\pi_{1}}(\mathbf{P},\Omega(1),t)]$ when using policy $\pi_{1}$. From Lemma 2, we know that each time when we switch from policy $\pi_{2}$ to policy $\pi_{1}$, at most we lose a constant-level value from the second part. So if the number of selections of policy $\pi_{2}$ in Line 9 of Algorithm 1 is bounded by $O(\ln{n})$, both parts of the regret can be bounded by $O(G(n)\cdot\ln{n})$.

For ease of exposition, we discuss the slots $n$ such that $G||n$ , where $G||n$ denotes that time $n$ is the end of successive $G(n)$ plays.

We define $q$ as the smallest index such that $K_{q}\geq\lceil\frac{C_{1}+C_{2}}{|U_{1}-U_{2}|}\rceil$. Note that it is possible to define $\alpha(U_{1},C_{1},\mathbf{P})$ such that if policy $\pi_{1}$ is played $s_{1}>\alpha$ times,

We could also define $\beta(U_{2},C_{2},\mathbf{P})$ such that if policy $\pi_{2}$ is played $s_{2}>\beta$ times,

Moreover, there exists $\gamma=\lceil\max\{{5\alpha+1,e^{4\alpha/3},5\beta+1,e^{4\beta/3}}\}\rceil$ such that when $G(n)>K_{\gamma}$, policy $\pi_{1}$ is played at least $\alpha$ times and policy $\pi_{2}$ is played at least $\beta$ times.

Denote $T(n)$ as the number of times we select policy $\pi_{2}$ up to time $n$. Then, for any positive integer $l$, we have:

The condition $\{\frac{\hat{X}_{1,s_{1}}}{s_{1}}+\sqrt{\frac{3\ln{t}}{s_{1}}}\leq\frac{\hat{X}_{2,s_{2}}}{s_{2}}+\sqrt{\frac{3\ln{t}}{s_{2}}}\}$ implies that at least one of the following must hold:

Note that $\hat{X}_{1,s_{1}}=\hat{A}_{1,1}+\hat{A}_{1,2}+\cdots+\hat{A}_{1,s_{1}}$, where $\hat{A}_{1,i}$ is sample average reward for the $i_{th}$ time selecting policy $\pi_{1}$. Due to the definition of $\alpha$ and $K_{q}$, the expected value of $\hat{A}_{1,i}$ is between $U_{1}-\frac{C_{1}}{K_{q}}$ and $U_{1}+\frac{C_{1}}{K_{q}}$ if $i\geq q$ (Lemma 2). Then applying Lemma 1, and the results in (6) and (7),

For $\lambda(n)=\lceil(3(1+\frac{U_{2}+C_{2}/K_{q}}{U_{2}-C_{2}/K_{q}})^{2}\ln{n})/(U_{1}-U_{2}-\frac{C_{1}+C_{2}}{K_{q}})^{2}\rceil$, (11) is false. So we get:

This concludes the bound in case $p_{11}>p_{01}$. The derivation of the bound is similar for the case when $p_{11}\leq p_{01}$ with the key difference of $\gamma^{\prime}$ instead of $\gamma$, and the $C_{1},U_{1}$ terms being replaced by $C_{2},U_{2}$ and vice versa. Then we have that the regret in either case has the following bound:

This inequality can be readily translated to the simplified form of the bound given in the statement of Theorem 1, where: