Regret Bounds for Thompson Sampling in Restless Bandit Problems

Young Hun Jung 1 Ambuj Tewari 1

Abstract
Restless bandit problems are instances of nonstationary multi-armed bandits. There are plentyof results from the optimization perspective,
which aims to efficiently find a near-optimal policy when system parameters are known, but thelearning perspective where the parameters are
unknown is rarely investigated. In this paper,
we analyze the performance of Thompson sampling in restless bandits with unknown parameters.
We consider a general policy√ map to define ourcompetitor and prove an Õ( T ) Bayesian regretbound. Our competitor is flexible enough to represent various benchmarks including the best fixedaction policy, the optimal policy, the Whittle index policy, or the myopic policy. The empiricalresults also support our theoretical findings.

1. Introduction
Restless bandits (Whittle, 1988) are a variant of multi-armed
bandit (MAB) problems (Robbins, 1952). Unlike the classical MABs, the arms have non-stationary reward distributions. Specifically, we will focus on the class of restlessbandits whose arms change their states based on Markov
chains. Restless bandits are also distinguished from rested
bandits where only the active arms evolve and the passive
arms remain frozen. We will assume that each arm changes
according to two different Markov chains depending onwhether it is played or not. Because of their extra complexity, restless bandits can model more practical problems suchas dynamic channel access (Liu et al., 2011; 2013) or online
recommendation system (Meshram et al., 2017).
Due to the arms’ non-stationary nature, playing the same setof arms for every round usually does not produce the optimal
performance. This makes the optimal policy highly nontrivial, and Papadimitriou & Tsitsiklis (1999) show that it
is generally PSPACE hard to identify the optimal policy for
1
Department of Statistics, University of Michigan, Ann Arbor, Michigan, USA. Correspondence to: Young Hun Jung<yhjung@umich.edu>, Ambuj Tewari <tewaria@umich.edu>.

Real-world Sequential Decision Making workshop at ICML 2019.
Copyright 2019 by the author(s).

restless bandits. As a consequence, many researchers havebeen devoted to find an efficient way to approximate theoptimal policy (Liu & Zhao, 2010; Meshram et al., 2018).
This line of work primarily focuses on the optimization
perspective in that the system parameters are already known.
Since the true system parameters are unavailable in manycases, the learning perspective for the restless bandits isnecessary. Due to the learner’s additional uncertainty, however, analyzing a learning algorithm in restless bandits issignificantly challenging. Liu et al. (2011; 2013) and Tekin& Liu (2012) prove O(log T ) bounds for confidence boundbased algorithms, but their competitor always selects a fixed
set of actions, which is known to be weak. Dai et al. (2011;2014) show O(log T ) bound against the optimal policy, but
their assumptions on the underlying√ model is very limited.
Ortner et al. (2012) prove Õ( T ) bound in the general
restless bandits, but their algorithm is infeasible in general.
On a different path, Osband et al. (2013) study Thompson
sampling in the fully observable Markov decision√process(MDP) and show the Bayesian regret bound of Õ( T ). Unfortunately, this result is not applicable in our setting as ours
is partially observable due to bandit feedback. Following
Ortner et al. (2012), it is possible to transform our setting to
the fully observable case, but then we end up having exponentially many states, which restrict the practical utility ofexisting results.
In this work, we analyze Thompson sampling in restless bandits where the system resets every episode of a fixed lengthand the rewards are binary. We directly tackle the partial
observability and achieve a meaningful regret bound, which
also matches the result in the classical MAB. We are not
the first to analyze Thompson sampling in restless bandits,and Meshram et al. (2016) study this type of algorithm aswell, but their regret analysis remains in the one-armed-casewith a fixed reward of not pulling the arm. They explicitly
mention that regret analysis of Thompson sampling in themulti-armed case is an interesting open question.

2. Problem Setting
We begin by introducing our setting. There are K arms, andthe algorithm selects N arms every round. We denote thelearner’s action at time t by a binary vector At ∈ {0, 1}KRegret Bounds for Thompson Sampling in Restless Bandit Problems

