Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight
Authors: Jiacheng Guo
Minshuo Chen
Huan Wang
Caiming Xiong
Mengdi Wang
Yu Bai
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning theory
POMDPs
partially observable reinforcement learning
Primary area: reinforcement learning
TL;DR: We propose a new enhanced feedback model for learning POMDPs, and identify new broad classes of POMDPs that are sample-efficiently learnable under this feedback model.

Abstract: This paper studies the sample-efficiency of learning in Partially Observable Markov Decision Processes (POMDPs), a challenging problem in reinforcement learning that is known to be exponentially hard in the worst-case. Motivated by real-world settings such as loading in game playing, we propose an enhanced feedback model called ``multiple observations in hindsight'', where after each episode of interaction with the POMDP, the learner may collect multiple additional observations emitted from the encountered latent states, but may not observe the latent states themselves. We show that sample-efficient learning under this feedback model is possible for two new subclasses of POMDPs: \emph{multi-observation revealing POMDPs} and \emph{distinguishable POMDPs}. Both subclasses generalize and substantially relax \emph{revealing POMDPs}---a widely studied subclass for which sample-efficient learning is possible under standard trajectory feedback. Notably, distinguishable POMDPs only require the emission distributions from different latent states to be \emph{different} instead of \emph{linearly independent} as required in revealing POMDPs.

Published as a conference paper at ICLR 2024
SAMPLE-EFFICIENT LEARNING OF POMDPS WITH MULTIPLE OBSERVATIONS IN HINDSIGHT
Jiacheng Guo*
Minshuo Chen'
Huan Wang Caiming Xiong Mengdi Wang" Yu Bai
Princeton University "Salesforce Research
ABSTRACT
This paper studies the sample-efficiency of learning in Partially Observable Markov Decision Processes (POMDPs), a challenging problem in reinforcement learning that is known to be exponentially hard in the worst-case. Motivated by real-world settings such as loading in game playing, we propose an enhanced feedback model called "multiple observations in hindsight", where after each episode of interaction with the POMDP, the learner may collect multiple additional observations emitted from the encountered latent states, but may not observe the latent states themselves. We show that cumple-efficieee learning under this feedback model is possible for two new subclasses of POMDPs: mustii-bbsevaaion revealing POMDPs and tabular distinguishable POMDPs. Both subclasses generalize and substantially relax revealing POMDPs-a a widely studied subclass for which sample-efficient learning is possible under standard trajectory feedback. Notably, distinguishable POMDPs only require the emission distributions from different latent states to be different instead of linearly independent required in revealing POMDPs.
INTRODUCTION
Partially observable reinforcement learning problems, where the agent must make decisions based on incomplete information about the environment, are prevalent in practice, such as robotics (Ope- nAI et al., 2019), economics (Zheng et al., 2020) and decision-making in education or clinical settings (Ayer al., 2012). However, from theoretical standpoint, is well established that learn- ing near-optimal policy in Partially Observable Markov Decision Processes (POMDPs) requires exponentially many samples in the worst case (Mossel & Roch, 2005; Krishnamurthy et al., 2016). Such worst-case exponential hardness stems from the fact that the observations need not provide useful information about the true underlying (latent) states, prohibiting efficient exploration. This is in stark contrast fully observable RL in MDPs in which near-optimal policy can be learned in polynomially many samples, without any further assumption on the MDP (Kearns & Singh, 2002; Auer et al., 2008; Azar et al., 2017).
Towards circumventing this hardness result, one line of recent work seeks additional structural conditions under which a polynomial sample complexity is possible (Katt et al., 2018; Liu et al., 2022a; Efroni al., 2022). A prevalent example there revealing POMDPs (Jin et al., 2020a; Liu et al., 2022a), which requires the observables to reveal some information about the true latent state so that the latent state is (probabilissically) distinguishable from the observables. Another approach, which explore in this paper, entails using enhanced feedback models that deliver additional information beyond what is provided by standard trajectory- based feedback. This is initiated by the work of Lee al. (2023), who proposed the framework of Hindsight Observable POMDPs (HOMDPs). In this setting, latent states are revealed in hindsight after each episode has finished. This hindsgght revealing of latent states provides crucial information to the learner, and enables the adaptation of techniques for learning fully observable MDPs (Azar et al., 2017). As result, it allows a polynomial sample complexity for learning any POMDP (tabular or with a low-rank transition) under this feedback model, negating the need for further structural assumptions (Lee et al., 2023).
In this paper, we investigate new feedback model that reveals multiple additional observations- emitted from the same latent states as encountered during each episode- in hindsight to the learner. As opposed to the hindsight observable setting, here the learner does not directly observe the latent states, yet still gains useful information about the latent states via the additional observations. This model resembles practical scenarios such the save/load mechanism in game playing, in which

---

