Switching Latent Bandits
Authors: Alessio Russo
Alberto Maria Metelli
Marcello Restelli
Venue: Accepted by TMLR ()

Abstract: We consider a Latent Bandit problem where the latent state keeps changing in time according to an underlying Markov chain, and every state is represented by a specific Bandit instance. At each step, the agent chooses an arm and observes a random reward but is unaware of which MAB he is currently pulling. As typical in Latent Bandits, we assume to know the reward distribution of the arms of all the Bandit instances. Within this setting, our goal is to learn the transition matrix determined by the Markov process.
We propose a technique to tackle this estimation problem that results in solving a least-square problem obtained by exploiting the knowledge of the reward distributions and the properties of Markov chains. We prove the consistency of the estimation procedure, and we make a theoretical comparison with standard Spectral Decomposition techniques. We then discuss the dependency of the problem on the number of arms and present an offline method that chooses the best subset of possible arms that can be used for the estimation of the transition model. We ultimately introduce the SL-EC algorithm based on an Explore then Commit strategy that uses the proposed approach to estimate the transition model during the exploration phase. This algorithm achieves a regret of the order $\widetilde{\mathcal{O}}(T^{2/3})$ when compared against an oracle that builds a belief representation of the current state using the knowledge of both the observation and transition model and optimizes the expected instantaneous reward at each step. Finally, we illustrate the effectiveness of the approach and compare it with state-of-the-art algorithms for non-stationary bandits and with a modified technique based on spectral decomposition.

Published in Transactions on Machine Learning Research (09/2024)
Switching Latent Bandits
Alessio Russo
alessio. Spolimi.
Department of Electronics, Information and Bioengineering Politecnico di Milano
Alberto Maria Metelli
abertomariu.mcteel@@yyinnnn it
Department of Electronics, Information and Bioengineering Politecmico di Milano
Marcello Restelli
maroello.rettelli@hhomimm.
Department of Electronics, Information and Bioengineering Politecnico di Milano
Reviewed on OpenReview: https:
htttpe://ppenrevieu wptp:/viee..v....... net/ forum? id=420gCXcUqR
Abstract
We consider a Latent Bandit problem where the latent state keeps changing in time according to an underlying Markov chain, and every state represented by a specific Bandit instance. At each step, the agent chooses an arm and observes random reward but unaware of which MAB he is currently pulling. As typical in Latent Bandits, we assume to know the reward distribution of the arms of all the Bandit instances. Within this sctting, our goal is to learn the transition matrix determined by the Markov process. We propose a technique to tackle this estimation problem that results in solving a least-square problem obtained by exploiting the knowledge of the reward distributions and the properties of Markov chains. We prove the consistency the estimation procedure, and we make a theoretical comparison with standard Spectral Decomposition techniques. We then discuss the dependency of the problem on the number of arms and present an offline method that chooses the best subset of possible arms that can be used for the estimation of the transition model. We ultimately introduce the SL-EC algorithm based on Explore then Commit strategy that uses the proposed approach to estimate the transition model during the exploration phase. This algorithm achieves a regret of the order (TT2/3) when compared against an oracle that builds a belief representation of the current state using the knowledge of both the observation and transition model and optimizes the expected instantancous reward at each step. Finally, we illustrate the effectiveness of the approach and compare with state-of-the-arr algorithms for non-stationary bandits and with modified technique based spectral decomposition.
1 Introduction
The Multi-Armed Bandit (MAB) [Lattimore & Szepesvári 2020 framework a well-known model used for sequential decision-making with little or no information. This framework has been successfully applied in large number of fields, such as recommender systems, advertising, and networking. In the general MAB formulation, & learner sequentially selects an action among finite set of different ones. The choice over the arm to select is made by properly balancing the exploration-exxloiitaioo trade-off with the goal of maximizing the expected total reward over horizon T and guarantecing the no-regret property, thus meaning that the loss incurred by not knowing the best arm is increasing sublinearly over time. Standard MAB literature requires the payoff of the available actions to be stationary (i.e., rewards come from a fixed distribution) in order to design efficient no-regret algorithms.
However, in many real-life applications, the stationarity assumption may not necessarily hold data may be subject to changes time. In some applications, is also possible to identify different. data distributions,

---

Published in Transactions on Machine Learning Research (09/2024)
each one corresponding to specific working regime that can be modeled as MAB. In cases of large availability of historical data appearing in the form of past user interactions, it is possible to learn offline the observation models associated with the different arms for each working regime. Exploiting the knowledge of observation models leads to many advantages over the fully online exploration setting where no prior information is available at the beginning, and a massive number of interactions is required to learn the observation models associated with each working regime. It often the case that the underlying working regime (state) cannot be directly observed and the non-stationarity of the process caused by the continuous change over time of the underlying regimes. By knowing how these regimes are characterized, it is possible to learn the dynamics of the changes by repeatedly interacting with the evolving environment. Inferring the underlying state accelerates the adaptation of the agent to the environment, thus leading to improved performances over lime.
Learning observation models independently and prior to transition models can be a viable option when computational resources are limited. Indoed, we will show in the following that spectral decomposition (SD) techniques (Anandkumar et al.) 2014), which are used to learn jointly the observation and the transition model, typically require a large mumber of samples and involve computationally intensive operations. Other scenarios where we can assume that the observation models are alrcady known are those where the models are learned offiine from samples generated by simulators. Once these models are deployed in an environment that is characterized by changes, the dynamics can be learned by interacting with the environment. We can consider, for example, the problem of resource allocation such as the electricity allocation in a specific residential area. This problem can be modeled as a Bandit where each arm represents a specific resource allocation, while the rewards represent the extent to which the allocation has been optimal. Obviously, the optimality of the allocation depends on the state of the system, which may be conditioned by several factors such environmental conditions, community trends, and seasonality.
Another possible scenario that suits our setting is the one of Trensfer Learning, where partial knowledge of the system (in our case, the obscrvation model) can be used in a context with different dynamics (in this case the transition model, representing the dynamice of the system, needs to be learned). Building on the previously mentioned scenario, we can consider using the same observation models in new residential area, with a structure analog to the first one (thus justifying the use of the same observation model) but located in different place, with potentially different weather conditions and inhabitants having different behaviors (modeled using a different transition model).
Assuming the existence of finite set of discrete latent states is a relevant choice when approaching the modeling of complex real-life problems characterized by different and recurrent working regimes. Regimes of this type can typically be observed in domains such as the financial market and online advertising, generally
marked by high volatility and specific seasonality patterns (M. et al., 2022 Heston & &Sadka 2008 Guo
et al. 2021
Considering the financial market example, these regimes might include bull markets (characterized by rising prices), bear markets (characterized by falling prices), and periods of high or low volatility. The actual regime at any given time is not directly observable (hidden state), but we can infer it from observable data. In this example, the different actions available are the decisions whether to sell or buy different amounts of stocks and the obsorvations can be the different returns, trading volumes, or stock prices.
Concerning the online advertising example, the hidden states can be represented by the interests of users, which are not directly observable. The interests may vary according to seasonal patterns, new trends, exogenous variables that modify the market, and we can model it as Markov chain. The actions are the different types of content that can be displayed to the users, while the observations may be represented by factors such as conversions or interactions with the ads (metrics such as the click-through rate could be considered).
Past works focused on this state identification problem under the assumption of knowing the conditional observation models (Maillard & Mannor 2014 Zhou & Brunskill] 2016) and defined theoretically optimal UCB algorithms. Follow-up work by Hong et al. (2020a) provided more practical Thompson Sampling algorithms, also considrrnng the problem of model misspecification and came up with an analysis on the Bayes regret.
2

---