where ||At ||1 = N . We call the selected arms as active
and the rest as passive. We assume each arm k has binary
states, {0, 1}, which evolve as a Markov chain with transition matrix either Pkactive or Pkpassive , depending on whether
the learner pulled the arm or not.
At round t, pulling an arm k incurs a binary reward Xt,k ,which is the arm’s current state. As we are in the bandit
setting, the learner only observes the rewards of active arms,
which we denote by Xt,At , and does not observe the passivearms’ rewards nor their states. This feature makes our setting to be a partially observable Markov decision process, or
POMDP. We denote the history of the learner’s actions andrewards up to time t by Ht = (A1 , X1,A1 , · · · , At , Xt,At ).
We assume the system resets every episode of length L,
which is also known to the learner. This means that at
the beginning of each episode, the states of the arms are
drawn from an initial distribution. The entire time horizon isdenoted by T , and for simplicity, we assume it is a multipleof L, or T = mL.
2.1. Bayesian Regret and Competitor PolicyLet θ ∈ Θ denote the entire parameters of the system. It
includes transition matrices P active and P passive , and an initial
distribution of each arm’s state. The learner does not havethe knowledge of these parameters at the beginning.
In order to define a regret, we need a competitor policy, or abenchmark. We first define a class of deterministic policies
and policy mappings.
Definition 1. A deterministic policy π takes time index andhistory (t, Ht−1 ) as an input and outputs a fixed action
At = π(t, Ht−1 ). A deterministic policy mapping µ takes
system parameters θ as an input and outputs a deterministic
policy π = µ(θ).
We fix a deterministic policy mapping µ and let our algorithm compete against a deterministic policy π ? = µ(θ? ),where θ? represents the true system parameters, which areunknown to the learner.
We keep our competitor policy abstract mainly because weare in the non-stationary setting. Unlike the classical (stationary) MABs, pulling the same set of arms with the largest
expected rewards is not necessarily optimal. Moreover, it isin general PSPACE hard to compute the optimal policy whenθ? is given. Regarding these statements, we refer the readers
to the book by Gittins et al. (1989). As a consequence, researchers have identified conditions that the myopic policy
is optimal (Ahmad et al., 2009) or proven that an efficientindex-based policy has a reasonable performance against
the optimal policy (Liu & Zhao, 2010).
We observe that most of proposed policies including the
optimal policy, the myopic policy, or the index-based pol-icy are deterministic. Therefore, researchers can plug inwhatever competitor policy of their choice, and our regretbound will apply as long as the chosen policy mapping isdeterministic.
Before defining the regret, we introduce a value function
LXθ
Aj · Xj |H].
Vπ,i(H) = Eθ,π [
j=iThis is the expected reward of running a policy π from roundi to L where the system parameter is θ and the starting
history is H. Note that the competitor policy π ? obtains?
Vπθ? ,1 (∅) rewards per episode in expectation. Thus, theregret can be written as?

R(T ; θ? ) = mVπθ? ,1 (∅) − Eθ?

TX

At · Xt .

(1)

t=1

We are particularly interested in bounding the following
Bayesian regret,BR(T ) = Eθ? ∼Q R(T ; θ? ),where Q is a prior distribution over the set of system parameters Θ. The prior is assumed to be known to the learner.

3. Algorithm
Our algorithm is an instance of Thompson sampling, first
proposed by Thompson (1933). At the beginning of episodel, the algorithm draws system parameters θl from posterior
and plays πl = µ(θl ) throughout the episode. Once anepisode is over, it updates posterior based on additional
observations. Algorithm 1 describes the steps.
We want to point out that the history H fulfills two different
purposes. One is to update posterior Ql , and the other is
as an input to a policy π. For the latter, however, we don’t
need the entire history as the arms reset every episode. That
is why we set H0 = ∅ (step 6) and feed Ht−1 to πl (step 8).
Furthermore, as we assume that the arms evolve based on
Markov chains, the history Ht−1 can be summarized as(r1 , n1 , · · · , rK , nK ),(2)which means that the arm k is played nk rounds ago and rk
is the observed reward in that round. If an arm k is neverplayed in the episode, then nk becomes t and rk becomesthe expected reward from the initial distribution.

4. Regret BoundIn this section, we prove√ that the Bayesian regret of Algorithm 1 is at most Õ( T ). The following lemma decomposes the regret.

Regret Bounds for Thompson Sampling in Restless Bandit Problems

Algorithm 1 Thompson Sampling in Restless Bandits
1: Input prior Q, episode length L, policy mapping µ
2: Initialize posterior Q1 = Q, history H = ∅3: for episodes l = 1, · · · , m do
4:
Draw parameters θl ∼ Ql
5:Compute the policy πl = µ(θl )6:
Set H0 = ∅7:
for t = 1, · · · , L do
8:
Select N active arms At = πl (t, Ht−1 )9:Observe rewards Xt,At and update Ht
10:
end for11:
Append HL to H
12:
Update posterior distribution Ql+1 using H
13: end for

The second term can be written as?

Eθ? ,πl [(Vπθll,2 − Vπθl ,2 )(H1 )|H0 ],and we can repeat this L times to obtain the equation.
We also record the following technical result.
Lemma 4. Let ai , bi ∈ [0, 1] for i ∈ [k] and |ai − bi | ≤ ∆i .
Then we can showXYY|
axi i (1 − ai )1−xi −bxi i (1 − bi )1−xi |x∈{0,1}k

i

i

≤2

k
X

(3)
∆j .

j=1

Lemma 2. The Bayesian regret of Algorithm 1 can be decomposed as below
BR(T ) = Eθ? ∼Q

m
X

?

?

Eθl ∼Ql [Vπθ? ,1 (∅) − Vπθl ,1 (∅)]

Proof. Fix x. For simplicity, let ci = axi i (1 − ai )1−xi anddi = bxi i (1 − bi )1−xi . Since xi is either 0 or 1, we have|ci − di | = |ai − bi | ≤ ∆i . Then we write

l=1= Eθ? ∼Q

m
X?

Eθl ∼Ql [Vπθll,1 (∅) − Vπθl ,1 (∅)].

l=1

Eθ? ∼QkY
i=1

Proof. The first line is a simple rewriting of (1) based on Algorithm 1. Observe that given the history up to time (l−1)L,the distributions of θ? and θl are same as Ql . Furthermore,θthe mapping from θ to Vµ(θ),1(∅) is deterministic. Using
the observation by Russo & Van Roy (2014) and the tower
rule, we get
m
X

|

?

Eθl ∼Ql Vπθ? ,1 (∅) = Eθ? ∼Q

l=1

m
X

Eθl ∼Ql Vπθll,1 (∅),

ci −

k
Y

k−1
Y

di | ≤ (i=1ci )|ck − dk | + |

i=1
k−1
Y

≤(

k−1
Y

ci −

i=1

ci )∆k + |

i=1

k−1
Y

ci −

i=1

k−1
Y

k−1
Y

di |dki=1

di |dk

i=1

≤ ···
k j−1
k
X
Y
Y
≤
(
ci )∆j (di ).
j=1 i=1i=j+1

Summing the last term over x finishes the argument.

l=1

which leads to the second line of the lemma.

Now we are ready to prove our main theorem.

Next, we define the Bellman operator

Theorem 5. (Thompson Sampling, Regret Bound) The
Bayesian regret of Algorithm 1 satisfies the following boundTπθ V (Ht−1 ) = Eθ,π [At · Xt + V (Ht )|Ht−1 ].
θθIt is easy to check that Vπ,i
= Tπθ Vπ,i+1. The next lemma
further decomposes the regret.
Lemma 3. Fix θ? and θl , and let H0 = ∅. Then we have?

Vπθll,1 (H0 ) − Vπθl ,1 (H0 )= Eθ? ,πlL
X?

(Tπθll − Tπθl )Vπθll,t+1 (Ht−1 ).

p
BR(T ) = O( KL3 N 3 T log T ).
Remark. If the system is classical stationary MABs, then it
corresponds to the case
√ L = 1, N = 1, and our result reproduces the result of O( KT log T ) (Lattimore & Szepesvári,
2018, Chp. 36). Furthermore, when N > K
2 , we can thinkof the problem as choosing the passive arms, and the smaller
bound with N replaced by K − N would apply.

t=1
θθ
Proof. Using the relation Vπ,i
= Tπθ Vπ,i+1, we may write?

Vπθll,1 (H0 ) − Vπθl ,1 (H0 )?

Proof. We fix an episode l and analyze the regret in this
episode. Let tl = (l − 1)L so that the episode starts at time
tl + 1. Define?

= (Tπθll Vπθll,2 − Tπθl Vπθl ,2 )(H0 )?
?
?
= (Tπθll − Tπθl )Vπθll,2 (H0 ) + Tπθl (Vπθll,2 − Vπθl ,2 )(H0 ).

Nl (k, r, n) =

tl
X
t=1

1{At,k = 1, rk = r, nk = n}.

Regret Bounds for Thompson Sampling in Restless Bandit Problems

It counts the number of rounds where the arm k was chosen
by the learner with history rk = r and nk = n (see (2) for
definition). Note thatk ∈ [K], r ∈ {0, 1, ρ(k)}, and n ∈ [L],The above inequality holds whenever θ? , θl ∈ Θl . Whenθ? ∈/ Θl or θl ∈/ Θl , which happens with probability
less than 6δKL, then we have a trivial bound |Vπθll,1 (∅) −?
Vπθl ,1 (∅)| ≤ LN . Therefore, we can deduce?

where ρ(k) is the initial success rate of arm k. This implies
that there are 3KL possible tuples of (k, r, n).

|Vπθll,1 (∅) − Vπθl ,1 (∅)| ≤ 6δKL2 N+ 3LN 1(El )Eθ? ,πl

L X
N
X

∆i (tl + t),
Let ω θ (k, r, n) denote the conditional probability of Xk = 1
t=1 i=1
given a history (r, n) and system parameters θ. Also let
where El denotes the event θ? , θl ∈ Θl .
ω̂(k, r, n) denote the empirical mean of this quantity (using
Nl (k, r, n) past observations and set the estimate to 0 if
Combining this with Lemma 2 and Lemma 3, we getNl (k, r, n) = 0). Then definesBR(T ) ≤ 6δmKL2 N
2 log(1/δ)
m
L X
N
X
X
Θl = {θ | ∀k, r, n, |(ω̂−ω θ )(k, r, n)| <}.
(6)
1 ∨ Nl (k, r, n)?
?
+ Eθ ∼Q 3LN
1(El )Eθ ,πl∆i (tl + t).
Since ω̂(k, r, n) is Htl -measurable, so is this set. Using the
Hoeffding inequality, one can showP(θ? ∈/ Θl ) = P(θl ∈/ Θl ) ≤ 3δKL.

l=1

We further analyze the summation to finish the argument.
Recall that for this summation, we have θ? , θl ∈ Θl . We
shorten Nl (ki , rki , nki ) to Nl for simplicity. We have

We now turn our attention to the following Bellman operator

m X
L X
N
X

Tπθl Vπθll,t (Ht−1 ) = Eθ,πl [Atl +t · Xtl +t + Vπθll,t (Ht )|Ht−1 ].

l=1 t=1 i=1

≤

=

N
X

ωθ,i +i=1

X

Pxθ Vπθll,t (Ht−1 ∪ (Atl +t , x)),x∈{0,1}N(4)
QN
xi
where Pxθ = i=1 ωθ,i(1 − ωθ,i )1−xi . Under the event that?
θ , θl ∈ Θl , we haves
8 log(1/δ)|ωθl ,i − ωθ? ,i | < 1 ∧=: ∆i (tl + t),
1 ∨ Nl (ki , rki , nki )where the dependence on tl + t comes from the mappingfrom i to ki . Lemma 4 provides
Xx∈{0,1}N?

|Pxθl − Pxθ | ≤ 2

NX∆i (tl + t).

(5)?

|(Tπθl − Tπθll )Vπθll,t (Ht−1 )| ≤ (2LN + 1)

NX∆i (tl + t)

i=1

≤ 3LN

N
X
i=1

∆i (tl + t).

X(7)

where the second inequality holds because there are 3KL
possible tuples of (k, r, n) and a tuple can contribute at most
2L to the first summation.
We can bound the second term as follows
r
m X
L X
N
X
1
1{Nl > L}Nl
t=1 i=1
l=1

m X
X

r
1
=
1{Nl > L}(Nl+1 − Nl )Nl
l=1 (k,r,n)
s
m X
X
2
≤
(Nl+1 − Nl )Nl+1
l=1 (k,r,n)
√ X p
≤ 8
Nm+1 (k, r, n)i=1

θFrom (4), (5), and the fact that |Vπ,t| ≤ LN , we obtain?
given Ht−1 and the event θ , θl ∈ Θl ,∆i (tl + t)

1{Nl ≤ L} + ∆i 1{Nl > L}s
X
8 log(1/δ)
2≤ 6KL +
1{Nl > L},
Nl

Since πl is deterministic, so is Atl +t given Ht−1 and πl .
Let (k1 , . . . , kN ) be the active arms at time tl + t and writeω θ (ki , rki , nki ) = ωθ,i . Then we can rewrite
Tπθl Vπθll,t (Ht−1 )t=1 i=1≤√(8)(k,r,n)24KLN T .

For the first inequality, we use Nl+1 ≤ Nl + L ≤ 2Nl . The
second inequality holds due to the integral trick. Finally,
the last inequality holds P
by the Cauchy-Schwartz inequality
along with the fact that (k,r,n) Nm+1 (k, r, n) = N T .
Combining (6), (7), and (8), we getpBR(T ) = O(δKN LT +KL3 N + KL3 N 3 T log(1/δ)).

Regret Bounds for Thompson Sampling in Restless Bandit Problems

Figure 1. The Gilbert-Elliott channel model

Since N T is a trivial upper bound of BR(T ), we may ignore
the KL3 N term. Setting δ = T1 completes the proof.

5. Experiments
We empirically examine our model in a practical case.
5.1. Model Design
We particularly investigate the Gilbert-Elliott channel model,
which is studied by Liu & Zhao (2010) in a restless bandit
perspective. This model can be broadly used in communication systems such as cognitive radio networks, downlink
scheduling in cellular systems, opportunistic transmission
over fading channels, and resource-constrained jamming
and anti-jamming.
Each arm k has two parameters pk01 and pk11 , which determine the transition matrix. We assume P active = P passive andeach arm’s transition matrix is independent on the learner’s
action. There are only two states, good and bad, and thereward of playing an arm is 1 if its state is good and 0 otherwise. We assume the initial distribution of arm k follows
the stationary distribution. In other words, its initial state ispk
01
good with probability ωk = pk +1−p
k .
01

11

We fix K = 8, N = 3, L = 50, and m = 30. We use Monte
Carlo simulation with size 100 to approximate expectations.
As we assume K = 8 and each arm has two parameters,
there are 16 parameters. For these, we use the uniform priorover the support {0.1, 0.2, · · · , 0.9}.
5.2. Competitors
As mentioned earlier, one distinguishable strength of ourresult is that various policy mappings can be used as acompetitor. Here we test three different policies: the best
fixed arm policy, the myopic policy, and the Whittle index
policy. We emphasize again that these competitor policies
know the system parameters while our algorithm does not.
The best fixed arm policy computes the stationary distribupk
01tion ωk = pk +1−pk for all k and pulls the arms with top N
01
11values. The myopic policy keeps updating the belief ωk (t)Figure 2. Bayesian regret of Thompson sampling versus episode(left) and its log-log plot (right)

for the arm k being in a good state and pulls the top N arms.
Finally, the Whittle index policy computes the Whittle index
of each arm and uses it to rank the arms. The Whittle index
is proposed by Whittle (1988), and its computation in thisparticular setting can be found in Liu & Zhao (2010).
One observation is that these three policies are reduced tothe best fixed arm policy in the stationary case. However,the first two policies are known to be sub-optimal in general(Gittins et al., 1989). Liu & Zhao (2010) justify both theoretically and empirically the performance of the Whittle
index policy on the Gilbert-Elliott channel model.
5.3. Resultsθ
The value functions Vπ,1(∅) for the best fixed arm policy, the myopic policy, and the Whittle index policy are
105.4, 110.3, and 111.4, respectively. If a competitor policy has a weak performance, then Thompson sampling alsouses this weak policy mapping to get a policy πl for theepisode l. This implies that the regret does not necessarily become negative when the competitor policy is weak.
Figure 2 shows the trend of regret as a function of episodeindices. Regardless of the choice of policy mapping, theregret is sub-linear, and the slope of log-log plot is less than0.5, which agrees with Theorem 5.

References
Ahmad, S. H. A., Liu, M., Javidi, T., Zhao, Q., and Krishnamachari, B. Optimality of myopic sensing in multichannel opportunistic access. IEEE Transactions on
Information Theory, 55(9):4040–4050, 2009.
Dai, W., Gai, Y., Krishnamachari, B., and Zhao, Q. The
non-bayesian restless multi-armed bandit: A case of nearlogarithmic regret. In IEEE International Conference on
Acoustics, Speech and Signal Processing (ICASSP), pp.
2940–2943. IEEE, 2011.
Dai, W., Gai, Y., and Krishnamachari, B. Online learning for multi-channel opportunistic access over unknown
markovian channels. In IEEE International ConferenceRegret Bounds for Thompson Sampling in Restless Bandit Problems

on Sensing, Communication, and Networking (SECON),
pp. 64–71. IEEE, 2014.
Gittins, J. C., Glazebrook, K. D., Weber, R., and Weber, R.
Multi-armed bandit allocation indices, volume 25. Wiley
Online Library, 1989.
Lattimore, T. and Szepesvári, C. Bandit algorithms. preprint,
2018.
Liu, H., Liu, K., and Zhao, Q. Logarithmic weak regret ofnon-bayesian restless multi-armed bandit. In IEEE International Conference on Acoustics, Speech and Signal
Processing (ICASSP), pp. 1968–1971. IEEE, 2011.
Liu, H., Liu, K., and Zhao, Q. Learning in a changing
world: Restless multiarmed bandit with unknown dynamics. IEEE Transactions on Information Theory, 59(3):1902–1916, 2013.
Liu, K. and Zhao, Q. Indexability of restless bandit problems
and optimality of whittle index for dynamic multichannel
access. IEEE Transactions on Information Theory, 56(11):5547–5567, 2010.
Meshram, R., Gopalan, A., and Manjunath, D. Optimal
recommendation to users that react: Online learning for aclass of pomdps. In IEEE 55th Conference on Decision
and Control (CDC), pp. 7210–7215. IEEE, 2016.
Meshram, R., Gopalan, A., and Manjunath, D. Restlessbandits that hide their hand and recommendation systems.
In IEEE International Conference on Communication
Systems and Networks (COMSNETS), pp. 206–213. IEEE,
2017.
Meshram, R., Manjunath, D., and Gopalan, A. On thewhittle index for restless multiarmed hidden markov bandits. IEEE Transactions on Automatic Control, 63(9):3046–3053, 2018.
Ortner, R., Ryabko, D., Auer, P., and Munos, R. Regretbounds for restless markov bandits. In International
Conference on Algorithmic Learning Theory, pp. 214–228. Springer, 2012.
Osband, I., Russo, D., and Van Roy, B. (more) efficient
reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pp.
3003–3011, 2013.
Papadimitriou, C. H. and Tsitsiklis, J. N. The complexityof optimal queuing network control. Mathematics ofOperations Research, 24(2):293–305, 1999.
Robbins, H. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society,58(5):527–535, 1952.

Russo, D. and Van Roy, B. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221–1243, 2014.
Tekin, C. and Liu, M. Online learning of rested and restlessbandits. IEEE Transactions on Information Theory, 58(8):5588–5611, 2012.
Thompson, W. R. On the likelihood that one unknown
probability exceeds another in view of the evidence of
two samples. Biometrika, 25(3/4):285–294, 1933.
Whittle, P. Restless bandits: Activity allocation in a changing world. Journal of applied probability, 25(A):287–298,
1988.