Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

Concerns:

-The definition of \rho* in line 182 needs more care.
 
- 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. 

- 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. 

- 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?

- Looks like there is no need in Theorem 3, results of Theorem 1 and 3 can be stated as one result. 
limitations_and_societal_impact: There is no potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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.

The 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.

The 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. 

To 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. 

Although 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. 

Detailed Comments:

1- 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. 
All 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). 

In 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. 

2- 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. 

3- 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. 

Despite 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. 

A minor comment:

Line 298: the total number of episodes … satisfy => … satisfies

limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
The 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.
The contribution is threefold: a new bandit formulation, an algorithm for solving this new problem and the theoretical analysis of the proposed algorithm.
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.

The 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.

While 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.

Most 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.

I 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). 
How was the sliding window of SW-UCB tuned in the experiment ?

Remarks:
I 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.
limitations_and_societal_impact: I think the authors also did a good job for explaining the limitation of their work: 
- 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.
- they acknowledge the gap between the upper and the lower bound
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
This 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.
The 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.  

The 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.
In their problem setting, the changing budget is linear in T. 

The authors present an algorithm for this problem and derive a O(T^{2/3}\sqrt{\ln{T}}) regret bound against the previously mentioned oracle.
Their 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.




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. 
Achieving any sublinear bound for this problem is already a significant contribution to this problem.

The paper is nicely written and clear for the most part.
The proofs are available in the appendix, and they appear to be quite thorough.
They also provide experiments where their algorithm outperforms different baselines.

I 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. 

====== Minor comments and typos ======

line 293 exportation -> should it rather be exploration?

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. 
It would be good for the lower bound section
review_title: null

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)