Published in Transactions on Machine Learning Research (09/2024)
The works cited above assume that the latent state does not change during the interaction process: once the real state is identified, the agent can act optimally. Differently, we embrace a more realistic scenario and assume that the latent state can change through time. In accordance with the latent bandits setting, we assume that the learning agent is aware of the observation models of the arms conditioned on each latent state. A setting similar to ours has been considered also in Hong et al. (2020b); the key difference is that they assume to have either full or partial knowledge of both the observation model and the transition model. We instead focus on the problem of learning the transition model given the knowledge of the observation models and maximizing the cumulative reward over T interaction steps.
More specifically, our problem is modcled by assuming the existence of finite set S of different MABs all sharing the same set of finite arms I, each generating rewards (observations) in a finite set V. Each state s e represents a different instance of a MAB. At each time step t, there is a transition from latent state 8t-1 to the new latent state &t according to the transition matrix governing the process. The action az selected in will thus generate a reward conditioned on the latent state St.
Contributions and Outline We introduce the Related Works in Section 2 and the Preliminaries in Section 3 After that, in Section 4 we define the formulation of the problem that considers known Bandit instances that switch through time according to an underlying Markov process. The information about the reward distributions of the bandit instances is encoded into a suitable obscrvation matrix, while the transition model of the chain needs to be estimated. The learning objective of the agent to maximize each instant the expected instantaneous reward given the estimated belief over the current Bandit. After this part, we introduce the main assumptions that hold in our setting, motivate the reasons behind them, and show how they can be relaxed for the estimation of the transition model (Section 4.1b.
Section 5.1 presents the estimation procedure of the transition model that uses samples collected using a round-robin procedure for selecting arms. Then, we propose an offline arm selection strategy that chooses a subset of the available arms for the estimation approach, with the objective of promoting diversity between observation distributions induced by the selected arms. In Section 5.2 we detail the ST.-ECC algorithm that employs an Explore then Commit approach and uses the proposed estimation procedure for lcarning the transition model during the exploration phase.
Finally, Section shows numerical simulations on synthetic and semi-syuthetic data. We provide additional experiments that highlight the difference in performance between our estimation procodure and a technique based on SD approaches. We complement. the numerical simulation with further experiments in A Appendix A while we present a comparison with SD) approaches on the theoretical side in Appendix D
2 Related Works
Non-stationary Bandits Non-stationary behaviors are closer to worl-world scenarios, and this has induced a vast interest in the scientific community leading to the formulation of different methods that consider either abruptly changing environments (Garivier & Moulines 2011), smoothly changing environments (Trovà et al., 2020), or settings with bounded variation of the rewards (Besbes et al., 2014). It. is known that when rewards may arbitrarily change over time, the problem of Non-Stationary Bandits is intractable, meaning that only trivial bounds can be derived on the dynamic pseudo-regret. That is the main reason why in the literature, there is a large focus on non-stationary settings enjoying some specific structure in order to design algorithms with better guarantees. Non-stationary MAB approaches typically include both passive methods in which arm selection is mainly driven by the most recent feedback (Auer al. 2019 Besbes et al. 2014: Trovò et al., ) and active methods where change detection layer is used to actively perceive drift in the rewards and to discard old information (Liu et al. 2017 Cao et al. 2018). Works such as Garivier & Moulines 22011) provide a O(VT) regret guarantee under the assumption of knowing the number of abrupt changes. Other works, such as Besbes et al.] (2014), employ a fixed budget. to bound the total variation of expected rewards over the time horizon. They are able to provide a near-optimal frequentist algorithm with pseudo-regret (T2/33 and a iestrbbutioon-nddeeeenett lower bound. All the above methods are not suited for environments that switch between different regimes as they do not keep in memory past interactions but rather tend to forget discard the past.
3

---

Published in Transactions on Machine Learning Research (09/2024)
A particular type of non-stationary Bandit problem related to our work includes the restless Markov set- ting (Ortner et al. 2014 Slivkins & Uplal, 2008) where each arm is associated with a different Markov process and the state of each arm evolves independently of the learner's 's actions. Differently, Fiez et al.) (2018) investigate MAB problems with rewards determined by an unobserved Markov chain where the tran- sition to the next stale depends on the action selected at each time step, while Zhou et al. (2021) focus on MAB problems where the state transition dynamics evolves independently of the chosen action. This last work has many similarities with our setting. The main difference lies in the fact that they do not assume to know the conditional reward models and learn them jointly with the transition matrix. They make use of SD techniques (Anandkumar et al., 2014] and use this tool in regret minimization algorithm achieving a O(12/3) regret bound. Their setting is more complex than ours but involves additional assumptions, like the invertibility of the transition malrix that defines the chain. Furthermore, spectral met need a vast amount of samples in order to provide reasonable estimation errors and can hardly be used in large problems. A detailed discussion on the differences between the cstimation procodure used in Zhou ct al. (2021) and ours is presenled in Appendix [
A setting similar to the one we consider has also been described in Kontorovich et al. 2013 in the context of Hidden Markow Model. They adopt estimation approach of the transition model that shares some similarities with our estimation approach since they consider couples of consecutive observations, but their procedure is more involved and leads to worse convergence guarantees than ours.
Latent Bandits More similar lines of work are related to bandit studies where latent variables determine the distribution of rewards (Maillard & Mannor 2014 Zhou & Brunskill 2016). In these works, the unob- served state is fixed across different rounds, and the conditional rewards depend on the latent state. Maillard & Mannor (2014) developed UCB algorithms without context, considering the two different cases in which the conditional rewards are either known or ncod to be estimated. This line of work has been extended to the contextual bandit case in Zhou & Brunskill (2016) where there is an oflline procedure to learn the policies and selection strategy to use them online. HHnn et al. (020a) proposed a TS procedure in the contextual case that updates a prior probability over the set of states in order to give higher probability to the real latent state. A non-stationary variant of this setting is proposed in Hong et al. (020b)) where the latent states are assumed to change according to an underlying Markov chain. They develop TS algorithms under different cases when both the reward and transition models are completely known and when partial information about them is available. For the partial information case, they provide an algorithm basod on particle filters, which will be used for comparison in the experimental section. Differently from Hong et al. (020b), we do not assume any prior information about the transition matrix, and we learn it through interactions with the environment using the information about the reward models.
Another interesting work associated with latent bandits is the one from Kwon et al. (2022) where, differently from previously cited works, they assume an episodic setting with a fixed horizon H. At the beginning of each episode, a specific MAB instance is sampled from a fixed mixing distribution, and the agent interacts with the sampled MAB until the end of the episode without being aware of the MAB she is interacting with, The goal is to learn both the mixture weights and the reward distributions associated with each MAB. The relevant difference with our work is that they consider an episodic setting, while consider a continuous one. Another main difference is that they provide results in terms of sample complexity needed in order to learn a near-optimal policy, not taking into account the suffered regret.
In Appendix C we provide further discussion comparing our setting with related works and we report a table summarizing the differences with respect to the most related ones.
3 Preliminaries
In the following, we will present the main elements that are useful to understand what will follow. We will denote with (X) the simplex of a finite space X, and we will use the bold symbol P denote the transition matrix and the probabilities associated with a Markov chain (see Section 3.2
4

---

Published in Transactions on Machine Learning Research (09/2024)
3.1 Multi-Armed Bandits
A I-armed stochastic bandit (Lattimore & Szepesvári 2020g is a collection of distributions == (Pr(-la) e A(V) I) where II is the set of available actions with cardinality I and V is finite set of possible rewards with cardinality V. A learning agent sequentially interacts with the environment over T rounds. For each round & E (1....,T}, the learner chooses action de E I and the environment gives as output reward T V. The goal of the learner is to maximize the sum of cumulative rewards Σt= 't, which is random quantity that depends
the stochasticity of both the environment and the choice of the agent's actions. The behavior of an agent interacting with an environment is defined by policy 0 H - A that maps the observed history to actions. In general, the performance of a bandit algorithm is measured using the notion regret, which is defined as the deficit suffered by the learning agent with respect to the optimal policy. The regret of a policy 0 on a bandit instance is defined as:
T Σ rt
Rr(0)= = E
where s² defines the maximum expected reward among the available arms, while the expectation is taken with respect to the policy 0 and the stochasticity of the environment.
3.2 Markov Chains
A Markov Chain (MC) Feller 1968) is defined by a tuple M := PS, where S is a finite state space (S) 5), P: A(S) is the transition model, such that P(s, 8') denotes the probability of reaching state s' E S when being in state S, and v is the initial state distribution. We will denote with P the stochastic matrix of size S' x S representing the transition model.
A Markov chain is said to be ergodic if its associated transition matrix consists of a single recurrent class containing all states (Puterman) 1994). Ergodic Markov chains satisfy the properties of being irreducibile, thus meaning that it is possible to reach any state from any other state with positive probability in a finite number of steps and aperiodic, meaning that the chain does not follow regular, repeating pattern in its transitions.
We state the following result for ergodic Markov chains.
Proposition 3.1. Let P be the transition matrix of an ergodic Markov Chain and v an arbitrary probability vector. Then:
lim v n 11+000
where Pn represents the transition kernel induced after n steps, π is the unique stationary distribution of the chain, and the components of the vector x are all striclly posilive. By definition,, this distribulion salisfies the equation TP- n.
Since the stationary distribution of the Markov chain unique, it follows that there only one eigenvalue with unitary value (Amax = 1). Let's define the set of ordered moduli of the eigenvalues of transition matrix P as ((A1)) By denoting [Amaxl -Ar,, we have the following relation:
A = 2. AAsl
where the inequality between [Aal and D2g is strict for ergodic chains. The quantity 1 - Dael is defined the absolute spectral gap of the Markov chain and controls the rate of convergence of the chain towards its stationary distribution (Krishnamurthy 2016). In what will follow, we will use the symbol X to denote the modulus of the second largest eigenvalue, namcly X = P22]-
We define history à = (aj.ry)}=o E with Hi being space of histories of length and denote instead with H. the space of the histories of arbitrary length.
5

---

Published in Transactions on Machine Learning Research (09/2024)
4 Switching Latent Bandits
We consider to have a finite set S := {s,,..., of S = [S] different MAB instances. Each MAB is characterized by the same set of discrete arms I := fai.....ay! with cardinality = [I] and the same set of finite rewards V fri,....,rv) rvv with cardinality V |VI. Whenever an arm a E is pulled, corresponding reward E V is generated by the environment. We consider each reward r V bounded for simplicity in the range [0. 1]. The distribution of rewards Pr(-Is, a) conditioned on MAB instance and action is categorica In particular, we assume to know the parameters characterizing these distributions and to store this information into matrix O E RVVx which we call action observation matrix. Each row of this matrix encodes a specific action-reward pair (a, r) E EIx V. Then, for any pair (a, E 1 x V and any state E S, we have:
(((a,)), r), = Pr(
(2)
where Pr(r|s, a) represents the probability value of observing reward r while pulling action a from MAB s. At each step i, only one MAB & is active, and it determines the reward r, that is received when the agent pulls action az. The choice over the active MAB is determined by an underlying Markov chain with transition matrix P E R More precisely; the probability over the next active MAB 8t+1 is determined by the distribution P(s,,) (S) and is thus independent of the chosen action ag. The setting we consider assumes that the agent is not able to observe the active MAB at cach step, and the objective is to learn the transition matrix P characterizing the underlying process while knowing the observation ion model O.
Learning objective As alrcady seen, the agent does not observe the sequence of MAB instances, but by deriving an estimate of the transition matrix P, a belief representation over the current active MAB E S can be defined. In the following, we will report the update rule of the belief vector b, A(S) under the knowledge of the observation model O and the transition model P. The update of the belief derives from the typical correction and update step of the Bayes rule, where the correction step adjusts the current belief b, using the reward Y2 obtained by pulling arm 0g and the prediction step computes the new belief b simulating a transition step of the chain. More formally, for each clement b141(8) (s) of the belief vector by41, the update step is as follows:
bs+1(s) = Eves ((s') ri).s) Exee (0
After having defined the update rule of the belief vector b,, we introduce, for cach action a E I, vector m(aa E IR where element pla, 8) referred to state 8 E 8 contains the expected reward obtained when pulling arm a while being in state s. More formally:
((a, 8) = _()))))).))
(4)
rEV
Given the belief b. over the states, the objective of the agent is to pull the action that maximizes the instantancous expected reward such that:
a arg max
Eu(a, s)b,(5) arg max (M(a), bb),
(5)
ael
#E8
where (..) denotes the scalar product between the two vectors. From the considerations reported above, we are now ready to formulate the notion of regret we try to minimize:
Ry Σ max (u(a), by) - max (p(a), ba), ael
(6)
ael
where b, and 6, denote the belief vectors updated using the real transition matrix and the estimated one P respectively. Here, used symbol R to characterize the regret defined in Equation in order to discriminate from the standard notion of regret R. introduced in Section 3.1
II Appendix we will see how this formulation can be extended to continuous distributions.
6