Published as a conference paper at ICLR 2024
the player can replay the game from a previously saved state. Similar feedback models such as RL with replays (Amortila et al., 2022; Li et al., 2021; Lee et al., 2023) have also been considered in the literature in fully observable settings. This feedback model is also theoretically motivated, as the additional observations in hindsight provide more information to the learner, which in principle may allow us to learn a broader class of POMDPs than under standard feedback as studied in existing work (Jin et al., 2020a; Liu et al., 2022a; Zhan et al., 2022: Chen et al., 2022a; Liu et al., 2022b).
Our contributions can be summarized as follows.
We define novel feedback model-POMIDPS with k multiple observations (Ł-MOMDP)) for enhancing learning in POMDPs over the standard trajectory feedback (Section 3). Under k-MOMDP feedback, after each episode is finished, the learner gains additional observations emitted from the same latent states as those visited during the episode.
We propose M-MOOreve POMDPs, a natural relaxation of revealing POMDPs to the multiple observation setting, and give algorithm (k: (E-OMLE) that learn k-MO-revealing POMDPs sample-efficiently under k-MOMDP feedback (Section 4). Concretely, we provide learning results for both the tabular and the low-rank transition settings.
We propose tabular distinguishuble POMDPs as an attempt towards understanding the minimal structural assumption for sample-efficient learning under k-MOMDP feedback (Section 5. While being natural superset of a-MO-revelling POMDPs for all k, also show reverse containment that any distinguishable POMDP is also a d-MM-rrvcaling POMDP with a suffi- ciently large k. Consequently, any distinguishable POMDP can be learned sample-efficiently by reducing to k-MOOrevealing POMDPs and using the k-OMLE algorithm (Section 5.2).
For distinguishable POMDPs, we present another algorithm OST (Section 5.3) that achieves a sharper sample complexity than the above reduction approach and is computationally efficient given POMDP planning oracle. The algorithm builds on a closeness testing subroutine using the multiple observations to infer the latent state up permutation. Technically, compared with the reduction approach whose proof relies implicitly on distribution testing results, the OST algorithm utilizes distribution testing techniques explicitly in its algorithm design.
1.1 RELATED WORK
Sample-efficient learning of POMDPs Due to the Man--Maaviinn characteristics of observations. policies in POMDPs generally rely on the complete history of observations, making them more challenging to learn compared to those in fully observable MDPs, Learning near-optimal policy in POMDPs is statistically hard in the worst case due to an exponential sample complexity lower bound in the horizon (Mossel & Roch, 2005; Krishnamurthy et al., 2016; Papadimitriou & Tsitsiklis, 1987), and also computationally hard (Papadimitriou & Tsitsiklis, 1987; Vlassis et al., 2012).
To circumvent this hardness, a body of work has been dedicated to studying various sub-classes of POMDPs, such as revealing POMDPs (Hsu et al., 2012: Guo et al., 2016; Jin et al., 2020c; Liu et al., 2022a; Chen et al., 2023), and decodable POMDPs (Efroni et al., 2022) (with block MDPs (Krishnamurthy et al., 2016; Du et al., 2019; Misra et al., 2020) as a special case). Other examples include reactiveness (Jiang et al., 2017), revealing (future/past sufficiency) and low rank (Cai et al., 2022; Wang et al., 2022), latent MDPs (Kwon et al., 2021; Zhou et al., 2022), learning short- memory policies (Uehara et al., 2022b), and deterministic transitions (Uehara et al., 2022a). Our definitions of d-MO-revcaling POMDPs and distinguishable POMDPs can be seen as additional examples for tractably learnable subclasses of POMDPs under stronger feedback (O-MO.DP).
More recently. Zhan et al. (2022); Chen et al. (2022a); Liu et al. (2022b); Zhong et al. (2022) study learning in more general Paiiinngg-eeiiivvee State Representations (PSRs), which include POMDPs as subclass. Zhan et al. (2022) show that sample-efficient learning is possible in PSRs, and Chen et al. (2022a) propose a unified condition (B-stability, which subsume revealing POMDPs and decodable POMDPs as special cases) for PSRs, and give algorithms with sharp sample complexities. Our results on (a, ---erelng POMDPs can be viewed as an extension of the results of Chen et al. (2022a) for revealing POMDPs, adapted to the multiple observation setting.
POMDPs with enhanced feedback Another line of work studies various enhanced feedback models for POMDPs (Kakade et al., 2023; Amortila et al., 2022: Li et al., 2021; Lee et al., 2023). Kakade et al. (2023) propose interactive access model in which the algorithm can query for
2

---

Published as a conference paper at ICLR 2024
samples from the conditional distributions of the Hidden Markov Models (HMMs). Shi et al. (2023) study the POMDP with partial hindsight state information, in which the agent can get access to a partial representation of the latent states. In their model, the agent immediately observes the partial information of the latent states, whereas, in our work, the agent gets the information after an episode. Closely related to our work, Lee et al. (2023) study the Hindsight Observable Markov Decision Processes (HOMDPs) as a special type of POMDPs, where the latent states are revealed to the learner in hindsight. Our feedback model can be viewed as a conceptual weakening of their model. Yet we remark that neither is strictly stronger than the other (learnrr can use neither one to simulate the other); see Section 3 for details. Also, in the fully observable setting, Amortila et al. (2022): Li et al. (2021) have studied feedback models similar to ours where the learner could backtrack and revisit previous states.
Distribution testing Our analyses for distinguishable POMDPs build on several techniques from the distribution testing literature (Paninski, 2008; Andoni et al., 2009; Indyk et al., 2012; Ba et al., Batu et al., 2013; Acharya et al., 2015; Chan et al., 2013); see (Canonne, 2020) for a review. Notably, our OST algorithm builds on subroutines for the closeness testing problem, which involves determining whether two distributions n elements are E-close from samples. Batu et al. (2013) were the first to formally define this problem, proposing tester with sub-linear (in n) sample complexity with any failure probability d. Subsequent work by Chan et al. (2013) introduced testers whose sample complexity was theeotiio optimal for the closeness testing problem with constant probability. The sample complexity of their tester in & norm is θ (max //axx/2//////// /e1/3, n (e²)). Our OST algorithm uses an adapted version of their tester and the technique of Batu et al. (2013) to determine whether two latent states are identical with any failure probability through the multiple observations emitted from them.
2011; Valiant & Valiant, 2011: Goldreich & Ron, 2011;
set with
2 PRELIMINARIES
Notations For any natural number n E N. we use [m] to represent the set [n] = 1, 1......, n. Im to denote the identity matrix within Rmxm For vectors, we denote the f--norm as || lIpp and Il- -lg--pp and the expression ||a||| A represents the square root of the quadratic form T Az. Given a set S, we use (SS) to denote the set of all probability distributions defined on S. For an operator O defined on S and a probability distribution E A(S), the notation 0b O - denotes the integral series
We use
...
of O(o s) with respect to b(s), where the integration is performed over the entire set S. For two
and {6x In21. we use a, I O(b,) ) to mean that there exists a positive constant C such that an S C. bb. For X 2 O, we use Poi(A) to denote the Poisson distribution with parameter X.
POMDPs In this work, we study partially observable Markov decision processes (POMDPs) with finite time horizon, denoted P. The POMDP can be represented by the tuple P = (S, A, H,O,do do, { 1=: (TT ) (0r, )==) where S denotes the state space, A denotes the set of possible actions, H E N represents the length of the episode, O represents the set of possible observations, and de represents the initial distribution over states, which is assumed to be known. The transition kernel Tr S A + S describes the probability of transitioning from one state to another state after being given a specific action at time step h. The reward function N' : O + [0, 1] assigns a reward to each observation in O, and O2 : S - A(O) is the observation distribution function at time step h. For a given state E S and observation o E O, Oo s) represents the probability of observing o while in state s. Note that (with known rewards and initial distribution) POMDP can be fully described by the parameter 0 ((Tx)/= (On, ( We use тn
1
(o1:k, d1:x)= = (01, 01. ... Oh-1, Qh-1, On, on) to denote a trajectory of observations and actions at time step h E [H]. We use S, A, O to denote the cardinality of S, A, and O respectively.
7 where Fy : Th-1 x O + A(A) is a mapping from histories up to step h to actions. We detine the value function for for model 0 by Vo(T)=
A policy π is a tuple π =
Hf EP 1E Ty (ox)]. namely as the expected reward received by following x. We use (*(0)= =
max, Vo(aT) and x² =0) arg max, (z( to denote the optimal value function and optimal policy for a model 0. We denote the parameter of the true POMDP as l*. We also use the shorthand ((T)= := Vg- (TT).
3 POMDPS WITH MULTIPLE OBSERVATIONS
In this section, we propose POMDPs with multiple observations (E-MOMDP), a new enhanced feedback model for learning POMDPs defined follows. In the (-th round of interaction, the learner
3

---

Published as a conference paper at ICLR 2024
1. Plays an episode in the POMDP with a policy π², and observes the standard trajectory feedback
+¹ (o) (0)(1) aj. ... OH 1.(1) aiz)) (without observing the latent states {8% (E(T))
2. Receives k -1 additional observations (2(2kk) iid
Ob ~ (-(()))))) for h E [M] after the episode ends.
At k 1, the feedback model is the same as the standard trajectory feedback. At k > 1, the k 1 additional observations cannot affect the trajectory r but can reveal more information about the past encountered latent states, which could be beneficial for learning (choosing the policy for the next round). We remark that such a "replay" ability has also been explored in several recent works, such as Lee et al. (2023) who assume that the learner could know the visited states after each iteration, and Amortila et al. (2022); Li et al. (2021) who assume that the learner could reset to any visited states then continue to take actions to generate a trajectory.
We consider a general setting where the value of k in k-MOMDP can be determined by the learner. Consequently, for a fair comparison of the sample complexities, we take into account all observations (both the trajectory and the (k 1) additional observations) when counting the number of samples, so that each round of interaction counts as kH observationss/amplls..
Relationship with the hindsight observable setting Closely related to k-MOMDP, Lee et al. (2023) propose the hindsight observable setting, another feedback model for learning POMDPs in which the learner directly observes the true latent states {+% k after the /-th episode. In terms of their relationship, neither feedback model is stronger than (can simulate) the other in a strict sense, when learning from bandit feedback: Conditioned on the k 1 additional observations, the true latent state could still be random; Given the true latent state, the learner in general, does not know the emission distribution to simulate additional samples. However, our multiple observation setting is conceptually "weaker" (making learning harder) than the hindsight observatbility setting, the true latent state is exactly revealed in the hindsight observable setting but only "approximately" revealed in our setting through the noisy channel of multiple observations in hindsight.
A natural first question about the K-MOMDP feedback model is that whether it fully resolves the hardness of learning in POMDPs (for example, making any tabular POMDP learnable with polynomially many samples). The following result shows that the answer is negative.
Proposition (Existence of POMDP not polynomially learnable under k-MO feedback for any finite k). For any H, A 2 2, there exists a POMDP with H steps, A actions, and S = O = (non-revealing combination lock) that cannot be solved with ((AH-l) samples with high probability under K-MOMDP feedback for any k 2 1.
Proposition shows that some structural assumption on the POMDP is necessary for it to be sample- efficiently learnable in k-MOMDP setting (proof can be found in Appendix B.1), which investigate in the sequel. This is in contrast to the hindsight observable setting (Lee et al., 2023) where any tabular POMDP can be learned with polynomially many samples, and suggests that k-MOMDP an enhanced feedback model is in sense more relaxed.
4 A-MO-REVEALING POMDPS
We now introduce the class of M-Mo-rev POMDPs, and show that they are sample-efficiently learnable under k-MOMDP feedback.
4.1 DEFINITION
To introduce this class, we begin by noticing that learning POMDPs under the k-MOMDP feedback can be recast as learning an augmented POMDP under standard trajectory feedback. Indeed, can simply combine the observations during the episode and the hindsight into an augmented observation (1:4k (of
( )e(( which belongs to O* (1:) () O}. The policy class that the learner optimizes over in this setting a restricted policy class (denoted as IIsingleobs) that is only allowed depend on
the first entry 0f instead of the full augmented observation 0) (l:k)
(1)
We now present the definition of a k-MO revealing POMDP, which simply requries its aug- mented POMDP under the k-MOMDP feedback is (single-step) revealing. For any matrix O (0(ols) E Rxxx and any & 2 1, let 0&8 go*xs denote the column-wise
self-tensor of 0, given by 0** (01sa))))) T ((o.ss).
4

---

Published as a conference paper at ICLR 2024
Definition 2 (MO-revealing POMDP). For any k 1 and (0. POMDP is said to be (a, -o-eeallnl if its augmented POMDP under the k-MOMDP feedback is a-revealing. In other words, a POMDP is k-MO-revealing if for all h E [H), the matrix 0% has a left inverse 0g IRSxO* (i.e. 05 Iushccch such that
1 ll Saa
Above, we allow any left inverse of 0% and use the matrix (1 + 1) norm to measure the revealing constant following Chen al. (2023), which allows tight characterization of the sample complexity.
As a basic property, we show that (a, -)-O-rrevalling POMDPs are strictly larger subclasses of POMDPs as k increases. The proof can be found in Appendix B.2.
Proposition 3 (Relationship between (a, k)-M-rrevalllnng POMDPs), For all a E (0, and 2 1, any (a, (a, -O-revallg POMDP is also (a, k + 1)-Ml-revallnng POMDP. Conversely, for all 2 2, there exists a POMDP that is (a, k + 1e-eelirve for some a > but not (a', k.)-M-- revealing for any a' 0.
Proposition 3 shows that (a,, -)-0--revalinn POMDPs are systematic relaxations of the standard o-revealing POMDPs (Jin al., 2020e; Liu al., 2022a; Chen et al., 2023), which corresponds to the special case of (a, -)-MO-revaaling with k = 1. Intuitively, such relaxations are also natural, as the k-multiple observation setting makes easier for the observations reveal information about the latent state in any POMDP. We remark in passing that the containment in Proposition 3 is strict.
4.2 ALGORITHM AND GUARANTEE
In this section, we first introduce the k-OMLE algorithm and then provide the theoretical guarantee of l- 1-OMLE for the low-rank POMDPs.
k-Optimistic Maximum Likelihood Estimation (k-OMLE) Here, we provide a brief introduction Algorithm k-OMLE. The algorithm is an adaptation of the OMLE algorithm (Liu et al., 2022a; Zhan et al., 2022: Chen et al., 2022a; Liu et al., 2022b) into the k-MOMDP feedback setting. As noted before, we can cast the problem of learning under k-MOMDP feedback as learning in an augmented POMDP with the restricted policy class singleoos Then, the k-OMLE algorithm is simply the OMLE algorithm applied this problem.
Algorithm:
Concretely, each iteration i E [T] of the k-OMLE algorithm consists of two primary steps:
1. The learner executes exploration policies { (#fh, T 0 where each =h.exp is defined via the од-1 notation as follows: follows n² for the first h steps, then takes the uniform action Un)f(.4), and then takes arbitrary actions (for example using Unif(.A) afterwards (Line 5). All collected trajectories are then incorporated into D (Line 6).
2. The learner constructs a confidence set O' within the model class O, which is a super level set of the log-liilihood of all trajectories within the dataset (Line 7). The policy n² is then selected as the greedy policy with respect to the most optimistic model within @ (Line 3).
Theoretical guarantee Our guarantee for k-OMLE requires the POMDP to satisfy the A-MO- revealing condition and an additional guarantee on its rank, similar to existing work on learning POMDPs ( (Wang et al., 2022; Chen et al., 2022a; Liu et al., 2022b). For simplicity of the presentation, here consider the case of POMDPs with low-rank latent transitions (which includes tabular POMDPs as a special case); our results directly hold in the more general case where d is the PSR rank of the problem (Chen et al., 2022a; Liu al., 2022b; Zhong al., 2022).
Definition (Low-rank POMDP (Zhan et al., 2022; Chen et al., 2022a)). A POMDP P is called low- rank POMDP with rank d its transition kernel T5 S x A S admits low-rank decomposition of dimension d, i.e. there exists two mappings ,*, S + Rdd and 07 : S x A Idd such that Tr (s' 8, pi, (8') (s)
We also make the standard realizability assumption that the model class contains the true POMDP: 8" @ (but otherwise does not require that the mappings {Pī, 4% ), known).
We state the theoretical guarantee for OMLE on low-rank POMDPs. The proof follows directly by adapting the analysis of Chen al. (2022a) into the augmented POMDP (see Appendix C.
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 k-Optimistic Maximum Likelihood Estimation (k- (M-L) and & N.
Input: Model class Q. parameter Initialize:
O, Ø.
2: for iteration / = 1, do'do
3: Set 0r, T = arg max pe0s= Vo(T).
4: for h = 0..........................
do
5: Set exploration policy n Tipexp n on-1 Unif(A).
6:
Execute exp collect k-observation trajectory 7 and add (Th.exp: ) to D. where Th t.(1.k) 1.(1:)))
(of.(2:h) : (xx as in Section 3.
7:
Update confidence set
@ T
Σ
log (
max #EB
Σ (m,rt)
log (g)) {
8:
Return π
Theorem (Results of k-OMLE for (a,, -oM--reval low-rank POMDPs). Suppose the true model 0 is a low-rank POMDP with rank d is realizable (0" & O), and every 0 E θ is (a, k)-MO- revealing, Then choosing 3 Ollog (Ne/8), with probability least 1- 8. Algorithu ourputs policy n such that V V(=*) & within
N = THK = (poly(H))ddA Ne/ (a²=²)
samples. Above, Ne is the optimistic covering number of θ defined in Appendix C.
We also state a result of tabular (a,, -everell POMDPs. Note that any tabular POMDP is also low-rank POMDP with rank d = S A, hence Theorem 5 applies; however the result below achieves slightly better rate (by using the fact that the PSR rank most S).
Theorem 6 (Results of k-OMLE for (a, k)- tabular POMDPs). Suppose 8" is (o. k)) MO-revealing and O consists of all tabular (a, -o-vevelgg POMDPs. Then, choosing B O(H (S² SO) + log(1/5)), then with probability at least 1- 5, Algorithmm I outputs a policy nT such that V (x=)) (T²)) & e within the followinng number of samples:
δ (poly(H))&SA($AAA) 500/ (a²=²))
We remark that the rate asserted in Theorem & 6 also hold for the Explorative Estimation-To To- Decisions (Explorative F2D) (Foster et al., 2021) and the Model-based Optimistic Posterior Sam- pling (Agarwal Zhang, 2022) algorithms (with an additional low-rank requirement on every E θ for Explorative E2D), building upon the unified analysis framework of Chen et al. (2022b;a), See Appendix C.1 for details.
DISTINGUISHABLE POMDPS
Given 6-MO-revealing POMDPs as first example of sample-effiiintly learnable POMDPs under k-MOMDP feedback. it is of interest understand the minimal structure required for learning under this feedback. In this section, we investigate a natural proposal- distiglldistinnnuishablll POMDPs, and study its relationship with k-MO-rrev POMDPs as well as sample-efficient learning algorithms.
5.1 DEFINITION
The definition of distinguishable POMDPs is motivated by the simple observation that, if there exist two states 8;, 8j E that admit exactly the same emission distributions (i.e. Oge; = O,e, E A(O)), then the two states are not distinguishable under k-MOMDP feedback no matter how large k is. Our formal definition makes this quantitiative, requiring any two states to admit a-different emission distributions in the & (total variation) distance.
Definition 7 (Distinguishable POMDP). For any (0, 1}, a POMDP is said be a-distinguishable for all h E [H] (where e, E SRS denotes the i-th standard basis vector),
min ||On(e: e;)ll a.
$$jES
Qualitatively, say POMDP is distinguishable if is a-distinguishable for 0.

---

Published as a conference paper at ICLR 2024
Notably, distinguishability only requires the emission matrix O, to have distinct columns. This is much weaker than the (single-step) revealing condition (Jin et al., 2020a; Liu et al., 2022a; Chen et al., 2022a; 2023) which requires 0 to have linearly independent columns. In other words, in distinguishable POMDP, different latent states may not be probabilistically identifiable from a single observation as in revealing POMDP; however, this does not preclude the possibility that we can identify the latent state with k > 1 observations.
Also, we focus on the natural case of tabular POMDPs (i.e. S, A, O are finite) when considering distinguishable POMDPs', and leave the question extending or modifying the definition to infinitely many states/observations future work.
5.2 RELATIONSHIP WITH --MO-REVEEEEEEE NOORRVVAAINGG POMDPS
We now study the relationship between distinguishable POMDPs and M-MO-revealing POMDPs. Formal statement and proof of the following results see Appendix D.1 and Appendix D.2.
We begin by showing that any M-O revealing POMDP is necessarily distinguishable POMDP. This is not surprising, as distinguishability is a necessary condition for k-MO-revealing if distinguisha- bility is violated, then there exists two states with identical emission distributions and thus identical emission distributions with k iid observations for any k 2 1, necessarily violating --MO-revealing.
Proposition 8 (k-MO revealing POMDPs C Distinguishable POMDPs). For any a E (0, k 2 any (a, k) rrevealing tabular POMDP is distinguishable POMDP.
Perhaps more surprisingly, we show that the reverse containment is also true in a sense if we allow be large-Ant Any a-distinguishable POMDP is also k-MO revealing POMDP for suitable large depending on (S, O, a), and revealing constant (1).
Theorem 9 (Distinguishable C MO-revealing with large k)). There exists an absolute constant for any k 2
C' > O such that any a-distinguishable POMDP is also
(oO)og(SO)/aa
Proof by embedding a distribution test The proof of Theorem 9 works by showing that, for any distinguishable POMDP, the k-observation emission matrix 0% admits a well-conditioned left inverse with suitably large k. The construction of such a left inverse borrows techniques from distribution testing literature, where we embed an identity test (Batu et al., 2013; Chan et al., 2013) with i observations into S O+ matrix, with each column consisting of indicators of the test result. The required condition for this matrix be well-conditioned (and thus 0%* admitting left inverse) is that A is large enough-preciset k 2 Ō(VO/a²) (given by known results in identity testing (Chan et al., 2013)) such that the test succeeds with high probability.
Sample-efficient learning by reduction to A-MO-reveallng case a-distinguishable POMDP is also (1/2, M)) POMDP with k O( O(VOlog(SO))/o) it can be efficiently learned by the ls- k-OMLE algorithm, with number of samples
Theorem 9 implies that, since any
(poy(HnsSAvo(SS*++5500 A S0)/ (a²+²)
given by Theorem 6. This shows that any distinguishable POMDP is sample-efficiently learnable under k-MOMDP feedback by choosing a proper kt
5.3 SHARPER ALGORITIMM: OST
We now introduce more efficient algorithm Optimism with State Testing (OST; Algorithm 2) for learning distinguishable POMDPs under k-MOMDP feedback.
Recall that in distinguishable POMDP. different latent states have a-separated emission distributions. and we can observe k observations per state. The main idea in OST is to use closeness testing algorithms (Chan et al., 2013; Batu et al., 2013) to determine whether any two k-fold observations are from the same state. As long as all pairwise tests return correct results, we can perform a clustering to recover a "pseudo" state label that is guaranteed to be the correct latent states up to a permutation.
When S is infinite (e.g. if the state space S is continuous), requirii any two emission distributions to differ by in & distance may he an unnatural requirement, as near-hy states could yield similar emission probabilitics in typical scenarios.
7

---

OST operates over rounds, beginning with arbitrary initial T, and Ô the model. We set the initial pseudo state space as empty set. Then, each iteration t, OST calculates reward bonuses be a) and (s) to capture the uncertainty of T. and Ō, quantified by the number of visits each latent state in the pseudo state space (Line 4). The bonuses defined in (2) are added to the following Published as a conference paper at ICLR 2024
Algorithm 2 Optimism with State Testing (OST)
Input: POMDP planner POP. parameters 31. .9 0 and lo EN..
Initialize: Emission and transition models Os. Ti. initial pseudo state space [xf] (i.e. nf 0) and
initial visitation counts n n (s, 0 for all S1, E A and h [M
2: for iteration 1.... .T do
3: for all (s, a) E [S] x A do
4: Set (8.
min {VBL/no(s,a) 2H) and (s()) min V/V//////// [s)mm(s)) the exploration
bonus.
5: Set F (8. a) (s) + (b) + (s. a)), where Fz is defined in (2).
6: Update n' POP R.. Ft).
Execute x' to collect a k-ohservation trajectory The where - (of (1(kk))
((1s))
7:
OH ,a
8:
Call DASIGN_PSFUDD__SS STATES (Algorithm
obtain pseudo states { [
9:
Set n (8) = > (M 1(3, = s) for all (h, s) [H] x [S].
10: Set n (s. = Meal 1(5). A ah a} for all s,, E [M] x [8] A.
11: Update T141 and Õ.41 by (3).
12:
return x².
Algorithm 3 Pseudo state assignment via closeness testing (ASSIGN PSEUDO (TATES)
1: for lt E [H] do
2: assigned 0.
3: for 3 E [n do
4: if closeness closeness_test(of (.(1:)) ((((k:)) = accept (Algorithm 4) for all t' [ =3] then 0)
5:
Set 5 = 5, assigned 1, n ni, break 6: if assigned then
7: Set of = ni + 1, 1, m/ +1.
1+1
Given the pseudo states, we can then adapt the techniques from the hindsight observable setting (Lee al., 2023) to accurately estimate the model of the POMDP and learn near-optimal policy.
Algorithm description serves abstraction of the optimal planning procedure that maps any POMDP (T, O, r) to an optimal policy of it.
We first define a planning oracle (Lee et al., 2023; Jin et al., 2020b), which
Definition 10 (POMDP Optimal Planner). The POMDP O planner POP takes as inpul a transition
function T == ( an emission function O= (O and reward function r : S x A > [0, 1] and returns a policy π = (TP O, to maximize the value function under the POMDP with h=11 and reward function
latent transitions (Th Tk= emissions )
empirical reward estimates (Line 5). We then call POP to calculate the policy for the current iteration and deploy it to obtain a k-observation trajectory from the k-MOMDP feedback (Line 6-7).
r(o) (6) = min [in(
F (s. a) = E.oo EtE(o
(2)
We next employ closeness testing and clustering to assign pseudo states (7,....,37) to the trajectory Tk (Line 8) using Algorithm 3. For each k-observation of((1:b) generated in the new iteration,
perform a closeness test with all past (o) (1((1)))) to check if they belong to the same pseudo state: Two states are the same state their l observations pass closeness testing, different if they fail
t.(1:k) passes the closeness test Using the test results, we perform a simple "clustering" step: If o,
against all (or ((::)) who has been assigned as pseudo state ă. then we assign 8 to o (.(1:a) If the state not assigned after all tests, then that indicates the encountered latent state has been encountered
8

---

Published as a conference paper at ICLR 2024
Algorithm 4 Closeness Testing closeness ( [E) (6( kEER))
Input: [ [ot) kejN] Sample N1,... NM ~ Poi(k/M where M = 0(0g((1/))
2: return fail if N1 + +... + NM > k.
3: for j [M] do
4: B, (Ni
N, 1, NN +
N₂}-
5: No LiER, 110, 0). No) EiEn, 1 o}.
6: z 1(oo ((Ng)) -N No No (/No + No.) S /3N,).
7:
return accept 2 2(6 M/2, else reject
1.(1:k) with new pscudo before (not in the current pseudo state space (m/]), in which case we assign On
state ni, 1, which enlarges the pseudo state space to [n%, [n] = [m] +
Our particular closeness testing algorithm (Algorithm 4) adapts the test and analysis in Chan et al. (2013) and makes certain modifications, such repeating test with Poisson number of samples (og(1/6) times to reduce the failure probability from a (11) constant to 6, as well as imposing a hard upper limit & the total sample size (so that the test be implemented under the k-MOMDP feedback), instead of a Poisson number of samples which is unbounded.
Finally, using the assigned pseudo states, update the visitation counts of each (pseudo) state 8 and state-action (s, a) (Line 9-10). Then we update the pseudo latent models (T++1, O+41) = ([T++11 (1T Th=1 11
Th=1) using empirical estimates based on the previous data (Line 11):
4. t 8) -Ete()) 1,H.=s,of T (s' 8,,a) = EnE(H) min(La) (s.a))
(3)
min(I. (+))
Theoretical guarantee We now present the main guarantee for OST for learning distinguishable POMDPs. The proof can be found in Appendix D.3. Further, OST is computationally efficient given the planning oracle POP, as all other operations in Algorithm 2 takes poly (H, S, O,O,T, k) time.
Theorem 11 (Learnining distinguishable POMDPs by OST). For any a-distinguishable POMDP. choosing 31 O(H3 O O0O (oS and k: O((v0/a2 02/3 /a //3)), with probability least 6, the output policy of Algorithm 2 s-optimal after the following number of samples:
ō (poly(M))
SO
SAK
-00(po)((())
(
S0 SAVO
SAO2/3 Ea44/3
E²0²
The proof of Theorem 11 builds on high-probability correctness guarantees of closeness jest which enables to adapt the algorithm and analysis of the hindsight observable setting Lee al. (2023) if all tests return the correct results (so that pseudo states coincide with the true latent states up to permutation). Compared to the rate obtained by OMLE (Eq, (1)), Theorem achieves a better sample complexity (all three terms above are smaller the S2 AO 1.5 /(a?=²) term therein, ignoring H factors). Technically, this is enabled by the explicit closeness tests built into OST combined with sharp analysis of learning tabular POMDPs with observed latent states, rather than the implicit identity tests used the reduction approach (Theorem 9) with the k 1-OLEE algorithm.
CONCLUSION
In this paper, we investigated k-Multiple Observations MDP (k-MOMDP). a new enhanced feedback model that allows efficient learning in broader classes of Partially Observable Markov Decision Processes (POMDPs) than under the standard feedback model. We introduced two new classes of SOMDDP---MO-reveall
POMDPs and distinguishable POMDPs and designed sample-efficient algorithms for learning in these POMDPs under 6-MOMDP feedback. Overall, our results shed light on the broader question of when POMDPs can be efficiently learnable from the lens of enhanced feedbacks. We believe our work opens up many directions for future work, such as lower bounds for the sample complexities, identifying alternative efficiently learnable classes of POMDPs under k-MOMDP feedback, generalizing distinguishable POMDPs to the function approximation setting, or developing more computationally efficient algorithms.

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDDEMENTTS
Mengdi Wang acknowledges the support by NSF grants CPS-2312093, 1MS-1953686, IIS-2107304, CMMI1653435, ONR grant 1006977 and C3.AI.
REFERENCES
Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. Advances in Neural Information Processing Systems, 28, 2015.
Alekh Agarwal and Tong Zhang. Model-baset RL with optimistic posterior sampling: Structural conditions and sample complexity, 2022.
Philip Amortila, Nan Jiang, Dhruv Madeka, and Dean P. Foster. A few expert queries suffices for sample-efficien RL with resets and linear value approximation, 2022.
Alexandr Andoni, Piotr Indyk, Krzysztof Onak, and Ronitt Rubinfeld. External sampling. In Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part 36, pp. 83-94, Springer, 2009.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances neural information processing systems, 21, 2008.
Turgay Ayer, Oguzhan Alagoz, and Natasha K. Stout. Or forum a POMDP approach to person- alize mammography screening decisions. Operations Research, 60(5):1019-1000 1034,, 2012. ISSN 0030364X, 15265463. URL http: //www//www////////////////////// jstor.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pp. 263-272. PMLR. 2017.
Khanh Do Ba, Huy I. Nguyen, Huy N Nguyen, and Ronitt Rubinfeld. Sublinear time algorithms for earth mover's distance. Theory of Computing Systems, 48:428 442, 2011.
Tuugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM (JACM), 60(1):1-25, 2013.
Stephen Boyd and Lieven Vandenberghe. Introduction to applied linear algebra: vectors, matrices, and least squares. Cambridge university press, 2018.
Qi Cai, Zhuoran Yang, and Zhaoran Wang. Reinforcement learning from partial observation: Linear function approximation with provable sample efficiency. In International Conference on Machine Learning, pp.
PMLR, 2022.
Clément Canonne. survey on distribution testing: Your data is big. but is it blue? Theory of Computing, pp. 1-100, 2020.
Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant. Optimal algorithms for testing closeness of discrete distributions, 2013.
Fan Chen, Yu Bai, and Song Mei. Partially observable RL with B-stability: Unified structural condition and sharp sample-efficient algorithms. arXiv preprint M2Xi::200.1149900 2022a.
Fan Chen, Song Mei, and Yu Bai. Unified algorithms for RL with decision-estimation coefficients: No-regret, PAC, and reward-free learning, 2022b.
Fan Chen, Huan Wang, Caiming Xiong, Song Mei, and Yu Bai. Lower bounds for learning in revealing POMDPs. arXiv preprint arXiv:2302.0133, 2023.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference Machine Learning, pp. 1665-1674. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2024
Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforcement learning with a short-term memory. In International Conference on Machine Learning, pp. 5832- 5850. PMLR. 2022.
Dylan J. Foster, Sham Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. CoRR, abs/2112.134433 2021. URL httttp:///axiv.... 2112. 13487.
Oded Goldreich and Dana Ron. On testing expansion in bounded-degres graphs. Studies in Complexity and Cryptography Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pp. 68-75, 2011.
Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A PAC RL algorithm for episodic POMDPs. In Artificial Intelligence and Statistics, pp. 510-518. PMLR, 2016.
Daniel Hsu, Sham M Kakade, and Tong Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 78(5): 1144460008800 2012.
Piotr Indyk, Reut Levi, and Ronitt Rubinfeld. Approximating and testing k-histogram distributions in sub-linear time. Proceedings of the 31st ACM JGMOD-SIGACT--SIAA symposium on Principles of Database Systems, pp. 15-22, 2012.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete POMDPs. Advances in Neural Information Processing Systems, 33: 18530-18539, 2020a.
Chi Jin, Sham M. Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reintorcemnnt learning of undercomplete POMDPs, 2020b.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Leurning Theory, pp. 2137-2143. PMLR, 2020c.
Sham M. Kakade, Akshay Krishnamurthy, Gaurav Mahajan, and Cyril Zhang. Learning hidden markov models using conditional samples, 2023.
Sammie Katt, Frans Oliehoek, and Christopher Amato. Bayesian reinforcement learning in factored POMDPs. arXiv preprint arXiv: 1rX1v:1811..0512,, 2018.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49:209-232, 2002.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RL for latent mdps: Regret guarantees and lower bound. Advances in Neural Information Processing Systems, 34: 24523-24534, 2021.
Jonathan N Lee, Alekh Agarwal, Christoph Dann, and Tong Zhang. Learning in POMDPs is sample-efficient with hindsight observability, arXiv preprint arXiv:2301.13857 2023.
Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, and Yuting Wei. Samplc-efficient reinforcement learning is feasible for linearly realizable mdps with limited revisiting, 2021.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? arXiv preprint 2284002200400866, 2022a.

---

Published as a conference paper at ICLR 2024
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle-a generic model-based algorithm for partially observable sequential decision making. arXiv preprint arXiv:2209. 14997, 2022b.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning. pp. 6961-6971. PMLR, 2020.
Elchanan Mossel and Sébastien Roch. Learning nonsingular phylogenies and hidden markov models. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 366-375, 2005.
OpenAI, Ilge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, Jonas Schneider, Nikolas Tezak, Jerry Tworek, Peter Welinder, Lilian Weng, Qiming Yuan, Wojciech Zaremba, and Lei Zhang. Solving rubik's cube with robot hand, 2019.
Liam Paninski. coincidence- test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54(10))4750 2008.
Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):441450,, 1987.
Ming Shi, Yingbin Liang, and Ness Shroff. Theoretical hardness and tractability of POMDPs in RL with partial hindsight state information, 2023.
Masatoshi Uehara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Computationally efficient PAC RL in POMDPs with latent determinism and conditional embeddings. arXiv preprint arXiv:2206. 12081, 2022a.
Masatoshi Uehara, Ayush Sekhari, Jason Lee, Nathan Kallus, and Wen Sun. Provably efficient re- inforcement learning in partially observable dynamical systems. arXiv preprint 120000 2022b.
Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 685-694- 694, 2011.
Nikos Vlassis, Michael L. Littman, and David Barber. On the computational complexity of stochastic controller optimization in POMDPs. ACM Transactions on Computation Theory (TOCT), 4(4): 1-8, 2012.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Embed control partially observed sys- tems: Representation learning with provable sample efficiency. arXiv preprint arXiv:2205. 13476, 2022.
Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason Lee. PAC reinforcement learning for predictive state representations. arXiv preprint arXiv:2207.05738, 2022.
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C. Parkes, and Richard Socher. The ai economist: Improving equality and productivity with ai-driven tax policies, 2020.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. A posterior sampling framework for interactive decision making. arXiv preprint arXiv:2211.01900 2022.
Runlong Zhou, Ruosong Wang, and Simon S Du. Horizon-free free reinforcement learning for latent markov decision processes. arXiv preprint arXiv:22100. 1604, 2022.
12

---

Published as a conference paper at ICLR 2024
A TECHNICAL LEMMAS
Lemma A.I. Suppose Y, {0, 1) for all 8 E S, and the locations of the 1's are disjoint within the rows & E S. The matrix Y is defined by
Then we have
1-11-11 =1
Proof of Lemma A.I. Let's analyze the action Y on an arbitrary non-zero vector x R Since each column of Y has most non-zero element, which is 1, the action of Y x is:
Σn Mi
T
Yx
Σ
Jis
Here, Xj, is the element of x corresponding to the non-zero entry in row 8 of Y. Then, we have:
8
O
Y x
= |
It follows that
Yx | < 1 for any
RO*
Y 1-+1 S 1.
Now let's find a non-zero vector x for which ||x]| to 1, i... 2; for all i. Then, the action of Y x is:
Let x be the vector with all elements equal
||x|||
Yx
This gives us || 2 1.
Combining the two inequalities, we finish the proof of Lemma A.1.
Lemma A.2. Suppose E is matrix satisfies that |E 1->1 < 1, then I I+ E is invertible.
Proof. To prove this lemma, we will show that I + E has eigenvalue equal to zero. If there 0 is an eigenvalue and there exists x + 0, s.t.
F) O,
which means
| = ||
This implies that [|111 1, which contradicts with the fact that [|]111 < Hence I must be invertible.
D
B PROOFS FOR SECTION
B. PROOF OF PROPOSITION
Proof. Inspired by the bad case Liu et al. (2022a), we construct a combination lock to prove the proposition, which is defined as follows:
13

---

Published as a conference paper at ICLR 2024
Consider two states, labeled "good state" (sy) and "bad state" (56), and two observations, 0g and Ob. For the initial H steps, the emission matrices are
(
1/2 1/2 1/2 1/2 )
while at step H, the emission matrix becomes
( 11 0 )
This implies that no information is learned at each step h E [H 1]. but at step H, the current latent state is always directly observed.
In our model, there are A different actions with the initial state set as 8g. The transitions are defined follows: For every h E [H - 1]. one action is labeled "good", while the others are "bad". If the agent is in the "good" state and makes the "good" action, it remains in the "good" state. In all other scenarios, the agent transitions to the "bad" state. The good action is randomly selected from for each h E H - 1]. The episode concludes immediately after is obtained.
All observations during the initial H steps get reward of O. At step H, observation Og produces reward of 1, while observation yields O. Therefore, the agent receives a reward of solely if it reaches the state 8n at step Hf, i.e., the optimal action is taken at every step.
Assume attempt to learn this POMDP using algorithm X', where k-multiple observations, to interact with the POMDP. Regardless of the selection of k, no information can be learned at step [H 1], making the best strategy random guess of the optimal action sequence. More specifically, the probability that X incorrectly guesses the optimal sequence, given that we have T guesses, is
given T episodes, with
( (AH-1-1) (AZ-1) (A- -T)AA-
For T' < AA"-1110, this value is at least 9/10. Therefore, with minimum probability of 0.9, the agent learns nothing except that the chosen action sequences are incorrect, and the best policy can produce is to randomly select from the remaining action sequences, which is less efficient than (1/2) This concludes our proof.
B.2 PROOF OF PROPOSITION
Proof. First, we prove the existence of an (a, k + 1)-M0-revelling POMDP P that is not an (a,, k))- MO-revealing POMDP. To this end, suffices to consider a POMDP with single step (H 1) with emission matrix C O E O
We consider the following POMDP with = 1, O = 2 and S = + We denote O for 02) and S {s1,- ) The probabilities 0(01 s:) and O(2 s;) for i E [K 2] are denoted as u, and 0; respectively, with {ei..... Uk+2] C (0, 1) being distinct. It should noted that u, + 2 = for any i.
We first consider the rank of Oal R22 (k++2) Note that (0* only depends on the number of o 's and 02 within ol which only has k + possibilities (of, of k-1 02.-- of)). Therefore, O only has at most (k: + 1) distinct rows, and thus rank(O**)) < k Since k+1 min (2 + 2} for all & 2 2, O,k is rank-deficient, and thus the constructed POMDP with emission matrix O is not an (a', Mo--O-revelln POMDP for any a' > 0.
Next, we consider the rank of @0++ Using similar arguments above, 00++1 has (A + 2) distinct rows, and thus its rank equals the rank of the corresponding (A: + 2) x (k + 2) submatrix:
u k+1
k+1
k+1 "k42
u
U1
u2u2
2k+2
A+1
1+1
R+1 144
14

---

Published as a conference paper at ICLR 2024
By rescaling each column with 1/u the resulting matrrix is a Vandermonde matrix generated by distinct values (e and thus has full rank (Boyd & Vandenberghe, 2018, Exercise 6.18). This implies that 0 is full-rank and thus admits a finite left inverse (for example its pseudo inverse) (0@k+1)+ with finite (1 + 1) norm. This shows the constructed POMDP is (a, 1)MO-revaaln with a (10k++) 1 >0.
Now we prove that any (a, koe-kk------- ----eealllln POMDP also an (a, k + Let d be an (a, reveellg POMDP. Fix any h E [H] and let O = On for shorthand. Let (aty) kg represent the O matrix of P, where i E O and E S. Let (big)is denote the 0ok+ matrix of P, where E S and j E Ok:
POMDP.
By the definition of O we have the following equations:
Σ
0e.01-oo o' (s =s}, Vs, ES.
(4)
mo FOR
Let (āzj)is represent the 0Sk+1 matrix of P, where OK+1 and j S. Note that have ao 10
Oor 0(x++1 s).
Now we construct 00++I+ = (bız)ss as b 00.01--0241 = 00. For all s, s' E S, we have:
Σ
b 0 0041 00:1i''
b Cor or O(ok+1 s')
11
Σ
Ds 001 Oa.
01-00EEOM
= (1
where the last equation follows from (4). This shows that the constructed (DSk+1)+ is indeed a left inverse of 000+1 Further, for any vector R o
have
( (ooktttttll = =Σ Σ
|0 Vor Pou
Σ
Σ
bs.0r 1oo41
NES 02st
SES OLE11
Σ (00 111 a Σ DE+1
| aa
ok+1
This shows that (0 Il -a Since the above holds for any h [H], have P is an (a, ls 1)-revealing POMDP.
C PROOFS FOR SECTION
C.1 PROOF THEOREM 5 AND THEOREM 6
First, define the optimistic cover and optimistic covering number for any model class θ and 0. The definition is taken from Chen et al. (2022b).
Lemma C.1 (Optimistic cover and optimistic covering number (Chen al., 2022b)). Suppose that there is context space X. An optimistic p-cover of θ is tuple (iP; 0 where Op θ is finite set, JP- (.)
E
R T 20
specifies optimistic likelihood function for each 0 Og, such Be
that:
1. For 0 E O there exists 0n O, satisfying: for all T and n, it holds that 0, (T) > Pr(r);
2. For 0 E Og, max, |2 (TH =) -
575 (TH = pp
The optimistic covering number Ne(p) is defined as the minimal cardinality of O2 such that there exists such that (P, is an optimistic p-cover of O.
15

---

Published as a conference paper at ICLR 2024
Remind that consider the k-MOMDP as augmented POMDP and note that we going find
the optimized policy in singleabs: which only depends on the single immediate observation 0n (1)
Our k-OMLE algorithm can be seen as an adaptation of Algorithm OMLE in Chen et al. (2022a) to the augmented POMDP with policy class singiiabbs
Chen et al. (2022a) showed that OMLE achieves the following estimation bound for low-rank POMDPs.
Theorem C.2 (Theorem 9 in Chen et al. (2022a)). Choosing 3 = Olog (Na/5)). then with probability at least 1 - 6, Algorithm OMLE outputs policy n² such that V. - Vo- (T²) < e, after
Ô (poly((f)dssRA loge (a²=²)
samples, where they considered POMDPs as Predictive State Representations (PSRs), and desR is the PSR rank. In our setting, the poly(H) is H (accounting for the additional H² factor introduced by reward scaling and H factor by counting the number of samples instead of episodes). For low-rank POMDP, drsn I d, where d is the rank of the decomposition of the transition kernel.
In the proof of Theorem 9 in Chen et al. (2022a), the use of the policy class is based on the fact that the policy x² at each iteration is chosen to be the optimal policy within the model confidence set Of for that round, specifically x' arg maxøget. (T). By replacing the policy class with Trss we still maintain this property, ensuring that the chosen policy remains optimal within the updated model confidence set. Therefore, the replacement is valid and does not affect the optimality of the selected policies throughout the algorithm. In k-OMLE, we can select the model class ( covering of the original model class (with a single observation), which will induce an O'vverrigin of the augmented POMDP class by the k-fold product structure of the augmented emission matrix. Therefore, since the covering number only depends logarithmically on the precision parameter, the e-covering number for the augmented POMDP class will not change when omitting the logarithmic term. Hence, by invoking Theorem C.2 and the above argument, we obtain the convergence rate stated in Theorem 5.
For tabular POMDPs with S states, the PSR rank becomes S. Additionally, Liu et al. (2022a) showed that log (p) I O(H(S discussion about the covering number as above, the covering number is also Ô (HSS A SO)). derive the convergence rate for the tabular case.
(og(HHA/)))) By utilizing this result and repeating the
Therefore,
Extension to Explorative E2D and MOPS The above augmentation (considering k-MOMDP as augmented POMDP and searching in Ilsingleobs) can also be applied to extend Theorem 10 in Chen et al. (2022a). The theorem is achieved by Algorithm Explorative (Explorative E2D). Furthermore, it can be extended to Theorem F.6 in Chen et al. (2022a), which is achieved by Model-based optimistic posterior sampling (MOPS). The OMLE, Explorative E2D, and MOPS extension 1-MOMDPs share the same sample complexity rates.
coiinattonnto-eeciiiiin
MOPS and E2D require slightly stronger conditions compared to OMLE, While OMLE only necessi- tates 0* possess the low PSR rank structure, E2D requires every model within θ to exhibit the same low-rank structure. All three algorithms require every model within θ to be k-MO-revealing, not just 0*
D PROOFS FOR SECTION 5
D.I PROOF OF PROPOSITION 8
Proof. We utilize proof by contradiction to establish the validity of this problem. Suppose we have tabular POMDP, denoted by P. that is not distinguishable. Hence there exists i, E S, such that
Oxxxe e;)ll, 0,
which means that there must exist two different states, s and 52 belonging to S, such that they share the same emission kernels. As a result, the columns associated with $ and 82 will be identical. Consequently, the f-lold tensor power of the observation space 0 for P will be renk-deficient matrix, implying that it lacks a left inverse. This leads us to conclude that P cannot be a revealing POMDP. This contradiction substantiates original proposition, hence completing the proof. |1]
16

---

Published as a conference paper at ICLR 2024
D.2 PROOF OF THEOREM 9
Proof. Consider any a-distinguishable POMDP and any fixed / E [M]]
Step 1. By lemma D.3, construct Z, (o for each S, such that
Ze S 1/2 with probability at least 8 under 0% (-(s), and Z, Z 1 with probability least 1 under 0, (-Is") for any s' s.
Step 2. For every E S, define "identity test for latent state s":
(1(xx)) = 1 Zo(01x) min Z (01x) E {0, 1}. s'ES
with an arbitrary tre-brea rule for the min (such as lexicographic order). Understand Y, E RO* vector. Define matrix
E RBSXO*
YA ==
By step 1, we have
Y4 4, Is E,
where the matrix E E RSS satisfies E,yl - 88. We pick 5 = 1/(252) (which requires k > vO/a² log 1/)). Further, notice that each Y, E {0, 13 o+ and the locations of the I's are disjoint within the rows s S. By Lemma A.1 we have
| =
Step 3. Notice that (where {e, J JEES rows of E)
|B = max
c x
Σ
Eleoll S S < 1/2.
||
#ES
SES
By Lemma A.2 we know that Is + E is invertible. Further, we have
1
(Is + E) (Is Is + 1)* E
2. E 1-+1
1
|
k=1
1-11
km
Finally, define the matrix
@ == (Is + E) E)- Vn SxO
We have Oak O
(Is + E) 11 0gh0 (Is + E)- - (Is + E)) Is. Further,
10 |1-1 S (Is F) - / 2.
This completes the proof.
D.3 PROOF OF THEOREM 11
Proof. First, introduce the Hindsight Observable Markov Decision Processes (HOMDPs), POMDPs where the latent states are revealed to the learner in hindsight.
HOMDP (Lee al., 2023) There are two phases in the HOMDP: train time and test time. During train time, at any given round E [T'. the learner produces history-dependent policy œ' which is deployed the partially observable environment as the learner is interacting with standard POMDP. Once the f th episode is completed, the latent states $f. are revealed to the learner in hindsight, hence the terminology hindsight observability. Lee et al. (2023) showed that HOP-B achieves the following estimation bound for HOMDPs.
Theorem D.1 (Theorem 4.2 in Lee et al. (2023)). Let M HOMDP model with S latent states and O observations. With probability at least - 6, HOP-B B outputs sequence of policies n' ...., mT such that
Reg(T) = H (SO SA)T
17

---

Published as a conference paper at ICLR 2024
Adapted modified setting where each latent state yields K observations, by adapting their proof (using all K observations collectively to estimate the emission matrices), we have
(T) = H V SAAT))
(5)
Our proof is reduction from the result (5) combined with results for closeness testing to ensure that states are correct (up to permutation). Suppose in algorithm the pseudo-states are indeed true states (up to permutation). Then, our algorithm 2 achieves the sample complexity
SO E2
SAVO
SAO2/3
ThH = Ō H
+
E²O²
e2A/3
Now explain our proof, our Algorithm 2 are different from HOP-B in points:
1. HOP-B works for HOMDP, where the exact information of the pseudo-states can be immediately known. In k-MOMDP, cannot determine the exact state even when we can distinguish all the states. Therefore, Algorithm 2 reduces to the HOP-B algorithm up to permute.
2. Since we cannot know the exact pseudo-states, couldn't assume the reward the pseudo state space X' is known for each E X. We can only estimate the reward towards the estimated emission kernel.
rh(o)) 1 {sf = = =o]
a),aa
Σ C.lo (.(o)s))n(o)
(8)
LEJA
where 0g is the estimated emission kernel in the t-th iteration. This leads to an extra between the estimated reward function F and true reward function (x = Eoco O(o ())
Since assume the reward function r can be bounded by 1, the error between the estimated reward function F and true reward function r(s, a) can be bounded as:
Fn(ss a) - rn(ss,)) a) = Σ (o) s) - -o s)))
oEO
<
Σ
|0 () O(o |s]]--
oEO
which can be bounded by (oog(((O//))/////
with probability 1 - 8 as showed in Lee et al. (2023). Hence we can additionally handle the reward estimation, however, this will not result in change of the rate, as we can just choose larger constant in the exploration bonus for states in their HOP-B algorithm (line4, 32) to ensure optimism still holds.
The previous theorem requires the pseudo-states to be true. To ensure this requires the guarantee of closeness testing, which we give here, we will prove
Section D.4. We state that with high probability, we could identify the pseudo-states (up to permutation), which means that after an iteration, we could know whether the states visited in this iteration were visited before. use the closeness testing algorithm to test whether two observation sequences were generated from the same state.
Lemma D.2 (Closeness testing guarantee). When k = + 4/3) log 1/8), with probability - the following holds: Throughout the execution Algorithm 2, we have that there exists permutation π S - S, such that pseudo-states are up permutation of true states (we could identify each state).
After identifying the pscudo-states (up permutation), can think that we have information about the state after each iteration, as we said in Section
On the success event of closeness testing, states are indeed correct. Therefore we can invoke (5) to obtain the sample complexity
Tklf - 11.
S0 2
+
SAK) 22
)
=ō
H
SO 2
+
SAVO
SA02/3
))
2
EPa//3
18

---

Published as a conference paper at ICLR 2024
by taking & O((VV(((v))))))) 0 //+) log 1/6) the bound of Theorem D.1, which finish the proof.
D.4 CLOSENESS TESTING
In this section, we prove the theoretical guarantee for closeness testing.
Proof of Lemma D.2. Let's assume X ~ Poi(A). We have tail bound for X: for any 0,
S - (Ata))l(((+)))
P(X
Employing this tail bound, we conclude that Algorithm will not return fail with a probability of 1 O()). Our subsequent analysis is contingent upon this event.
Based on Proposition 3 in Chan et al. (2013), given & = O((VOa² + +0/3 10//3/////// //3/3) log 1/6), we can infer that for any j E [M]] z = with a probability of at least 2/3 if of f-(1=k) and of ((ssk) generated from the same state, Z = with probability of at least 2/3 if they are produced by different states. Utilizing standard repeating techniques, we find that with (log })) iterations, we can attain error probability of at most 8.
(.(1=k) and o (1:()))) are generated from the same state, Algorithm Thus, we' ve established that if on will return accept with probability of 1 6. Conversely, if they generated from different states, the algorithm 4 will return a reject with probability of 1 5.
Algorithm 5 Closeness Testing closeness closeness_testt2(ddf (E(K))
kE(H))
Input: [of) kE(N
1: Sample NI. NM Poi(k/M), where M (llg((16))
2: return fail if N1 + +... NM > k.
3: for E [M] do
4: Bj = (N1 +........ (N 1, I.... N1 +... -.
NO EieB, 1(0 = o}.
5:
6:
AUI = (o:03 a/(5))
C EoeAth ((No N2q,)²2 )/Ngo))
7:
8: 200 1(06) < &Nya2/10}:
9:
return accept if Σ)E(M] 2 2 M/2, else reject
Lemma D.3. Suppose P is an a-distinguishable POMDP, then we can construct tests 2. (Z, (O1.k (aok)))oo. Jou for each s S, such that Z, = O with probability least å under 0₂ (-ss) and Z, with probability at least 5 under 0g. (-1s') for any s' +
Proof. We construct Z. by using the closeness testing technique.
First, we give consider a problem: Given samples from an unknown distribution p, is it possible distinguish whether equal to O versus p being o-far from every O?
Chan et al. (2013) proposes an algorithm to achieve its lower bound vo/a². We improve their algorithm by repeating log( (1g(1 times to attain error probability of most 8. We denote 4o O 8). The algorithm is listed in Algorithm 5.
Finally, apply the repeating technique Theorem 2 in Chan al. (2013). Then set k v²/a² log 1/6 and (01.a) /closeness_tess22(oaaa accept). Hence we can identify whether an observation sequence 01.k is generated from state s with probability - Therefore, we complete the proof of Lemma D.3.
19


Reviews:
[{"review_id": "DajkIhyZFK", "reviewer": "Reviewer_FWjL", "summary": "Summary: \n\nThe papers consider learning in POMDPs, where in addition to receiving a single observation along the trajectory as is the case for standard POMDP setting, the learner can also get K additional observations from the corresponding latent states at every timestep (but at the end of the trajectory). The authors consider structural assumptions under which learning with K-observations is statistically tractable and provide algorithms to tackle them. The main results are as follows: \n1. First, the authors show via a lower bound that even under the K observation model, we need additional assumptions to make learning tractable. \n2. Then they consider additional structural called multi-observation revealing POMDPs and distinguishable POMDPs under which statistically efficient learning is possible. The former considers a rank-type assumption on the observation matrix whereas the latter considers a separability assumption on the columns. The two assumptions are equivalent to each other up to polynomial factor blow-up in k. \n3. They provide algorithms for efficient learning under the above assumptions.", "questions": "Apart from the ones listed in the weaknesses above. I have a few more questions: \n\n1. Can the authors provide examples / settings where there is a computational or statistical separation between K = 1 and K > 1. I am guessing that proposition 3 already captures this, but can you please provide more intuition on why we can expect such separation. \n2. Are there settings where one can get k-observations but only at the end of the episode? In particular, one needs to wait to terminate to get more observations. \n3.  From what I understand, it is a feature of the algorithm that only needs full trajectory information to construct MLEs. Hence, there is no separation between getting k-observations in real-time or at the end of the episode. Is there a fundamental separation between the two settings? \n4. What is the dependence on H in the sample complexity bound?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. A new framework to consider POMDPs, and get statistically efficient algorithms. \n2. Easy-to-understand analysis. The paper is only 20 pages long which is rare in the modern RL theory literature. This is primarily because the approach heavily builds on the OMLE algorithm from Liu et. al. 2022a. \n3. A complete set of results.", "weaknesses": "1. The considered approaches are only statistically efficient. Can the authors provide a discussion on the possibility of getting computationally efficient or oracle-efficient algorithms? \n2. I am not yet convinced by the motivation for considering k-observation settings, or natural problem settings where one can get k-observations in hindsight at the end of the trajectory. Can the authors provide examples of settings where (a) one can get k-observations, but (b) we do not have the ability to reset to the latent state (or generative model)? My worry is that the ability to reset to the latent state needs knowledge of the latent state which is practically equivalent to hindsight observability (in the game playing example provided in the paper one seems to need knowledge of the latent state to reset).  \n\n\nAnother related work to compare to: \"Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations\", Dann et. al. 2021. Their algorithm seems to work for POMDP settings with low-rank dynamics - while the dependence on d is exponential, their work does not seem to require any lower bound on \\alpha and thus could be applicable when d is small/constant but \\alpha could be arbitrarily small. I am pointing this out because the authors seem to portray \\alpha-distinguishable POMDPs as the largest class of POMDPs that could be solvable statistically efficiently, however,  Dann et. al. 2021 gives another example which is solvable under orthogonal assumptions.", "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": "", "extra_scores": {}}, {"review_id": "akdJN3cY8m", "reviewer": "Reviewer_se9m", "summary": "This paper studied how to achieve sample-efficient learning in POMDPs, which have been known to be exponentially hard in the worst case. How to identify efficient feedback model and provide efficient learning algorithms for the challenging POMDP problem has been an important problem in the community. This paper studied the settings with additional observations generated by the latent unknown states at the end of the episode. With these additional observations and the additional assumptions, i.e., definition 2 and definition 7, this paper proposed efficient learning algorithms with performance guarantees.", "questions": "1. Could you provide one or more practical examples for the model with multiple observations?\n\n2. Could you explain the practical meaning of the assumptions, e.g., definition 2 and definition 7?\n\n3. Could you give a clearer explanation for the differences between your results and those for weakly-revealing settings, since it seems the algorithm developments and performance analyses are quite similar?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This paper studied the important and challenging POMDP problem, and showed two new subclasses where efficient learning is possible.\n\n2. This paper provided efficient learning algorithms for the new subclasses with performance guarantees.", "weaknesses": "1. The model and assumptions are not well-justified.\n\n2. The solution seems to be a simple extension of the existing results for weakly-revealing settings.", "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": "", "extra_scores": {}}, {"review_id": "UEhTDwjcup", "reviewer": "Reviewer_q33U", "summary": "The paper introduces two new subclasses of POMDP, multi-observation revealing POMDPs and distinguishable POMDPs. The paper shows a connection between the two classes of POMDPs and shows that sample-efficient learning in both classes is possible.", "questions": "1. What is the difference between k-MO revealing POMDPs in this work and MO revealing POMDPs in https://proceedings.mlr.press/v202/chen23ae.html, Definition 1?\n\n2. How does obtaining multiple observations in **hindsight** affect the learnability/sample efficiency? Why the same sample efficiency cannot be achieved with the observations obtained online?\n\n3. Shouldn't learnability for alpha-distinguishable POMPDs be established in a PAC setting rather than absolutely?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The work builds on the ongoing effort to establish classes of POMDPs for which sample efficient learning is possible. The new classes of POMDPs are formally and rigorously defined, and their introduction is backed by practical motivation. Bounds on sample efficiency are established and proved, with some proofs using less common techniques of distribution testing embedded in the algorithm. I have read and I believe I understood the proofs, although I cannot swear that the proofs are correct.", "weaknesses": "It is not clear to me whether MO revealing POMDPs are novel --- see my question below. \n\nIt is not clear to me from the paper how hindsight observations are related/required. It seems that MO revealing POMDPs are defined independently of hindsight observability. Definition 2 does not require or that the observations are obtained in the hindsight.\n\nThe significant results of the work seems to be only applicable to tabular POMDPs, which only becomes clear deep into the paper. I believe that should be stated early.\n\nMinor: the bibliography is not properly capitalized. Abbreviations (POMDP, PAC etc.) and names should be capitalized.", "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": "", "extra_scores": {}}, {"review_id": "9wXtZYQqYc", "reviewer": "Reviewer_jqb5", "summary": "This work studies the problem of sample-efficient learning in POMDP. Especially, a new feedback model is discussed, i.e., multiple observations in hindsight, where instead of one observation in canonical POMDP setting, after one trajectory, multiple extra observations can be obtained. This feedback model extends the canonical single-observation feedback model in POMDP and is suitable to capture applications such as game-playing where replaying or loading is enabled.\n\nBased on this new feedback model, one new revealing condition is presented, i.e., multi-observation revealing, which is extended from canonical revealing conditions in POMDP. Based on this condition, the k-OMLE design is first proposed, which is demonstrated to be sample efficient. Then, a second class of POMDP, defined as distinguishable POMDP, is also introduced, which relies on the intuition that different states should have distinct observation generation. The relationship between multi-observation revealing POMDP and distinguishable POMDP is established. Furthermore, leveraging the techniques from closeness testing and POMDP with hindsight observation, a new design, OST, is proposed, which is also demonstrated to be sample efficient.", "questions": "- First, it would be really helpful if the authors can illustrate more on the technical innovation of this work. Especially, I would love to know whether the authors believe the main contribution of this work is to identify new subclasses of POMDP while the leveraged techniques are mostly same as previous works.\n\n- Also, in the design of OST, as stated in Theorem 11, the value of \\alpha is required to determine the value of k, which seems to be a rather stringent condition. I would love to hear about the authors' opinion on this.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The POMDP problem has received growing interest in recent years and this work is a valuable investigation following the line of identifying learnable subclass of POMDP, which makes reasonable contribution.\n\n- The overall motivation is also clear, i.e., having a class of POMDP with stronger feedback than single observation while still weaker than directly revealing the true state. Having multiple observations is also a valid and practical consideration in my view as indeed replaying or loading is often allowed in settings such as game-playing.\n\n- The paper is organized well and the overall flow is quite clear. Although being technically heavy, the key points and main intuitions are explained well.", "weaknesses": "- The major concern that I have is that this work mainly rely on techniques from previous works. Especially, k-OMLE, as the authors stated, is a different instantiation of the OMLE algorithm, and the proof is also extended rather straightforwardly. While I do believe using closeness testing and the notion of distinguishable POMDP are interesting, the OST design is then about returning to the POMDP design with exact hindsight observability.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)