RL for Latent MDPs: Regret Guarantees and a Lower Bound
Authors: Jeongyeol Kwon
Yonathan Efroni
Constantine Caramanis
Shie Mannor
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Reinforcement Learning
Partially Observable
Latent Variable
Lower Bound
Upper Confidence Bound
Expectation-Maximization
Predictive State Representation

Abstract: In this work, we consider the regret minimization problem for reinforcement learning in latent Markov Decision Processes (LMDP). In an LMDP, an MDP is randomly drawn from a set of $M$ possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. We first show that a general instance of LMDPs requires at least $\Omega((SA)^M)$ episodes to even approximate the optimal policy. Then, we consider sufficient assumptions under which learning good policies requires polynomial number of episodes. We show that the key link is a notion of separation between the MDP system dynamics. With sufficient separation, we provide an efficient algorithm with local guarantee, {\it i.e.,} providing a sublinear regret guarantee when we are given a good initialization. Finally, if we are given standard statistical sufficiency assumptions common in the Predictive State Representation (PSR) literature (e.g., \cite{boots2011online}) and a reachability assumption, we show that the need for initialization can be removed. 

RL for Latent MDPs: Regret Guarantees and a Lower Bound
Jeongyeol Kwon
Yonathan Efroni
The University of Texas at Austin kwonchungl
Microsoft Research, NYC jonathan efroni @gmail
pronchhngli@utteeee Sirggll@uuue wwweeetteeecmmm edu
Constantine Caramanis The University of Texas at Austin constant constantine@utexen edu
Shie Mannor Technion, NVIDIA shi technion. ac il, smannor@nvidia.com com
Abstract
this work, we consider the regret minimization problem for reinforemment learning in latent Markov Decision Processes (LMDP). In LMDP, MDP is randomly drawn from a set of M possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. We first show that general instance of LMDPs requires at least 5?(( ((((A)) episodes to even approximate the optimal policy. Then, consider sufficient assumptions under which learning good policies requires polynomial number of episodes. We show that the key link is notion of separation between the MDP system dynamics. With sufficient separation, we provide an efficient algorithm with local guarantee, i.e., providing sublinear regret guarantee when we are given standard statistical sufficiency assumptions common in the Predictive State Representation (PSR) literature (e.g.. [6]) and reachability assumption, we show that the need for initialization can be removed.
given a good initialization. Finally, if
1 Introduction
Partially observable Markov decision processes (POMDPs) [42] give general framework describe partially observable sequential decision problems. In POMDPs, the underlying dynamics satisfy the Markovian property, but the observations give only partial information on the identity of the underlying states. With the generality of this framework comes high computational and statistical price to pay: POMDP' are hard, primarily because optimal policies depend on the entire history of the process. But for many important problems, this full generality can be overkill, and in particular, does not have way leverage special structure. We are interested settings where the hidden or latent (unobserved) variables have slow dynamics or are even static in each episode, This model is important for diverse applications, from serving user a dynamic web application [18], to medical decision making [45], to transfer learning in different RL tasks [8]. Yet, as we explain below, even this area remains little understood, and challenges abound.
Thus, in this work, we consider reinforcement learning (RL) for special type of POMDP which we call latent Markov decision process (LMDP). LMDPss consist of some (perhaps large) number M of MDPs with joint state space S and actions A. In episodic LMDPs with finite time-horizon H, the static latent (hidden) variable that selects one of M MDPs randomly chosen the beginning of each episode, yet is not revealed to the agent. The agent then interacts with the chosen MDP throughout the episode (see Definition for the formal description).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

Related Work. The LMDP framework has previously been introduced under many different names, e.g., hidden-model MDP [11], Multitask RL [8], Contextual MDP [18]. Multi-modal Markov decision process [45] and Concurrent MDP [9].
Learning in LMDPs is challenging problem due the unobservability of latent contexts. For instance, the exact planning problem is P-SPACE hard [45], inheriting the hardness of planning from the general POMDP framework. Nevertheless, the lack of dynamics of the latent variables, offers some hope. As an example, if the number of contexts M is bounded, then the planning problem can be least approximately solved (e.g., by point-based value iteration (PBVI) [39], or mixed integer programming (MIP) [45]).
The most closely related work studying LMDPs is in the context of multitask RL [47, 8, 34, 18). In this line of work, a common approach is to cluster trajectories according to different contexts, an approach that guided us in designing the algorithms in Section 3.4. However, previous work requires very long time-horizon H >> SA in order to guarantee that every state-action pair can be visited multiple times in a single episode. In contrast, we consider a significantly shorter time-horizon that scales poly-logarithmic with the number of states, i.e., H = poly log M S.A. This short time-horizon results in significant difference learning strategy even when we get feedback on the true context at the end of episode. We refer the readers to Appendix A for additional discussion on related work.
Main Results. To the best of our knowledge, none of the previous literature has obtained sample complexity guarantees or studied regret bounds in the LMDP setting. This paper addresses precisely this problem. We ask the following:
Is there sample efficient RL algorithm for LMDPs, with sublinear regret?
The answer turns out to be not so simple. Our results comprise a first impossibility result, followed by positive algorithmic results under additional assumptions. Specifically:
First, we find that for a general LMDP, polynomial sample complexity cannot be attained without further assumptions. That is, to find an approximately optimal policy we need at least 52 ((SA) A)) samples, i.e., at least exponential in the number of contexts M (Section 3.1). This lower bound even applies to instances with deterministic MDPs.
We find that there are several natural assumptions under which optimal policies can be learned with polynomial sample complexity. Similarly to mixture problems without dynamics, the key link notion of separation between the MDPs. With sufficient separation, we show that there is a Mlaninggoraccle efficient RL algorithm with polynomial sample complexity. A critical development is adapting the principle of optimism as in UCB, but to the partially observed setting where value-iteration cannot be directly applied, and thus neither can the UCRL algorithm for MDPs.
Finally, under additional statistical sufficiency assumptions that are common in the Predictive State Representation (PSR) literature (e.g.. [6]) and a reachability assumption, we show that the need for initialization can entirely removed.
Finally, we perform an empirical evaluation of the suggested algorithms on toy problems (Section 4), while focusing on the importance of the made assumptions.
2 Preliminaries
2.1 Problem Setup: Latent MDPs
We start with the definition of episodic reinforcement learning in latent Markov decision process:
Definition 1 (Latent Markov Decision Process (LMDP)) Consider set of MDPs M with joint
state space S joint action space A in a finite time horizon H. Let M [M], S | and AA) Each MDP Mm E M is tuple (S, Tm, Rm, vm) where Tm : S A x S > [0. probubility maps a state-action pair and a next state to a probability, Rm : S x A x [0, probability measure for rewards that maps state-action pair and a binary reward to probability. and un is an initial state distribution. Let wy ..., Was be the mixing weights of LMDPs such that at the start of every episode, one MDP Mm E M is randomly chosen with probability Wm.
transition
2

---

We assume the mixing weights are uniform and known priori. L.e, = wM 1/M. This only for the ease of presentation, and does not affect any algorithmic idea main results in this paper. The goal of the problem is to find (possibly non-Markovian) policy in a policy class that maximizes the expected return: VM= == maX Em=1 W mm
Σ "t ,where E [ is expectation taken over the mt MDP with policy If not specified otherwise, we find the best policy in of history-dependen policies (S,A, {0, 13)* x A(A) that map an entire history to probability distribution over actions.
We define the notion of regret relative to a (possibly approximate) planning oracle. Thus, suppose we have a planning-oracle with the following approximation guarantee: VM 2 p1 Vi P2, where is returned policy when M is given the planning-oran oracle, and Pt, P2 multiplicative and additive approximation constants respectively. We then define the regret as the comparison to the best approximation guarantee that the planning-
can achieve:
Regret (K)
D (p1V% p2) VM.
where Ty is policy executed in the htth episode. For example, we can use point-based value-iteration (PBVT) [39] as planning-oracle:
Example 1 PBVI [39] with discretization level Ea > 0 in the belief space (over IR M returns an e Hz
additive approximate policy. That is, equation (1) holds with f1 and P2 c.H
2.2 Predictive State Representation (PSR)
partially observable dynamical system can viewed as a model that generates a sequence of observations from observation space O with (controlled) actions from action space A. A predictive state representation (PSR) is a compact description of a dynamical system with a set of observable experiments, tests [41]. Specifically, test of length is sequence of action-observation pairs given as T = of of ...aao oī history = a o' of is a sequence of action-observation pairs that has been generated prior given time. A prediction P(T[h) the probability of seeing the test sequence from a given history, given that we intervene to take actions aTaç...a In latent MDPs, the observation space can be considered as pair of next-states and rewards, i.e., O x {0, 1} and o, = (8t+1.3)).
P(oj..//lldd ai.) denotes
As we work with special class of POMDPs, we customize the formulation for LMDPs. The set of histories consists subset of histories that end with different states, i.e., H U, H.. where each element h E H, is short sequence of state-action-rewards of length / ending with state
saaf 2/ s/ s sf a)
We define PT, (H.s) a vector of probabilities where each coordinate is probability of sampling each history in Hs in the mh MDP with policy т. Likewise, each element tests 7 E T is a short sequence of oetion-reward-neg states of length at most t:
== ajris of rī s (a.r,
We denote Pm (T]s) as a vector of probability where each coordinate is a success probability each test in the m th MDP starting from a state That is.
Pm.. (T]ss, Pm s7 ...Ti s Islloo aF....
2.2.1 Spectral Learning of PSRs in LMDPs
In spectral learning, we build a set of observable matrices that contains the (joint) probabilities of histories and tests, and then we can extract parameters from these matrices by performing singular value decomposition (SVD) and regressions [7]. In order to apply spectral learning techniques, we require the following technical conditions statistical sufficiency of tests:
Condition (Sufficient Tests) For all E S, for the test set T, let It (P)()s)) (T..))... (T(s)) s)), Then (La) 2 o, for all S with some a 0.
3