---

Published in Transactions on Machine Learning Research (09/2024)
4.1 Assumptions
We need now to introduce some assumptions that should hold in our setting: Assumption 4.1. The smallest element of the transition matriz defining the Markov chain is sin P(s,5)>> 0.
This assumption ensures non-null probability of transitioning from any state to any other in one step. It is possible to show that under this assumption, the induced Markov chain is ergodic, thus guarantecing the presence of a unique stationary distribution, as shown in Proposition [.1] Under the ergodic condition, the chain is able to reach its stationary distribution π geometrically fast, regardless of its initial distribu- tion Krishnamurthy (2016). Our assumption on the minimum entry is not a necessary condition for the two aforementioned motivations but sufficient one. However, we require this condition bound the error between the belief computed using the real transition matrix and an estimated one. This result is presented in Proposition E.6 and builds on the original result present in De Castro et al. (2017). This one-step reach- ability assumplion is always present in works dealing with partial observability that show results in terms of regret in non-episodic scenarios. Notably, it has been used in similar works such as Zhou et al. (2021) i [jiang ctt al. 2023 Mattila et al. (2020) and also employed in the more complex POMDP sctting (Xiong ct al. 2022 1. Works not using this assumption either do not need it since they use a less powerful class of policies such as memoryless 7 [Azizzaennesheli al. 2016) or they directly impose an error of the estimated belief that adequately decreases with the number of collected samples (Jafarnia Jahromi et al., 2022).
Assumption 4.2. The action observation matriz O E IV is full column rank.
This second assumption, instead, is related to the identifiabiliyy of the parameters of the problem and has been largely used in works using spectral decomposition techniques (Zhou al. 2021 Azizzadenesheli all 2016 Hsu et al. 2012). A robust version of this assumption, called weakly-revealing is also present in other works involving learning parameters in POMDPs (Liu et al. 2022: Jin et al. 2020 In the following, we will see that this is a necessary condition in order to recover matrix P. Indeed, we will see that the error of the estimation procedure has an inverse dependency on the minimum singular value miin (O) of the action
observation matrix O and through Assumption 4.2 we implicitly require that Omin (0) >
5 Proposed Approach
As clarified in the previous section, our goal is to minimize the regret formulated in Equation 6 this objective, we need to define a good estimate P of the transition matrix that in turn results in a more accurate update of the belief vector by. We will now show how the transition model can be learned by exploiting the knowledge of the observation model O (Section 5.1 and we will present. the SL-EC algorithm that makes use of the presented estimation approach in order to minimize the regret (Section 5.2
To reach
5.1 Transition Model Estimation
The Markov chain estimation procedure presented in this section holds under weaker assumptions than those presented in Section 4.1 In particular, we relax the one-step reachability assumption (Assumption 4.1 and we only require the ergodicity of the transition matrix P.
Stationary Distribution of Consecutive States matrix that defines the chain. Building on Proposition 3.1 an ergodic chain admits a unique stationary distribution म.
We start with a consideration about the transition
From the uniqueness of this distribution, it can be easily shown that there exists as well a unique stationary distribution on consecutive states that we represent with matrix W E A(8?) having dimension S x S.
"A memoryless policy defines the action to choose only based on the last observation seen. For this reason, does not require notion of belicf over the states.
"The weakkly revealing assumption defines lower bound the minimum singular value of the observation matrix O, such that miin (O) 2 a.
7

---

Published in Transactions on Machine Learning Research (09/2024)
Its elements are obtained as 8's, (s)) By defining with II ( the diagonal matrix of size S x S having values of the stationary distribution л along its diagonal, we can express matrix W of the stationary distribution of consecutive states as follows:
W IP,
which is obtained by multiplying each row of the transition matrix P by the associated probability value of the stationary distribution. The reverse procedure that allows retrieving matrix P from W is defined by the following equation:
8(8,8') Ev'es (ss,"")
P(s.s')=
(7)
which shows that the rows of matrix P are obtained by normalizing the rows of matrix W such that they sum to 1, as required for stochastic matrices.
The next paragraph shows how the matrix W stationary distribution of consecutive states relates to the stationary distribution of consecutive rewards.
I: we will denote with d, A(V) the stationary distribution of rewards conditioned on pulling action when the chain has mixed" Vector d, has dimension V and its elements are characterized as follows:
Stationary Observation-State Relation Let's choose
dr(r) = ()((s)))))
VrEV,
(8)
#E8
where we recall that (s) represents the probability of state taken from the stationary distribution of the chain and r(), represents the probability of obscrving reward r while pulling action a and being in state 8. similar rationale can be extended to consecutive rewards (r,r") E V2 conditioned on pulling a couple of consecutive actions (a, a') 12 We denote with de A(V²) the distribution over consecutive rewards conditioned on pulling the pair of arms (a,a'). We represent it with a vector of size 82 and define it follows:
da (r,r)))))))))))))))))))))))))))) = Σ ((a,r),,) ((d)))))8) 8',
Vr,r' EV,
(9)
S,s'ES ESS
where we recall that matrix W E A(92) represents the stationary distribution of consecutive states. By considering the different vectors of type da,a', we define vector:
d = (du.a) (a.a
(10)
where the term on the right denotes a concatenation of vectors da,a' for all (a, 1 and the resulting vector d has size 1222.
We define now new matrix A E xS* to which we will refer as reference matrix. It extends the information contained in the action observation matrix O considering consecutive pairs of elements and it is characterized as follows:
A O,
(11)
where symbol @ refers to the Kronecker product (Loan 2000). Since assume knowledge of the observation model O, we can directly compute the reference matrix by applying the Kronecker operator.
As a last step before presenting the main result, we transform matrix W and vectorize it to obtain vector w A (S?) having dimension S2. By using the quantities just defined, we can finally reformulate Equation g so that it can extended to all pairs of actions. Using vector notation, we have:
d Au.
(12)
TTe distribution states in mixed chain corresponds by definition stationary distribution 6rehe vectorization operation used here creates new vector by concatenating each row matrix W.
8

---

Published in Transactions on Machine Learning Research (09/2024)
Basically, this equation relates the stationary probability distribution of consecutive observations with the stationary cratiinary_probbbllly probability distribution of consecutive latent states. The next paragraph shows how to obtain an estimate d of vector d, from which, by reversing Equation 12 an estimate ve of the stationary distribution of consccutive states can be computed.
Transition Model Estimation We will now see how to concretely compute an estimate of w using Equa- tion 12. Going back to vectors aa we can build an estimate da,a' a for each pair of actions (a,a') IP For this purpose, let's take pair of action (a, a') and repeatedly pull it. We can count the number of occurrences of each pair of observed rewards (r,)") E 2 and store this information in suitable count vector no,a of size V2. We can casily derive an estimate of vector da,a' as follows:
da,a' na.a N
(13)
where N represents the number of times the pair of consecutive arms (a, a') has been pulled.
We propose an estimation procedure that pulls each pair of arms (a,a') E T in a round-robin fashion and stores the observed pairs of rewards in the corresponding vector count na,a' The choice of round-robin approach highlights interesting properties in the theoretical analysis, will be shown later in Section G By executing N different rounds, thus meaning that each pair of arms is pulled exactly N times and by exploiting the knowledge of the reference matrix A, we can derive:
w A A n
(14)
N'
where A the Moore- Penrose inverse of reference matrix A, while vectors d and n are obtained by concatenating the different vectors da and na,a' as also done Equation 10 The second equality is derived by extending Equation 13 to the concatenated vectors. The stated equation shows that the estimation procedure involves solving a simple least-square problem, which can be done in computationally efficient
way.
Once an estimate T is computed, the corresponding matrix W can be obtained by reverting the vectorization operation and eventually an estimate P of the transition model is computed using Equation 7
The pseudocode of the presented estimation procedure is detailed in Algorithm
We acknowlodge that other approaches can be devised for choosing the action policy used during estimation. Some approaches have been devised for the Latent Bandit setting such as the one in Kinyanjui et al. (2023) which face a pure exploration problem. However, their method is tailored for the stationary setting and they update their policy as new information is acquired. Instead, in our scenario, it is necessary to select prior an action policy and keep it constant during the interaction with the environment: approaches that work in this direction and that could be potentially used in our setting are those based on Experimental Design Kiefer & Wolfowitz 1960).
5.1.1 Arm Selection Strategy
In Algorithm I we propose a simple approach for choosing the arms to pull. Each pair of arms is indeed pulled the same number of times during the exploration phase by using a deterministic approach. However, it can be shown that the estimation procedure proposed in Scction 5.1 can be extended to a more ficxible arm selection policy. We may randomize the arm choice by assigning non-uniform probabilities to each pair of arms. In principle, this aspect allows exploiting the knowledge of the known reward distribution of each arm, for example, giving the beginning a higher probability to the pairs of arms that are more rewarding, For example, this arm selection policy may be beneficial if we plug our estimation approach into an iterative two-phase exploration and exploitation algorithm, as the one used in Zhou et al. 2021).
Offline arm selection In problems with a large number of available arms, a round-robin approach among all possible pairs of arms may be detrimental as it considers all arms equivalently. There may be cases where some actions are less useful for state identification. The extreme case is an action that induces the same observation distribution for all the Bandit instances. Indeed, pulling that action will not provide any additional information on the current. MAB and the effect will only be to slow down the estimation
9

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 1: Estimation Procedure
Input: Action Observation matrix O, mumber of rounds N
Build Reference matrix A using Equation 11
Initialize vector of counts na with zcroes for all (a, d') E I?
k = 0
while k < N do k=
foreach (a, a') E I2 do
7
Pull arm a = a
Observe reward T1
Pull arm a++1 a' Observe reward ri+1 =r na (r, (r,r') ) na (r, +1
10
11
12
1=1+2
18 Compute da,a' for all (a, a') E If using Equation 13
Obtain d by concatenating all the different d' (as done in Estimate w from Equation 14
10
16 Reshape vector s to obtain matrix W
17 Compute P using Equation
procedure. In general, actions that induce simillar observation distributions for all the MABs will provide less information with respect to actions that induce highly different. distributions for all the MABs.
A more convenient approach, in this case, would be to select a subset of different arms to be used during the exploration phase. Intuitively, the arm selection procedure tends to promote diversity among arms conditioned on the latent states, with the objective of increasing the identifiability capabilities deriving from the actions. It turns out that we are able to get an understanding of the information loss we suffer by selecting specific arms, given the knowledge of the action observation matrix O. In particular, in Section f that the quality of the estimation highly depends the
devoted to the theoretical analysis, we will minimum singular value miin (O) of the action observation matrix O. We thus this value drive the choice of the best subset of arms to use.
In particular, by fixing a number J < I of arms to use among those available, the choice over the best subset of size can be done as follows. We consider all the possible subsets of arms of size J, and for cach of these subsets, we derive a reduced action observation matrix G of size JV x S that is obtained by simply removing from the original matrix O all the rows associated the actions not belonging the considered subset of arms. Having defined new action observation matrix for each generated subset, good candidate subset of arms is the one yiclding the reduced action observation matrix G with the highest of min (G). Understandably, this approach implies that the reduced action observation matrix G' derived from the subset of selected arms should be full-column rank, thus satisfying Assumption
5.2 SL-EC Algorithm
Having established an estimation procedure for the transition matrix P, we will now provide an algorithm that makes use of this approach in a regret minimization framework.
We consider a finite horizon T for our problem. We propose an algorithm called Switching Latent Explore then Commit (SL-EC) that proceeds using an EC approach where the exploration phase is devoted finding the best estimation of the transition matrix P, while during the exploitation phase, we maximize the instantancous expected reward following the formulation provided in Equation 5 The exploration phase
lasts for To episodes, where Ty is optimized w.r.t. the total horizon T, will be seen in Section pseudocode of the ST.FEC Algorithm is presented in Algorithm 2
The
10

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 2: SL.-EC Algorithm
Input: Observation model O, Exploration horizon To, Total horizon T
Define number of rounds N To/21 SstimatiionProcedureee
P =
(Algorithm
bo UniformOverStater.
Compute br, using samples collected during Algorithm
To while t s T do
at = arg max (M(a), ba)
Observe reward Ti
D AydateBelict fel rt) (Equation 1+1+1
10
Basically, the exploration phase pulls each pair of armss in round-robin fashion and uses the estimation procedure presented in Algorithm [ When the exploration phase is over, an estimation of the transition matrix P is computed. After that, a belief vector by is initialized by assigning a uniform probability to all the states (Line 3), and it updated using Equation and the estimated P, considering the history of samples collected from the beginning up to To (Line 4p. Finally, the exploitation phase starts, as described in the pseudocode of the algorithm.
6 Theoretical Analysis
Having defined the estimation procedure of the transition model in Section 5.1 and having introduced the SL-EC algorithm, we will now provide theoretical guarantocs for them.
6.1 Analysis of Estimation Procedure in Algorithm
We start with concentration bound on the transition matrix P computed from the estimation procedure in Algorithm D As already highlighted, this estimation procedure only requires the ergodicity of the chain, thus relaxing Assumption
Lemma 6.1. Suppose Assumption 4.2 holds and suppose that the Markov chain with transition matric P ()
is ergodic, such that Tmin == min.gs क (s) > O with ग E (S)) being the stationary distribution of the chain. By assuming that the choin starts from an arbitrary distribution v E A(8), by pulling each pair of orms in a round-robin fashion for N rounds and using the estimation procedure reported in Algorithm 1 we have that
with probability at least 5 the estimation error of the transition matriz P will be:
2S(C + log log(C((//))) (1-
|P 1P-P11- <
(15)
o2 min (0) Miin
where [|- represents the Frobenius norm Golub Van Loan 1996.. o Tmin (0) represents the minimum singular value of the action observation matrix O, constant C' defined as C' C= 1| Do where represents the vector of the element-wist ratio between the two probability distributions, while À represents the modulus of the second highest eigenvalue of matrix P. As reported in the statement of the Lemma, N denotes the number of times each pair of arms is pulled, thus meaning that the stated error guarantee holds when interacting with the environment for a total number of 2 steps, where the I term ariscs from the total number of pairs of arms while the constant value 2 accounts for considering pairs of arms.
As a last remark, we note that the presented Lemma assumes that the chain starts from an arbitrary distribution. This fact lcads the further constant in the bound. Indeed when the chain starts from the stationary distribution, we have
This result comes from Proposition E.4 that uses a concentration
result derived from Fan et al. 2021
11

---

appearing in Published in Transactions on Machine Learning Research (09/2024)
Here, we will provide sketch of the proof of the presented Lemma. A more detailed version of this proof is reported in Appendix B
Sketch of the proof. The proof of Lemma 6.1 builds on two principal results. The former comprises a relation that links the estimation error of the matrix P with the estimation error of matrix W, while the latter is a concentration bound on the estimated W from the true one W. Concerning the first result, we can say that:
2 W W
P- P
(P.1)
Tmin
This result follows from sequence of algebraic manipulations and makes use of Lemma F.1 Appendix
We now need to define a bound on w F. In order to bound this quantity, we resort to the vectorized versions and w of the two matrices and use the result ||
W |
|| -612. We proceed follows:
w TT. 1|2 = (d dì)
< ||2|dd d d||2
1
||d.
d|22 oinn (0) l| dl|2.
(P.2)
Omin (A)
where the first equality follows from Equation 14 In the inequality instead, we used the consistency property for the spectral norm of matrix A while in the last equality we used a property of the Kronecker product for which it holds that:
miin (A) mmin m (0) o min (O).
Let's consider the estimation error of cach vector da,a' that represents the stationary distribution over consecutive rewards conditioned pulling the pair of arms (a, a²). From Equation 10 we know that by concatenating each of these vectors, we obtain the quantity d. Thus, by definition, we have:
|| 2l12
Σ (a,a")
|da, 1o
(P.3)
The estimation error of each da,a' can be bounded by using result shown in Proposition E.4 E.4and inspired by the work of Hsu et al. (2012). It bounds the estimation error of calegorical distributions when the observed samples derive from a Markov chain. With probability at least 1 - 6/12 we have that:
(1+ C log((CC))
||da, Jn <
N
The exponential lerm 272 that appears to the modulus of the second highest eigenvalue has been introduced thanks to the adoption of the round-robin procedure for the choice of combinations of arms. Notably, each pair of arms is pulled every 2/2 steps of the Markov Process, thus resulting in a faster mixing of the chain. For more details, please refer to Appendix B
By combining the last obtained bound with P2 and P.3 and using a union bound for the estimation error of all vectors of type d' we have that with probability at least 1 - d:
X212
T2(C + Dog(CT2/0)
||w 1 11 S _ oiin
(0)
V
1- x213
N
I
2(C +lg (C12/8))
02 min
(0)
(1-X
Ultimately, by putting together the bound in P.1 with the one just obtained, we are able to obtain the final result stated in the Lemma.
12

---

Published in Transactions on Machine Learning Research (09/2024)
Dependency on the Problem Parameters Lemma 6.1 shows the dependencies of the result obtained from the proposed estimation approach. The estimation error scales almost linearly with the number of arms 1. This may seem concerning when dealing with problems involving a high number of arms. However, we have already observed in Section 5.1.1 that when the number of arms is large, is possible to reduce this dependency by using the arm selection stralegy detailed in Section 5.1.1 We further have a dependency on the minimum value of the induced stationary distribution Tmin; which common in the partially observable setting.
Concerning instead the dependency on the minimum singular value m (O), it is related to Assumption 4.2 It defines the amount of identifiability of different states given the information provided by the observations. This dependency characterizes the class of weakly-revealing POMDPs and is unavoidable in order to have a tractable problem (Chen et al. 2023).
The dependency on the modulus of the second largest eigenvalue À derives from the fact that observed samples are not independent but come from a Markov chain. The dependency on this term is thus unavoidable and we believe it to be light. for the considered setting. It derives from recent. results from the work of Fan et al.) (2021) which improves over the existing concentration results of samples coming from Markov Chains. For thorough comparison of our estimation approach with standard Spectral Decomposition techniques, we refer to Appendix D
Continuous Reward Distributions The presented setting tackles the case of discrete observations. It appears that handling continuous reward distributions within this framework not feasible and this is true if we apply our approach as is. However, we can discretize the observation distributions and consider the discretized distribution as categorical one. The process of discretization involves dividing the continuous observation distributions into predetermined number U of distinct consccutive intervals. Each interval is assigned a probability value that represents the likelihood of a sample drawn from the continuous distribution and belonging to that interval. Throughout this discretization procedure, we can define an action observation matrix of dimension IU x S and then apply Algorithm Appendix
More details on this aspect can be found in [
6.2 Analysis of the SL-EC Algorithm
Having established the results on the estimation matrix P, we can now provide regret guarantees for Algo- rithm 2 We recall that the oracle we use is aware of both the observation model O and the transition model P but does not observe the hidden state. As shown in the definition of the regret in Equation 6 it builds a belief over the states, using the formulation defined in Equation 3 and selects the arm that maximizes the expected instantaneous reward. The derived regret upper bound is provided in the following:
Theorem 6.1. Suppose Assumptions 4.1 and 4.2 hold and suppose that the Markou chain with transition matric P has stalionary stationary distribution E A(S). By assuming that the chain starls from an arbitrary distribution E (SS) and by considering finite horizon T, there erists constant To, with T >> To, such that with probability at least 1- -- 6, the regret of the SL-EC Algorithm satisfies:
2/3
2L12
(oo++(CCP)))
R(T 2
(16)
min (0) Tiin
X2F)
where L= - 18(1-))3 + V is a constant that used bound the error in the estimated belief (more details in Proposition E.6 in Appendix E}. The presented regret has an order of (TT233) w..tt. the horizon T, as common when using an Explore then Commit algorithm. A detailed proof of this theorem can be found in Appendix B. The presented bound on the regret can be achioved by appropriately choosing the exploration horizon To- More specifically, we set it. follows:
2/3
2LTT2 min (T)
S(C - log(C12/8)) (1 --222)
To
(17)
02
To compute To, we need to have information about the minimum value of the stationary distribution Rmin and about the modulus of the second highest eigenvalue X. Tf they are not available, slightly different
13

---

Published in Transactions on Machine Learning Research (09/2024)
(a)
(b)
5 states
0.16
low Owin
hight Oven
Estimation Error
0.35
15 states
Estimation Error
0.12
0.25
0:10
0.15
0.06
0.05
0.04
les
Figure (a) Difference between the estimated and real transition matrix with an increasing number of samples. The metric used is I1-Iee (10 runs, 95% c.i.) (b) Difference between real and estimated transition matrix using two different subsets of arms of size arms from the available problem with states. The metric used is I| (10 runs, 95% c.i.).
version of the bound can derived so that To can optimized by only requiring the knowledge of from Assumption 4.1 More details are reported in Section B.3 of Appendix
Choice of Explore then Commit The choice of an Explore then Commit type of algorithm is mainly due to the simplicity of this approach. We believe that this scaling of the regret with respect to time cannot further improved within the considered class problems and this mainly due to the identifiability condition reported in Assumption 4.2 Indeed this class problems includes worst-case instances where we are guaranteed to acquire information only by pulling all the available arms, thus a forced exploration phase is always required. A similar approach has been used in Zhou et al. (2021): they devise the SEEU algorithm which alternates bet ween full exploration and full exploitation phases reaching O(T)2/3 regret guaranlee. Instead of the phased algorithm, we opted for an EC approach.
7 Numerical Simulations
In this section, we provide numerical simulations on synthetic and semi-synthetic data based on the Movie- Lens 1M (Harper & Konstan 2015) dataset, demonstrating the effectiveness of the proposed Markov chain estimation procedure. Specifically, we show the efficiency of the offline arm selection procedure described in Section
5.1.1 and conduct comparison between our ST-FC Algorithm and several baselines in non-stationary settings. In Section 7.3 we provide additional experiments that highlight the performance difference be- tween our approach and a modified technique based on Spectral Decomposition. Finally, in Appendix A we provide different sets of experiments showing the regret comparison under different exploration horizons (Appendix A.2 and we provide some numerical simulations showing the estimation error incurred when the provided observation model is misspecified (Appendix A.3)
7.1 Estimation Error of Transition Matrix
The first set of experiments devoted showing the error incurred by the estimation procedure of the transition matrix in relation to the number of samples considered and the set of actions used for estimation. The left side of Figure [ illustrates the estimation error of the transition matrix given different instances of Switching Bandits with increasing number of states. In particular,
fix the number of total actions I= 10 and number of obscrvations V = 10 and consider three instances with S = 5, S 10 and S 15 number of states. As expected, we can see that as the number of states increases, the problem becomes more complex, and more samples are needed to improve the estimation. Figure [ reports the Frobenius norm I| of the error between the true and the estimated transition matrix. We can notice that the estimation procedure is particularly efficient leading to low error values even with a limited number of samples, as can be observed from the steep error drop appearing in the first. part of the plot.
14

---

Published in Transactions on Machine Learning Research (09/2024)
(a)
(b)
SW-UCB
17000
25000
8R(())
2000
(R(L)
20000
6000
10000
2000
5000
20000
40000
60000
20000
100000
25000
50000
75000
100000
125000
15000C
175000 200000
Figure 2: Plots of regret comparing the SL-EC Algorithm with some non-stationary bandit algorithms using: (a) synthetic data with parameters S 3 states, actions and V 5 observations (5 runs, 95% e.i.): (b) data from MovieLens assuming S states, I = 18 actions and V observations (5 runs, 95% c.i.).
The right plot in Figure I instead, shows the estimation error obtained by using different subset of arms. As mentioned in previous sections, it not always beneficial to use all the available actions during the estimation procedure, but selecting subset of actions may be preferable. Furthermore, we show that by selecting specific subsets of arms, we can improve the estimation w.r.t using other subsets. For this experiment, we consider J = 3 arms among the I = 8 available for a Switching MAB instance with $ = 5 states. We then identify the optimal subset of arms of size J and initiate the estimation process using the selected subset. In order to find the best one, we generate all matrices type G, as described in Section 5.1.1 and choose the matrix with the highest mmin (G). The subset of arms generating that matrix will be used for estimation. The estimation error of the best subset of arms is represented in the plot with the red line, while represent in green the estimation error of the subset having the lowest min (G). The figure clearly exhibits the performance dilference between the two choices, thereby validating our claims. Additional details about the characteristics of the matrices used in the experiments are provided in Appendix A.1
7.2 Algorithms Comparisons
In this second set of experiments, we compare the regret suffered by our SL-EC approach with other algo- rithms specifically designed for non-stationary environments. Following the recent work of Zhou et al. (2021) we consider the subsequent baseline algorithms: the simple e-greedy heuristics, a sliding-window algorithm such as UCB (Garivier Moulines 2011) that is generally able to deal with non-stationary settings and the Exp3.S (Auer et al.) (2002) algorithm. The parameters for all the baseline algorithms have been properly tuned according to the scttings considered. For the specific experiments considered, we adopted scaled values for the exploration horizon To w.r.l. the result derived from the theory
It is worth noting that, unlike our SL-EC algorithm, the baselines do not assume knowledge of the obser- vation model or the underlying Markov chain. In contrast, our approach utilizes the observation model to estimate the transition matrix and to update the belief over the current state. Additionally, we compare our approach with a particle filter algorithm proposed in Hong et al. (2020b) about non-stationary Latent Bandits. They consider two settings: one with complete knowledge of both the observation and transition models and another that incorporates priors on the parameters of the models to account for uncertainty. We compare against a mixture of these two settings by providing their algorithm with full information about the observation model (as it is for our case) and an informative prior about the true transition model. The comparison is made in terms of the empirical cumulative regret Ri( averaged over multiple independent runs.
We used the value suggested by Equation 17 divided by (10L)2/3, Scaling the values obtained by thcory common in the scientific litcrature and mostly translates into bigger multiplicative constants in the final regret bound similar bounds but holding with smaller probahility. For our case, under the reduced exploration value, regret presented in Theorem 6.1 increases by multiplicative factor of (10I)1/3.
15

---

Published in Transactions on Machine Learning Research (09/2024)
7.2.1 Synthetic Experiments
These experiments have been conducted on various problem configurations with different numbers of states S, actions 1, and observations V. The regret results for one configuration are shown in Figure 2(a). From the figure, is clear that most of the bascline algorithms display a lincar time dependence for the regret. This is expected since these algorithms do not take into account the underlying Markov chain that governs the process. The particle filter algorithm, despite being given good initial prior on the transition model, does not achieve the same performance of SL-EC in the long run. Conversely, we can notice quite different behavior for our algorithm that, in line with an Explore then Commit approach, initially accumulates large regret and then experiences a drastic slope change when the exploitation phase begins. The regret shown in each plot is the average over all the runs. For further information regarding the generation of the transition and observation models, as well as the hyperparameters used for the bascline algorithms, we refer the reader to Appendix A.1
As remark, our algorithm outperforms the others when the absolute spectral gap 1 À of the chain has values closer to 1. Indeed, if this is not the case, simple exploration heuristics such e-greedy would lead to comparable performance. A clear example is when the transition matrix P defining the chain assigns equal probability to all transitions. In this scenario, all states can be considered independent and identically distr distributed, and we get no advantage from the knowledge of the matrix P over the use of an algorithm such as e-greedy.
7.2.2 MovieLens Experiments
We also perform some experiments on semi-synthetic data. based MovieLens 1M (Harper & Konstan 2015), well-known collaborative filtering dataset where users rate different movies each belonging to a specific set of genres. We adopt a procedure similar to the one used in Hong et al.] (2020b). The datasct is initially filtered to include only users who rated al. least 100 movies and the movies that have been rated by at least 100 users. After that, we combine the available information in order to obtain a table where each row contains the mean of the ratings for each observed genre for each user gene--gerr--atinng table). the user didn't observe any movie belonging to a specific genre, the cell is empty. From the obtained matrix, we select 70% of all ratings as training dataset and use the remaining 30% as test set. The sparse matrices obtained are completed using least-squares matrix completion (Mnih & Salakhutdinov 2007 using rank 10 and leading to a low prediction ion error.
Having defined the appropriate rank, we use the predictions on the empty cells of the original user-genre rating matrix to fill the entire table. We define a switching bandit instance by using the notion of a superuser inspired by Hong et al. (2020b). We use k-means to cluster users using the rows of the user-genre-raling matrix. The users belonging to the same cluster define superuser that embeds a set of users with similar tastes. The information about the users belonging to the same clusters is then combined and used to generate categorical distributions on the rating, given each superuser and each possible genre (our actions). We choose k = 5 for the number of superusers as it is the one that yields clusters with more similar dimensions, and we use 1 = 18 for the actions since it represents the number of identified genres. The number of observations V = 5 corresponds to the 5 possible ratings that a movie can get. The transition matrix that governs the dynamics with which superusers alternate defined by giving higher probabilities to transitions to similar states and also giving higher weights to self-loops in order to avoid too frequent changes. The interaction goes as follows. At each step, a new superuser 8, is sampled based on 8t-1 and the transition model. The agent chooses an action a corresponding to a genre to propose and gets rating that is sampled from the catogorical distribution defined by vector (((a,)) )).
As for the synthetic case, our algorithm is compared to other baselines. From Figure b), we can see that our SL-EC still outperforms the other baselines in the considered horizon. However, we highlight that our goal is not to beat the basclines since the comparison is not fair as most of them do not take into account the underlying Markov process, but we aim to show the difference w.r.t. other algorithms belonging to state of the art More details about the experiments Movielens are reported in Appendix A
16

---

Published in Transactions on Machine Learning Research (09/2024)
Table 1: Comparison with Nearly Deterministic Models.
2 States
3K samples
6K samples
9K samples
15K samples
SD O
0.0493 (0.0097)
0.0379 (0.0103)
0.0335 (0.0097)
0.0259 (0.0081)
SD T
0.0342 (0.0185)
0.0189 (0.0097)
0.0149 (0.0032)
0.0101 (0.007)
Alg. 1
0.0234 (0.015)
0.02 (0.0203)
0.0119 (0.009)
0.008 (0.0032)
3 States
150K samples
300K samples
600K samples
900K samples
SD O
0.0165 (0.0044)
0.0113 (0.0036)
0.0097 (0.0033)
0.0085 (0.0018)
SD T
0.1547 (0.0517)
0.154 (0.0532)
0.1544 (0.0534)
0.1541 (0.0532)
Alg. 1
0.0066 (0.0026)
0.0046 (0.0012)
0.0037 (0.0018)
0.0031 (0.0008)
5 States
150K samples
300K samples
600K samples
900K samples
SD O
0.0681 (0.0178)
0.0513 (0.0111)
0.0354 (0.0127)
0.0283 (0.0082)
SD T
0.24409 (0.0633)
0.2484 (0.0584)
0.243 (0.0603)
0.2407 (0.0601)
Alg. 1
0.0283 (0.0054)
0.0195 (0.0036)
0.0137 (0.0033)
0.0115 (0.0034)
7.3 Numerical Comparisons with a Modified Spectral Decomposition Technique
The focus of this last set of experiments is to show the difference between a. modified Spectral Decomposition (SD) technique and our estimation approach detailed in Algorithm 1 Among the various applications, SD techniques are typically used for learning with Hidden Markov Models (HMM) where no information about the observation and transition model is provided. Zhou et al. 2021) make use these techniques to get an estimation of both the observation and the transition model. is important to highlight that SD methods are hardly used in practice because of their computational and sample complexity. Indeed, both the related works of Zhou et al. (2021) and Azizzadeneshelii et al. (2016) include only proof-of-coneee experiments with 2 hidden states and 2 possible actions.
To make the comparison fairer, we consider a modified SD technique that is provided with information about the observation model in order to help the estimation process, as will be briefly explained. The original SD technique to which we refer follows the procedures highlighted in Anandkumar et al. (2014) for HMM and makes use of the Robust Tensor Power (RTP) method for orthogonal tensor decomposition. In typical SD techniques, data is collected by sampling an action at each time step and updating the computed statisties with the observed realization. With the presented modified SD technique, at cach step, do not simply updale the statistice with the observation obtained when pulling the arm, but we give information about the observation distribution for all the available arms, with this information being conditioned on the underlying current state. In this way, it is like pulling all the arms at each step and receiving full information about their associated reward distributions, given the underlying state.
We perform various experiments by fixing the number of arms (1 20) and the number of possible rewards (V= for each arm and by changing the number of states. Each experiment is performed over 10 different runs, where for each run transition and observation model are generated. For each experiment, our estimation procedure uses 3 arms among the 20 available, which are selected using the offline arms selection strategy. The transition and observation matrices are created in two different ways: the former focuses on nearly-determinisicc matrices (Table I while the latter considers more stochasticity for both of them (Table D.
The results of the experiments are structured in the following way. Each of the two Tables contains mini- tables representing sets of experiments characterized by different number of states. By fixing the number of states for the experiments, each mini-table shows three rows: the first one (indicated with SD O) contains the Frobenius norm of the estimation error of the observation matrix with the modified SD technique, the sccond row (indicated with SD T') represents the Frobenius norm of the estimation error of the transition matrix with the modified SD technique, while the third row represents the Frobenius norm of the estimation error of the transition matrix computed with Algorithm D For each experiment, we report the mean error over the 10 runs and one standard deviation between parenthesis. The modified SD technique clearly enhances the accuracy of estimating the observation model compared to standard SD approaches: this aspect is
17

---

Published in Transactions on Machine Learning Research (09/2024)
Table 2: Comparison with Higher Model Stochasticity.
2 States
150K samples
210K samples
270K samples
SD O
0.1500 (0.2639)
0.1411 (0.2741)
0.1455 (0.2665)
SD T
0.1488 (0. (0.1536)
0.1699 (0.1742)
0.1576 (0.1702)
Alg. 7
0.0145 (0.0175)
0.0145 (0.0134)
0.0125 (0.0103)
3 States
300K samples
600K samples
900K samples
SD 0
0.2987 (0.2128)
0.3078 (0.2177)
0.2594 (0.2309)
SD T
0.3916 (0.2804)
0.4425 (0.2637)
0.4187 (0.2728)
Alg. 1
0.0077 (0.003)
0.0063 (0.0023)
0.0052 (0.002)
evident from the relatively low estimation errors observed in the SD O rows. We present this information to illustrate that the comparison between our estimation procedure and SD approaches is now more fair due to the modified SD technique employed. Having clarified this aspect, we focus on the estimation error of the transition model between the two different methods: this information is indeed separated from SD O by a dashed line. We show the experiments with lower estimation errors in bold.
The results of this first set of experiments are reported in Table | As alrcady anticipated, both the obser- vation and transition matrices are almost deterministic, hence having high probability on specific observa- tion/state and low probabilities for all the others. For transition matrices, the highest probability is assigned to the probability of staying in the same state. Near-determinism is defined to simplify the problem by making states more distinguishable. By inspecting the results, it is clear that Algorithm [ outperforms the modified SD technique in almost all the scenarios. Comparable results are only achieved in the experiment with 2 states.
Table 2 reports instead the experimental results obtained using both transition and observation matrices with less peaked distributions, thus higher stochasticity. The discrepancy between our approach and the modified SD technique is more evident in this scenario. This aspect can be justified by the theoretical comparison reported in Appendix D where it can be obscrved that, compared to our estimation approach, SD techniques have dependency of higher order on the minimum singular values of both the observation and the transition models. Thus, when the observation matrix is more stochastic, its o (O) typically decreases, and this aspect results a higher estimation error. Indeed, can be noticed that the estimation error is significant and the number of samples required to perform this set of experiments is much higher than that used for the mearin-deteriinistic case. Experiments involving a higher number of states instead were not able to reach convergence with number of samples of the order 10 and, by trying to increase this quantity, there were memory space problems with the used hardware (Intel i7-11th and 16G RAM).
Again, we would like to emphasize that SD techniques are explicitly meant to work in a different setting, intrinsically more complex, where no information about either the transition or the observation model is provided. However, with this set of experiments, we wanted to show that if, instead, we have knowledge about the observation model, directly using this information in the SD techniques does not lead to performances comparable our approach.
8 Discussion and Conclusions
This paper studies Latent Bandit problem with latent states changing in time according to underlying unknown Markov chain. Each state is represented by different Bandit instance that is unobserved by the agent. As common in the latent Bandit literature, we assumed to know the observation model relating cach MAB to the reward distribution of its actions, and by using some mild assumptions, we presented a novel estimation technique using the information derived from consecutive pulls of pairs of arms. As far as we know, we are the first to present an estimation procodure of this type aiming directly estimating the stationary distribution w of consecutive states. The approach is easy to use and does not require specific hyperparameters to be set. We provided an offline arm selection that selects the best subsets of arms to speed
18

---

Published in Transactions on Machine Learning Research (09/2024)
up the estimation process. We analyzed the dependence of the parameters the complexity of the problem, and we showed how our estimation approach can be extended to handle models with continuous observation distributions. We used the presented technique in our SL-EC algorithm that uses an Explore then Commit approach and for which we proved a O(T2/3) regret bound. The experimental ovaluation confirmed our theoretical findings showing advantages over some baseline algorithms designed for non-stationary MA and showing good estimation performances even scenarios with larger problems. Furthermore, we compared our approach both empirically and theoretically (Appendix D with SD techniques, taking into account the differences between the two procedures.
We identify different future rescarch directions for the presented work, such as designing new algorithms that are able to exploit the flexibility in the exploration policy determined by the defined procedure, allegedly in an optimistic way. It may also be interesting to deepen the understanding of this problem when dealing with continuous reward models, trying to design optimal ways to discretize them order to reach faster estimation performances. We could also consider the extension to the continuous state space sctting (e.g., linearMDPs)): among the main challenges in this scenario, consider the adoption of different representation for the reference matrix that would otherwise not be computable with infinite states and the redefinition of the stationary distribution over consccutive states. In such a case, it might be beneficial to estimate the feature functions directly by means of which the linear MDP is defined. Finally, it might be worth considering a contextual version of the proposed setting. According to the assumptions made, for example, whether the context discrete or continuous or whether it related or not to the latent state, this aspect may bring another dimension to the observation space. Redefining the reference matrix by taking this feature into account will likely lead to more informative components and help with the estimation process.
References
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky. Tensor decompo- sitions for learning latent variable models. J. Mach. Learn. Res., 15(1):2773-25)) 2832, jan 2014.
Peter Auer, Nicolò Cesa-Bianchs Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit. problem. STAM Journal on Computing, 32(1):48 77, 2002.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with unknown number of distribution changes. In Proceedings of the Thirty-Secome Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 138 158, 2019.
Kamyar Azizzadenesheli, Alessandro Lazaric, and Anima Anandkumar. Reinforcement learning of pomdps using spectral methods. Tn Annual Conference Computational Learning Theory, 2016.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed- problem with non-stationary rewards. In Advances in Neural Information Processing Systems, 2014.
Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xic. Ncarly optimal adaptive procodure with change detec- lion for piecewise-slationary bandit. In International Conference on Artificial Intelligence and Statislics, 2018.
Fan Chen, Huan Wang, Caiming Xiong, Song Mei, and Yu Bai. Lower bounds for learning in revealing POMDPs. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 5104 5161. PMLR, 23 29 Jul 2023.
Yohann De Castro, Elisabeth Gassial, and Sylvain Le Corlf. Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden markov models. 1EEE Transactions on Infor- mation Theory, 487: 4777, 2017.
Jianqing Fan, Bai Jiang, and Qiang Sun. Hoeffding's inequality for general markov chains and its applications statistical learning. Journal of Machine Learning Research, 22(139)::-35, 2021.
William Feller. An Introduction to Probabilily Theory and its Applications Vol. I. Wiley, 1968.
19

---

Published in Transactions on Machine Learning Research (09/2024)
Tanner Fiez, Shreyas Sekar, and Lillian J. Ratliff. Multi-armed bandits for correlated markovian environ- ments with smoothed reward feedback. arxiv: Learning, 2018.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory, pp. 174-188, 2011.
Gene H. Golub and Charles F. Van Loan. Matric Computations. The Johns Hopkins University Press, third edition, 1996.
Jiaxing Guo, Qian Sang, and Niklas Karlsson. Adaptive scasonality estimation for campaign optimization in online advertising. In 2021 American Control Conference (ACC), pp. 1450-1455, 2021.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), dec 2015.
Steven I.. Heston and Ronnie Sadka. Seasonality in the cross-section of stock returns. Journal of Financial Economics, 87(2):418-445, 2008. ISSN 0304-405X.
Joey Hong, Branislav Kveton, Manzil Zaheer, Yinlam Chow, Amr Ahmed, and Craig Boutilier. Latent bandits revisited. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Newral Information Processing Systems, volume 33, pp. 13423-13439. Curran Associates, Inc., 2020a.
Joey Hong, Branislav Kveton, Manzil Zaheer, Yinlam Chow, Amr Ahmed, Mohammad Ghavamzadeh, and Craig Boutilier. Non-stationary latent bandits. CoRR, 200//2202.00866,, 2020b.
Danicl Hsu, Sham M. Kakade, and Tong Zhang. A spectral algorithm for learning hidden markov models.
Journal of Computer and System Sciences, 78(5):1460-1480, 2012. ISSN 0022-0000. JCSS Special Issue: Cloud Computing 2011.
Mehdi Jafarnia Jahromi, Rahul Jain, and Ashutosh Nayyar, Online learning for unknown partially observable mdps. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, 2022.
Bowen Jiang, Bo Jiang, Jian Li, Tao Lin, Xinbing Wang, and Chenghu Zhou. Online restless bandits with unobserved states. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Chi Jin, Sham M. Kakade, Akshay Krishnamurthy, and Qinghua Liu. Samplc-effciinn reinforcement learning undercomplete pomdps. In Proceedings of the 34th International Conference on Newral Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
J. Kiefer and J. Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960. doi: 10.4153/ D0.4153/CJM-- CC/CCCJMMM90 11MM-1960030-11
Newton Mwai Kinyanjui, Emil Carlsson, and Fredrik D. Johansson. Fast treatment personalization with latent bandits fixed-confidence pure exploration. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL httpp:://openrevier. htt.://www......eeeeeoooooraaaaa
Expert Certification.
Aryeh Kontorovich, Boaz Nadler, and Roi Weiss. On learning parametric-outple hmmss. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 702-710, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Vikram Krishnamurthy. Portially Observed Markov Decision Processes: From Filtering Controlled Sens- ing. Cambridge University Press, 2016.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. Tractable optimality in episodic latent mabs. In Advances in Neural Information Processing Systems, volume 35, pp. 23634- 23645. Curran Associates, Inc., 2022.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
20

---

Published in Transactions on Machine Learning Research (09/2024)
Fang Liu, Jookyung Lee, and Ness B. Shroff. A change-detection based framework for piccevise-stationary multi-armed bandit problem. In AAAT Conference on Arlificial Intelligence, 2017.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary?, 2022.
Charles Van Loan. The ubiquitous kronecker product. Journal of Computational and Applied Mathematics, 123(1):85 100, 2000. ISSN 0377-0427. Numerical Analysis 2000. Vol. III: Linear Algebra.
Krishnadas M., K.P. Harikrishnan, and G. Ambika. Recurrence measures and transitions in stock market dynamics. Physica A: Statistical Mechanics and its Applications, 608:128240, 2022. ISSN 0378-4371.
Omid Madani. On the computability of infinite-horizon partially observable markov decision processes. 12 1999.
Adalric-Ambrye Maillard and Shie Mannor. Latent bandits. 31st International Conference on Machine Learning, ICML 2014, 1, 05 2014.
Robert Mattila, Cristian Rojas, Eric Moulines, Vikram Krishnamurthy, and Bo Wahlberg, Fast and consis- tent learning of hidden Markov models by incorporating non-consecutive correlations. Hal Daumé IIT and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6785 6796. PMLR, 18 Jul 2020.
Colin McDiarmid. On the method of bounded differences, pp. 148-188. London Mathematical Society Lecture Note Series. Cambridge University Press, 1989.
Andriy Mnih and Russ R Salakhutdinov. Probabilistic matrix factorization. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advonces in Neural Information Processing Systems, volume 20, Curran Associates, Inc., 2007.
Ronald Ortner, Daniil Ryabko, Peter Auer, and Rémi Munos. Regret bounds for restless markov bandits. Theoretical Computer Science, 558:62-76, 2014. ISSN 0304-3975. Algorithmic Learning Theory.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley; Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
Giorgia Ramponi, Amarildo Likmeta, Alberto Maria Metelli, Andrea Tirinzoni, and Marcello Restelli. Truly batch model-free inverse reinforcement learning about multiple intentions. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Proceedings Machine Learning Research, 2020.
Aleksandrs Slivkins and Eli Upfal. Adapting to a changing environment: the brownian restless bandits. In Annual Conference Computational Learning Theory, 2008
Francesco Trovò, Stefano Paladino, Marcello Restelli, and Nicola Gatti. Sliding-window thompson sampling for non-stationary settings. Journal of Artificial Intelligence Research, 68:311-364, 05 2020.
Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps, 2022.
Li Zhou and Emma Brunskill. Latent contextual bandits and their application to personalized recommen- dations for new users. In Proceedings of the Twenty-Fiit International Joint Conference on Artificial Intelligence, IJCAF16, pp. 3646 3653. AAAT Press, 2016. ISBN 9781577357704.
Xiang Zhou, Yi Xiong, Ningyuan Chen, and Xueleng Gao. Regime switching bandits. In A. Beygelz- imer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
21


Reviews:
[{"review_id": "MejcFx9aan", "reviewer": "Reviewer_yNot", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe problem setup is interesting, and the paper is well-structured. The writing is comprehensive, and notations are clear. Experiments are reported on synthetic and real data.\n\nWeaknesses:\n\nAlgorithm and Regret Bound: I am concerned about the $O(T^{2/3})$ regret guarantee, which is standard for Explore and Commit algorithms, and the analysis is straightforward. I am missing the novelty of the algorithmic ideas and analysis techniques, especially given the work is predominantly theoretical. I am wondering why the authors did not try a UCRL type approach (UCB-based method) to achieve $O(\\sqrt{T})$ bound? This appears to be a major limitation of the work. In fact, few related works, e.g., Azizzadenesheli et al. (2016) achieved $O(\\sqrt{T})$ regret, and it is unclear the contribution of the current work over these related works.\n\nIt would be beneficial to have a table listing all the related works, their modeling assumptions, objectives, and performance guarantees to understand the precise contribution of this work.\n\nDependencies on the problem parameters: In the final regret bound of Theorem 6.1, the dependency of the problem-dependent parameters, e.g., $\\epsilon$, $\\sigma_{\\min}$, $\\lambda$, etc., requires more discussion. Are these dependencies tight? For example, I am surprised by the $O(1/\\epsilon^2)$ dependency; why do we need to explore all $P(s,s')$, especially if the rewards associated with these states are small? Seems non-intuitive. Some discussions on the tightness of the derived regret bounds would be useful.\n\nAssumptions: Following from the above point, it will also be important to understand the necessity of the assumptions, e.g., Assumptions 4.1 and 4.2 --- can they be relaxed if the dependencies on the parameters are not tight? Also, how practical are these assumptions for real-world problems? Can you give a real-world problem scenario where such examples are satisfied?\n\nIn general, the motivation of the setting needs to be explained better; the one-paragraph discussion on the financial market and online advertising is not enough to understand the exact mapping of the problem framework to these practical examples; a better and more detailed explanation would be useful.\n\nMinor: The citation Kwon et al. (2022) seems to have typos. Check the formatting of the bibliography.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel approach to address the switching latent bandits problem, where an agent must solve multiple multi-armed bandit (MAB) problems evolving according to an unknown underlying Markov chain. The proposed explore-then-commit algorithm effectively handles this challenge by estimating the transition matrix during exploration and selecting actions optimally based on the believed latent state during exploitation. The theoretical analysis establishes a regret bound of $O(T^{2/3})$, demonstrating the algorithm's competitiveness compared to existing approaches. Empirical evaluations validate its effectiveness through numerical simulations and real data experiments, showcasing superior performance over alternative methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please considered the detailed feedback provided under Weaknesses above, specifically the concerns around regret optimality, modeling assumptions, novelty against existing techniques (with a table), and justifying motivations.", "broader_impact_concerns": "The work is predominantly theoretical, I do not see any specific broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "MH4fBnWeI9", "reviewer": "Reviewer_vJgb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n- This paper studies an interesting problem that, to the best of my knowledge, is underexplored in the literature.\n- The paper is well-written. \n- The estimator seems novel. \n\n### Weaknesses:\n- The approach requires full knowledge of the reward model for each latent state which is restrictive. Are there any real-world problems where this is true? Does your algorithm work well even when we only have access to an approximation of the reward distributions ?\n- The $T^{2/3}$ scaling is undesirable and I think it might be unavoidable when using explore-then-commit. Why go for explore-then-commit rather than approaches based UCB or Thompson sampling that usually enjoys much better regret? Are there any particular challenges with applying these approaches to this problem?\n- Both $\\sigma_{\\min}$ and $\\pi_{\\min}$ can be very small in practice and my understanding is that this could make the bound in Thm 6.1 vacuous. This since it could happen that $T_0 > T$ even for moderately large $T$.  It seems like this undesirable scaling is due to the fact that we try to perfectly estimate $P$ and do we really need to do that to have good regret?\n- The regret bound holds only under the assumption that the chain starts from its stationary distribution. The authors state that similar results can be shown without this assumption. Why not have this stronger result in the paper?\n- The empirical evaluation can be improved. \n    - SL-EC is not evaluated using the budget suggested by Eq 17 and instead uses scaled values. The amount of scaling is not presented in the paper. I understand that what is suggested by theory often is conservative in practice but having a version of SL-EC that uses the budget suggested by Eq 17 would help making sense of the theoretical results. \n    - Plotting the R(t) for a single horizon, as in Figure 2, is not very informative. We know already that the algorithm has linear regret up to $t=T_0$ and then either zero regret or with ,low probability, linear regret. I suggest that the authors also plot the regret over several horizons, i.e $R(T)$, to illustrate the dependence in $T$ (since the budget $T_0$ is a function of $T$). This would tell us for which horizons the SL-EC has an advantage over baselines. \n    - The confidence intervals in the empirical section looks too good to be true given the small number of seeds , e.g. see Fig 2 where only 5 seeds are used.  I wonder if this is due to the fact that the cumulative regret has a multimodal distribution and the CI wrongly assumes a Gaussian distribution. Note that with probability $1-\\delta$ the algorithm suffers no regret after $T_0$ and with probability $\\delta$ it suffers linear regret. Thus, with probability $(1-\\delta)^k$, k being the number of seeds, the sample variance in instant regret for any $t>T_0$ will be zero which will result in an incorrect CI around cumulative regret that has a very small width. I suggest that the authors run the experiments using more random seeds.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a latent bandit problem where the latent state evolves according to an unknown Markov chain. The authors assume perfect knowledge of reward distribution of each arm, conditioned on the latent state. They introduce a novel estimation method of the transition matrix that leverage this knowledge. This result is later used in the proposed explore-then-commit algorithm SL-EC. This algorithm enjoys a $\\tilde{O}(T^{2/3})$ regret bound and the authors illustrate that the algorithm has an empirical advantage over baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have the following requested changes.\n\n\n### Critical\n- Discuss whether the scaling in $\\sigma_{\\min}$, $\\pi_{\\min}$, and $T$ is optimal or if it can be improved. If possible, please state a lower bound on the cumulative regret. \n- Address the weaknesses in the empirical section (see weaknesses). An experiment where the reward model is misspecified would also be nice to see.  \n\n### Would improve the paper\n- I think the paper would benefit from a discussion on applications where the reward model is perfectly known. \n- It would improve the theory if the results wouldn't require the chain to start from the stationary distribution. \n- Discuss why use explore-then-commit for this problem and what the challenges with implementing more competitive approaches, like those based on optimism or Thompson sampling, are.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ykAatqDjBE", "reviewer": "Reviewer_UHGH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\n- The paper is easy to understand \n- The authors present both algorithms, regret upper bounds as well as numerical simulations to illustrate the efficacy of the approach\n\nWeaknesses\n- I have doubts about the regret definition/model/objective: the authors are purely concerned with making sure that the estimated belief state ${\\hat b}_t$ is an accurate estimate of the actual belief state $b_t$, but they do not care at all about the collected rewards. In fact, if there exists a very informative action (that allows to quickly guess the state) but has 0 reward, playing it incurs no regret. Not only is this counter intuitive, but i'm not even sure that the problem at hand is a bandit problem. It is essentially just an estimation problem. The regret definition would make sense if the agent were forced to play the \"estimated belief\" policy maximizing $\\mu(a)^\\top {\\hat b}_t$, but it is not the case here and the learner may play as she wishes.\n\n- The strategy (uniform exploration) seems overly simplistic and probably highly suboptimal. The authors argue that, in order to counteract this problem, when there are too many non informative arms one can just exclude arms a priori, and concentrate on a well chosen, small subset of arms to apply uniform exploration on this subset, but I do not believe that this is true in general. Consider the following example where one has $K$ states $\\mathbb{S}=\\\\{1,...,K\\\\}$, and K-1 arms $\\mathbb{I}=\\\\{1,...,K-1\\\\}$, and the rewards are binary $\\mathcal{V}=\\\\{0,1\\\\}$ such that $O((a,1),s) = 1$ if $a=s$ and $O((a,1),s) = 0$ if $a \\ne s$. Essentially, sampling action $a$ is equivalent to asking the question \"is the system in state a ?\" and getting an exact answer. For the algorithm to be consistent, we cannot exclude any arm from the set of arms, otherwise if $a$ is excluded, it becomes impossible to guess (for instance) the probabilities $P(s,s')$ with $s=a$. So one has to sample uniformly over all the arms if we use the authors strategy. Now consider two fixed states $s_1$ and $s_2$, a positive number $\\epsilon$ arbitrarily small and $P$ such that $P(s,s') \\le \\epsilon$ if $s,s' \\not\\in \\\\{s_1,s_2\\\\}$ (i.e the chain concentrates mostly on states $s_1$ and $s_2$). Then clearly, whenever we select actions that are not in $\\{s_1,s_2\\}$ we acquire little to no information about $P$ and collect no reward either. So only at most a fraction $4/K^2$ of the samples collected are useful, and the regret is at least $O(K^2)$ greater than what one would obtain with an optimal approach. I believe that, to design good algorithms for this problem (like in all bandit problems) one must sample adaptively to adjust the exploration strategy to the emerging information.\n- Why is Assumption 4.1 necessary ? This seems like a very strong assumption and clearly unnecessary for ergodicity. For instance very simple Markov chains like birth and death processes do not verify this assumption. This assumption greatly reduces the applicability of the results.\n- While the writing is very clear, I believe that the article is much too long. For instance Section \"5 Proposed Approach\" it is almost 3 pages of simple definitions and properties. Especially since the proposed approach is quite intuitive to a reader with a basic understanding of Markov chains: one simply estimates the transition probability matrix of rewards, and then one inverts a linear system to retrieve the transition probability of the states. \n\n\nMinor remarks:\n- \"The regret of a policy $\\theta$ on a bandit instance is defined as:\" -> the authors do not define what a \"policy\" is at that point.\n- \"is the unique stationary distribution of the chain\" -> it might be worth reminding the reader that the stationary distribution is the solution to $\\pi = \\pi P$ at this point of the text.\n- \"Each MAB is characterized by a finite set of discrete arms ... \" This phrase is misleading because it sounds like there may be different sets of arms for different MAB instances, whereas here, all MABs have the same set of arms and rewards.\n- \"The distribution of rewards Pr(·|s, a) conditioned on MAB instance s and action a is categorical\" By categorical do you mean discrete ?\n- \"Stationary Distribution of Consecutive States\" Why not simply define $W(s,s') = \\pi(s) P(s,s')$ ?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of latent bandits where the reward of arms depend on an unobserved state, and where the learner knows the conditional distribution of the reward knowing both the state and the chosen action. The problem consists in estimating the state transition probability through the rewards. This also enable accurate estimation of the belief state.\n\nThe authors propose an algorithm which starts by (possibly) pruning the set of arms, then explores them uniformly to infer the state transition probability matrix by inverting the (linear) relationship between state transition probability matrix and rewards transition probability matrix.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While initially this paper wasn't unanimously appreciated by the reviewers, the author response has convinced one of the reviewers to change their minds and eventually support acceptance. One reviewer remained skeptical about the significance of the results, and in particular the strength of the assumptions that the authors have made. While I very much share these concerns and believe that the strength of the results leaves much to be desired, the paper does live up to the TMLR criteria for publication, and I am thus recommending the paper for acceptance. I nevertheless encourage the authors to keep working on this problem until a more satisfactory result can be achieved.
Decision: Accept (poster)