ONLINE RESTLESS BANDITS WITH UNOBSERVED STATES
Authors: Bowen Jiang
Bo Jiang
Jian Li
TAO LIN
Xinbing Wang
Chenghu Zhou
Venue: Submitted to ICLR 2023 (2023)
Keywords: Thompson Sampling
Explore-Then-Commit
online restless bandit

Abstract: We study the online restless bandit problem, where each arm evolves according to a Markov chain independently, and the reward of pulling an arm depends on both the current state of the corresponding Markov chain and the action. The agent (decision maker) does not know the transition kernels and reward functions, and cannot observe the states of arms all the time.  The goal is to sequentially choose which arms to pull so as to maximize the expected cumulative rewards collected.  In this paper, we propose TSEETC, a learning algorithm based on Thompson Sampling with Episodic Explore-Then-Commit. The algorithm proceeds in episodes of increasing length and each episode is divided into exploration and exploitation phases. In the exploration phase in each episode, action-reward samples are collected in a round-robin way and then used to update the posterior as a mixture of Dirichlet distributions.  At the beginning of the exploitation phase, TSEETC generates a sample from the posterior distribution as true parameters. It then follows the optimal policy for the sampled model for the rest of the episode. We establish the Bayesian regret bound $\tilde {\mathcal{O}}(\sqrt{T})$ for TSEETC, where $T$ is the time horizon. This is the first bound that is close to the lower bound of restless bandits, especially in an unobserved state setting. We show through simulations that TSEETC outperforms existing algorithms in regret.