---

Here, (-) is the minimum (M singular value of matrix. Another technical condition for spectral learning method is a rank non-degeneracy condition for sufficient histories:
Condition 2 (Sufficient Histories) For all 8 E S. for the history set Hss ending with a state let Hs [P (H.)) (H,)) with a sampling policy n. Then d (L)H)) z ("nd state = 8) di with some on O.
Here P" (end state = 8) a probability of sampling history ending with 8. Along with the rank condition for tests, pairs of histories and tests can be thought as many short snap-shots of long trajectories obtained by external experts or some exploration policy (c.g.. random policy in uniformly ergodic MDPs). Following the notations in [7]. let Pr,., H, Conditions and 2 ensure au (ar(PT,,.) > O. Under these conditions, the goal of spectral learning algorithm is to output PSR parameters which are used to compute (r]],), the estimated probability of any future observations (or tests r) given any sampled histories h. We refer to Appendix E. for a detailed procedure.
2.3 Notations
We denote the underlying LMDP with true parameters as MM. With slight abuse of notation, we denote the I distance between two probability distributions D, and D2 on random variable X conditioned on event E as [I (PX=DD - P x (X = =ExEx PX (X [) P Xx>D2 (X EE), where X is support of X. When we do not condition on any event, we omit the conditioning on E. When we measure a transition or reward probability at a state-action pair (s, a), we use T or R instead of P. We use Pm to refer to the probability of any event measured in the mh context (or in m MDP). In particular, Pm (m Fn.ss'rlss rls,a) Tm, (s'|s, (rlsmrr a). If we use P without any subscript, it is a probability of an event measured outside of the context, i.e. P-)) = Em= WmPPm the probability of an event depends a policy т, add superscript to P. Similarly, Em is expectation taken over the m² context and и is added as superscript if the expectation depends on We use : denote any estimated quantities. a S b implies a less than up to some constant and logarithmic factors. poly(-) means the order of polynomial complexity (up to logarithmic factors) in referenced parameters. We interchangeably use o, an observation, to replace a pair of next-state and immediate reward r)) to simplify the notation. We occasionally express length / >> O history (#1, a1, Tl.... St, ae, Tt) compactly as (s, a, r)..
Main Results
In this section, we first obtain hardness result for the general case. We then consider sample- and computationally efficient algorithms under additional assumptions.
3.1 Fundamental Limits of Learning General LMDPs
We first study the fundamental limits of the problem. In particular, we are interested in whether we can learn the optimal policy after interacting with the LMDP for number of episodes polynomial in the problem parameters. We prove a worst-case lower bound, exhibiting an instance of LMDP that requires at least Ω ((SA) A) episodes:
Theorem 3.1 (Lower Bound) There exists an LMDP such that for finding an c-optimal policy n for which Vi Va= we need at least Ω ((SA/M)N / /²² episodes.
The hard instance consists of fully deterministic MDPs with possibly stochastic rewards, indicating an exponential lower bound in the number of contexts even for the casiest types of LMDPs. The example is constructed such that, in the absence of knowing true contexts, all wrong action sequences of length M cannot provide any information with zero reward, whereas the only correct action sequence gets a total reward of 1 under one specific context. The construction is given in Appendix B.
Theorem 3.1 prevents design of efficient algorithms with growing number contexts. We note here that Theorem 3.1 holds even for restricted classes of policies, e.g., memoryless policies. Fur- thermore, our construction of hard instances does not allow to find any approximate policy with P1 (((A))-M within polynomial number of episodes either. To the best of our knowledge, this

---

Algorithm Latent Upper Confidence Reinforcement Learning (L-UCRL)
Initialize counts Nm (8, a), (m) and parameters (Tmy Ron Pm) properly
1: for each kthh episode do
2: Get a policy Ty for M₁ in Lemma 3.2
3: Play policy тy and get the trajectory (s,
4: Get an estimated belief over contexts b with either Algorithm (when contexts are given), or Algorithm 3 (when we infer contexts) 5: for m = 1,,,, M and /. 1,... H do
6:
Nm (m 9t) + (s+1 az st) + b(m)
7:
Nm (ra 4x) < Nm (relsss ar) + b(m) (s1) + (s1) + b(m)
8:
9: Update empirical parameters Tmny Rm, Pm
10: end for
11:
end for
is the first lower bound of its kind for LMDPs. Next, we investigate natural assumptions which help us develop an efficient algorithm when only polynomial number of episodes are available.
3.2 The Critical First Step: Contexts in Hindsight
Suppose the true context of the underlying MDP is revealed to the agent at the end of each episode. We do not require any assumptions the environments in this scenario. Note that this scenario is different from fully observable settings (i.e., knowing the true context at the beginning of an episode). In the latter scenario, we would simply have M-decoupled RL problems in standard MDPs. While this can be considered as a "warm-up" for the sequel, it is motivated by real-world examples. Moreover, the key technical insight here will prove important for the sequel as well.
Knowing contexts in hindsight allows us to construct a confidence set for parameters:
C = {M Ill(um - (s) I Vc,/N(m), ([ (n) a)ll S Vor/Nm(s,a), [I(Rm R... (r(s, a)Il S VeR/Nm(s,a), 8,,,
where Nm. (s, a) is the number of times each state-action pair (s,a) in m MDP is visited, and (m) is the number of episodes we interact with the mh MDP. With properly set parameters er = OSS log(K/n))) CR = (log( K/ k/n)) and cu = O(S (og(())))))) for the confidence intervals, M E C with high probability for all K episodes.
With the construction of confidence sets, is then natural to try design an optimistic RL algorithm, as in UCRL [22]. An obvious optimistic value in light of (2) is max..Mec Vλ- However, solving this optimization problem more general than solving an LMDP. In fully observable settings, we could replace the complex optimization problem by adding proper exploration bonus to obtain an optimistic value function [4].
In partially observable environments, value iteration is only defined in terms of belief-states and not the observed states. For this reason, existing techniques solely based the value-iteration cannot be directly applied for LMDPs. Yet, we find that proper analysis of the Bellman update rule over the belief state reveals that an empirical LMDP with properly adjusted hidden rewards is optimistic:
Proposition 3.2 We construct an optimistic LMDP M whose parameters are given such that:
(s'(' a) I' (s'(ss a), Feghs (rls, a) (r|sr, Vmn (s) (m)(s)
Rhid (m) min (1, (o./N(m) Thiid H min (1, (1, + N,T)//Nmss.)))
where Bhid (m) is an initial hidden reward given when starting an episode with a context m, and [eobe(-ss. js,0 a) is probability measure of an observable immediate reward r whereas Rhid (8, a) is hidden immediate reward (that is not visible to the agent) for state-action pair (8, a) in a context m. Then for any policy the expected long-term reward is optimistic, i.e., V > VM-
5

---

Algorithm 2 Access to True Contexts
Algorithm Inference of Contexts
Input: Receive true context m" in hind- sight
Input:
Trajectory ($1, d1, (1,71, ..... SH, ag rH)
Output: Return an estimate of belief over contexts b. (m(() = ( (1- -2-5)) rels,, pm((T)
Output: Belief over hidden contexts:
B(m) = { 1. for m m 0, for * m
b(m) = Em (T)
Here, hidden reward is deterministic reward that happens for every state-action pair, but does not appear in any observation history during the episode. We note that most existing planning algorithms can incorporate the hidden-reward structure without changes to maximize the long-term observed + hidden rewards. For instance, the PBVI algorithm [39] can be executed as is in the planning step. Hence in each episode, planning planning-oracle to get a policy to execute for the episode. Then we simply run the policy and update model parameters in foowagh manner. The algorithm can be efficiently implemented as long as some efficient (approximate) planning algorithms are available.
build one optimistic model from Proposition 3.2, and call the
To establish Proposition 3.2, we make use of the "alpha vector' representation [42] of the value function of general POMDPs. Detailed analysis deferred to Appendix C.I. With the optimistic model constructed in Proposition 3.2, planning-oracle efficient implementation is straightforward. The resulting latent upper confidence reinforcement learning (L-UCRL) algorithm summarized in Algorithm 1. Based on the established optimism in Proposition 3.2 and by carefully bounding the on-policy errors we arrive to the following regret guarantee of L-UCRL.
Theorem 3.3 Let N -K. The regret of the Algorithm I is bounded by:
K
Regret K) S
Σ(v
VM-) HSVMAN.
M₁
Proof of Theorem 3.3 is given in Appendix C.4. The central result of this section, Theorem 3.3 leads to the following observation: a polynomial sample complexity is possible for the LMDP model assuming the context of the underlying MDP is supplied at the end of each episode. Next, we explore ways to relax this assumption, while keep supplying with polynomial sample complexity guarantee.
3.3 When we can Infer Contexts?
Without explicit access the true context at the end of an episode, it is natural to estimate the context from the sampled trajectory. One sufficient condition to infer the context is the following:
Assumption 1 (5-Strongly Separated MDPs) For all m, my. m2 E [M] such that mı + 422. for all (8, a) E S x A, l distance between probubility of observations o = (s', r) of two different MDPs in LMDP is at least 8 > 0, i.e., [I(P,, - - Pmmg) (ola)))s))) a)]l 2 8 for some constant 8 >>> 0.
In order to reliably infer the true contexts the seperatedness between MDPs alone is not sufficient, since need to estimate the contexts from the current empirical estimates of LMDPs. In order to reliably estimate the context from empirical estimate of LMDPs, we need a well-initialized empirical transition model of the LMDP:
[[ (s' a) [I(2m vm (s) [I(R,, - Rm, (rls, a)ll1 S Cinit- V(s,a), (3)
for some initialization error <iiit > O. Note that while the initialization error is relatively small, can be still not good enough obtain near-optimal policy (i.c., it will result in a linear regret). We can consider as if the state-action pairs are already visit at least No = cr/e?ne times in each context.
Once the initialization is given along with separation between MDPs, we can modify Algorithm 1 to update the empirical estimate of LMDP using the estimated belief over contexts computed in Algorithm 3. Note that when we update the model parameters, we increase the visit count of state- action pair (s, a) m MDP by 6(m). With Assumption 1, it approximately adds count for the

---

Algorithm 4 (Informal) Recovery of LMDP parameters
Learn PSR parameters up to precision o())
Get clusters (-ls, a), R. (s.a) with learned PSR parameters Build each MDP model by correctly assigning contexts to estimated model parameters Return Well-initialized model (Tm, Rm ImE(M)
correctly estimated context, but without Assumption 1, the update steps can still be applied. In fact, this is equivalent to an implementation of the so-called (online) expectation- snaectationmmaximizatioo maximizaaion (EM) algorithm [10] for latent MDPs. Thus Algorithm I with Algorithm 3 essentially results in combining L-UCRL and the EM algorithm.
In terms of performance guarantees, using Algorithm 3 as a sub-routine for L-UCRL gives the same order regret as Theorem 3.3 as long as the true context can be almost reliably inferred:
Theorem 3.4 Suppose Assumption holds with > C-
1-85-1oog log (1/o) (og(N/n) (/1]) for some absolute
constants C, >> O, and a parameter o >> O such that In(1/a) S 8 (200S). If the initialization parameters satisfy equation (3) with some initialization error tina S 8² 00/(2200))) (200 then with probability at least 7), the regret of Algorithm is bounded by:
Regret(K) S HSVMAN.
The proof of Theorem 3.4 is given in Appendix D.3. The provable guarantees are only given for well- separated LMDPs. Nevertheless, we empirically evaluate Algorithm 1 as a function of separations and initialization (see Figure 1).
An interesting consequence of Assumption 1 is that the length of episode can be logarithmic in the
number of state and actions. With much longer time-horizons H 2 ? A A/5²), ).2). [8, 18] assumed similar d-separation only for some (s, a) pairs. While Assumption requires a stronger assumption of ô-separation for state-actions, the requirement on the time-horizon can significantly weaker with large state and action spaces. For a more discussion on the separation condition, we refer the readers to Appendix D.I.
3.4 Learning LMDPs without Initialization
Finally, discuss efficient initialization with some additional assumptions. Clustering trajectories is the cornerstone of all our technical results, as this allows us to estimate the parameters of each hidden MDP and then apply the techniques of Section 3.2. The challenge is how to cluster when have short trajectories, and no good initialization.
The key is again in Assumption 1. In Section 3.3, we use good initialization to obtain accurate estimates of the belief states. These can then be clustered, thanks to Assumption I, allowing us to obtain the true label in hindsight. Without initialization, we cannot accurately compute the belief state, so this avenue is blocked. Instead, our key idea is to leverage a predictive state representation (PSR) of the POMDP dynamics, and then show that Assumption allows us to cluster in this space.
Algorithm gives our approach. We first explain the high-level idea, and subsequently detail some of the more subtle points. Suppose we have PSR parameters allowing us to estimate P(o//||do a). (the probabilities of any future observations
(s', given history h and intervening action a) to within accuracy o()). We then show that we can again apply Assumption 1, to (almost) perfectly cluster the MDPs by true context at the end of the episode, After we collect transition probabilities at all states near the end of episode, we can construct a full transition model for each MDP.
Learning the PSR sufficient accuracy requires additional assumption. We show that the following standard assumption on statistical sufficiency of histories and tests, is sufficient for our purposes (see also Section 2.2.1 and Appendix E.1):
Assumption 2 (Sufficient Tests/Historres) Lei T and H be the set of all possible tests and histories of length = O(1) respectively, with given sampling policy π (e-g., uniformly random policy) for histories H. T and H. satisfy Condition I and 2 respectively.
7

---

LOCKL Coorena Scratre
Sodil CIEPeT Scover Cerrato
30
(a)
(b)
Figure 1: (a) L-UCRL when true contexts are revealed in hindsight and when we run with the EM algorithm.
(b) EM + L-UCRL (Algorithm 1) under different levels of separation and horizon length.
While the worst- instance may require 1 2 M to satisfy the full-rank conditions, we assume that the length of sufficient tests/histories ( O(1). In fact, [ has been (implicitly) the common assumption in the literature on learning POMDPs [20, 5, 17, 25J. Empirically, we observe that the this point, we are not
more MDPs differ, the more easily they satisfy Assumption See Figure aware whether sample-efficient learning is possible with only Assumption 1.
Though the main idea and key assumption are above, few important details and technical assumptions remain to complete this story. The primary guarantee still required is that we have access to an exploration policy with sufficient mixing, guarantee can collect all required information to perform the PSR-based clustering. The following assumption ensures that additional (MM /a2) sample trajectories obtained with the exploration policy т can provide M clusters of estimated one-step predictions Pm, (o)s, a) for every state s and intervening action a.
Assumption 3 (Reachability of States) There exists priori known exploration policy such that, for all m E [M] and E S, we have P ($H = 3) 2 022 for some Q2 > O.
subtle point here is that we still have an ambiguity issue in the ordering of contexts (or labels) assigned in different states, which prevents us from recovering the full model for each context. We resolve this issues ambiguity assuming the MDP is connected, and give the full description of Algorithm 4 in Appendix E.2. We conclude this section with an (informal) end-to-end guarantee:
Theorem 3.5 (Informal) Let Assumption 2 hold for an LMDP instance with sampling policy т. Furthermore, assume the LMDP satisfies Assumptions 1 and 3. Then there exists an algorithm such that with probability at least 2/3, it returns a good initialization of LMDP parameters that satisfies (3) in time poly(A', S, H, 1 M, hn oT 0tg Ö, Esnit).
Theorem 3.5 completes the pipeline for learning in latent MDPs: we initialize the parameters by the estimated PSR and clustering (see Appendix E) up to some accuracy, and then we run L-UCRL to refine the model and policy up to arbitrary accuracy (Algorithm 1). Full version of Theorem 3.5 can be found Theorem E.3.
4 Experiments
In this section, we evaluate the proposed algorithm on synthetic data. Our first two experiments illustrate the performance of L-UCRL (Algorithm 1) for various levels of separation and quality of initialization. Then, we empirically study the performance of the PSR- EeR-Clust algorithm for randomly generated LMDPs for different levels of separation and time-horizon
4.1 The Value of True Contexts in Hindsight
We first study the importance of receiving the true contexts hindsight for the approach analyzed in this work, by comparing the performance of Algorithm 1 when instantiating it with Algorithm 2 or as sub-routine. We generate random instances of LMDPs of size set the time-horizon H 30. The reward distribution is set to be 0 for most state-action pairs. We compare when we give a true context to the algorithm (Algorithm 2) and when we infer a context with random initialization good initialization (Algorithm 3). In the latter, it is equivalent to
7, = 15, A = 3 and

---

Wed wed.Caegaarrdreee us Det's
Mediorr ding Velle
Peefommae of PSR weriing clumeey
CIT 00000 21 True centent
12.
0.4
8.7
Figure 2: PSR learning and Clustering (Algorithm 4). Left: Convergence belief state. Middle: M singular value of sufficient histories/tests matrix PT, Right: Accuracy of the estimated model.
running the EM algorithm for the model estimation. For the planning algorithm, use Q-MDP heuristic [32] which shows good empirical performance. We measure the model estimation error as where Permyr denotes all length M permutation sequences. The measured errors are averaged over 10 independent experiments.
error = eeemar L(m,s.a s.). (I (m - P (m)))(sss (s',)
The experimental results are given in Figure ((a). When the true context is given the end of episode (with Algorithm 2), L-UCRL converges to the optimal policy as our theory suggests. On the other hand, if the true context is not given (with Algorithm 3), the quality of initialization becomes crucial; when the model is poorly initialized, the estimated model converges to a local optimum which leads to sub-optimal policy. When the model is well-initialized. L-UCRL performs well when true contexts are given hindsight.
4.2 Performance of L-UCRL with Good Initialization
In our second experiment, we focus on the performance of L-UCRL. (Algorithm 1) along with Algorithm 3 under different levels of separation (5 in Assumption 1) when approximately good model parameters are given. For various levels of 8, we generate the parameters for transition probabilities randomly while keeping the distance between different MDPs satisfy d S [[(Tm, (s')(s a)ll2 < 26 for m, + m2.
We show the error in the estimated model and average long-term rewards in Figure 1(b). When the separation is sufficient (larger 5 or H), the estimated model converges fast to the true parameters. When the separation gets small (smaller 8 or H), the convergence speed gets slower. This type of transition in the convergence speed of EM (the update of model parameters with Algorithm 3) is observed both in theory and practice when the overlap between mixture components gets larger (e.g., (291). On the other hand, the policy steadily improves regardless of the level of separation. We conjecture that this because the optimal policy would only need the model to be accurate in the total-variatio distance, not in the actual estimated parameters.
4.3 Initialization with PSR and Clustering
In the third experiment, we evaluate the initialization algorithm (Algorithm 4) for randomly generated LMDP instances. Since PSR learning requires (relatively) large number of short sample trajectories. we evaluate this step on smaller instances with S 7, = 2, MM 3. The LMDP instances are generated similarly as in the second experiment with different levels initial distributions are set the same across all MDPs. To learn the parameters of PSR, we run 106 episodes with = 4. We assume historics and tests of length I are statistically sufficient with the uniformly random policy. In the clustering step, run additional 5 10 cpisodes to obtain longer trajectories of length = 20, 40 and 80, We report the experimental results in Figure 2.
and H. The reward and
We first observe how the level of separation between MDPs impacts trajectory separation, i.e., belief state vs true label (left). Recall that this separation property the key for clustering trajectories. We then examine the performance of Algorithm 4 (see full Algorithm 5) for various levels of separation. Empirically, succeeds to get a good initialization of an LMDP model when we have sufficient separation. As the separation level decreases, the algorithm starts to fail (Right). There are two possible sources of the failure: (1) the belief state is far from the true context, and (2) the similarity between MDPs drops the M singular value of PT (Middle). We can compensate for (1) if

---

have a longer time-horizon to infer true contexts, as in the leftmost graph. For (2), if the M singular value drops, we require more samples for the estimation of PSR parameters. In our experiments, as we decreased 8 we found that failure in the spectral learning step was the more significant of the two.
5 Future Work
There are several interesting research avenues in continuation of this work. An interesting direction is to study RL algorithms for LMDPs with no underlying assumptions. Although our lower bound suggests such an algorithm necessarily suffers an exponential dependence the number of contexts, if this number is small, such dependence might be acceptable. Specifically, we conjecture that general LMDPs can be learned with sample complexity of poly ((HSA)*, ...). ( For special case when MDPs are deterministic, we show that the exponential dependence in M is sufficient In Appendix G. The case for general LMDPs is an interesting open question. Furthermore, a needed empirical advancement is to design efficient ways to learn the set of sufficient histories/tests for learning predictive state representation LMDPs. This can dramatically improve the performance of algorithms when sufficiently good initial model needs to be learned.
Acknowledgement
The research was funded by NSF grant 2019844, and by the Army Research Office and was accom- plished under Cooperative Agreement Number contained in this document are those of the authors and should not interpreted as representing the official policies. either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
The views and conclusions
References
[1] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15:2773-2833 2014.
[2] A. Anandkumar, D. Hsu, and S. M. Kakade. A method of moments for mixture models and hidden markov models. In Conference on Learning Theory, pages 33-1, 2012.
[3] D. Arthur and S. Vassilvitskii. k-means++ the advantages of careful seeding. In Proceedings of the eighteenth annual ACM- SIAM symposium on Discrete algorithms,, pages 1027-1035, 2007.
[4] M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. arXiv preprint arXiv: arXiv: 170.00549, 2017.
[5] K. Azizzadenesheli, A. Lazaric, and A. Anandkumar. Reinforcement learning of POMDPs using spectral methods. In Conference on Learning Theory, pages 193-256, 2016.
[6] B. Boots and G. J. Gordon. An online spectral learning algorithm for partially observable nonlinear dynamical systems. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
[7] B. Boots, S. M. Siddiqi, and G. J. Gordon. Closing the learning-planning loop with predictive state representations. The International Journal of Robotics Research, 30(7):954-99) 966, 2011.
[8] E. Brunskill and L. Li. Sample complexity of multi-takk reinforcement learning. In Uncertainty in Artificial Intelligence, page 122. Citeseer, 2013.
[9] Buchholz and D. Scheftelowitsch. Computation of weighted sums of rewards for concurrent MDPs. Mathematical Methods of Operations Research, 89(1): 1-42, 2019.
[10] O. Cappé and E. Moulines. On-line pnretaaion-mmxxiizaatii algorithm for latent data models. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 71(3):593-613, 2009.
[11] I. Chadès, J. Carwardine, T. Martin, S. Nicol, R. Sabbadin, and O. Buffet. Momdps: solution for modelling adaptive management problems. In Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12), 2012.
10

---

[12] C. Dann, N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. On oracle- efficient PAC RL with rich observations. In Advances in neural information processing systems, pages 1422-1432, 2018.
[13] S. Du, A. Krishnamurthy, N. Jiang, A. Agarwal, M. Dudik, and J. Langford. Provably efficient with rich observations via latent state decoding. International Conference on Machine Learning, pages 1665-1674, 2019.
[14] A. Garivier, P. Ménard, and G. Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
[15] C. Gentile, S. Li, P. Kar, A. Karatzoglou, G. Zappella, and E. Etruc. On context-dependent clustering of bandits. In International Conference Machine Learning, pages 1253-1262. PMLR, 2017.
[16] C. Gentile, S. Li, and G. Zappella. Online clustering of bandits. International Conference on Machine Learning, pages 757-765, 2014.
[17] Z. D. Guo, S. Doroudi, and E. Brunskill. A PAC RL algorithm for episodic POMDPs. In Artificial Intelligence and Statistics, pages 510-518, 2016.
[18] A. Hallak, D. Di Castro, and S. Mannor. Contextual markov decision processes. arXiv preprint arXiv: wrXiv:550.002255 2015.
[19] A. Hefny, C. Downey, and G. J. Gordon. Supervised learning for dynamical system learning. In Advances in neural information processing systems, pages 1963-1971, 2015.
[20] D. Hsu, S. M. Kakade, and T. Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 78(5):1460-1455 1480, 2012.
[21] T. Jaakkola, S. Singh, and M. I. Jordan. Reinforcement learning algorithm for partially observable markov decision problems. In Advances in neural information processing systems, pages 345-352, 1995.
[22] Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11: 11:1563-1600, 2010.
[23] N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford. and R. E. Schapire. Contextual decision processes with low bellman rank are PAC-learnable. International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
[24] N. Jiang, A. Kulesza, and S. Singh. Improving predictive state representations via gradient descent. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[25] C. Jin, S. M. Kakade, A. Krishnamurthy, and Q. Liu. Sample-efficient reinforcement learning of undercomplete POMDPs. arXiv preprint arXiv:2006. 12484, 2020.
[26] A. Krishnamurthy, A. Agarwal, and J. Langford. PAC reinforcement learning with rich observa- tions. In Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
[27] J. Kwon and C. Caramanis. The EM algorithm gives sample-optimality for learning mixtures of separate gaussians. In Conference on Learning Theory, pages 2425-2487, 2020.
[28] Kwon and C. Caramanis. EM converges for mixture of many linear regressions. In International Conference on Artificial Intelligence and Statistics, pages 1727-1736, 2020.
[29] J. Kwon, N. Ho, and C. Caramanis. On the minimax optimality of the EM algorithm for learning two-component mixed linear regression. arXiv preprint arXiv:2006. 02600,, 2020.
[30] Y. Li, B. Yin, and Xi. Finding optimal memoryless policies of POMDPs under the expected average reward criterion. European Journal of Operational Research, 21 211(3)5556-35 567, 2011.
[31] M. L.. Littman. Memoryless policies: Theoretical limitations and practical results. In From Animals to Animats 3: Proceedings of the third international conference on simulation of adaptive behavior, volume 3, page 238. Cambridge, MA, 1994.

---

[32] M. L. Littman, A. R. Cassandra, and L. P. Kaelbling. Learning policies for partially observable environments: Scaling up. In Machine Learning Proceedings 1995, pages 362-370. Elsevier, 1995.
[33] M. L. Littman and R. S. Sutton. Predictive representations of state. In Advances in neural information processing systems, pages 1553-1561, 2002.
[34] Y. Liu, Z. Guo, and E. Brunskill. PAC continuous state online multitask reinforcement learning with identification. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pages 438-446, 2016.
[35] O.-A. Maillard and S. Mannor. Latent bandits. In International Conference on Machine Learning, pages 136-144, 2014.
[36] A. Modi, Jiang, S. Singh, and A. Tewari. Markov decision processes with continuous side information. In Algorithmic Learning Theory, pages 597-618, 2018.
[37] A. Y. Ng and M. Jordan. PEGASUS: policy search method for large MDPs and POMDPs. In Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence, pages 406-415, 2000.
[38] C. H. Papadimitrion and J. N. Tsitsiklis. The complexity of Markov decision processes. Mathe- matics of operations research, 12(3):441-450, 1987.
[39] J. Pineau, G. Gordon, and S. Thrun. Anytime point-based approximations for large POMDPs. Journal of Artificial Intelligence Research, 27:335-380 380, 2006.
[40] Ross, M. Izadi, M. Mercer, and Buckeridge. Sensitivity analysis of POMDP value functions. In 2009 International Conference on Machine Learning and Applications, pages 317-323. IEEE, 2009.
[41] S. Singh, M. R. James, and M. R. Rudary. Predictive state representations: a new theory for modeling dynamical systems. In Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 512-519, 2004.
[42] R. D. Smallwood and E. J. Sondik. The optimal control of partially observable markov processes over finite horizon. Operations research, (55):0071-1088) 1973.
[43] Smith and R. Simmons. Heuristic search value iteration for POMDPs. Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 520-527, 2004.
[44] M. T. Spaan and N. Vlassis. Perseus: Randomized point-based value iteration for POMDPs. Journal of artificial intelligence research, 24:195-220, 2005.
[45] L. N. Steimle, D. L. Kaufman, and B. Denton. Multi-model markov decision processes. Optimization Online URL http://www. optimizationn-mlinee org/DBBFll FFIIDBFIIII221000//44453 pdf. 2018.
[46] G. W. Stewart. Matrix perturbation theory. 1990.
[47] M. E. Taylor and P. Stone. Transfer learning for reinforcement learning domains: A survey, Journal of Machine Learning Research, 10(7), 2009.
[48] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: [tt::1001.3022. 1.302,, 2010.
12


Reviews:
[{"review_id": "uRBJgQTBdf", "reviewer": "Reviewer_Nz8R", "summary": "The authors propose an online algorithm to deal with the latent MDP setting. Theoretical lower bounds and upper bounds for the regret are derived under various assumptions. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the presentation of the main ideas is clear and the paper is easy to read.\n\nThe extension of UCRL to the latent-MDP setting seems novel. I did not check the proofs but the results as well as the arguments are convincing. I believe the contributions are solid for publication in NeurIPS.\n\nFor the planning part, the authors keep pointing to the PBVI algorithm in the main text but in the experiments, Q-MDP is used. I wonder whether there is any violation of the \"planning-oracle\" assumption with respect to Proposition (or Lemma?) 3.2.\n\nThe authors mention that even the case where the true context is revealed at the end of each episode is motivated by real-world examples. Perhaps the authors should also provide these examples in the text (or even better in the experiments).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "H5a_w2SnGCh", "reviewer": "Reviewer_pwrf", "summary": "This paper studies episodic RL in the regret minimization setup in Latent MDPs (LMDPs), which belong to the family of POMDPs. The paper presents a sample complexity lower bound for general LMDPs (i.e., in the absence of any restrictive assumption on the LMDP) that grows exponential with the number $M$ of contexts (or base MDPs) --- that is, learning a near-optimal policy in the worst-case may require an exponential (in $M$) number of episodes. It then presents L-UCRL, a UCRL2-style algorithm for LMDPs, which is proven to achieve $O(\\sqrt{T})$ regret with high probability under some assumptions, where the regret bound depends polynomially on the number of state-action pairs and on the number of base MDPs.  ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written very well and admits a clear presentation. It investigates an interesting but challenging problem, which in my opinion is relevant both in practice and for NeurIPS.\n\nStrengths: Although LMDPs were studied prior to this work under various names, no regret or sample complexity bound was provided for them, to my knowledge. The LB is new and interesting, and would be a nice addition to the literature. The main contribution of the paper is an algorithm for the considered LMDP setup, which under some separability assumptions, is shown to be sample efficient, enjoying a rate-optimal regret with polynomial dependencies on the size of the state-action space and the episode length.\n\nThe paper starts with a warm-up case, when contexts are revealed at the end of the episode, which I believe is interesting in its own right. It was interesting to see that optimism is maintained by just relying on a hidden reward function suitably injected to empirical estimates.  \nOverall the studied problem is highly relevant in practical aspects of RL, and the paper presents a solid contribution, advancing state-of-the-art. However I have a couple of concerns:\n\n- Theorem 3.4 presenting the main technical result of the paper requires some further scrutiny. It is claimed to improve over the result by Li and Brunskill as the latter requires $H=\\Omega(S^2A/\\delta^2)$, while that in Theorem 3.4 depends on $S$ and $A$ only logarithmically. The comparison is not thorough however: The paper remains silent about the fact that here: (i) $H$ depends on $\\delta^{-4}$ (much worse than $\\delta^{-2}$ in Li and Brunskill [8]), and (ii) one has $H=\\Omega(\\log(HK))$, that is the episode length has to grow with time (or the current implementation is not anytime). Could you please explain?\n- Further discussion related to Theorem 3.4 might be helpful. Specifically, $H$ has to satisfy a bound dependent on $\\alpha$, which itself is determined via an inequality depending on both $\\delta$ and $S$. What is the final, explicit dependency of minimal $H$ on the relevant parameters (in particular, $\\delta$ and $S$)?\n\nSome minor comments:\n\n- In line 67, the authors mention “initialization”, which is seemingly supposed to be discussed/motivated in the previous statements (though, some pointer to that is provided in the abstract). Discussions in later sections make it clear, however. Clarifying that could improve the readability. \n\n- A more concrete comparison between the regret bound of Theorem 3.3 and of Theorem 3.4 could be very helpful. Do the bounds together imply that one achieves the same regret (order-wise), but only at the expense of large enough $H$ and separability? Or we would lose more.\n\n- Throughout: UCRL --- > UCRL2. If you refer to the algorithm in (Jaksch et al., 2010), you should use UCRL2 instead of UCRL. UCRL is indeed the precursor of UCRL2, and is presented in (Ortner & Auer, 2007). \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential societal impact, to my knowledge. For other limitations or constructive suggestions, see above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "6ZC1IbELEj0", "reviewer": "Reviewer_8oDh", "summary": "In this paper, the authors study efficient algorithms and hardness results for Latent MDPs. In a latent MDP, in each iteration, an MDP is randomly drawn from a set of M possible MDPs, and the agent interacts with that MDP without knowing its identity. The goal is to find a policy so that the expected cumulative reward is maximized, where the expectation is taken over the choice of the MDP and its stochasticity. The authors first show that without further assumptions, LMDPs are hard to learn. The authors then give a set of sufficient conditions so that LDMPs are learnable with polynomial sample complexity. One possible condition that makes LMDPs learnable with polynomial number of samples is the case when the identity of the randomly chosen MDP is revealed to the agent at the end of each trajectory. The authors further show that such identity can be learned if certain seperatedness condition holds. Preliminary experimental results are attached. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper contains an interesting set of results and I recommend acceptance. \n\nThe hardness result looks interesting, and suggests that extra conditions are indeed necessary to make LMDPs efficiently learnable. The authors then show that if the identity of the MDP is revealed to the agent at the end of each trajectory, then LMDPs are learnable with sublinear regret / polynomial sample complexity. The idea is to use the identity of the MDP to build confidence intervals, with which standard algorithms based on the principle of optimism in the face of uncertainty can be applied. The authors then discuss conditions under which the identity of the MDP can be learned. \n\nAlthough the writing is good in general, the statement of the hardness result seems a bit incomplete. In particular, in the statement of Theorem 3.1, there is no constraint on the value of H. It would be better if the authors state that H=M in the hardness result, since the hardness result will be trivial if H can be arbitrarily large.\n\nMoreover, the proof in Appendix B is not satisfying. The argument seems to be pretty informal, and should better be regarded as a proof sketch instead of a formal proof. In particular, statements like \"therefore, we cannot gain any information from executing wrong action sequences besides of eliminating this wrong action sequence. \" should be made formal using information theory. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "-_suYUfrP-", "reviewer": "Reviewer_RsHS", "summary": "The authors in this work consider RL under the latent MDP model, where an unknown MDP is sampled from a known set of $M$ MDPs each episode. In this setting, the authors first show a general statistical lower bound which indicates that (approximately) learning optimal policy in the L-MDP setting requires exponential number of episodes (exponential in $M$). Given the hardness result, the authors first resolve the problem in the standard *online* framework where each episode is revealed to the learner after the episode itself: in this scenario, they provide an optimistic parameter estimation algorithm that eventually yields an efficient algorithm with sublinear regret. Finally, the authors show that the learner can actually infer these episodes after they are played assuming separation between the different MDPs and benign initialization (which is also investigated and relaxed into other assumptions such as test sufficiency and reachability of MDPs).", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I believe this is a submission ready for publication. It's a good paper, tackling a problem of potential significance in the community. The paper itself provides both negative and positive results, and gives a full view of the problem in terms of what is possible, what is necessary, etc. Such papers are much appreciated. Clear accept from me.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sufficiently addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors study efficient algorithms and hardness results for Latent MDPs. In a latent MDP, in each iteration, an MDP is randomly drawn from a set of M possible MDPs, and the agent interacts with that MDP without knowing its identity. The goal is to find a policy so that the expected cumulative reward is maximized, where the expectation is taken over the choice of the MDP and its stochasticity. The authors first show that without further assumptions, LMDPs are hard to learn. The authors then give a set of sufficient conditions so that LDMPs are learnable with polynomial sample complexity. One possible condition that makes LMDPs learnable with polynomial number of samples is the case when the identity of the randomly chosen MDP is revealed to the agent at the end of each trajectory. The authors further show that such identity can be learned if certain seperatedness condition holds. Preliminary experimental results are attached. There is a clear consensus amongst reviewers that this is a strong accept. 
Decision: Accept (Spotlight)