Regime Switching Bandits
Authors: Xiang Zhou
Yi Xiong
Ningyuan Chen
Xuefeng Gao
Venue: NeurIPS 2021 Poster (2021)
Keywords: regime switching
POMDP
hidden state
exploration-exploitation
spectral method
multi-armed bandit

Abstract: We study a multi-armed bandit problem where the rewards exhibit regime switching. Specifically, the distributions of the random rewards generated from all arms are modulated by a common underlying state modeled as a finite-state Markov chain. The agent does not observe the underlying state and has to learn the transition matrix and the reward distributions. We propose a learning algorithm for this problem, building on spectral method-of-moments estimations for hidden Markov models, belief error control in partially observable Markov decision processes and upper-confidence-bound methods for online learning. We also establish an upper bound $O(T^{2/3}\sqrt{\log T})$ for the proposed learning algorithm where $T$ is the learning horizon. Finally, we conduct proof-of-concept experiments to illustrate the performance of the learning algorithm.

Regime Switching Bandits
Xiang Zhou *f
Yi Xiong
Ningyuan Chen
Xuefeng Gao
Abstract
We study a multi-arman bandit problem where the rewards exhibit regime switching. Specifically, the distributions of the random rewards generated from all arms modulated by a common underlying state modeled as a finite-state Markov chain. The agent does not observe the underlying state and has learn the transition matrix and the reward distributions. We propose a learning algorithm for this problem, building spectral method-of-momeet models, belief error control in partially observable Markov decision processes and uuper-coonfidencebbumr methods for online learning. We also establish an upper bound D(T2/3</ogg] learning horizon. Finally, we conduct proof-of-concep experiments to illustrate the performance of the learning algorithm.
estimations for hidden Markov
T") for the proposed learning algorithm where T is the
Introduction
The multi-armed bandit (MAB) problem is a popular model for sequential decision making with unknown information: the decision maker makes decisions repeatedly among different options, or arms. After each decision she receives random reward having an unknown probability distribution that depends on the chosen arm. The objective is to maximize the expected total reward over a finite horizon of T periods. The MAB problem has been extensively studied in various fields and applications including Internet advertising, dynamic pricing, recommender systems, clinical trials and medicine 12 13 43 In the classical MAB problem, is typically assumed that the random reward of each arm is i.idd (independently and identically distributed) over time and independent of the rewards from other arms. However, these assumptions do not necessarily hold in practice [10). To address the drawback, a growing body of literature studies MAB problems with non- -tnstaaionaay rewards capture temporal changes in the reward distributions in applications, see e.g. 16 20)
In this paper, we study a non-stationary MAB model with Markovian gegime-switching rewards. We assume that the random rewards associated with all the arms modulated by common unobserved state (or regime) [M, : t = 1, 2..... modeled as finite-state discrete-time Markov chain. This chain makes a transition each period regardless of which arm is pulled and its transition probabilities are independent of the action chosen. Given M,- = m. the reward arm i i.i.d., whose distribution is denoted (-Imm, i). Such structural change of the environment is usually referred to regime switching in finance [33]. The agent doesn't 't observe or control the underlying state Mr, and has to learn the transition probability matrix P of {M,} as well as the distribution of reward of each arm Q(-mm, i), based on the observed historical rewards. The goal of the agent is to design a learning policy that decides which arm to pull in each period to minimize the expected regret over T periods.
'The first two authors (Xiang Zhou and Yi Xiong) have equal contribution. Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong: 191 1606962 @ qq.com
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong;
yxiong @ www.cuhk.edu..
$ The Rotman School of Management, University of Toronto; ningyuan wwwaaanchennee @ utoronto.ca
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong;
xfgao@ se. cuhk.cdu.hk
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The
models are widely used in various industries. For example, in finance, the sudden changes of market environments are usually modeled as hidden Markov chains. In revenue management and marketing, firm may face a shift in consumer demand due to undetected changes in sentiment or competition.
such cases, when the agents (traders or firms) take actions (trading financial assets with different strategies or setting prices), they need to learn the reward and the underlying state at the same time. Our setup is designed to tackle such problems.
Our Contribution. Our study features novel designs in three regards: we propose a new bandit problem formulation, develop new learning algorithm, and prove regret bounds with new techniques.
In terms of problem formulation, online learning with unobserved states has attracted some attention recently [8 19]. We consider the strongest oracle among the studies, who knows P and Q(-Im, i). but doesn't It observe the hidden state M₁- The oracle thus faces a partially observable Markov decision process (POMIP) [26] (with long-run average reward objective). By reformulating it as a Markov decision process (MDP) with a continuous belief space (i.e., a distribution over hidden states), the oracle then solves the optimal policy (mapping belief' states actions) using the Bellman equation. Having sublinear regret benchmarked against the strong oracle, our algorithm has better theoretical performance than others with weaker oracles such as the best fixed arm or memoryless policies (the action only depends on the current observation)
In terms of algorithmic design, propose learning algorithm (see Algorithm 2 with two key ingredients. First, it builds on the recent advance on the estimation of the parameters of hidden Markov models (HMMs) using spectral method-of-moment theoretical finite-sample bound of spectral estimators, while the finite-sample guarantees of other alternatives such as maximum likelihood estimators remain an open problem 30 Second, it builds on the well-known "upper confidence bound" (UCB) method in reinforcement learning [5]. There are two difficulties here as the oracle uses the optimal (belief-based) policy of the POMDP. First, the spectral method can not use the non i.i.d. samples generated from the belief-based policy due to the complex history dependency. Second, the belief of the hidden state is subject to the estimation error. Hence, we divide the horizon into nested exploration and exploitation phases. We use spectral estimators in the exploration phase to gauge the estimation error of P and Q--mm i). We use the UCB method to control the regret in the exploitation phase. Different from other learning problems, we re-calibrate the belief at the beginning of each exploitation phase based on the parameters estimated in the most recent exploration phase using previous exploratory samples.
methods 3 2 g It benefits from the
In terms of technical analysis, we establish a regret bound of O O(T2/5//og(TT) for our proposed learning algorithm where T is the learning horizon. Our regret analysis draws inspirations from [25] 35 for learning MDPs and undiscounted reinforcement learning problems, but the analysis differs significantly from theirs since there are two main technical challenges our problem.
First, to control the regret, we need to control of the error of the belief state, which itself is not directly observed and needs to be estimated. This is in stark contrast to learning MDPs 25 25) with observed
states. Specifically, we need to bound the estimation error of belief states by the estimation errors of the model parameters. In addition, since the belief state is un-observable, we also need to bound the error in the belief transition kernel, which measures the distance between the belief transition kernel under the optimistic belief MDP model (from the UCB component of our algorithm) at each episode and the belief transition kernel under the true model. These bounds are not trivial since the transition kernel of the belief state depends on the model parameters in complex way via Bayesian updating. We overcome the difficulties by building on [18] and delicate analysis of the belief transition kernel to control the errors in the estimations of belief states and the belief transitions.
Second, to establish regret bound, we need an explicit bound for the span of the bias function (also referred the relative value function) for the belief MDP which has continuous state space. Such bound is often critical in the regret analysis of undiscounted reinforcement learning of continuous MDP, but it is either taken that do not hold for the belief transitions in our setting [35 27). We overcome this challenge and bound the bias span by developing novel approach, which could be of independent interest for learning continuous-state MDPs. Specifically, we bound the bias span by bounding the Lipschitz module of the bias function for our infinite-horizon undiscounted problem (with a long-run average reward objective). To achieve this, we rely on non-trivial application of the results in (23) which provide general tools for proving Lipschitz continuity of value functions in finite-horiat discounted MDPs. One key step is to bound the Lipschitz module of the belief transitions using the Kantorovich
assumption [39 proved under Hölder continuity assumptions
2

---

metric, which allows us to establish a bound on the Lipschitz module of the value function of the finite-horizon discounted problem uniformly over the discounting factors. Exploiting the connection with the infinite-horizon undiscounted problem then yields an explicit bound on the bias span for our problem. We also mention that our bound on the bias span unrelated to the diameter of the POMDP discussed in [8. The diameter in [8] is only for observation-basee
policies, not for belief-state based policies we consider. That also explains why we need a new approach to bound the bias span.
Related Work. Studies on non-statioonary/swicchnng MAB investigate the problem when the rewards of all arms may change over time 5 20 TO 6]. Our formulation can be regarded as non-stationary MAB with a special structure. They consider an even stronger oracle than ours, the best arm in each period. However, the total number of changes or the changing budget have be sublinear in T to achieve sublinear regret. In our formulation, the total number of transitions of the underlying state linear in T, and the algorithms proposed in these papers fail even considering our oracle (See Section 5). Other studies focus on linear changing budget with some structure such as seasonality [5]. which is not present in this paper.
in which the state of each arm evolves according to independent Markov chains. In contrast, our regime-switching MAB model assumes a common underlying Markov chain so that the rewards of all arms are correlated, and the underlying state is unobservable to the agent. In addition, our work is related to MAB studies where rewards of all arms depend on a common unknown parameter or latent random variable, see, e.g., Our model differs from them in that the common latent state variable follows a dynamic stochastic process which introduces difficulties in algorithm design and analysis.
Our work is also related to the restless Markov bandit problem 21 36
22 32
Two papers have similar settings ours. [9] studies MAB problems whose rewards are modulated by an unobserved Markov chain and the transition matrix may depend on the action. However, their oracle is the best fixed arm when defining the regret, which is much weaker than the optimal policy of the POMDP (the performance gap is linear between the two oracles). Therefore, their algorithm is expected to have linear regret when using our oracle. g proposes an algorithm based on spectral estimators for learning POMDPs. Their algorithm will generally suffer linear regret in our problem setting. This is because we consider a stronger oracle which is the optimal POMDP policy, whereas their oracle is the optimal memoryless policy, i.e., a policy that only depends on the current reward observation instead of using all historical observations form the helief of the underlying state. is known that memoryless policies are in general not optimal and hence the gap between their oracle and our oracle can be linear. Note that considering the memoryless policy allows R to cireumvent the introduction of the belief entirely. Indeed, the dynamics under the memoryless policy can be viewed as finite-state (modified) HMM and spectral estimators can be applied. Instead, because we consider the optimal belief-based policy, such reduction is not available. Our algorithm and regret analysis hinge on the interaction between the estimation the belief and the spectral estimators. Our algorithm needs separate exploration to apply the spectral methods and uses the belief-based policy for exploitation. For the regret analysis, unlike [8), we have to carefully control the belief error and bound the span of the bias function from the optimistic belief MDP in each episode. The comparison of our study with related papers is summarized in Table Note that we only present the regret in
terms of T.
Papers
Oracle
Changing Budget
Regret
Best fixed action
Linear
Õ(VT)
20
Best action in each period
Finite
Ö(VT)
10
Best action in each period
Sublinear
(T2233)
Optimal memoryless policy
Linear
Ö(VT)
This paper
Optimal POMDP policy
Linear
0(12/3)
Table 1:
Comparison of our study with some related literature.
2 MAB with Markovian Regime Switching
2.1 Problem Formulation
Consider the MAB problem with arms I = [1,..., ..... There is a Markov chain (Mr} with states
M = 21,2,...,,A M) and transition probability matrix P e M XM, In period ( = 1,2,..., if the state of the Markov chain M, m and the agent chooses arm 4 i, then the reward in that period
3

---

is Rs with discrete finite support, and its distribution is denoted by i)) == P(R, E MMM m, = i). with Mmmi == R, MM; = m, 1, i]. We use μ4 := (Jmm,i) E R to denote the mean reward matrix. The agent knows M and 7, but has no knowledge about the underlying state M, (also referred to as the regime), the transition matrix P or the reward distribution ((- The goal is to design learning policy that is adapted to the filtration generated by the observed rewards to decide which arm to pull in each period to maximize the expected cumulative reward over I periods where T' is unknown in advance.
If an oracle knows P. Q0-mm, i) and the underlying state My then the problem becomes trivial as s/he would select - = a MM, in period f. If we benchmark a learning policy against the oracle, then the regret must be linear in T. because the oracle always observes M, while the agent cannot predict the transition based on the history. Whenever transition occurs, there is non-vanishing regret incurred. Since the number of transitions during [0, T is linear T, the total regret of the same order. Since comparing to the oracle knowing M, is uninformative, we consider a weaker oracle who knows P. (- m, i), but not Mr. In this case, the oracle solves a POMDP since the states Mj are unobservable and the optimal policy maps belief' states (a distribution over the hidden state) to actions. The total expected reward of the POMDP scales linearly in T. and asymptotically the reward per period converges to a constant denoted by p" under the optimal belief-based policy. See Section 2.2
For learning policy n, we denote by RT the reward received under the learning policy πT (which
does not know P. Qm-mm, i) initially) in period t. We follow the literature (see, e.g., [25] 36 I and define its total regret after T periods by
T
RT = Tp'
R
(1)
Our goal to design learning algorithm with theoretical guarantees including high probability and expectation bounds (sublinear in 7) on the total regret.
Without loss of generality consider Bernoulli rewards with mean Mmm,i E (0, 1) for all m, é. Hence jmm,i characterizes the distribution Q(- i). Our analysis holds generally for random rewards with discrete finite support. In addition, we impose the following assumptions.
Assumption 1. The transition matrix P of the Markov chain {Mi} is invertible. Assumption 2. The mean reward matrix μ = (pm,) has full row rank.
Assumption 3. The smallest element of the transition matrix == min Pij >
The first two assumptions are required for finite-sample guarantees of spectral estimators for HMMs 2]. The third assumption is needed to control the belief eπror of the hidden states by the statc-of-art methods, see [8] and our Proposition 3
We next reformulate the POMDP as belief MDP.
2.2 Reduction of POMDP to Belief MDP
To present our learning algorithm and analyze the regret, we first investigate the POMDP problem faced by the oracle where parameters P. l (equivalently Q for Bernoulli rewards) are known with unobserved states Mr. Based on the historical observed history, the oracle forms a belief of the underlying state. The belief can be encoded by a M-dimension vector b, (b.(1), ...., (.)) E B
(mm) = P(M, = ml [1. I Ri.... ... RR-1),, where B == b E R ΣM b(m) = 1 It well known that the POMDP of the oracle can be seen as MDP built on a (continuous) belief state space B, and here policy is mapping from belief states to actions, see (26).
We next introduce few notations that facilitate the analysis. For notation simplicity, we write e(m, i) == (mm.. Given belief b E B, the expected reward of arm i is a(b, i) = Em c(m, i)m(m). In period 1, given belief b, = b, I, = i, R. r, by Bayes' theorem, the belief b is updated by
Σ P(m', .m)- J (m),)))))' bem'))
b = (b. i, r), where the m-th entry is (m+) =
Σ Eimm" a (1 (0-mmm))))
be(m")
is obvious that the forward function H depends on the transition matrix P and the reward matrix u. We can also define the transition probability of the belief state conditional on the arm pulled:
T() == P(b E -16, i), where b is random due to the random reward.

---

The long-run run average reward of the infinite-horizon belief MDP following policy given the initial belief b can be written P == lim supr-> -E RT bj. The optimal (belief-based) policy maximizes P for a given b. One can show that sup, Pb is independent the initial belief (Proposition 8.2.1 (38). Therefore, we use p sup, P to denote the optimal long-ru average reward. Under this belief MDP formulation, for all E B, the Bellman equation states that
0² + u(b) = max iEI
c(b,)) + ((ab(lb, (()
(2)
where u -+ R is the bias function. It can be shown (see the proof of Proposition 2 in Appendix) that under our assumptions, p² and v(b) are well defined and there exists stationary deterministic optimal policy x² which maps a belief state to an arm to pull (an action that maximizes the right side of 2).. Finding the optimal policy for the POMDP model is computationally intractable in general 37]. Therefore, various approximate methods have been proposed to solve (2) and to find the optimal policy for the belief MDP, see e.g. [46] 42). In this work, we do not focus on this planning
problem for known model, and we assume the access to an optimization oracle that solve ( and returns the optimal average reward p and the optimal stationary policy for a given known model.
3 The SEEU Algorithm
This section describes learning algorithm for the regime switching MAB model: the Spectral Exploration and Exploitation with UCB (SEEU) algorithm. To device a learning policy for the POMDP with unknown Tl and P. one needs a procedure to estimate those quantities from observed propose the so-called spectral estimator for the unknown parameters in HMMs. However, the algorithm is not directly applicable to ours, because there is decision making involved in HMMs To use the spectral estimator, we divide the learning horizon T into nested "exploration" and "exploitation" phases. In the exploration phase, randomly select arm in each period. This transforms the system into a HMM so that we can apply the spectral method to estimate a and P from the observed rewards in the phase. In the exploitation phase, based on the estimators obtained from the exploration phase, we use a UCB-type policy to further narrow down the optimal belief-based policy in the POMDP introduced in Section 2.2
rewards. 3 2
3.1 Spectral Estimator
We introduce the spectral estimator 3 21. and adapt it to our setting. To simplify the notation, suppose the exploration phase starts from period I until period n, with realized arms {i...... in). and realized rewards {r,....,,', sampled from Bernoulli distributions. Recall / is the cardinality of the arm set I, then can create one-to-one mapping from a pair (i, into scalar (1,2,... 21}. Therefore, the pair can be expressed as a vector y E {0, 1)27 such that in each period Vt satisfies (y, )e.)
(r.me,i mi). where e, is a basis vector with its s-th element being one and zero otherwise. Let A 2 be the observation probability matrix conditional on the state: A(s, m) = PR,
4 = i m). It can be shown that A satisfies Efy] = m] = Aem and E Mr = m APT Cm- Write @ for the tensor product. For three consecutive observations Vt-1, Dt. 1t+11 define
T 1 Ely++1 & yn Blyr-1 yi] "1
De == E Ely y1-1 1 & u1-1]_ 9
M₂ = E & vel.
M2 = E T
& De @ 1c+1].
From the observations {31, .2..... }. we may construct the estimations M2 and M3 for M2 and M3 respectively, and apply the tensor decomposition to obtain the estimator ja for the unknown mean reward matrix and P for the transition matrix. This procedure is summarized in Algorithm We use Åm (respectively B,, to denote the m-th column vector of Á (respectively B). In addition, we have the following result (8) and provides the confidence regions of the estimators in Algorithm []
Proposition 1. Under Assumptions [nd 2 for any 8 E (0, 1) and any initial distribution, there exists No such that when No. with probability 1 8, the estimated ja and P by Algorithm 1
5

---

Algorithm 1 Spectral estimation of (j,, P) from the observations from the exploration phase 2 3
Input: sample size n, {8r, U2.... yn created from the rewards TTi,...,TTR and arms {d1.... in)
Output: The estimation jr,
1: For i, E { 1-1,0, 0, 1}: compute Wiy 1 21=2 btti @ ye+s.
N-2
2: For t = 2..... n 1: compute Ut-1 == Wi,oW (1,00 11-1.8 Dr = WW.-(Wo.-1)
3: Compute M2 N-z 2 Vt-1 @ Dt. M3 = N-2 E 9c-1 2 de @ y1+1.
4: Apply tensor decomposition ((2)):
B B= Tensor MM2, Ma).
5: Compute A. (W1,o(W1.n)) t.m. for each m M.
6: Return mith row vector (f²)* of ja from A..
7: Return P = (Át B) (f represents the pseudoinverse of a matrix)
satisfy
log(6 $249)
11())* - (1o) s Civ
m E M.
log(6 52448)
1P- S C21
(3)
where (p)) and (f)) are the m-th row vectors of μ and i. respectively. Here, S 21, and Cr C2 are constants independent of n.
The expressions of constants No, C1, C2 are given in Section B in the appendix. Note that parameters μ, P are identifiable up to permutations of the hidden states g
3.2 The SEEU Algorithm
The SEEU algorithm proceeds in episodes of increasing length. As mentioned before, each episode divided into exploration and exploitation phases. In episode k., it starts with the exploration phase that lasts for fixed number of periods Tı, and the algorithm uniformly randomly chooses an arm and observes the rewards. After the exploration phase, the algorithm applies Algorithm T to (re-)estimate fe and P. Moreover, it constructs confidence interval based on Proposition T with confidence level - 6g. where 6% == 5/k-3 is a vanishing sequence. Then the algorithm enters the exploitation phase. Its length is proportional to Vk. In the exploitation phase. it conducts UCB-type learning: the arm is pulled according a policy that corresponds to the optimistic estimator of fa and P inside the confidence interval. The detailed steps are listed in Algorithm 2 Note we use the UCB component in the exploitation phase instead of point estimators of μ. and for the ease of analysis.
3.3 Discussions on the SEEU Algorithm
Computations. For given parameters (14, P). we need to compute the optimal average reward p² (n. that depends on the parameters (Step g in Algorithm 2} Various computational and approximation methods have been proposed to tackle this planning problem for belief MDPs as mentioned in Section 2.2 In addition, need to find out the optimistic POMDP in the confidence region (5x) with the best average reward. In general is not clear whether there is an efficient computational method to find the optimistic plausible POMDP model in the confidence region when the unknown parameters are nigh-dimensional. The extended value iteration method in [25] does not work in our POMDP setting. This is because we cannot separately find μ and P as and T in (2) both depend on μr. and we cannot write the inner optimization in the extended value iteration to find optimistic P as a linear programming over the convex polytope (x( since T is a nonlinear function of µu and P. This issue is also present in recent studies on learning continuous-str upper confidence bound approach, see e.g. (2 for further discussions. For low dimensional models, one can discretize Cx( into grids and calculate the corresponding optimal average reward p* at each grid point so as to find (approximately) the optimistic model (μ&, Px). The discretization error does affect the regret, although it can be controlled arbitrarily well with sufficient computational capacity.
MDPs with the

---

Algorithm 2 The SEEU Algorithm
Input: Initial belief b1, precision exploration parameter 71, exploitation parameter 72
1: for = 1, 3.... do
2: Set the start time of episode k,
3: for Lx, la + 1....,, la + Ti do
4: Uniformly randomly select arm: Pl, = =
5: end for
6: Input the realized actions and rewards in all previous exploration phases Ix
( + and Rg = (Tradt (eattetr to Algorithm | to compute
ügg Px = Spectral Estimation (Ix, Rx)
7: Compute the confidence interval C. (6x) from 3 using the confidence level 6y
such that (M, P) E Cx() 2 6%
8:
Find the optimistic POMDP the confidence interval
(pt: Ps) (1 (1, P)
9:
for 1. = 1,2,.... 1 + Ti do
Update belief by 1/111 P. (U/, it, under the new parameters (JuR, Pt) end for
11:
12:
for t t4 + + l.......t., + TI v2v/ do
13:
Execute the optimal policy ((k) by solving the Bellman equation under parameters
(Jg,Pu) Px):: i, = =x(( (B²))
14:
Observe reward rt:
15:
Update the belief at /. 1 by bb+1 = He,, de,
end for
17: end for
Below we discuss its impact on regret. The discretization kicks when we want to find the optimistic POMDP in the confidence region, whose gain is denoted as p in episode k. In practice, we have to discretize the confidence region into grid points and find the optimistic POMDP among the finite set. Suppose one obtain approximate optimistic model with error Ex. that is, suppose can find model with the gain Ok 2 p EE. Then we can infer from formula (22) the appendix that the extra regret incurred due to the discretization error is given by Σx= Σre EA- = 72 Σk=1 VİER, where Eg denotes the exploitation phase in episode One can show that the order K, the number of episodes up to time T, is T2/3 Hence if the discretization error can be controlled at c c/Vk. then the extra regret is simply CT₂K, which O(T2/3). On the other hand, if the discretization error c₁ is constant > 0 in all the exploitation phases, then the extra regret incurred is of the order ΣK Vie c K3//2, which is of order cf' There is a trade-off between the additional computational complexity due to discretization and the regret bound. For instance, to control the discretization eтror at = c/ /k, the computational cost is higher compared with the case c c. In general, remains open to find efficient methods to solve the optimistic POMDP approximately in the high-dimense dineeniiniii setting. In our regret analysis below, we do not take into account approximation errors arising from the computational aspects discussed above, as [35 27).
Dependence on the unknown parameters. When computing the confidence region in Step 7 of Algorithm [ the agent needs the information of the constants C1 and C2 in Proposition | These constants depend on a few "primitives" that can be hard to know, for example, the mixing rate of the underlying Markov chain. However we only need upper bounds for C1 and O2 for the theoretical guarantee, and hence rough and conservative estimate would be sufficient. Such dependence on some unknown parameters common in learning problems, and one remedy to dedicate the beginning of the horizon to estimate the unknown parameters, which typically doesn't 't increase the rate of the regret. Alternatively, C₁ and C2 can be replaced by parameters that are tuned by hand. See Remark 3 of 8 for further discussion on this issue.
4 Regret Bound
This section presents main theoretical results the regret bound for the SEEU algorithm. We first state two technical results that are important in proving the regret bounds.
7

---

Proposition 2 (Uniform bound on the bias span). If the belief MDP satisfies Assumption 3 then for (p. v) satisfying the Bellman equation 2 we have the span of the bias function span(e) = max (b)) mingeB v(b) is bounded by ((e), where
8 (m-a + (1 +1+10 (x) loga D(c) =
8
1 - 2c
with
1- E (0, 1).
1
Recall Uy the bias function for the optimistic belief MDP in episode k. Proposition 2 guarantees that spen(u)) is bounded by D = D(e/2) uniformly in k. because Assumption 3 can be satisfied (with replaced by c/2) by the optimistic MDPs when sufficiently large due Proposition [
Proposition 3 (Controlling the belief error). Suppose AssumptionSholle Given (βt, P), an estimator of the true model parameters (p. P). For an arbitrary reward-action action sequence {ria, d1:t heal let be and by be the corresponding beliefs in period under (js, P) and (ne, respectively, Then there exists constants L, Le such that
l|b bell1 S L1 p pll1 L2ll PI(F
(4)
where I,1 min Saiinspammi Maiin Mmaxx L 4M + VM, 1I 11 is the Frobenius norm, Mmaa and Min are the maximum and minimum element of the matrix μe respectively.
4M(1-6)
We now state our first main result. The proof is given in Appendix
Theorem 1. Suppose Assumptions to 3 hold. Fix the parameter Tı in Algorithm 2 to be sufficiently large. Then there exist constants To, C which are independent of such that when T >> To, with
probability 1 - 36, the regret of Algorithm 2 satisfies
9(S + T) Top'
R S CT2/3
log
where S 21 and p" denotes the optimal long-run average reward under the true model.
The constant To measures the number periods needed for the sample size in the exploration phases exceed No arising in Proposition| [
The constant C has the following expression:
C C=3v2 (D-1+ (1+ D(1 -
L1
M3/2 + (1+
D(1 D(1-a0 -0-)
L2M
1/2 -13,,-11
2
2
+ 3T 2 D) +D+ / In 8
Here, M is the number of hidden states, C C2 are given in Proposition 1 is given in Proposi-
2 and L,, L2 are given in Proposition One can verify that C O C, M3/3)) Here we require тı to be large so as apply Proposition [ from the first episode to simplify the presentation. Theoretically, this requirement is not essential and can be removed without affecting the order of the regret. For 72, it can be an arbitrary positive integer in our regret analysis.
Remark 2 (Effect of lengths of exploration and exploitation phases regret order). In Algorithm 2
exploration phase of length Tı and exploitation phase of length T rayle in episode k. This in the end leads to (TT2/3) of the regret as the total length of exploration (and the total number of episodes) is (TT233). The intuition of such a choice is the following. After k episodes, the total length of exploration is Tyk. and hence the estimation error of the model parameters and also the belief states is of order 1/Vk. As result, needs to choose exploitation phase with length T & to balance this that the regret incurred per episode is controlled. One might wonder whether one can simply choose a longer exploitation phase of length T2k" with a 2 1/2, and then the regret order will be reduced. This not possible, and the intuition is as follows. The total number of episodes satisfies >K (T= +2) T, which yields K ~ T 0+11 The total regret incurred then at11/2
VE. T22""), which T One can immediately see that the choice of a = 1/2 actually optimal, leading to regret of order 22/3 The impact of the exper-parameteny and T2 the regret will be studied numerically in Section
is, ignoring the logarithmic factors, on the order of "K
1
5
8

---

From Theorem we can choose an appropriate 5 = 9(S+1) expectation bound on the regret. The proof omitted. Theorem 3. Under the same assumptions as Theorem 7 the regret of Algorithm 2 satisfies
T and readily obtain the following
[[ S CCT2/ / 2 T + (To + 32(S + 1))p².
Remark 4 (Lower bound). For the lower bound of the regret, consider the problem instances (equal to the number of arms): In instance i, let pm. = e all m for a small positive constant and let pmm.j = 0.5 for all m and j + i. Such structure makes sure that the oracle policy simply pulls one arm without the need to infer the state. Since the problem reduces to the classic MAB, the regret is at least ((v / IT) in this case. Note that the setup of the instances may violate Assumption 2. but this can be easily fixed by introducing an arbitrarily small perturbation to μ. The gap between the upper and lower bounds is probably caused by the split of sxplorationlexploiaaion phases in our algorithm. In the exploration phase, arms have be pulled purely randomly in order to estimate the parameters. Such naive exploration without any maximization may lead to unnecessary regret. In fact, it resembles the structure of the explore- seterre-tee--coe then-commit algorithm (Chapter 6 of (29]) for the classic MAB problem, which turns out to have the suboptimal regret (T23/3) as well. With special structures, such as a common mean for all states, special- purriose algorithms can be designed achieve the optimal rate O(T)/2). Unfortumately, our algorithm doesn't I adapt to the special structure. In fact, the spectral estimator no longer works because of the degeneracy as it cannot differentiate belween states from the observations. One natural direction that may potentially improve our algorithm and close the gap is to integrate the exploration and exploitation. We may follow the design similar to UCRL2 in [25)] in each episode, we use the parameters estimated in previous episodes and use the optimistic policy in the confidence region. The observations are then used to update the estimation. This can lower the cost for exploration because the naive exploration is replaced by a near-optimal policy when the confidence region is small. However, requires the spectral estimator to work with non L..d. samples generated by the optimistic belief- based policy. The design of the spectral estimator makes it hard to handle non i.i.d. observations with complex history dependency. This is also why (8) focused on inservation--usee policies in order to apply the spectral estimator. We may replace the spectral estimator by other estimators with better theoretical properties. The iikelihod-baser estimators may be a promising candidate [45]. but they have not been fully extended to POMDPs yet. In summary, we need better estimators for POMDP/HMMs (which is a dynamic research area itself) with finite-sample guarantees to improve the upper bound. Nevertheless, we are not aware of other algorithms that can achieve sublinear regret in our setting.
Remark 5 (General reward distribution). Our model requires the estimation the reward distribution instead of just the mean to estimate the belief. For discrete rewards taking O possible values, the regret bound holds with S OI instead of 21 for Bernoulli rewards. For continuous reward distributions, it might be possible to combine the non-parametric HMM inference method in []8] with our algorithm design to obtain regret bounds, and we leave it fituure work.
5 Numerical Experiment
In this section, we present long-run average objectives (the oracle in our problem) are computationally difficult to solve, i.e. it is challenging to find the optimal belief-based policy [4] On the other hand, while there can be many hidden states in general, often only two or three states are important model in several application areas, c.g. "bull market" and "bear market" in finance [17.. Hence we focus on small-scale experiments, following some recent literature on reinforcement learning for POMDPs (4).
experiments. Note that large-scale POMDPs with
1/3
2/3
As representative example, we consider 2-hidden-state, 2-arm setting with P =
and
3/4
1/4
[0.9 0.1
=
0.5 0.6] where the random reward follows a Bernoulli distribution. We compare our algo-
rithm with (1) c-greedy (c 0.1), non-stationary bandits algorithms including (2) Sliding- Winddow UCB (SW-UCB) 20 with tuned window size, (3) Exp3.S [5] with L = T (the hyperparameter L the number of changes in their algorithm), and (4) the optimal memoryless policy for POMDPs discussed in R To implement (4) under our model setting, we assume the reward μ and the transition matrix P are known and search for the optimal stochastic memoryless policy that maps the reward and action in the last period to discrete distribution over two arms. We also run an algorithm/oracle

---

Foid Hanay
3.2
fye506 1009
20-20.33
3.0
2.4
22-
log7 4.8
4.6
Figure 1: (a) Regret comparison of different algorithms; (b) Effect of (TI, T2) on the regret of SEEU.
that implements SEEU with known P but unknown μ. This allow value of knowing the information P. In Figure we plot the average regret versus T of different algorithms in log-log scale, where the number of runs for each algorithm is 500. The numerical experiments are conducted on a PC with 3.10 GHz Intel Processor and 16 GB of RAM. We observe that the slopes of all algorithms except for two SEEU implementations that they incur linear regrets. This is expected, because these algorithms don't take into account the hidden states. On the other hand, the slope of SEEU is close 2/3. This is consistent with our theoretical result (Theorem 3p. Similar observations are made on other small-scale examples. This demonstrates the effectiveness of our SEEU algorithm, particularly when the horizon length T' is relatively large.
better understand the
close one, suggesting
We also briefly discuss the impact of parameters тı and 72 the performance of the SEEU algorithm. For the example above, we calculate the average regret for several pairs of parameters (T1. 72). It can be seen that the choices of these parameters do not affect the order (TT2/3) of the regret (the slope). See Figure (b) for illustration.
Conclusions, Limitations and Future Research
In this paper, we study non-stationary MAB model with Markovian regime-switching rewards. We propose learning algorithm that integrates spectral estimators for hidden Markov models and upper confidence methods from reinforcement learning. We also establish a regret bound of order of O(T2/3 [oo T)) for the learning algorithm. As far as we know, this is the first algorithm with sublinear regret for MAB with unobservable regime switching.
The main limitation of our work that the regret upper bound does not match the lower bound. would be interesting to find out whether one can improve the regret upper bound O /log T). The gap in the upper and lower bounds are likely to be filled if one can resolve either of the following two fundamental open questions: (I) show the spectral method can applied to non i.i.d. samples generated from belief-based policies, and (2) establish finite-sample guarantees for other estimators (e.g. maximum likelihood estimators) of POMDP parameters with data generated from adaptive policies. We leave them for future research.
Acknowledgments and Disclosure of Funding
The authors thank the Area Chair and three anonymous referees for constructive comments and helpful suggestions. Xuefeng Gao acknowledges support from Hong Kong RGC GRF Grants 14201520 and 14201421. The research of Ningyuan Chen is partially supported by NSERC Discovery Grants RGPIN-2020-0400-
10

---

References
[1] S. Agrawal and R. Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In In Advances in Neural Information Processing Systems, pages 1184-1194, 2017.
[2] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky. Tensor decompositions for learning latent variable models. The Journal of Machine Learning Research, 15(1 1577:227332282, 2014.
[3] A. Anandkumar, D. Hsu, and S. M. Kakade. A method of moments for mixture models and hidden markov models. In Conference on Learning Theory, pages 33-1, 2012.
[4] O. Atan, C. Tekin, and M. van der Schaar. Global bandits. IEEE trunsactions on neural networks and learning systems, 29(12):5798-530 5811,1811111 2018.
[5] P. Auer, N. problem. SIAM journal on computing, 32(1):48-77 2002.
Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit
[6] P. Auer, P. Gajane, and R. Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, pages 138-158, 2019.
[7] Auer and R. Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. In Advances in Neural Information Processing Systems, pages 49-56, 2007.
[8] K. Azizzadenesheli, A. Lazaric, and A. Anandkumar. Reinforcement learning of POMDPs using spectral methods. arXiv preprint urXiv: (00X.00660207764 2016.
[9] K. Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 99(3):357-367 1967.
[10] O. Besbes, Y. Gur, and A. Zeevi. Stochastic multi-armed-bandee problem with non-stationary rewards. In Advances in neural information processing systems, pages 199-207, 2014.
[11] O. Besbes, Y. Gur, and A. Zeevi. Optimal exploration-exploiiee problem with non-stationary rewards. Stochastic Systems, 2019.
in a multi-armes setti-armed-baan bandit
[12] D. Bouneffouf and Rish. A survey on practical applications of multi-armed and contextual bandits. arXiv preprint arXiv: 1904. 10040, 2019.
[13] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[14] K. Chatterjee, R. Saona, and B. Ziliotto. The complexity of pomdps with long-run average objectives. arXiv preprint arXiv:1904.133 13360, 2019.
[15] N. Chen, C. Wang, and L. Wang. Learning and optimization with seasonal patterns. Working paper, 2020.
[16] W. C. Cheung, D. Simchi-Levi, and R. Zhu. Learning to optimize under non-stationarity. arXiv preprint arXiv: 1810.03024 2018
[17] M. Dai, Q. Zhang, and Q Zhu. Trend following trading under a regime switching model. SIAM Journal on Financial Mathematics, 1(1):780-81)) 810, 2010.
[18) Y. De Castro, E. Gassiat, and S. Le Corff. Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden markov models. IEEE Transactions on Information Theory, 4358)4775 2017.
[19] T. Fiez, S. Sekar, and J. Ratliff. Multi-armed bandits for correlated markovian environments with smoothed reward feedback. arXiv preprint arXiv: 04008, 2019.
[20] A. Garivier and E. Moulines. On upper-confidence bound policies for switching bandit prob- lems. In International Conference on Algorithmic Learning Theory, pages 174-188, Berlin, Heidelberg, 2011. Springer.

---

[21] S. Guha, K. Munagala, and P. Shi. Approximation algorithms for restless bandit problems. Journal of the ACM (JACM), 58(1):3, 2010.
[22] Gupta, G. Joshi, and O. Yagan. Correlated multi-armed bandits with a latent random source. arXiv preprint arXiv: 1808.05904 2018.
[23] K. Hinderer. Lipschitz continuity of value functions in markovian decision processes. Mathe- matical Methods of Operations Research, 3-21), 2005.
[24] M. Igl. L., Zintgraf, T. A. Le, F. Wood, and S. Whiteson. Deep variational reinforcement learning for pomdps. arXiv preprint arXiv: /806.00220 2018.
[25] T. Jaksch, R. Ortner, and Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):153-1600) 2010.
[26] V. Krishnamurthy. Partially observed Markov decision processes. Cambridge University Press, 2016.
[27] K. Lakshmanan, R. Ortner, and D. Ryabko. Improved regret bounds for undiscounted continuous reinforcement learning, In Proceedings of the International Conference on Machine Learning, pages 524-532, 2015.
[28] Lattimore and R. Munos. Bounded regret for finite-armed structured bandits. In Advances in Neural Information Processing Systems, pages 550-558, 2014.
[29] T. Lattimore and C. Szepesvári. Bandit algorithms. preprint, 2018.
[30] L. Lehéricyy Consistent order estimation for nonparametric hidden markov models. Bernoulli, 25(1):464-498, 2019.
[31] O. Madani, S. Hanks, and A. Condon. On the computability of infinite-horizon partially observable markov decision processes. In AAA198 Fall Symposium on Planning with POMDPs, Orlando, FL. Citeseer, 1998.
[32] O. A. Maillard and S. Mannor. Latent bandits. In International Conference on Machine Learning, pages 136-144, 2014.
[33] R. S. Mamon and R. Elliott. Hidden Markov models in finance volume 4. Springer, 2007.
[34] A. Mersereau, P. Rusmevichientong and J. N. Tsitsiklis. A structured multiarmed bandit problem and the greedy policy. IEEE Transactions on Automatic Control, 54(12):2787-2802. 2009.
[35] R. Ortner and D. Ryabko. Online regret bounds for undiscounted continuous reinforcement learning. In Advances in Neural Information Processing Systems, pages 1763-1771, 2012.
[36] R. Ortner, D. Ryabko, Auer, and R. Munos. Regret bounds for restless markov bandits. Theoretical Computer Science, 558:62-76, 2014.
[37] C. H. Papadimitriou and J. N. Tsitsiklis. matics of operations research, 12(3):441-450, 1987.
The complexity of markov decision processes. Mathe-
[38] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014.
[39] J. Qian, R. Fruit, M. Pirotta, and A. Lazaric. Exploration bonus for regret minimization in undis- counted discrete and continuous markov decision processes. arXiv preprint 181.0033, 2018.
[40] M. Ross. Arbitrary state markovian decision processes. The Annals of Mathematical Statistics, 39(6):21 18 (16))2218-2122. 1968.
[41] N. Saldi, S. Yüksel, and T. Linder. On the asymptotic optimality of finite approximations to markov decision processes with borel spaces. Mathemaics of Operations Research, 42(4):945- 978, 2017.
12

---

[42] H. Sharma, M. lafamia-Jahromi. and R. Jain. Approximate relative value learning for average- reward continuous state mdps. Uncertainty in Artificial Intelligence, pages 956-964, PMLR. 2020.
[43] A. Slivkins. Introduction to multi-armed bandits. arXiv preprint wrXiv:1904.07272, 2019.
[44] A. Slivkins and E. Upfal. Adapting changing environment: the brownian restless bandits.
In Conference on Learning Theory, pages 343-354, 2008.
[45] Yang, S. Balakrishnan, and M. J. Wainwright. Statistical and computational guarantees for the baum-welch algorithm. The Journal of Machine Learning Research, 18(1):4528-4580, 2017.
[46] H. Yu and D. P. Bertsekas. Discretized approximations for pomdp with average cost. In Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 619-627. AUAI Press, 2004.
13


Reviews:
[{"review_id": "zYPdx_afHKQ", "reviewer": "Reviewer_JZ7M", "summary": "In this paper, the authors consider a variation of the well-known MAB problem where the Multi-Arm bandit can be in different regimes modelled by a common finite-state Markov Chain unobservable to the learner. \nThe means of the different arms can vary in the different regimes and the learner needs to infer both the transition matrix and the reward distribution in the different states.\nThe contribution is threefold: a new bandit formulation, an algorithm for solving this new problem and the theoretical analysis of the proposed algorithm.", "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": "The study of non-stationary bandits with unobservable Markov chain has seen little treatment and the proposed solution is a first step towards a better understanding of this problem. Compared to other existing non-stationary models, the proposed approach here has a sublinear regret even if the state is changing at every time-step. I think that the proposed formulation can be of interest for the community.\n\nThe paper is overall clearly written, the authors did a good job mentioning different related works, how this work differs from others and the main technical issues due to the POMDP structure of the problem. I enjoyed reading the paper.\n\nWhile the authors clearly explain the main difficulty for the different aspects of the problem: existing tools for estimating the transition matrix requires i.i.d samples, the estimation of the means in the different states, I have the feeling that there is not much novelty in the way those issues are solved.\n\nMost of the work consists in bringing together tools from separate works (which I agree is already a contribution) but the proposed algorithm is not surprising. By completely separating the learning aspects and the tracking aspects with distinct exploration and exploitation phase most of the theoretical difficulties are avoided, limiting the novelty of this paper.\n\nI think that the paper can be improved with a better understanding of the gap between the lower-bound and the upper-bound. Does the proposed algorithm recover the \\sqrt{T} bound if the mean is the same across the different states. The experiments section is not really convincing, 50 independent replications is not enough (few hundreds would be more convincing). \nHow was the sliding window of SW-UCB tuned in the experiment ?\n\nRemarks:\nI was a bit surprised with line 9 and 10 of Algorithm 2, after the exploration phase from episode $k$, one has an estimate of the transition matrix and the different means in the different states. Then the belief is updated using all previous rounds (from 1 to the current time), not only using the information from episode k. I think discussing the complexity of the algorithm because of this step would be of interest, in particular this also implies that all the rewards and choice of arms have to be stored from the beginning of the experiment which is usually not the case for bandit algorithms.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors also did a good job for explaining the limitation of their work: \n- the computation of the optimal average reward is hard and given the confidence sets solving the optimisation program from line 8 in Algorithm 2 can be problematic.\n- they acknowledge the gap between the upper and the lower bound\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Around 6 hours"}, "extra_text": {}}, {"review_id": "ptOvfaebA9", "reviewer": "Reviewer_q6bE", "summary": "The authors study a variation of the multi-armed bandit problem where the rewards are neither adversarial nor stochastic. The rewards are actually random variables drawn from distributions that change based on an unknown state. \nThis changing state is modeled by a finite-state Markov chain, and the learner does not know the current state, nor the matrix and reward distribution.\nThe difficulty of this problem seems to be controlled by two different aspects: how strong is the oracle you compare the learner to, and how much budget has the environment to change the state that it is in.  \n\nThe oracle is the best action in hindsight, then results for adversarial MAB would apply, which give  $ \\tilde O(\\sqrt T)$ types of regret bounds. The authors consider a much stronger oracle that is aware of the transition and the reward matrix of the MDP, but not of the current underlying state.\nIn their problem setting, the changing budget is linear in T. \n\nThe authors present an algorithm for this problem and derive a O(T^{2/3}\\sqrt{\\ln{T}}) regret bound against the previously mentioned oracle.\nTheir algorithm combines several concepts such as the spectral method of moments methods to estimate the parameters of the MDP and the commonly used UCB method.\n\n\n\n", "questions": "", "limitations": "", "rating": 7, "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": "The problem of regime-switching bandits has been studied on multiple occasions in the past, but this work appears to be the first to consider a setting where the switching budget is linear while simultaneously considering a strong oracle. \nAchieving any sublinear bound for this problem is already a significant contribution to this problem.\n\nThe paper is nicely written and clear for the most part.\nThe proofs are available in the appendix, and they appear to be quite thorough.\nThey also provide experiments where their algorithm outperforms different baselines.\n\nI find that the lower bound section (Remark 4) is not very clear. It would be useful to have a clearer idea of what the suboptimality gap is for this problem. \n\n====== Minor comments and typos ======\n\nline 293 exportation -> should it rather be exploration?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly mention that a current limitation of their work is the fact that the theoretical guarantees that they derive for their algorithms are not optimal. \nIt would be good for the lower bound section ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "_GjFIFywLxS", "reviewer": "Reviewer_oiQG", "summary": "This paper studies a non-stationary and finite bandit model with Markovian regime-switching rewards, which is termed “regime switching bandit”. As mathematically formalized in the paper, in this new bandit model, the reward distributions of various arms are modulated by an underlying finite-state Markov chain, with unknown transition matrix, and whose state is assumed unobservable. The paper develops a learning algorithm called SEEU, which combines spectral estimators for the Markov chain involved with the optimism principle (together with some forced exploration). Ignoring logarithmic factors, SEEU is shown to achieve a regret of $O(T^{2/3})$, with high probability, against an oracle who knows reward distributions and the transition function of the Markov chain, but as the learner, does not observe the state of the Markov chain. ", "questions": "", "limitations": "", "rating": 7, "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": "The paper studies a novel and interesting non-stationary bandit model, which, to the best of my knowledge, does not match those in the existing literature. Despite being interesting from a theoretical standpoint, it is also well motivated by some existing applications.\n\nThe authors do a good job of precisely formalizing the “regime switching bandit” model. They provide an adequate literature review and make a fair and informative comparison between their model and other existing non-stationary bandit models. Compared to the existing literature, the presented formulation considers a stronger oracle (if not the strongest possible), who follows the optimal POMDP policy. This is in my opinion one strong aspect of the presented formulation.\n\nThe presented SEEU algorithm follows the optimism principle combined with a forced exploration strategy, and makes use of spectral estimators to estimate unknown transition probabilities and mean rewards. Forced exploration appears to be sub-optimal in many regimes, but as it turns out, for regime switching bandits avoiding that is not that easy, due to the complicated nature of the problem. \n\nTo my best knowledge, the presented SEEU algorithm, though being rate sub-optimal, is the first algorithm amenable to the presented model. I suspect that the regret of SEEU, in terms of $T$, is unimprovable, mainly because of forced exploration, as the authors mentioned already. \n\nAlthough the design of SEEU makes sense, it has some drawbacks, which include dependence on some unknown parameters, very weak regret bounds, and unimplementability --- See the detailed discussion below. I could not check all the proofs in the appendix in this limited time, but they appear correct to me. \n\nDetailed Comments:\n\n1- The regret under SEEU has a prohibitively large dependence on $\\epsilon = P_{\\min}$ as follows. The main term in the regret bound depends on $C$, which is $O(DL_1C_1M^{3/2} + DL_2C_2M^{1/2})$. Here $D = D(\\epsilon)$ grows as $O((1-\\alpha)^{-3})$, with $\\alpha$ being proportional to $1-\\epsilon$. Moreover, $L_1 = O(M\\epsilon^{-2})$ and $L_2 = O(M\\epsilon^{-3})$ – I already ignored other factors, such as $\\mu_{\\min}$, which would only worsen the bound. \nAll in all, the multiplicative factor $C$ scales as $O(\\epsilon^{-5}M^{5/2}C_1 + \\epsilon^{-6} M^{3/2}C_2) )$, where $C_1$ and $C_2$ further depend on mixing times related quantities (which could be large in some case). \n\nIn line 287, the authors report the dependence of $C$ only on $M$ and $I$, remaining silent about its prohibitive dependence on $\\epsilon = P_{\\min}$. Although $\\epsilon$ is assumed away from zero, it could be arbitrarily small, making the regret bound essentially uninformative, if not useless.  Of course, I understand $C$ would necessarily depend on $\\epsilon$, but it seems the current analysis is quite crude so that the final bound has such an unacceptable dependence. Therefore, the derived regret bound, which is already rate-sub-optimal, suffers from a crude multiplicative constant, which could come from a crude regret analysis. \n\n2- Dependence on prior knowledge. As already remarked in the paper, to determine $C_1$ and $C_2$, as well as $\\tau_1$ and $\\tau_2$, SEEU relies on some parameters of the hidden Markov chain, including its mixing time and minimal stationary distribution. All these quantities are crucial for the algorithm to work properly. This is a weak aspect of SEEU, making its applicability quire restricted. The parameters needed to compute $C_1$ and $C_2$ (or upper bounds on them) are a priori unknown, and even assuming an upper bound on them is sort of a strong assumption. I appreciate the authors’ remarks in Section 3.3 in this regard, but their idea in line 260 to remedy this would not work in my opinion, because the corresponding estimation errors might be non-trivial to control. \n\n3- Another weak aspect of SEEU is related to solving the optimistic POMDP. Assuming access to an oracle for solving (2) might be tolerated as the main goal here is to achieve statistical efficiency. However, the optimistic MDP in SEEU is totally non-trivial to solve, even assuming access to the said oracle. This further renders SEEU unimplementable. Although discretization of $\\mathcal C_k$ could be an option, the corresponding discretization error could impact the regret in a non-trivial manner. In my view, the algorithm needs further elaboration in this regard. \n\nDespite introducing a novel and interesting bandit model, the presented SEEU algorithm and its analysis, which constitute the main contributions here, are not practical or significant enough for several reasons motivated above. I therefore believe the paper could still benefit from further elaboration, and in its current status, it does not pass the acceptance threshold by a good margin. All in all, I vote for a score of 6, mainly scoring the paper due a new interesting bandit model. However, I would like to hear the authors’ responses to my raised comments. \n\nA minor comment:\n\nLine 298: the total number of episodes … satisfy => … satisfies\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "YXtb3Y0CNfH", "reviewer": "Reviewer_pMqb", "summary": "This paper studies a multi-armed bandit problem where the reward of the arm depends on the hidden state. The state changes according to the dynamics of the MDP, which means that the arms chosen in the past will influence the states chosen in the future time steps. The number of states and available actions at each state in the MDP is assumed to be finite, and the reward is assumed to be drawn from a distribution with finite support. This work studies the setting where the learner the transition matrix and the reward distribution of the arm for a given state and also the learner doesn't observe the reward. The main contribution of the paper is the algorithm that is shown to achieve T^2/3 regret in the described setting, where the regret is measured against the best policy that doesn't observe the current state and is not restricted to be a memoryless policy.", "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": "Overall, the work shares many similarities with Azizzadenesheli et al 2016, with the main difference that there the regret was measured with respect to the memoryless policy, which is a weaker result since for POMDP the optimal policy doesn't have to be memoryless. This work claims that this difficulty has been overcome and this is the first result that achieves the sublinear regret in this setting. \n\nConcerns:\n\n-The definition of \\rho* in line 182 needs more care.\n \n- In the paragraph between lines 192 and 202, there is no mention of the result of Azizzadenesheli et al 2016, which contradicts the state that the spectral estimation technique wasn't applied for the decision making. \n\n- The Theorem 1 states that \\tau_1 has to be large enough. How this quantity depends on other parameters of the problem? Nothing is said about \\tau_2 in the statement. \n\n- It is worth mentioning the result of Madani 1998, which has shown that finding the optimal policy is uncomputable for infinite horizon regret minimization. You also mention the lower bound in line 354, could you please provide the reference to it?\n\n- Looks like there is no need in Theorem 3, results of Theorem 1 and 3 can be stated as one result. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agreed that the paper provides a nice contribution by presenting a learning algorithm for the problem which competitive with a much stronger baseline than what was previously used in the literature. On the other hand, several issues were raised, most importantly that (i) the algorithm design with the forced exploration part seems suboptimal and the induced separation makes combining existing results relatively easy; and (2) the algorithm can't be implemented in an efficient way yet supposedly does not achieve the optimal rate.

Nevertheless the reviewers felt that the positives outweigh the negatives, hence I recommend acceptance of the paper. In the revised version the authors should address the several problems discussed in the review process, and provide a better and more transparent comparison to Azizzadenesheli et al. (2016) (how the algorithm relates to their method), as well as including new baselines in the experiments, such as a modified version of the algorithm of  Azizzadenesheli et al., as well as some oracle baselines which allow the experimental analysis of different parts of the algorithm.
Decision: Accept (Poster)