Under review as a conference paper at ICLR 2023
ONLINE RESTLESS BANDITS WITH UNOBSERVED STATES
Anonymous authors Paper under double-blind review
ABSTRACT
We study the online restless bandit problem, where each arm evolves according to a Markov chain independently, and the reward of pulling arm depends on both the current state of the corresponding Markov chain and the action. The agent (decision maker) does not know the transition kernels and reward functions, and cannot observe the states of arms even after pulling. The goal is to sequentially maximize the expected cumulative rewards col-
choose which arms pull lected. In this paper, we propose TSEETC, learning algorithm based on Thomp- son Sampling with Episodic Explore-Then-Comiee episodes of increasing length and each episode is divided into exploration and exploitation phases. In the exploration phase in each episode, action-reward sam- ples are collected in a round-robin way and then used to update the posterior as a mixture of Dirichlet distributions. At the beginning of the exploitation phase, TSEETC generates sample from the posterior distribution as true parameters. It then follows the optimal policy for the sampled model for the rest of the episode. We establish the Bayesian regret bound ((VT) for TSEETC, where is the time horizon. This is the first bound that is close to the lower bound of restless ban- dits, especially in an unobserved state setting. We show through simulations that TSEETC outperforms existing algorithms in regret.
The algorithm proceeds
INTRODUCTION
The restless multi-armed problem (RMAB) general setup to model many sequential decision making problems ranging from wireless communication (Tekin & Liu, 2011; Sheng et al., 2014), sensor/machine maintenance (Ahmad et al., 2009; Akbarzadeh & Mahajan, 2021) and healthcare (Mate et al., 2020: 2021). This problem considers one agent and N arms. Each arm is modulated by a Markov chain M with state transition function pi and reward function R At each time, the agent decides which arm to pull. After the pulling, all arms undergo an action-dependent Markovian state transition. The goal is to decide which arm to pull to maximize the expected reward, i.c., E[ rr). where ri is the reward at time and is the time horizon.
In this paper, consider the online restless bandit problem with unknown parameters (transition functions and reward functions) and unobserved states. Many works concentrate on learning unknown parameters (Liu al., 2010; 2011; Ortner et al., 2012; Wang et al., 2020; Xiong et al., 2022a;b) while ignoring the possibility that the states are also unknown. The unobserved states assumption is common real-world applications, such cache access (Paria & Sinha, 2021) and recommendation system (Peng et al., 2020). In the cache access problem, the user can only get the perceived delay but cannot know whether the requested content stored in the cache before or after the access. Moreover, in the recommender system, we do not know the user's preference for the items. There are also some studies that consider the unobserved states. However, they often assume the parameters are known (Mate et al., 2020; Meshram et al., 2018; Akbarzadch & Mahajan, 2021) and there is a lack of theoretical result (Peng et al., 2020; Hu et al., 2020). And the existing algorithms (Zhou et al., 2021; Jahromi al., 2022) with theoretical guarantee do not match the lower regret bound of RMAB (Ortner et al., 2012).
One common way to handle the unknown parameters but with observed states is to the optimism in the face of uncertainty (OFU) principle (Liu et al., 2010; Ortner et al., 2012; Wang et al., 2020). The regret bound in these works is too weak sometimes, because the baseline they consider, such

---

Under review as a conference paper at ICLR 2023
as pulling the fixed arms (Liu et al., 2010), is not optimal in RMAB problem. Ortner et al. (2012)
derives the lower bound ((VT) for RMAB problem. However, it is not clear whether there is an efficient computational method to search out the optimistic model in the confidence region (Laksh-
manan et al., 2015). Another way to estimate the unknown parameters is Thompson Sampling (TS) method (Jung & Tewari, 2019; Jung et al., 2019; Jahromi et al., 2022; Hong et al., 2022). TS algo- rithm does not need to solve all instances that lie within the confident sets as OFU-based algorithms (Ouyang et al., 2017). What's s more, empirical studies suggest that TS algorithms outperform OFU- based algorithms in bandit and Markov decision process (MDP) problems (Scott, 2010; Chapelle & Li, 2011; Osband& & Van Roy, 2017).
Some studies assume that only the states of pulled arms are observable (Mate et al., 2020; Liu & Zhao, 2010; Wang et al., 2020; Jung & Tewari, 2019). They translate the partially observable Markov decision process (POMDP) problem into fully observable MDP by regarding the state last observed and the time elapsed as a meta-state (Mate et al., 2020; Jung & Tewari, 2019), which is much simpler due to more observations about pulled arms. Mate et al. (2020), and Liu & Zhao (2010) derive the optimal index policy but they assume the known parameters. Restless-UCB in Wang et al. (2020) achieves the regret bound of ((T2/$), which does not match the lower bound Ö(VT) regret, and also restricted to specific Markov model. There are also some works that consider that the arm's 's state is not visible even after pulling (Meshram et al., 2018; Akbarzadeh & Mahajan, 2021; Peng al., 2020; Hu et al., 2020; Zhou al., 2021; Yemini et al., 2021) and the classic POMDP setting (Jahromi et al., 2022). However, there are still some challenges unresolved. Firstly, Meshram et al. (2018) and Akbarzadeh & Mahajan (2021) study the RMAB problem with unobserved states but with known parameters. However, the true value of the parameters are often unavailable in practice. Secondly, the works study RMAB from a learning perspective, e.g., Peng et al. (2020); Hu et al. (2020) but there are no regret analysis. Thirdly, existing policies with regret bound ( (Zhou et al., 2021; Jahromi et al., 2022) often do not have a regret guarantee that scales Õ(VT), which is the lower bound in RMAB problem (Ortner et al., 2012). Yemini et al. (2021) considers the arms are modulated by two unobserved states and with linear reward. This linear structure is quite a bit of side information that the decision maker can take advantage of for decision making and deppeddet log(T) is given.
To the best of our knowledge, there are provably optimal policies that perform close to the offline optimum and match the lower bound in restless bandit, especially in unobserved states setting. The unobserved states bring much challenges to us. Firstly, we need to control estimation error about states, which itself is not directly observed. Secondly, the error depends on the model parameters in complex way via Bayesian updating and the parameters are still unknown. Thirdly, since the state is not fully observable, the decision-makee cannot keep track of the number of visits to state-action pairs, a quantity that is crucial in the theoretical analysis. We design a learning algorithm TSEETC to estimate these unknown parameters, and benchmarked on a stronger oracle, we show that our algorithm achieves a tighter regret bound. In summary, we make the following contributions:
Problem formulation. We consider the online restless bandit problems with unobserved states and unknown parameters. Compared with Jahromi et al. (2022), our reward functions are unknown.
Algorithmic design. We propose TSEETC, a learning algorithm based on Thompson Sampling with Episodic Explore-Thent ThennCComiin The whole learning horizon divided into episodes of increasing length. Each episode is split into exploration and exploitation phases. In the exploration phase, to estimate the unknown parameters, we update the posterior distributions about unknown parameters as mixture of Dirichlet distributions. For the unobserved states, we use the belief state to encode the historical information. In the exploitation phases, we sample the parameters from the posterior distribution and derive an optimal policy based on the sampled parameter. What's more, we design the determined episode length in an increasing manner to control the total episode number, which is crucial to bound the regret caused by exploration.
Regret analysis. We consider a stronger oracle which solves POMDP based on our belief state. And we define the pseudo-count store the state-action pairs. Under Bayesian framework, we show that the expected regret of TSEETC accumulated up time T is bounded by Õ(VT), where Ô hides logarithmic factors. This bound improves the existing results (Zhou et al., 2021; Jahromi et al., 2022).
2

---

Under review as a conference paper at ICLR 2023
Experiment results. We conduct the proof-of-concepl experiments, and compare policy with existing baseline algorithms. Our results show that TSEETC outperforms existing algorithms and achieve near-optimal regret bound.
2 RELATED WORK
We review the related works in two main domains: learning algorithm for unknown parameters, and methods to identify unknown states.
Unknown parameters. Since the system parameters are unknown in advance, it is essential to study RMAB problems from learning perspective. Generally speaking, these works can be divided into two categories: OFU (Ortner et al., 2012, Wang et al., 2020; Xiong et al., 2022a; Zhou et al., 2021; Xiong et al., 2022b) or TS based (Jung al., 2019; Jung & Tewari, 2019; Jahromi et al., 2022; Hong et al., 2022). The algorithms based on OFU often construct confidence sets for the system parameters each time, find the optimistic estimator that is associated with the maximum reward, and then select an action based on the optimistic estimator. However, these methods may not perform close to the offline optimum because the baseline policy they consider, such as pulling only one arm, is often a heuristic policy and not optimal. In this case, the regret bound Olog T) (Liu et al., 2010) is less meaningful. Apart from these works, posterior sampling (Jung & Tewari, 2019; Jung et al., 2019) were used to solve this problem. A TS algorithm generally samples a set of MDP parameters randomly from the posterior distribution, then actions are selected based on the sampled model. Jung & Tewari (2019) and Jung et al. (2019) provide theoretical guarantee (VVT) in the Bayesian setting. TS algorithms are confirmed to outperform optimistic algorithms in bandit and MDP problems (Scott, 2010; Chapelle & Li, 2011; Osband & Van Roy, 2017).
Unknown states. There are some works that consider the states of the pulled arm are observed (Mate et al., 2020; Liu & Zhao, 2010; Wang et al., 2020; Jung & Tewari, 2019). Mate et al. (2020) and Liu & Zhao (2010) assumes the unobserved states but with known parameters. Wang al. (2020) constructs an offline instance and give the regret bound ((T2/3). Jung& & Tewari (2019) considers the episodic RMAB problems and the regret bound Ö(VT) is guaranteed in the Bayesian setting. Some studies assume that the states are unobserved even after pulling. Akbarzadeh & Mahajan (2021) and Meshram al. (2018) consider the RMAB problem with unknown states but known system parameters. And there is no regret guarantee. Peng et al. (2020) and Hu et al. (2020) consider the unknown parameters but there are also no any theoretical results. The most similar to our work is Zhou et al. (2021) and Jahromi et al. (2022). Zhou et al. (2021) considers that all arms are modulated by a common unobserved Markov Chain. They proposed the estimation method based on spectral method (Anandkumar et al., 2012) and learning algorithm based upper confidence bound (UCB) strategy (Auer al., 2002). They also give the regret bound O(T2/3) and there is gap between the lower bound ((VT) (Ortner et al., 2012). Jahromi et al. (2022) considers the POMDP setting and propose the pseudo counts to store the state-action pairs. Their learning algorithm is based on Ouyang et al. (2017) and the regret bound is also (TT2/3). And their algorithm is not programmable due to the pseudo counts is conditioned the true counts which uncountable.
3 PROBLEM SETTING
Consider a restless bandit problem with one agent and N arms, Each arm i [N] := (1, associated with an independent discrete-time Markov chain Mt = (S', P'), where S is the state space and pi E SsS's the transition functions. Let sf denote the state of arm at time t and 8t (s} s? "?......"" s!") the state of all arms. Each arm i is also associated with a reward functions R E TR'' XR where Ré (r 8) is the probability that the agent receives a reward r R when he pulls arm i in state s. We assume the state spaces St and the reward set R are finite and known to the agent. The parameters p and R², E [NV are unknown, and the state 8t is also unobserved to the agent. For the sake of notational simplicity, with size S. Our result can be generalized in a straightforward way to allow different state spaces.
assume that all arms have the same state spaces
The whole game is divided into I time steps. The initial state sf for each arm [N] is drawn from a distribution h; independently, which we assume to be known to the agent. At each time t, the agent chooses one arm a, [N] to pull and receives a reward r, R with probability R R (.). Note
3

---

Under review as a conference paper at ICLR 2023
that only the pulled arm has the reward feedback. His decision on which arm a, to pull is based on the observed history 74 = [11, 71, dg, r2- ...... 0r-1, rt-1]. Note that the states of the arms are never observable, even after pulling. Each arm i makes state transition independently according to the associated Pt, whether is pulled or not. This process continues until the end of the game. The goal of the agent is to maximize the total expected reward.
We use A to denote the unknown P and R' for i E [N] collectively. Since the true states are unobservable, the agent maintains belief state bj = [b](s, 0), E S*] Ag: for each arm where 0),
(s(s,) 0) == (s}
.Eess b(s) = =1] is the probability simplex in R Note that (s. 0) de- pends on the unknown model parameter 0, which itself has to be learned by the agent. We aggregate all arms as whole Markov chain .M and denote its transition matrix and reward function as P and R, respectively. For a given 0, the overall belief state he- = (b,, bgg ... bb²) is a sufficient statistic for H4-1 (Smallwood & Sondik, 1973), so the agent can base his decision time on b, only. Let A := Asi X ... x Asx. A deterministic stationary policy x Ab + [N] maps a belief state to an action. The long-term average reward of a policy æ is defined as
and As :=
J" (h, 0) lim sup 7
Σ
Tr h
T-200
We use J(h, - sup- J (h, 0) to denote the optimal long-term average reward. We assume J(h, B) is independent of the initial distribution h as in Jahromi al. (2022) and denoted it by J(0). We make the following assumption.
Assumption 1. The smallest element 61 in the transition functions Pi E N is bigger than zero. Assumption 2. The smallest element 62 in the reward functionn R² i E N bigger than zero
Assumption I and Assumption 2 are strong in general, but they help us bound the error of belief estimation (De Castro et al., 2017). Assumption 1 also makes the MDP weakly communicating (Bertsekas et al., 201 1). For weakly communicating MDP, it is known that there exists a bounded function v( 0) A. -> IR such that for all E Ab (Bertsekas al., 201 1),
J(0) + vb, = max
r(b. + Σ P(r b), 0)
(2)
where e is the relative value function, rb, = E, E, (s, R) s)r is the expected reward, D' is the updated belief after obtaining the reward r. and P(r b, 0) is the probability of observing r in the next step, conditioned on the current belief and action a. The corresponding optimal policy is the maximizer of the right part in equation 2. Since the value function v(, 0) is finite, we can bound the span function sp(0) == max, u(b, f)- - ming v(b. 0) as Zhou et al. (2021). We show the details about this bound in Proposition and denote the bound as H.
We consider the Bayesian regret. The parameters 6* is randomly generated from a known prior distribution Q the beginning and then fixed but unknown to the agent. We measure the efficiency of a policy и by its regret, defined as the expected gap between the cumulative reward of an offline oracle and that of π, where the oracle is the optimal policy with the full knowledge of 0*, but unknown states. The offline oracle is similar to Zhou et al. (2021), which is stronger than those considered in Azizzadenesheli al. (2016) and Fiez et al. (2018). We focus on the Bayesian regret of policy (Ouyang et al., 2017; Jung& & Tewari, 2019) as follows,
Σ (J(0) - mm))
T
Ry = Eg-~
(3)
The above expectation is with respect to the prior distribution about 6*, the randomness in state transitions and the random reward.
THE TSEETC ALGORITHM
In section 4.1, define the belief state and show how update it with new observation. In section 4.2, we show how to update the posterior distributions under unknown states. In section 4.3, we show the details about our learning algorithm TSEETC.
4

---

Under review as a conference paper at ICLR 2023
4.1 BELIEF ENCODER FOR UNOBSERVED STATE
Here we focus on the belief update for arm i with true parameters 0*. At time I, the belief for arm i in state is (s, 0*). Then after the pulling of arm i, we obtain the observation rt. The belief (s,, 0*) can be update as follows:
(5,(000)) E. (i(s, 0 R (re P:(s' 1s)
(4)
E. (x, (r, ())
where the (s' 5) is the probability of transitioning from state time state s' and R (re is the probability of obtain reward ry under state
the arm is not pulled, we update its belief as follows:
1 (8', 000
Σ 1((s,0')P! 1s).
(5)
Then at each time, we can aggregate the belief of all arms as b, Based on equation 2, we can derive the optimal action at for current belief bz.
4.2 MIXTURE OF DIRICHLET DISTRIBUTION
In this section, we estimate the unknown and R based on Dirichlet distribution. The Dirichlet distribution parameterized by count vector, Φ (01,..., 2k), where Φ; 2 0, such that the density of probability distribution defined as f'v Φ)) x I p.--1 (Ghavamzadeh al., 2015).
Since the true states are unobserved, all state sequences should be considered, with some weight proportional to the likelihood of each state sequence (Ross et al., 2011). Denote the reward history collected from time & till t2 for arm as i2 and similarly the states history is denoted si, And the belief state history is denoted = Then with these history information, the posterior distribution (P') and (e(R)) at time be updated in Lemma 1.
Lemma Under the unobserved state setting and assuming transition function pi with prior 9o (P)) = f( [(Pi=n1 o²), reward function H' with prior go (I1') f( R8---1 (t)), with the information ró. and bo. then the posterior distribution are as follows:
9r (Pt)
Σ
(Pt)
w(s
II S,5"
Pi (s'' 8)
No. (o..((s))) (5:)+
(6)
1-
EES
(1(rr 5) -2 +3
R2)) x Σ 90 (R') w (s
II
9t
62
SRESt
8,7
where w(sba)) is the likelihood of state sequence tbe and is the vector with one each position.
The element 1 can be different lengths in correspondence with the dimension of and R. This procedure is summarized in Algorithm 1.
Algorithm Posterior Update for Ri(s,) -) and (s((s.)
1: Input: the history length 51, the state space S,, the belief history bb.r,, the reward history ró:r. the initial parameters &'..r v/i,r, for s' E S,, R.
2: generate 8 possible state sequences
3: calculate the weight wi(j)= = I (s, 0).j E S
4: for in ......S!' S do
5: count the occurence times of event (s, and (s, as N s.ats Ni,, in sequence
6: update d' + - + +i o,a bir + wh. + Ni.
7: aggregate the d' as Φ(j), sar as +() for all s E Sir R
8: end for
9: update the mixture Dirichlet distribution
In (P*) x E w())(( o(i)).
Ir. (IT) x E w(i) w() Ri- (())
5

---

Under review as a conference paper at ICLR 2023
With Algorithm 1, we update the posterior distribution about the unknown parameters and sam- ple from the posterior distribution as true parameters. The belief estimation error can be bounded by the distance between the sampled parameters and the true values (Proposition 2 ). The theoretical guarantee about estimation errors about unknown parameters is provided in Lemma 2.
4.3 OUR ALGORITHM
Our algorithm, TSEETC, operates in episodes with different lengths. Each episode split into exploration phase and cxploitation phase. Denote the episode number is KT and the first time in each episode is denoted as tg. We use Tk to denote the length episode & and it can be determined
1, where T /T+1 The length of exploration phase in each episode is 2
as: T3
fixed as T. which satisfies n Kr = ( (T) and 7 S Tr+Kr-1 With these notations, our whole algorithm is shown below.
Algorithm Thompson Sampling with Episodic Explore-These Then-Commi
1: Input: prior go (R.), initial belief bu. exploration length 71, the first episode length Ti
2: for episode l- 1, ..... do
3: start the first time of episode k. l. :==1.
4: generate R(tx)
5: for t= tb, t + 1,,.... - RR) and P(tx) ~ -
Ti do
6: pull the arm for rI/N times in a round robin way
7: receive the reward r2
8: update the belief bi using R(tx), P(tx) based on equation
9: update the belief bi.jj E N {i} using P(tx) based on equation end for
11: for i= 1, N do
input the obtained rt,s + Pe be bunte Algorithm update the posterior distribution Ieutri (P), Ita (R) end for
13:
14:
generate R(4, + TI) ) tu (P), P(le + mi) Dh (R) 15: for in 0, .....,,N .N do
16: re-upe the belief b; from time 0 to tg based on R(ts + T1) and P(tx TI) end for
17:
18:
compute ()))) = Oracle (., R(tx + 72), P(tx 71))
19:
for t l4 + + 1,... 14-1 - do
20:
apply action a; = m (b.)
21: observe new reward Tt+1
update the belief b, of all arms based equation equation 23: end for
end for
In episode k, for the exploration phase, first sampled the O, from the distribution gtg-1++ 1 (P) and 9t,-1+r (R). We pull each arm for 7 /N times in round robin way. For the pulled arm, we update its belief based on equation using 9r, For the arms that are not pulled, we update its belief based on equation 5 using 0,,- The reward and belief history of each arm are input into Algorithm to update the posterior distribution after the exploration phase. Then we sample the new 0,,t7 from the posterior distribution, and re-calibrate the belief b, based on the most recent estimated 6,, +m Next we enter into the exploitation phase Firstly we derive the optimal policy कy. for the sampled parameter 0 Then we policy गą for the rest of the episode k.
We control the increasing of episode length in a deterministic manner. Specially, the length for episode is just more than the last episode k. In such deterministic increasing manner, the episode number Kr is bounded by ((VT) in Lemma 10. Then the regret caused by the exploration phases be bound by O (VTT), which is crucial part in Theorem 1.
In TSEETC, for the unknown states, we propose the belief state to estimate the true states. What's more, under the unobserved state setting, consider all possible state transitions and update the

---

Under review as a conference paper at ICLR 2023
posterior distribution of unknown parameters mixture of each combined distribution, in which each occurence is summed with different weight.
Remark 1. We use Oracle to derive the optimal policy for the sampled parameters in Algorithm The Oracle can be the Bellman equation for POMDP as we introduced in equation 2, or the approximation methods (Pineau et al., 2003; Silver & Veness, 2010). etc. The approximation ervor discussed in Remark 3.
PERFORMANCE ANALYSIS
In section 5.1, we show theoretical results and discussions. In section 5.2, provide proof sketch and the detailed proof is in Appendix B.
5.1 REGRET BOUND AND DISCUSSIONS
Theorem Suppose Assumptions 1,2 hold and the Oracle returns the optimal policy in each episode. The Bayesian regret of our algorithm satisfies
RT S 48C,C28 NT log( (TA H +CCCCSNNTT+C
where C1 =1=11 L2N + N + S2, C2 Tmax H constants independent with time horizon of C1 and 62 are the minimum elements of the functions P and R", respectively. is the fixed exploration length in each episode, AR is the biggest gap of the reward obtained at each two different time, H is the bounded span, Tmax is the maximum reward obtain each time, N is the number of arms and S is the state size for each arm.
T, L = 4(1-c1)² L = 4(1-c1)² 10:=4(1-) Nefez
Remark 2. The Theorem I shows that the regret of TSEETC is upper bound by Ö(VT). This is the first bound that matches the lower bound in restless bandit problem (Ortner et al., 2012) in such unobserved state setting. Although TSEETC looks similar explore-then tootomm-then-oommitt (Lattimore & Szepesvári, 2020), a key novelty of TSEETC lies in using the approach of posterior sampling to update the posterior distribution of unknown parameters as the mixture of each combined distribu- tion. Our algorithm balances exploration and exploitation in a deterministic-episode manner and ensures the episode length grows at linear rate, which guarantees that the total episode number is bounded by O(VT). Therefore the total regret caused by exploration is well controlled by O(VT) and this is better than the bound OTT2/3) in Zhou el al. (2021). What's more, in the exploitation phase, our regret bound Ö(VT) ) is also better than (TT2/3) (Zhou al., 2021). This shows our posterior sampling based method is superior to UCB based solution (Osband & Van Roy, 2017). In Jahromi et al. (2022), their pseudo count of state state-action pair is always smaller than the true counts with some probability at any time. However, in our algorithm, the sampled parameter is more concentrated on true values with the posterior update. Therefore, our pseudo count (defined in equation 13) based on belief approximates the true counts more closely, which helps obtain tighter bound.
5.2 PROOF SKETCH
In our algorithm, the total regret can be decomposed as follows:
ky tut
Ry
1
RT Eg.
J(0*)
rz
+
Eg.
J(O*) - rt
(8)
++
Regret (A)
Regret (B)
Bounding Regret (A). The Regret (A) is the regret caused in the exploration phase of each episode. This term can simply bounded as follows:
kT Σ
Regret (A) S Eg.
TAR
Ti
S Ti ART
(9)
where AR = r Tmaz Tmin is the biggest gap of the reward received at each two different times. The regret in equation is related with the episode number ky, which can be bounded as ((vT) in Lemma 10.
7

---

Under review as a conference paper at ICLR 2023
Bounding Regret (B). Next we bound Regret(B) in the exploitation phase. Define b, is the be- lief updated with parameter 0g and b represents the belief with 8*. During episode k, based on equation 2 for the sampled parameter O2 and that = x" (b+), we can write:
(0x) ) u(be, 0s) r(be, ae) + Σ P(r 8 ar, 0z)u(b' 0x).
(10)
With this equation, we proceed by decomposing the regret as:
Regret(B) R1 + R2 + Rs R4
(11)
where each term defined as follows:
lT
R = Eg.
[Th - -)
kr
((bb+1,0))) obb -((
R2
Eg.
kr
h
Σ P rr| B ar 2x o(b' 0x) ((brr1,0a) 0a)) 0u)]
R3 Eg.
Σ
kT
f
R4 = Eg.
Σ
(r(b),a)--((b)) rbbr
Bounding Ry. One key property of Posterior Sampling algorithms is that for given the history Hie the true parameter 6* and sampled 0g are identically distributed the time tę as stated in Lemma 13. Due to the length Th determined and independent with 0j. then Rı is zero thanks to this key property.
Bounding R2. The regret R2 is the telescopic sum of value function and can be bounded as Rs < KT.. It solely depends on the episode number and the upper bound H of span function. As a result, R2 reduce to finite bound over the number of episodes kr, which can be bounded in Lemma 10.
Bounding R3 and R4. The regret terms RG and R4 is related with estimation error about A. Thus we should bound the parameters' error especially in our unobserved state setting. Recall the definition of Φ, v. we can define the posterior mean of P'(s' s) and R'(r s) for arm at time t follows:
E + (1 - =1) (t)
E2 + (1 E2) a. (t)
(i [t)
R' ()))) Sc2 + (1 - (2) 1/ (1)
(12)
Se + (1 - (1) 01 (1]
We also define the pesudo count of the state-action pair (s, a) before the episode k as
No. (s, a) = [[ (tx)l, - [[)]
(13)
where vi. (f&) represents the count of state-action 2 = (s, a) pair before the episode k. Let Mi be the set of plausible MDPs in episode A with reward function R (r =) and transition function P (s') 2) satisfying.
Σ S'ES
2() P 22) Ba(z),
Σ F
R
R (r 2) Bc(2),
(14)
where as)
max I,N [ is chosen conservatively (Auer et al., 2008) that Mj. con-
145 L4Slog(2Nt,77) T)
tains both Pt and Pt. R. and Ri with high probability. Pd and RC are the true parameters as we defined in section 4.1. Specially, for the unobserved state setting, the belief error under different parameters is upper bounded by the gap between the estimators as in Proposition 2. Then the core of the proofs lies in deriving a high-brobability confidence set with our pesudo counts and show that the estimated error accumulated to T for each arm is bounded by VT. Then with the error bound for each arm, we can derive the final error bound about the MDP aggregated by all arms as stated in Lemma 2.
8

---

Under review as a conference paper at ICLR 2023
Lemma 2. (estimation errors) The total estimation error about transition accumulated by all exploitation phases satisfies the following bound
KT
1=11-1
Egg Σ
Σ
IP-- Polla S NTNN +SN2
(15)
The Lemma 2 shows that the accumulated enror is bounded by O(VT), which is crucial to obtain the final bound as the observed-statee setting (Ortner et al., 2012; Jung & Tewari, 2019). With C1 In N N2 + 52, We show the final bound about R3, R4 and the detailed proof in Appendix B.3,B.4.
Lemma 3. R3 satisfies the following bound
Ra S SS Nog NT 4C1SNNNT++ C.H.
Lemma 4. RA satisfies the following bound
R4 S 48C,Srman v NT (NT) + 4C,SSN VT + CLTmax
NUMERICAL EXPERIMENTS
In this section, we present -oonceet experiments and approximately implement TSEETC. We consider two arms and there are two hidden states for each arm. We pull just one arm each time. The learning horizon and reward functions for all arms are the same. We initialize the algorithm with uninformed Dirich- let prior on the unknown parameters. We compare our algorithm with simple heuristics e-greedy (Lattimore & Szepesvári, 2020) (e 0.01), and Bidding-Window UCB (Garivier & Moulines, 2011) with specified window size, RUCB (Liu et al., 2010), Q-learning (Hu et al., 2020) and SEEU (Zhou et al., 2021). The results are shown in Figure 1. We can find that TSEETC has the minimum regret among these algorithms.
50000, and each algorithm runs 100 iterations. The transition functions
-000
1933
222U TSCETE
TSCETE
2200
2000
1000
10000
20000
30000
43302
30000
24
fire
Thme
Figure 1: The cumulative regret
Figure 2: The log-log regret
In Figure 2, we plot the cumulative regret versus of the six algorithms in log-log scale. We observe that the slopes of all algorithms except for our TSEETC and SEEU are close to one, suggesting that they incur linear regrets. What is more, the slope of TSEETC close 0.5, which better than SEEU. This is consistent with our thcoretical result.
7 CONCLUSION
In this paper, we consider the restless bandit with unknown states and unknown dynamics. We propose the TSEETC algorithm to estimate these unknown parameters and derive the optimal pol- icy. We also establish the Bayesian regret of our algorithm as O(VT) which is the first bound that matches the lower bound especially in restless bandit problems with unobserved states Numer- ical results validate that the TSEETC algorithm outperforms other learning algorithms in regret. related open question is whether our method can be applied to the setting where the transition functions are action dependent. We leave it for future research.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sahand Haji Ali Ahmad, Mingyan Liu, Tara Javidi, Qing Zhao, and Bhaskar Krishnamachari. Opti- mality of myopic sensing multichannel opportunistic access. IEEE Transactions on Information Theory, (5(9):4040405555 2009.
Nima Akbarzadch and Aditya Mahajan. Maintenance of collection of machines under partial observability; Indexability and computation of whittle index. arXiv preprint arXiv:104.00555, 2021.
Animashree Anandkumar, Daniel Hsu, and Sham M Kakade. A method of moments for mixture models and hidden markov models. In Conference on Learning Theory, pp. 33-1. JMLR Work- shop and Conference Proceedings, 2012.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-255 2002.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement
learning. Advances in neural information processing systems, 21, 2008.
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learn- ing of pomdps using spectral methods. In Conference on Learning Theory, pp. 193-256. PMLR, 2016.
Dimitri P Bertsekas et al. Dynamic programming and optimal control 3rd edition, volume ii. Bel- mont, MA: Athena Scientific, 201 1.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
Yohann De Castro, Elisabeth Gassiat, and Sylvain Le Corff. Consistent estimation of the filtering and
marginal smoothing distributions in nonparametric hidden markov models. IEEE Transactions Information Theory, 63(8):4758-477) 4777, 2017.
Tanner Fiez, Shreyas Sekar, and Lillian J Ratliff. Multi-armed bandits for correlated markovian environments with smoothed reward feedback. arXiv preprint arXiv: 1rXiv:1803.00000 2018
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International Conference Algorithmic Learning Theory, pp. 174-188. Springer, 2011.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, Aviy Tamar, et al. Bayesian reinforcement learning: A survey. Foundations and Trends@ in Machine Learning, 8(5-6):359 483, 2015.
Joey Hong, Branislav Kveton, Manzil Zaheer, Mohammad Ghavamzadeh, and Craig Boutilier. Thompson sampling with mixture prior. In International Conference Artificial Intelligence and Statistics, pp.
PMLR 2022.
Zhisheng Hu, Minghui Zhu, and Peng Liu. Adaptive cyber defense against multi-stage attacks using learning-based pomdp. ACM Transactions on Privacy and Security (TOPS), 24(1):1-25, 2020.
Mehdi Jafarnia Jahromi, Rahul Jain, and Ashutosh Nayyar. Online learning for unknown partially observable mdps. In International Conference on Artificial Intelligence and Statistics, pp. 1712- 1732. PMLR, 2022.
Young Hun Jung and Ambuj Tewari. Regret bounds for thompson sampling in episodic restless bandit problems. Advances in Neural Information Processing Systems, 32, 2019.
Young Hun Jung, Mare Abeille, and Ambuj Tewari. Thompson sampling in non-episodic restless bandits. arXiv preprint arXiv: 1oXXv:99100055544 2019.
Kailasam Lakshmanan, Ronald Ortner, and Daniil Ryabko. Improved regret bounds for undis- counted continuous reinforcement learning. In International Conference on Machine Learning, pp. 524-532, PMLR, 2015.
10

---

Under review as a conference paper at ICLR 2023
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Haoyang Liu, Keqin Liu, and Qing Zhao. Learning in changing world: Non-bayesian restless multi-armed bandit. Technical report, CALIFORNIA UNIV DAVIS DEPT OF ELECTRICAL AND COMPUTER ENGINEERING, 2010.
Haoyang Liu, Keqin Liu, and Qing Zhao. Logarithmic weak regret of non-bayesian restless multi- armed bandit. In 20/ / IEEE International Conference on Acoustics, Speech and Signal Process- ing (ICASSP), pp. 1968-1971. IEEE, 2011.
Keqin Liu and Qing Zhao. Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access. IEEE Transactions Information Theory, 56(11):5547-5567 2010.
Aditya Mate, Jackson Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. Collapsing bandits and their application to public health intervention. Advances Neural Information Processing Systems, 05115999-16500 2020.
Aditya Mate, Andrew Perrault, and Milind Tambe. Risk-aware interventions in public health: Plan- ning with restless multi-armed bandits. In 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). London, UK, volume 10, 2021.
Rahul Meshram, D Manjunath, and Aditya Gopalan. On the whittle index for restless multiarmed hidden markov bandits. IEEE Transactions on Automatic Control, 63(9):3044-300 -00130066-33,,,,00 2018.
Ronald Ortner, Daniil Ryabko, Peter Auer, and Rémi Munos. Regret bounds for restless markov bandits. In International conference on algorithmic learning theory, pp. 214-228. Springer, 2012.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforce- ment learning? In International conference on machine learning, pp. 2701-2710. PMLR, 2017.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown markov decision processes: A thompson sampling approach. Advances in neural information processing systems, 30, 2017.
Debjit Paria and Abhishek Sinha. Leadeache: Regret-optimal caching in networks. Advances in Neural Information Processing Systems, 34:4435 4447, 2021.
Zhaoqing Peng, Junqi Jin, Lan Luo, Yaodong Yang. Rui Luo, Jun Wang, Weinan Zhang, Haiyang Xu, Miao Xu, Chuan Yu, et al. Learning to infer user hidden states for online sequential adver- tising, Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 2677-2684 2020.
Joelle Pineau, Geoff Gordon, Sebastian Thrun, et al. Point-based value iteration: An anytime algo- rithm for pomdps. IJCAL, volume pp. 1025-1032. Citeseer, 2003.
Stéphane Ross, Joelle Pineau, Brahim Chaib-draa, and Pierre Kreitmann. A bayesian approach for learning and planning in partially observable markov decision processes. Journal of Machine Learning Research, 12(5), 2011.
Steven L Scott. A modern bayesian look at the multi-an multi-armed bandit. Applied Stochastic Models in Business and Industry, 26(6):639-658, 2010.
Shang-Pin Sheng, Mingyan Liu, and Romesh Saigal. Data-driven channel modeling using spectrum measurement. IEEE Transactions Mobile Computing, 14(9):1794-1803 2014.
David Silver and Joel Veness. Monte-carlo planning in large pomdps. Advances in neural informa- tion processing systems, 23, 2010.
Richard D Smallwood and Edward J Sondik. The optimal control of partially observable markov processes over a finite horizon. Operations research, 21 1973.
Cem Tekin and Mingyan Liu. Online learning in opportunistic spectrum access: A restless bandit approach. In / Proceedings IEEE INFOCOM, pp. 2462-2470. IEEE, 2011.

---

Under review as a conference paper at ICLR 2023
Siwei Wang, Longbo Huang, and John Lui. Restless-ucb, an efficient and low-complexity algorithm for online restless bandits. Advances in Neural Information Processing Systems, 1871 1878-11889, 2020.
Guojun Xiong, Jian Li, and Rahul Singh. Reinforcement learning augmented asymptotically optimal index policy for finite-horizon restless bandits. 2022a.
Guojun Xiong, Shufan Wang, Gang Yan, and Jian Li. Reinforcement Learning for Dynamic Dimen- sioning of Cloud Caches: Restless Bandit Approach. In Proc. of IEEE INFOCOM, 2022b.
Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps. Production and Operations Management, 3109):3491-3504 2022c.
Michal Yemini, Amir Leshem, and Anelia Somekh-Baruch The restless hidden markov bandit with linear rewards and side information. IEEE Transactions on Signal Processing. 69:1 102-1123, 2021.
Xiang Zhou, Yi Xiong, Ningyuan Chen, and Xuefeng Gao. Regime switching bandits. Advances in Neural Information Processing Systems, 34, 2021.
12

---

Under review as a conference paper at ICLR 2023
A
TABLE OF NOTATIONS
Notation
Description
T
The length of horizon
KT
The episode number of time T
Ta
The episode length of episode k
T1
The fixed exploration length in each episode
P
The transition functions for arm
R
The reward function for arm
Pk
The sampled transition function for aggregated MDP
The sampled reward function for aggregated MDP
Ft
The reward obtained at time f
(s, 0)
The belief state for being in state at time / for with parameter 0
be
The belief of arms at time with parameter On
bj
The belief of all arms at time with parameter (
ag
The action at time f
(0%)
The optimal long term average reward with parameter Ox
Tian
The maximum reward obtained each time
Tmin
The minimum reward obtained each time
AR
The biggest gap of the obtained reward
B PROOF OF THEOREM 1
Recall that our goal is to minimize the regret: :
Σ (J(0)) -(10)- r2)
Rr Eg.
(16)
T: depends on the state 8t and de Thus Yz can be written as r(8r, az). Due to
Eg- (s) H4-1l rbb az) for any t, we have,
Σ (J(0)) ((1e))r(b(,a))))
RT = Eg-
(17)
In our algorithm, each episode is split into the exploration and exploitation phase then we can rewrite the regret as:
tut
kr
4+1111
RT = Eg.
Σ
-( Σ
+
Σ
Σ +2+++11
(j(0))r(1))
(18)
fR
where 71 is the exploration length for each episode. Ti is constant. 4 is the start time of episode k. Define the first part as Regret (A) which is caused by the exploration operations. The another part Regret (B) is as follows.
ky tetti
Regret (A) = EEgg
Σ
Σ
(J(O") (bi, ai))
kr
f-11-1
Regret (B) Eg-
Σ
Σ
(J(0") - (bi, a:))
fe+T++1
Recall that the reward set is R and we define the maximum reward gap in R as AR = Tman -Tmin- Then we get:
J(0") (b; oz) < AR.
Then Regret (A) can be simply upper bounded follows:
krr Σ
Regret (A) < Eg.
Ti TAR
S AARK.
13

---

Under review as a conference paper at ICLR 2023
Regret (A) is related with the episode number by obviously, which is bounded in Lemma 10. Next we should bound the term Regret (B).
During the episode k, based on equation 2, get:
J (Ox) + vbb, 0k) r(be, ai) + Σ P(r byg at, (x) (b', (6,00)) 0k),
(19)
where J (0x) is the optimal long-term average reward when the system parameter is O2, be is the belief at time updated with parameter OR. r(be, 0z) is the expected reward we can get when the action a, is taken for the current belief b,, D' is the updated belief based on equation 4 with parameter Og when the reward r is received.
Using this equation, we proceed by decomposing the regret
Regret(B)- = Rı + R2 Rs + R4,
(20)
where
by
R1 Eg.
(Th - -1 (J(()) J(0x))),
1441-1 -1
(u(b++1,0)) 0n) v(br, c(br.00i)
R2 = Eg.
k=
1uti++1
kT
1411-1
Σ P(r be, an 0x)o(b''b000 0x) (bmm1100)
R3 = Eg Σ
Σ
k=
by
1441-1
R4 = Eg.
Σ
Σ
(r(be,a)) - r(bb)
Next we bound the four parts one by one.
B.1 BOUND R
Lemma 5. R1 satisfies that Rı O.
Proof. Recall that:
R Eg- - -
k=1
For each episode, Tk is determined and is independent with 0g. Based on Lemma 13, we know that, therefore, the part Rg is O.
Eg [J(0"] EEg [0x)]
B.2 BOUND R2
Lemma 6. R2 satisfies the following bound
RA S HKT.
where Ky is the total number of episodes until time T.
Proof. Recall that R2 the telescoping sum of value function time + 1 and t.
ky
f
R₂
E.g
Σ
((8441,0%) u(be 0.)]
(21)
-
14

---

Under review as a conference paper at ICLR 2023
We consider the whole sum in episode k, then the Rg can be rewrite
KrT
R2 -
Eg.
u(bbr111 0x) u olbutttt1 0x)
Due to the span of o(b, 0) is bounded by H as proposition 1 then we can obtain the final bound,
R₂ S HKr.
B.3 BOUND R3
In this section, we first rewrite the Rg section B.3.1, In section B.3.2, we show the details about how to bound R3.
B.3.1 REWRITE R3
Lemma 7. (Rewrite Rg ) The regret Rg can be bounded as follows:
Kr
h-1-1
Kr
1+-111
Rs S HEg.
Σ
Σ
|P
Pall2
HEg-
Σ
Σ
1|b
Bell1
kT
1-1111
HTEg-
Σ
Σ
|
Rxll1
+
where Pk is the sampled transition functions in episode k, R& is the sampled reward functions in episode ki by is the belief at time f. updated with true p and R be is the belief at time updated with sampled Ps, Rx-
Proof. The most part is similar to Jahromi et al. (2022), except that we should handle the unknown reward functions.
Recall that R3 Eg-
1 EEa+h (E, bes at Ox) (6', 02) v(ber1,00))
Recall that Hi is the history of actions and observations prior to action Conditioned on H4, 6" and Oc, the only random variable in bet1 is 11+1, then we can get,
Eg- [1(6+11100) 0x) He, 0x = Σ v (6, (w) P(r bi,a,, a,, 0*),
(22)
eEf
where P(r bū. ae, 0*) is the probability of getting reward r given by ar 0r By the law of proba-
bility, P(r bi, at, 0r) can be written as follows,
P(r (e, Σ R (r (r(s') P( = 04)
Σ r (r
pr (81+1 = 8 18==8, He. at, (0, P He, 0')
(F
(23)
where pa is the transition functions for the MDP aggregated by all arms, R is the reward function for the aggregated MDP. Therefore, we can rewrite the Rg as follows,
kr
(P(r by, at, 0x) P(r by at, 0") (b', (6, (b)) )
R3 Eg.
Σ
Σ
PER
15

---

Under review as a conference paper at ICLR 2023
Based equation 23, get
ky
12+1-1
Rs
Eg-
ΣΣ
Ra Σ
Ry
(K11-1
Egg
Σ
(V. (( [
br
12+1-1
Egg
ΣΣ u (b, (b',
(24)
kg
f:11-
Eg
Σ
+=
Ry
(+41-1
+ Egg
Σ
e ΣΣ
16. O. 11
+
kr
fx-1-1
ΣΣ e (6. R2) (r 8) "((P)''' (s')s) 1s))
Eg-
Σ
Σ
+m
where Rg is the sampled reward function for aggregated MDP, Ps is the sampled transition function for aggregated MDP.
Define
Σ (() - 1s) (0) 1)]]
R'3 Bg.
Σ
ΣΣ
(v
k= +1++1
14-1-1
(Rx R (r ss)l (((s))(((')) (6()))(((\11))) 1s)
Ry = Eg.
Σ
ΣΣ
Bounding R'z. The part R3 can bounded as Jahromi al. (2022).
R₂3 Eg.
Σ
Ry
f-11-
Σ
ΣΣ
(c
(6(6))((611))) - ()) 11)]
(O) + (1)
where
Ry
(+-1-1
11 bt
R2(0) = Eg.
ΣΣ 1 (b' R (r bi(s))((s''
kT
1+-1-1
(x) 80) 20 I
ΣΣ
Eg-
kg
1411-1
Rs R (115s) 5') 16 :)) m)]
R1(
Eg.
Σ
ΣΣ v (b,0%)
+
ky
1+1-1
5F 18) ]
Egg
Σ
Σ
ΣΣ
Rx
16

---

Under review as a conference paper at ICLR 2023
For R0), because E, Rs (r 15))
1.E. Pa(s' s)= (b, - H, we have
kT
4+11-1
ΣΣ e (66. R& (2) 1s)) ]
(0)
Eg.
hpp
1++1-1
(r (8) Σ (0(()))((6111))) )
Egg
ΣΣ v (8', 0k) Ru (r
kT
f
Egg
e (6' 0k) (x 8)
- (0(())))())PP(($1])) (s)
k=
kT
1x41-1
< Egg
e (b', 0k) Ry (r) 8') [ib((s) - (3)) 8)
R= t
ky
f
(e(s)) - -b(())] ]
S H.g.
for f++1-1
(116(()- (o((s)-6(66) 09(60)1)
= -HE
Σ
Σ
where the first inequality is due to (.()) - (s) < (b)(s) (5)) and the second inequality is because Σ, R& (r s') -, E. Ps s) 1, (6', 0v) < H.
For the first term in (1) note that conditioned on H4, 0r, the distribution of s, is bt. Furthermore, a₂ is measurable with respect to the sigma algebra generated by H., O2 since at = 7 (b., 0z). Thus, we have
Egg v (b,O0s) 0k) (s' Hr, 0c
v (b',0s) 18g- [P* (8' 8) H 0s)
(25)
Eg.
(b' 0k) P
Ps (s)))(() He, 0g
v (6',0%) EEg. [P% (s') (s) He, Ox].
(26)
Substitute equation 25, equation 26 into R (1), we have
1
(1) Eg-
Σ
Σ
ΣΣ
(b'00z) Ra (rl 18)) - (= 1s))
k= tit +1
hr
M+1-1
< Eg-
Σ
(b', (z)) R& (r 1 s)
(s s)
kr
1+11-1
Σ PR (8) - P- - 101)
< HEg-
+
kr
f+-11
< HEg-
(1 (P&--1111))
where the first inequality is because Ps 8) - -P (s) S (P((s 8) - -P'(s's) 1 |s),, the second
inequality is due to (b',0)) H and Σ, Rs (r s =1
Therefore we obtain the final results.
Kr
Kr 1411-1
R < HE
Σ
Σ
||p"
Palla + HE
Σ
Σ
||ا bull1
17

---

Under review as a conference paper at ICLR 2023
Bounding Ry.. For part R3z note that for any fixed s', bss)ss |s) S S, therefore we can bound Rg as follows,
KT
(6', 0z) [Ro (r 12" (r (6)1 (rl'') (6(()) ]
R2 EØ-
Σ
ΣΣ
kT
Rs (r (r18)) 12 - 1911
SHE
ΣΣ
16-1-1
< SHEE
R R*1 11
+1
1
S
S22H
R 1²111
(27)
where the first inequality is due to 1 (b, 02) S H and E. P') {)) S S the second
inequality is due to for any fixed s', Σ. RR (r (8 - R (r x') - R4 R'
B.3.2 BOUND R3
Lemma 8. Rg satisfies the following bound
R3 S 48 L2N + N 8 HN (41 L2N + N + HSSH
+ 4(T T,N + N SSNSS + Kr 1).
Proof. Recall that the Rg is follows:
1+-1-1
(IPI+
R3 = Eg. Σ Li
E
E
be, az Onlo (6', 0x) - u(bit1,
This regret terms are dealing with the model estimation errors. That to say, they depend on the on-policy error between the sampled transition functions and the true transition functions, the sampled reward functions and the true reward functions. Thus we should bound the parameters' error especially in unobserved state setting. Based the parameters in our Dirichlet distribution, can define the empirical estimation of reward function and transition functions for arm i as follows:
+ - (1) (t)
62 + (1 (2) (t)
(i(s' [t) Se, + (1 - c1) (t),
R' ()) Seg + (1 62) E2) v/ (t)l,
(28)
where o' (f) is the parameters in the posterior distribution of p at time t, + (t) is the parameters in the posterior distribution of R at time t. We also define the pseudo count Ni. (s, a) of the state- action pair (s, a) before the episode is for arm i as
N t/ (s, a) = 1., 111)))1-111v3.0000 |I5
For notational simplicity, state-action pair. Then based on Lemma 7 we can decompose the R3 as follows,
(s, S A and 2; (se, ae) to denote the corresponding
kr
f
Eplo br at, Oxlu (b10%) (ba11).0))
R3 Eg.
Σ
Σ (P(r ae, P(r b%, ar, (0)))) o(b', 04))
Egg
< Rg + R1]
18

---

Under review as a conference paper at ICLR 2023
where
KT
Yk fk
R23 = HEg.
| - Pxlli
kmml 1= +1+11
KT
h-1-1
R3 = HEg.
Σ
Σ
|bb - -bllla
KT
R2 = S HEg.
RR Rulh
Note that the following results are all focused on one arm. Define Ps is the true transition function for arm i, P is the sampled transition function for arm We can extend the results on a arm the aggregated large MDP based on Lemma 11.
Bounding Rg. Since I v (b' s H from our assumption, each term in the inner summation is bounded by
Σ EES
(5) 21) - (8' =)) lo (s', 0x)
211
Σ
P (5') 2x) Ph (s' 20]
s'ES
<
Σ
PK (s') 21) P (s' 20) + H Σ Pl (s' 2 PE 120) s'ES
s'ES
where Pé P 2) is the true transition function, P (6' =x) is the sampled reward function and P (s' ze) is the posterior mean. The second inequality above in due triangle inequality. Let Mi be the set of plausible MDPs in episode k with reward function R (r =) and transition function P ((s z) satisfying,
Σ B'ES
1=) S (2),,
Σ ER
[((
R4 (r 2) S ()))),
where (1)
max I.N: (s.a) is chosen conservatively (Auer et al., 2008) that Mj. con-
14S (og
tains both Pi and Pi. R. and Rj with high probability. P and R are the true parameters as we defined in section 4. I. Note that B (2) is the confidence set with 8 = 1/tp. Recall the definition eh, we can define the pseudo count of state-action pair (s, as N (s, a) = || (4x) || (O)],, Then we can obtain,
Σ E'ES
Pt (8' 21) P (s' =x)
Σ E'ES
Ps (s') 22) P (8' =+)
(29)
$ 28 (z)) +2 [(PSERL) + [(peen))
We assume the length of the last episode is the biggest. Note that even the assumption does not hold, we enlarge the sum items as TKy-1- T1. This does not affect the order of our regret bound. With our assumption, because the all episode length not bigger than the last episode, that is f++1 - (4x + 71) s Tky Ti, then can obtain,
4
Tky
Σ
( t
B (zx)
(30)
Note that Eves (3' -
P 21) < 2 is always true. And with our assumption <
Ti K+tKr1 it is easy show that when No. 2 Tey -T. B6 (zx) 2 holds. Then we can obtain,
TT.
19

---

Under review as a conference paper at ICLR 2023
Ky -
KT Thy Ti
min 8 (=)) -
21(N < Toy -1)
(31)
Kr Tor
14S 145 (2NtxT) max (1, (2t)
I(N 4/ 2 Tkr vD
Consider the first part in equation 31. Obviously, the maximum of Ni, is Tir totally SA state-action pairs, therefore, the first part in equation equation 31 can be bounded as,
Because there
Kr ExsT - 21(N) < Tkr TI)= - 2(T S.A Due to Tky = Ti + KT - and Lemma
10, we get,
2(TRr - 71 51 2 + KT 71 - =
Consider the second part in including (). Due to we just consider the exploration phase in each episode, then N2 (s, a) can be calculated as follows,
31. Denote the N (s, a) is the count of (s, a) before time t(not
N (s) T < T E [tx, to + TT]. S k(t) (sh, (s)
where k(t) is the episode number where the time t is in.
In the second part in equation 31, when Ni, 2 Tkr can get,
TI, based on our assumption T₁ S 2i+KK-1
2
71 5 Ti + KT-1
2
2T1 < Ti + KT - 1 = TKr
therefore, Tkr - 2 Because Ni 2 Tkr Ti. then N (s, 2 TI For any t e (4,4 l. + w.e have
(s, S No 1/ (8, a) + n s 2N b (s,a).
Therefore (s) s 2N (s, Next 2N (s, a) follows,
bound the confidence set when Ni(s, a) s
Kr
Tay
Kr la 1-11
145 T2
3 (2+)
max (1, Ni. (=+))
Kr te
log (2NT2)
max (1, Ni (=+)
(32)
T
28.5 log (2NT2)
max (1, N2 (=))
565log(227
max (1, (z))
where the second inequality in equation 32 is due to S T for all episodes and the first equality is due to ()(ss,) a) < 2N; as.
Then similar to Ouyang et al. (2017), since Ný (z,) is the count of visits to 2g, we have
11 [[===]
max (1, (1, No (2)))
max (1,
(+)1
Σ (NN1)10)200 +
Σ
Vi
1=1
(UNBL) +2
N (z)
N
<3 Σ
V
No Nz)
20

---

Under review as a conference paper at ICLR 2023
Since E. N7 N7++(2) S T, we have
Σ (+)
53 SN Σ (1+1(()) 3VSNT.
(33)
With equation 32 and equation 33 we gel
Kr
M
2H
< (VTOSS/VTVTTT < 48HS logg
A=1
1=
Then we can bound the equation 30 as follows,
Ky
4441 -1
Σ
B
( S 245 NNNNoolggNTTT + 28A(T) + KT - T1 -1).
(34)
k=1
L=
Choose the = 1/ in Lemma 12, and based by Lemma 13, we obtain that
( Bx) (P: & B&) S 157
Then we can obtain,
K
2Eg-
Σ
The (T( + I(oeea))
$
k
6
1.
(35)
15
15
Therefore we obtain
KT
2HEg-
Σ
Th (I(o-g))) + +(meen))
$ S..
(36)
Therefore, we can obtain the bound for one arm as follows,
Eg- Σ
(P: 22) Pt (s' 2()) v (6,
(37)
AE'ES
< H 4SNH(T + Kr T1 1) 48HS log().
Next we consider the state transition of all arms. Recall that the states of all arms at time is st- Because every evolves independently, then the transition probability from state 8, state 8 as follows,
N (s
P ( Sc. 0')
st)
where Pi the true transition functions of arm i. Based by the Lemma 11 and our assumption that all arms have the same state space S, we obtain
Σ IP (sc+1 0²) - P P(t+1 0x)l < Σ Pt (s/41 (s)) P (sl41 s))
(38)
< N Pi (s/m1 |s] - P (bi41 st)l
Therefore, we can bound the RS as follows:
R < NH 4S.2
4 H(: Kr 71 1) 48SN / log()
(39)
Bounding RJ. Based on the Proposition 2, we know that
09 b1]1, S L R2 fulla + Le max (P Pa(s,;)ll2-
21

---

Under review as a conference paper at ICLR 2023
Note that the elements in the true transition matrix P and the sampled matrix Ps is between the interval (0, 1). Then based on the facts about norm, we know that
max (x.,;; Pa(8, & || Palli
Therefore, we can bound the belief error at any time follows:
|b b. - L Rall1 L2ll Palli-
(40)
Recall in the confidence for Mr. the enror bound is the same for | Rall1 and |P - Ps and based by the bound in equation 34 and equation 35, we can bound the R2 as follows:
Kr
R3 S H...
(I
Rxlli T2 -Pxlli)
Kr 1
< (L1 + H2N
(25) (ze) + (1. ((neB.i))
(41)
t=
< 48(L1 + L2N)SH /N log NT) = (L1 + L2N
4(L1+ (2N)SN + KT TI 7 1).
Bounding Rg. Based on equation 34 and equation 35, we can bound R3 as follows,
Kr
R3 = 52 HE.
Σ
Σ
[ 8) Re(. 16)1
+1
KT
1++1-1
(42)
S S HEE.
Σ
Σ
(28) (2)) + ( + (mneBn))
S H + N - 48HS NT
Combine the bound in equation 39, equation 41 and equation 42, we bound the term R3 as follows:
R3 S 48(L1 L2N)SH NT log(AT) 4(1 + L2NV) KT 71 1)
+ +L1 + L2N) + NN + 45-4 ( + Kr - 1) 48SN H VoTlog(NT
HS2 + 4
1) 4 log
(43)
=48(L1 - L,N + N L (41 L2 + N + S
+ 4(T, + N,, + N2 SS)SNN + 1-1
B.4 BOUND RA
Lemma 9. R4 satisfies the following bound
R4 S 48 + N + N + S2) man V Vog(oo(N) + (L1 L2N + N + 52)mmax
+ 4(L + L2N + N + ST mama (Ti + KT T1 - 1).
Proof. We can rewrite the R2 as follows:
Kr f-+1-1
R4
Egg
Σ
(s, b((s))
1=
11+TI+1
T
< Eg.
Σ
Σ The (s, br(s)
(t) ((()) + Σ (5,
(s,
(44)
22

---

Under review as a conference paper at ICLR 2023
where rk (s, = E, rRg (r s) is the expect reward conditioned the state of pulled arm and Og. when the reward function is Rg And r" (s, a,) = Σ, rB. s) is the expect reward conditioned on the state and with the true reward function R The equation 44 is due to the add the term Σ, rh (8,0s) by (8) and subtract it.
Denote
]
RQ = Eg-
Σ
Σ
(1) be(())
- Σ (8)
]
R1 Egg
Σ
Σ The (8, ax) (())) (r,
(x) 07(())
For RQ.
T
R29 = Eg-
Σ Th ar) (z) br(s) E nh (s, ar) (5)))
Eg-
Σ rh (x) ar) (be(s) - b(())
(45)
Σ Σ (e())) - (((0))
Bg-
where the last inequality is due to the fact Ik (s, az) S Tmax. For R1.
T
Σ Th (s) - (s ]
R = Eg
Eg
Σ Iou -r (3,,
T
< Eg.
Σ Inu (
-r- --' (s, (s,.a)))
(46)
S Eg.
Σ r [ (r s) 1 (r {)
T
< SSrmavLg-
R - R 111)
where the first inequality in 46 is due (s) 1, rk (s, a.) - r" (s, I Irx (s, - rr (s,
and the second inequality is due to Σ, [R (r (s]s) s) - R (r 8) S R R l1.
Based on the equation 41, we can bound the RQ.
R < 48(L1 + L2N) / NT log(T) + (L1 + L2 L 4[1 + LrN)SNrmadl (Ti Kr Ti - -1).
Note that for any reward function R (r) 2) in confidence set Mg. the reward function satisfics,
Σ
R Rth (r 2) s (x)
F
Then based on equation 42, we get
R1 48 maa V NTlog(NT) + 25 Nr max (Ti Kr JI -1) + Sr mazz
23

---

Under review as a conference paper at ICLR 2023
Then obtain the final bound:
R4 48(L1 L2N + S)Srmar v NNTlog(NN) 4(1 + L2N S)SNN max (Ii + KT 71 1)
+ (L1 + L2N + m)mmax
v 48(L1 N + N Sr mar v (NTlog((T) + (L1 L2N +N++ 52) maa
+ 4(L + L2N + S man (Ti + KT - -1-
where the last inequality is due S N
B.5 THE TOTAL REGRET
Next we bound the episode number.
Lemma 10. (Bound the episode number) With the convention Ti [T++] the episode number is bounded by Kr O(VT).
and T3 = Tx-1 + +1,
Proof. Note that the total horizon is The length episode k is T3 = Ti + Then we can
get,
T T2 ... TkT
= Ti + (T1 + + +..... + (T1 + Kr - 1)
KrTi +
KT 1)
(47)
KrTi + Kr(KT-1)
Therefore,
K2 (2T) KT 2T 0.
(48)
With the convention 7i
[T++1
then we get KT O(vT)
Denote C1 = L1 + N2N + N2 + S2 S² get the final regret:
H + Tmar and C3 = Ti + Kr T1 1, then we can
Rr Regret(A) R1 + R3 + R3 + Ra
S Ti ARK, HKT + SH / NT + +C +
+ 48 man V (oooT(NT) + 4C, C3S Arman Cirmas
< (nAR + HVVT + 48 + Tmax) logog(NT)
4C, (SA(ma HYTT CH Tmax)
C2S (TT + AR H +CCCCGSN)V+
Thus, we get the final Theorem.
Theorem Suppose Assumptions 1,2 hold and the Oracle returns the optimal policy in each episode. The Bayesian regret of our algorithm satisfies
Ry S 48C, / NT (T)) (nAR+ ACGSSN
where =1 L, N2 + S2 C2 Tmar H constants independent with time horizon T, Jn = 401-a)² T 4(1a)) and 62 are the minimum elements of the functions p* and R Netez
respectively. is the fixed exploration length in each episode, AR is the biggest gap of the reward obtained at each two different time, H is the bounded span, T Tmaa the maximun reward obtain each time, N is the number of arms and S is the state size for each arm.
24

---

is a Denote Ni. (s)z) as the occurence time of state Under review as a conference paper at ICLR 2023
Remark 3. (Approximation error.) If the oracle returns ca-approximate policy ih in each episode instead of the optimal policy. That is to say, r(b, (b)) + E,, P(r b, #x(b), d) (b', 0) S max, {r(b, a) E, P(r b, a, 8 (8' 8)} Ek. Then should consider the extra regret
E Exonug(TTe Te) in exploitation phase. If we control the error Ck -T-- then
can bound the extra regret as E ET TiEEK kt OOyT))Lemma 10). Thus the approximation error in the computation of optimal policy is only additive to the regret of our algo- rithm.
C POSTERIOR DISTRIBUTION
Note that we assume the state transition is independent of the action for each arm. Denote the states visited history from time 0 till of arm i as sh:: and the reward collected history is Tóa- And the action history from time evolves from 8 to s' for arm i in the state history sh.-- Hence, if the prior (P, .) is Dirich- let (o'.,,....,'"" Ss.s.), then after the observation of history sizz the posterior g (P.(s,)) so.)) is Dirichlet (o'.., + +N 8.51 (sh.)).....
....),....'. .....'..s. + Ni.s, (shz)) (Ross et al., 2011).
Similarly, if the prior g (Ri(s,))) is Dirichlet (v',,1 Virre), then after the ob- servation of reward history rhe and tb. the posterior g (R,(s,)) roar s6.t) is Dirichlet (vi.,, + Ni.,, (sb.e ro.t) ...., wa.n, + a,ry (b.):) and No, the number of times the observation (s,r) r) appears in the history (Sb2::0:))
Here we drop the arm index and consider a fixed arm. For the unknown transition function, we assume its prior (Pi) f( (("==a d¹). We consider this special prior is due to the minimum elements of the transition matrix is bigger than Next we show the details that how to update the posterior distribution for unknown /' and omit the details of unknown reward function It
P (To.t-1,3; 8t
P. (0.00-1 (P, ap:--1)
(P] 00:--11111 (0
P (ron-1, 81
P. P,a0--11 1) (P, a0:t-1 1) dPP
Σ E P (r Su:t Su:1 P. 00:1-11 1) ((P)
(ro:--1: P, P, (P, ao.- d.P
Esou (P) I[: P(s: 8i-1)
[ ( P. (0.00-1) 1) (P, a0:t-1) dP II. ((s'(s)= 1 (s0r))
Eson iEst 9 (P)
1-c:
J P (roa-1,.8)
P, P,aga-1) g (P, 40:1111))0) dP
where the last equality is due to the prior for unknown P is go (P')
f(
Pi-91 1-
6¹).
Next show the Bayesian approach to learning unknown P and R with the history (au.t-1, rua)- Since the current state 8, of the agent at time t is unobserved, we consider a joint posterior g (8t, P. R 00:-11 Fo:)) over 8t, P, and R (Ross al., 201 1). The most parts are similar to Ross
25

---

Under review as a conference paper at ICLR 2023
et al. (201 1), except for special priors.
g (8t, P. 00:--1,0::0 (0:-1) x (roat 81
P. R, a0 R, 00:t-1)
Σ
P (roce: Sua
P. R. ou: g(P R)
80:c-168
Σ
(30, P,R)
II
P(s: si-1) ssi
80.4 188
==1
P(s' s) - 61 N (soi))
Σ
9 (30, P)
I
x
E1
#D:C-1E8t
8,8'
R(r 88) - 62 Nar(S0:s
II
1-
where 9 (so, P. It) is the joint prior over the initial state so. transition function P. and reward func- tion R; Nes' (Su:) is the number of times the transition (s. appears in the history of state-action (So:t); 1 and Ner (Sa.e: Toa--1) is the number of times the observation (s, appears in the history of state-rewards (8oat To.-1).
D TECHNICAL RESULTS
Proposition 1. (Uniform bound on the bias span (Zhou et al., 2021)). If the belief MDP satisfies Assumption 1,2, then for (J(O), v(; 0)) satisfying the Bellman equation (2), we have the span of the bias function span(v, v. ==max max; vbb, mins,0es v(b, 0) bounded by H (e), where
8 2 H(e) = (a-aja (1 a) log., 1-a
1-c e/2
with a
E (0,1)
a
It is easy to check that (a) is increasing with Since is decreasing with and assume the smallest element in transitions matrix E1, the span function can be bounded by H(e)).
Proposition (Controlling the belief enror (Xiong et al., 2022c)). Suppose Assumption 1,2 hold. Given (Ra, Pk), an estimator of the true model parameters ,"). For an arbitrary reward- action sequence Fú, ie let Rr, Ru: P&) and bel., R', ,P) be the corresponding beliefs in period I under (Ry, Pk) and (R", ,)) respectively. Then there exists constants L1, L2 such that
be(,,',, -b( Rk, (h) S L, - R² 1 max (m..) (m,
where L1 4(1-11)² ? L Neft2
4(1-a1)²
61 and 62 are the minimum elements of the functions P and oi
R", respectively.
Lemma 11. (Lemma in Jung et al. (2019)) Suppose as and by are probability distributions over set for h E [K]. Then we have
K
K
K ||ok - bull
E
II
II Am
ak
ZESK [PL]
k=
Lemma 12.
(Lemma 17 in Auer et al. (2008)) For any t 2 the probability that the true MDP not contained in the set of plausible MDPs M(t) at time t. is most 5
15 that is
8
P(M & M(t)} <
15t6
Lemma 13. (Posterior Sampling (Ouyang et al., 2017)). TSEETC, ly an almost surely finite (Hs,)) stopping time. If the prior distribution (P (R) is the distribution of 0*, then for any measurable function g. E (8") He,l E [g (0x) He,.
26


Reviews:
[{"review_id": "j8F9U2151kw", "reviewer": "Reviewer_csbH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider a restless bandit problem where the states are unobserved. The authors propose algorithm Thompson Sampling with an Episodic Explore-Then-Commit (TSEETC). In the exploration phase, the algorithm uses a bayesian approach, based on mixtures of Dirichelet priors to update the unkown parameters and beliefs. In the the explotation phase the algorithm simply commits the estimated model and selects actions greedily.  This process is repeated for each episode. The authros porivde a bayesian regret guarantee of TSEETC scaling as $\\sqrt{T}$.", "summary_of_the_review": "My current recommendation of the paper is a score of 5 but I lean towards rejection, because of the following key points: \n\n- The study of restless bandit with unobserved states is appreciated, the proposed algorithm with a guarantee seems sound, but a relevant paper is not discussed (see https://arxiv.org/pdf/1910.10271.pdf ).\n- The major ingredient of TEECES to accommodate for unobserved states is the belief estimation part. More explanation and theoretical insight is needed about this part. \n- The design of TEECES relies on episodic learning and an explore-than-commit strategy. These are standard in the literature. \n- The readability of the paper can be improved\n\nMore questions on these points above. I may change my recommendation towards either acceptance or rejection depending on the authors response. ", "strength_and_weaknesses": "Weaknesses\n\n -  Assumption 1 seems to be too strong in comparison with a weakly communicating MDP, could the authors motivate why they restrict themselves to this assumption.\n-  (Literature review) I believe the paper: \"the restless hidden markov bandit with linear rewards and side information\" (see arxiv version https://arxiv.org/pdf/1910.10271.pdf ) is extremely relevant. The author did not cite this work nor discussed it. It seems an instance dependent regret bound of order $\\log(T)$ is provided. How does this result compare with $\\sqrt{T}$ bayesian regret bound provided by the authors here? A thorough comparison is needed here! \n- The readability of the paper can be improved and a clear explanation clarifying how challenging is the task of tackling unseen states is somewhat illusive in the main first 8 pages of the paper. I think the authors should focus on this aspect a bit more.\n\nStrengths\n\n+ The setting of restless bandits with unobserved states appear to be understudied to the best of my knowledge. \n+ Although I haven't thoroughly read most of the technical proofs, the results appear sound and technically correct.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "WHhlBt9kEO", "reviewer": "Reviewer_WLZD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the online Restless Bandit (RMAB) problem, where each arm of the RMAB is a Markov chain. The state space of each arm can be potentially unique, the states are assumed to be unobserved and the reward function is unknown. The goal is to design efficient algorithms that determine which arm to pull each round, so as to minimize the accumulated regret. \n\n\nThis paper proposes a Thompson Sampling based learning algorithm called TSEETC, which operates using alternating explore and exploit stages within each episode. The key contribution of the paper lies in establishing a Bayesian regret bound of O(\\sqrt(T)). Finally the paper also presents proof-of-concept empirical experiments to corroborate the theoretical results. \n", "summary_of_the_review": "Theoretically grounded paper, with good theoretical contribution improving over previous work, generally well-written", "strength_and_weaknesses": "## Strengths\n\n– I think the key strength of the paper lies in establishing the O(\\sqrt(T)) regret bound, which as the paper describes is an improvement over known bounds in the literature for RMABs. However, I think this positive also comes with the caveat that the RMAB considered here is rather simple with each arm representing a Markov Chain rather than an MDP (more on this under “weaknesses”)\n\n– The paper is very well written and is pleasurable to read. The coverage of existing related work is excellent and I believe the paper does a great job of pointing out limitations of previous work and the new contributions. \n\n## Weaknesses\n\n– Model: Markov Chains\nWhile the paper does a good job of highlighting the limitations of previous work and how all the previously known bounds are weaker than the one proposed, I think a key factor is that the setting considered makes it considerably simple: the RMAB arms are Markov chains, whose state transition probabilities are unaffected by actions taken. In most literature on RMABs, each arm is typically modeled as an MDP, which makes action planning considerably difficult. \n\n– The empirical experiments could compare against more interesting baselines: For example, the paper mentions the Liu et. al. 2010 paper in related work saying how their log(T) regret doesn’t mean much. However, their setting seems most relevant as they also consider RMAB arms with Markov chain. I’d be interested in checking how their algorithm compares against the proposed algorithm. \n\n– Although generally well written, the paper has several typos/missing words which need cleaning up (for eg: Page 2 – exiting, show that outperforms, Page 3 – methods to unknown states, reward functions) ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "VhKpfx5BUyZ", "reviewer": "Reviewer_EDfN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an algorithm, called TSEETC that aims at providing a low-regret learning algorithm for partially observable multi-armed bandits. In this paper, the decision maker faces N Markov reward processes and chooses which arm to activate at each time instant. The state of a given arm is revealed to the decision maker only when this arm is activated. As is classically done in the literature, by changing the state space, this Markovian bandit problem with non-observable states is transformed in a *restless* Markovian bandit problem with *observable* state.\n\nThe authors assume that the decision maker does not know the transition probabilities nor reward and design a learning algorithm for this setting. Under a quite strong condition that all states can ve attained with probability \\varepsilon, they prove that this algorithm has a $O(\\sqrt{T})$ regret.\n\n", "summary_of_the_review": "This paper uses a restless bandit approach to solve a Markovian bandit problem where states are only observable upon activating an arm. The authors derive an algorithm that has a good regret bound. The result is new but the novelty of the method is unclear to me.\n\n\nAfter reading the rebuttal, the contributions are clearer to me. ", "strength_and_weaknesses": "I like the problem studied in this paper. This particular restless bandit setting has been studied in the literature and can represent many problems one to send probes to estimate communication channels' quality. The regret bound is not particularly new but improves over previous work.\n\nWeaknesses:\n\nMy main problem with this paper is that the contributions are hidden: the authors explain their results but their is little comment about their relevance or their originality. For instance: the main claim of the authors is that the algorithm has a O(\\sqrt{t}) Bayesian regret. To me, it seems that any classical learning algorithm will have a linear regret for this problem (the only difficulty seems the unbounded state space if an arm is not activated for a long time). Hence: what makes this algorithm interesting and what is this specific form of explore-and-commit with multiple episodes? Is this specific to this particular restless bandits or could/should it be used elsewhere?\n\nAlso, Assumption 1 seems quite strong. In particular, it is not satisfied by the \"Dirichlet prior\" studied in the paper. It seems that this diminishes the value of the proposed algorithm because the theoretical properties are not applicable to the algorithm studied.\n\nMinor comments:\n- The paper needs an oracle to compute the policy. \n- page 4: in general, for weakly communicating MDPs, there are many functions satisfying (2) (not just up to an additive constant). Hence the span is not clearly defined.\n- On Figures 6: the authors plot the log of the performance as a function of the log of time -> using a log-log plot with proper scaling would be easier to read.\n- Is not Lemma 1 obvious?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8GnT6oAY5iL", "reviewer": "Reviewer_PrWt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on solving online restless bandits with unknown parameter and unobservable states by the proposed algorithm TSEETC. A Bayesian regret bound with $O(\\sqrt{T})$ dependency is established, which matches the lower bound dependency on $T$ and improves the existing $O(T^{2/3})$ bound derived for a related problem setting by [Zhou et al](https://arxiv.org/abs/2001.09390).  Also, simulations are showing that TSEETC outperforms existing algorithms in regret as proof-of-concept.\n", "summary_of_the_review": "Based on my current appreciation of the reget bound which I'm not fully convinced by and the current techinical presetation where misleading/confusing notations appear here and there, I give my recommendation as a borderline/ marginally weak rejection. I'd be more than happy to raise my score if mainly the **Weakness 2** and **Concern 1** can be addressed and cleared out, with notations being improved in the revision.", "strength_and_weaknesses": "**Strengths**\n1. This paper is a solid work providing theoretical understanding for a well defined problem, which has characteristics from both bandit and POMDP and is novel with no existing work addressing the exact same setting. \n2. The $O(\\sqrt{T})$ dependency, matching the lower bound dependency on $T$, is a significant improvement compared to the existing bounds of $T^{2/3}$. However, I’m not fully convinced by this improved dependency and have concern on the regret’s dependency on S and N, the number of states and arms respectively. See more detailed discuss in **weaknesses** and **concerns**.\n\n**Weaknesses**\n1. **Notations are somewhat sloppy**: To name a few which cause me the most trouble while reading:\n     - Even in the main theorem **Theorem 1**: the notation $A$ comes out of nowhere, I assume it should be the number of arms $N$.\n     - In the main algorithm **Algorithm 2**: \n            (i) Line 4, $g_{t_k} (P)$ and $g_{t_k} (R)$ could be misleading. If following **Lemma 1**, $g_{t_k} (P)$ should refer to the posterior of $P$ conditoned on the history up to $t_k$, however it could also mean $g_{t_{k-1} + \\tau_1}(P)$, which is what I assume the auther is actually referring to. This two interpretation have drastic difference since it depends on whether the data from the exploitation phase is used to update the posterior or not. \n             (ii) Line 12, it's no clear what are the obtained $\\bar r_{\\tau_1}$ and $\\bar b_{\\tau_1}$, though for this case I can guess them from the context.\n     - Some others in the main text like $M^*$, $M_k$ on page 9. Also I came across complete or repeated sentences in the appendix.  \n\nThough the paper is written in a well-organized way most of the time, notations coming out of the blue and not rigorous statements in the main algorithm make it confusing for ones who are trying to parse the algorithm and theorem to get some intuitions behind the math. Sloppy notations truly harm the clarity as well as the formality of this paper. \n\n2. **Exponential dependency on $S$**:\nIt feels the exponential dependency $S^{N}$ appering in constant $C_1$ is far from tight, given the markov chain associated with each arm is independent. To compare with, the regret by [Zhou et al](https://arxiv.org/abs/2001.09390) scales linearly with $M$, which is the number of hidden states in the common MC shared by all arms. In the restless bandit setting, the complexity should be of $M$ independent MCs with S hidden states rather than one MC with $S^N$ hidden states.\n\n**Other Concerns**\n1. **Why $\\sqrt{T}$? More Intuition is needed.**  I’m not fully convinced by why TSEETC is able to improve regret from $T^{2/3}$ by zhou, whose algorithm mostly resembles TSEETC, except for using the UCB estimator constructed with the spectral method for HMM. Based on comparing both algorithms and going through the proof sketch, what directly improves the bound is that TSEETC has a longer exploitation phase in each episode and thus there are only $\\sqrt{T}$ episodes less than $T^{2/3}$ by [Zhou et al](https://arxiv.org/abs/2001.09390). Given both algorithms do not use the on-policy data in exploitation phase (by the way I assume it happens for TSEETC because the notation is not clear), it implies posterior sampling concentrates to the ground truth model parameter better than UCB in terms of sample efficiency. It seems kind of counterintuitive based on the understanding of TS v.s. UCB from classic bandit literature, or the bottleneck of [Zhou et al](https://arxiv.org/abs/2001.09390) is to the spectral estimator around which the UCB is constructed?\n\n2. **Bayesian regret.** This concern relates to the previous one. A common understanding from the classic bandit literature is that UCB and TS based algorithms usually have regrets of the same order, and TS based algorithms have strictly worse regret bounds from a frequentist view. I’d like to know if it’s possible to have a UCB-based algorithm achieving \\sqrt{T} regret.\n\n3. **Computational cost of posteriors.** To compute the exact posterior, one has to exhaust all possible state transitions of length $\\tau_1$, which means a total number of passes exponential to $\\tau_1$,  for $\\sqrt{T}$ episodes. Though $\\tau_1$ would be of a constant order in theory, does this impose a higher computational cost when realizing TSEETC than SEEU in practice?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject