{'fraction_non_alphanumeric': 0.042931400541767334, 'fraction_numerical': 0.014642360348488176, 'mean_word_length': 4.251518646674356, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
When Is Partially Observable Reinforcement Learning Not Scary?

Applications of Reinforcement Learning (RL), in which agents learn to make a sequence of decisions despite lacking complete information about the latent states of the controlled system, that is, they act under partial observability of the states, are ubiquitous. Partially observable RL can be notoriously difficult -- well-known information-theoretic results show that learning partially observable Markov decision processes (POMDPs) requires an exponential number of samples in the worst case. Yet, this does not rule out the existence of large subclasses of POMDPs over which learning is tractable. In this paper we identify such a subclass, which we call weakly revealing POMDPs. This family rules out the pathological instances of POMDPs where observations are uninformative to a degree that makes learning hard. We prove that for weakly revealing POMDPs, a simple algorithm combining optimism and Maximum Likelihood Estimation (MLE) is sufficient to guarantee polynomial sample complexity. To the best of our knowledge, this is the first provably sample-efficient result for learning from interactions in overcomplete POMDPs, where the number of latent states can be larger than the number of observations.


Introduction
A wide range of modern artificial intelligence challenges can be cast as Reinforcement Learning (RL) problems under partial observability, in which agents learn to make a sequence of decisions despite lacking complete information about the underlying state of system. For example, in robotics the agent has to cope with noisy sensors, occlusions, and unknown dynamics (Akkaya et al., 2019), while in imperfect information games the player makes only local observations (Vinyals et al., 2019;Brown and Sandholm, 2019). Further applications of partially observable RL include autonomous driving (Levinson et al., 2011), resource allocation (Bower and Gilbert, 2005), medical diagnostic systems (Hauskrecht and Fraser, 2000), recommendation (Li et al., 2010), business management (De Brito and Van Der Laan, 2009), etc. As such, learning and acting under partial observability has been an important topic in operation research, control, and machine learning.
Because of the non-Markovian nature of the observations, learning and planning in partially observable environments requires an agent to maintain memory and possibly reason about beliefs over the states, all while exploring to collect information about the environment. As such, partial observability can significantly complicate learning and planning under uncertainty. While practical RL systems have succeeded in a set of partially observable problems including Poker (Brown and Sandholm, 2019), Starcraft (Vinyals et al., 2019) and certain robotic tasks (Cassandra et al., 1996), the theoretical understanding of learning to act in partially observable systems remains limited. Most existing results in RL theory focus on fully observable systems or, more generally, learning when the features of states are accessible and can faithfully represent value functions. As such, algorithms developed for this case need not to reason about what the latent state may be and in particular do not need to resort to using the observation histories. Thus, the resulting algorithms can be fundamentally limited and may not work beyond the narrow settings that they are designed for. Owning to the ubiquity of partially observable problems, addressing the theoretical challenges of partial observability is vital to closing the gap between the typical applications and the scope of available theoretical works.
This paper considers Partially Observable Markov Decision Process (POMDPs)-the standard model in reinforcement learning that captures the partial-information structure. Despite the existence of many efficient algorithms for learning MDPs in the fully observable settings, learning POMDPs is notoriously difficult in theory-well-known complexity-theoretic results show that learning and planning in partially observable environments is indeed statistically and computationally intractable in general (Papadimitriou and Tsitsiklis, 1987;Mundhenk et al., 2000;Vlassis et al., 2012;Mossel and Roch, 2005), even if in the favorable setting with a small number of states, actions, and observations. However, these complexity barriers are of a worst case nature, and they do not preclude efficient algorithms for learning rich sub-classes of POMDPs which could potentially cover interesting practical applications. This leaves an important question: Can we identify a rich sub-class of POMDPs that empowers sample-efficient RL?
Prior efforts on sample-efficient learning of POMDPs focus either on special cases of POMDPs such as latent MDPs (Kwon et al., 2021a,b), or on general POMDPs but with restrictive assumptions. In particular, Azizzadenesheli et al. (2016); Guo et al. (2016) do not address strategic exploration-a core challenge in RL;Jin et al. (2020a) considers the exploration setting but only addresses undercomplete POMDPs, where the number of states must be no larger than the number of observations. This paper answers the highlighted question above affirmatively. We identify a rich family of tractable POMDPs-weakly revealing POMDPs (see Section 3), which rule out the pathological instances whose observations contain no information to distinguish latent states. Weakly revealing POMDPs are very rich-it contains a majority of existing POMDPs classes which are known to be tractable (Azizzadenesheli et al., 2016;Guo et al., 2016;Jin et al., 2020a); it also handles overcomplete POMDPs where the number of latent states can be larger than the number of observations. We further propose a new simple algorithm for learning POMDPs-Optimistic Maximum Likelihood Estimation (OMLE). As its name suggests, OMLE (read, Oh-Em-El-Eeh) combines optimism with classical maximum likelihood estimation (Wilks, 1938). In contrast to the algorithm of Jin et al. (2020a) which heavily exploit the undercomplete structure, our algorithm is generic, does not explicitly rely on any special structure, and can be used for any POMDPs. We prove that OMLE learns a near-optimal policy for any weakly revealing POMDP within a polynomial number of samples (Theorem 4 and 7). To the best of our knowledge, this is the first provably sampleefficient result for learning overcomplete POMDPs in settings where exploration is necessary. Our result also reasserts that optimism is a powerful tool to address exploration needs, regardless of whether states are observable. We complement our positive results with lower bounds showing that certain polynomial dependency on the problem parameters in our sample complexity is necessary.
Finally, we remark that our algorithm, as well as all existing algorithms for learning large classes of POMDPs, remains computationally inefficient. This is due to the inherent computational hardness of learning POMDPs: planning (i.e., computing the optimal policy given model parameters) alone is already PSPACE-complete (Papadimitriou and Tsitsiklis, 1987), not mentioning the additional computation required for model estimation and exploration. We leave the challenge of computationally efficient learning for future work.

Overview of techniques
The major technical challenge of this paper is to establish the sample efficiency guarantee of OMLE for learning any weakly revealing POMDPs despite the simplicity of the algorithm. Our results rely on the following three key ideas. To the best of our knowledge, the second and the third ideas are novel in the context of learning POMDPs, while the first technique was used by Jin et al. (2020a).
• Observable Operator Model (OOM) (Jaeger, 2000): OOM provides an alternative parameterization of the POMDP model, by representing the probability of a trajectory over observations and actions as the product of a series of linear operators, which is known as observable operators. For more details, see Section 5.1. Such linear structure facilitates us to use existing tools from matrix analysis to analyze POMDPs. Although OMLE algorithm does not explicitly utilize the OOM representation, the observable operators serve as important intermediate quantities in our analysis. They help us to bound the suboptimality of the learned policy as a function of the size of our confidence set.
• MLE-based Confidence Set: In contrast to the current mainstream approaches of learning POMDPs which use spectral methods to directly estimate either the model parameters or the observable operators (see, e.g., Azizzadenesheli et al., 2016;Guo et al., 2016;Jin et al., 2020a), we use the maximum likelihood estimation (MLE) approach, which provides implicit guarantees on learning observable operators. We achieve this by adapting the classic techniques for analyzing MLE (e.g., Geer et al., 2000). An appealing feature of the MLE approach is its generality and that the confidence set construction does not need to rely on the specific structure of the problem. The strength of this unified approach is that it allows OMLE to be used with almost no changes in both undercomplete and overcomplete POMDPs. In constrast, spectral-based algorithms require more careful designs that are adjusted to specific problems (such as undercomplete vs. overcomplete settings). These adjustments, if not done optimally, easily lead to requirement of unnecessary, artificial assumptions.
• ℓ 1 -norm eluder Dimension: To prove the sample efficiency of optimistic algorithms, one needs to argue that, after a sufficient number of iterations, the size of the maintained confidence set is small enough to guarantee near-optimality of the learned policy. In the tabular setting, this is typically achieved by resorting to the pigeon-hole principle (e.g., Azar et al., 2017;Jin et al., 2018), while in the linear setting, one typically uses the so-called elliptical potential lemma (e.g., Lattimore and Szepesvári, 2020). To generalize these argument, Russo and Van Roy (2013) introduced the notion of eluder dimension for sets of real-valued functions with a common domain. The use of MLE-based confidence set requires us to develop a new result which is stronger than the standard elliptical potential arguments: While we have linear structures, the ℓ 2 -norms typically used are not suitable for our purposes. As such, the standard eluder dimension (which is tied to the ℓ 2 -norm) is also unsuitable. To address these challenges, we introduce a variation of the eluder dimension, which is called ℓ 1 -norm eluder dimension, and which might be of independent interest.

Related works
Reinforcement learning has been extensively studied in the fully observable setting (see, e.g., Azar et al., 2017;Dann et al., 2017;Jin et al., 2018Jin et al., , 2020bZanette et al., 2020;Jiang et al., 2017, and the references therein). For the purpose of this paper, we focus our attention on reviewing the theoretical results for partially observable reinforcement learning.
Hardness of learning POMDPs. There is a line of well-known computational hardness results for planning and learning in POMDPs. Firstly, even when the parameters of a POMDP are known, computing the optimal policy (i.e., planning) is PSPACE-complete (Papadimitriou and Tsitsiklis, 1987). Moreover, even if one only wants to find the optimal memoryless policy, the problem is still NP-hard (Vlassis et al., 2012). In addition, the model estimation of POMDPs is also computationally hard-Mossel and Roch (2005) proved an average-case computational result showing that estimating the model parameters for a subclass of Hidden Markov Models (HMMs) is at least as hard as learning parity with noise 1 . Since HMMs can be viewed as special cases of POMDPs without action control, their result directly implies estimating the model parameters of POMDPs is hard. Learning POMDPs is also known to be statistically hard: Krishnamurthy et al. (2016) proved that finding a near-optimal policy of a POMDP in the worst case requires a number of samples that is exponential in the episode length. The hard instances are those pathological POMDPs where the observations contain no useful information for identifying the system dynamics.
Positive results for learning POMDPs. Despite the worst-case hardness results, there is a long history of learning sub-classes of POMDPs. Even-Dar et al. (2005) studied POMDPs without resets, where the proposed algorithm has sample complexity scaling exponentially with a certain horizon time. Poupart and Vlassis (2008);Ross et al. (2007) developed Bayesian methods to learn POMDPs, while Azizzadenesheli et al. (2018) considered learning the optimal memoryless policies with policy gradient methods. PAC or regret bounds are not known for these approaches.
In the category of polynomial sample results, a sequence of recent works (e.g., Guo et al., 2016;Azizzadenesheli et al., 2016;Jin et al., 2020a;Xiong et al., 2021) applied spectral methods (Hsu et al., 2012;Anandkumar et al., 2014) to learning POMDPs and obtained polynomial sample complexity results. Among them, Guo et al. (2016);Azizzadenesheli et al. (2016);Xiong et al. (2021) made strong reachability assumptions and did not address the exploration problem. Furthermore, these results assume that both the transition and emission matrices are full rank, which are stronger than the weakly revealing conditions considered in this paper. Jafarnia-Jahromi et al.
(2021) proposed a posterior sampling-based algorithm, and provided sample-efficient guarantees assuming either sufficient separability between different models, or the success of belief state and transition kernel estimation. These assumptions significantly reduce the difficulty of estimating model dynamics-a core challenge in learning POMDPs, and thus reduce the generality of the results.
The most related work to us is Jin et al. (2020a), which addressed the exploration problem in learning undercomplete POMDPs, where the number of latent states must be no greater than the number of observations. Their algorithm is specially designed to exploit the undercomplete structure of POMDPs. It remains unclear if their techniques can be extended to the overcomplete 1 Learning parity with noise is conjectured to be NP-hard in the theory of computational complexity.
setting. In contrast, this paper presents a new generic algorithm based on MLE, which enjoys provable sample-efficiency in the exploration settings of both undercomplete and overcomplete POMDPs.
Very recently, Golowich et al. (2022) developed the first quasi-polynomial time planning algorithm for a subclass of POMDPs. Their result holds under the γ-observability condition, which is very similar to the weakly-revealing condition presented in this paper. 2 Compared to this paper, the result in Golowich et al. (2022) purely focuses on the computational efficiency. It is restricted to the undercomplete setting, and addresses only planning but not estimation or exploration, all of which are important components for learning POMDPs.
Latent MDPs. Latent MDPs (Kwon et al., 2021a)-where an MDP is randomly drawn from a set of M possible MDPs at the beginning of the interaction-can be considered as a special class of overcomplete POMDPs. Kwon et al. (2021a) proved that learning latent MDPs remains statistically hard in the worst case. They also provided several positive results for learning latent MDPs with additional assumptions, such as revealing the latent contexts at the end of each episode. Kwon et al. (2021b) provided positive results for latent MDPs without these additional assumptions, but the results only apply to the setting of M = 2 with a shared transition. Latent MDPs and weakly revealing POMDPs do not contain each other.
Decodable POMDPs. Block MDPs (Krishnamurthy et al., 2016) are POMDPs whose current latent state can be uniquely determined by the current observation. By simple algebra, one can verify that block MPDs are special cases of single-step weakly revealing POMDPs that satisfy As- The recently proposed m-step decodable POMDPs (Efroni et al., 2022) are generalizations of block MDPs, in which the latent state can be uniquely decoded from the most recent history (of observations and actions) of a short length m. This multistep decodability assumption can also be viewed as a special case of general "weakly revealing"-type of conditions. However, Efroni et al. (2022) assume that m-step history decodes (weakly reveals) the current state, while this paper assumes that m-step future weakly reveals the current state. Finally, we remark that most existing results for block MDPs or m-step decodable POMDPs (see, e.g., Krishnamurthy et al., 2016;Jiang et al., 2017;Du et al., 2019;Misra et al., 2020;Efroni et al., 2022) further involve decoder class or value function approximation, which is beyond the scope of this paper.
RL with function approximation. There is a recent line of research (e.g., Jiang et al., 2017;Ayoub et al., 2020;Du et al., 2021;Jin et al., 2021;Foster et al., 2021) on reinforcement learning with general function approximation. This line of results proposed certain complexity measure for sequential decision making problems, and developed generic algorithms which have sample-efficient guarantees as long as the complexity measure of RL problems is small. These frameworks are known to cover a special subclass of POMDPs-reactive POMDPs (Jiang et al., 2017), where the optimal value only depends on the current-step observation-action pair. It remains highly unclear whether weakly revealing POMDPs identified in this paper can be covered by those general frameworks.
As a result, these two conditions are "equivalent" up to a factor of at most O( √ O).
We remark that investigating this problem requires us to compute those complexity measures for POMDPs, which is highly non-trivial and may require techniques developed in this paper.
MLE approaches in bandit and RL. The idea of using the MLE principle in the confidence set construction can be traced back to Lai (1987), which considers the problem of Bernoulli bandits. MLE-based approaches are also used in the framework of reward-biased MLE (Kumar and Becker, 1982;Mete et al., 2021), which balances the reward with the likelihood value, for learning tabular MDPs. Recently, the MLE-based approaches are also used in the setting of representation learning in RL (Agarwal et al., 2020;Uehara et al., 2021).

Preliminaries
For a positive integer n, we let [n] = {1, . . . , n}. We consider episodic, tabular, partially observable Markov decision processes (POMDP). These processes generalize the standard Markov decision processes by making agents observe a "noisy function" of the state of a controlled Markov process. In a POMDP, the states are generally hidden from the agent: in every step a controlling agent can only see the observations and her own actions. At the beginning of each episode, the environment samples an initial state s 1 from µ 1 . At each step h ∈ [H], the agent first observes o h that is sampled from O h (· | s h ), the observation distribution of hidden state s h at step h. Then the agent receives reward r h (o h ) that is computed from o h , and takes action a h . After this, the environment transitions to s h+1 , whose distribution follows T h,a h (· | s h ). The current episode terminates immediately after a H is taken. We use τ h = (o 1 , a 1 , . . . , o h , a h ) to denote a trajectory from step 1 to step h.
the set of all length-h histories. Given a policy π, we use V π to denote its value, which is defined as the expected total reward received under policy π: where the expectation is with respect to the randomness of the transitions, observations and the policy. Since the state, action, observation spaces and the horizon are all finite, there always exists an optimal policy π ⋆ that achieves the optimal value V ⋆ := sup π V π . Different from MDPs, the optimal policies in POMDPs are in general history-dependent instead of only depending on the current observation, which makes not only learning, but already computing a near-optimal policy in known POMDPs more challenging than doing the same in MDPs.
Learning objective. Our goal is to learn an ε-optimal policy π in the sense that V π ≥ V ⋆ − ε, using a number of samples polynomial in all relevant parameters. We also consider the problem of learning with low regret. Suppose the agent interacts with POMDPs for K episodes, and plays a policy π k in the k th iteration for any k ∈ [K]. The total (expected) regret is then defined as: The question then is whether a learner can keep the regret small.
Notation. We use bold upper-case letters B to denote matrices and bold lower-case letters b to denote vectors. Given a matrix B ∈ R m×n , we use B ij to denote its (i, j) th entry, σ k (B) to denote its k th largest singular value, and B † to denote its Moore-Penrose inverse. For a vector b ∈ R m , we use diag (b) to denote a diagonal matrix with [diag (b)

Weakly Revealing POMDPs
The purpose of this section is to define the class of weakly revealing POMDPs. We first motivate our definition by revisiting the pathological instances which prevent sample-efficient learning of POMDPs in general. We then introduce the formal definition of weakly revealing POMDPs in the undercomplete setting when S ≤ O and finally extend it to the overcomplete setting when S > O. All the proofs for this section are deferred to Appendix H.

Hard instances of POMDPs
Here we revisit the hardness results and the pathological instances constructed by Krishnamurthy et al. (2016) and Jin et al. (2020a). As it turns out, learning POMDPs is statistically hard in the worstcase due to the existence of POMDPs with uninformative observations. It is not hard to see the optimal policy will take action a ⋆ h at step h, which will give a total reward of 1. However, since the agent effectively has no observation in the first H − 1 steps, she has no option but to try out all possible action sequences, which requires A Ω(H) episodes to find the correct action sequence with constant probability.

Weakly revealing condition in the undercomplete setting
Based on the hard instances constructed above, we conclude that if the observations do not contain information to distinguish two different latent states, then learning these POMDPs is statistically hard. For POMDPs with more than two states, the hardness result above can be easily extended to the case where there exist two mixtures of latent states with disjoint support such that the observations do not contain any information to distinguish these two mixtures. Concretely, by a mild abuse of language, a mixture of states is identified by a probability vector ν ∈ ∆ S ; ν 1 and ν 2 are said to have disjoint support if supp(ν 1 ) ∩ supp(ν 2 ) = ∅.
A direct approach to rule out the above-described pathological instances is to just assume that any two latent state mixtures ν 1 , ν 2 that have disjoint support induce distinct distributions over observations, that is, A linear algebraic argument then shows that this condition is equivalent to that the rank of the emission matrix O h is S.

Proposition 2. The emission matrix O h is rank S if and only if the induced distributions over observations are distinct for any two mixtures of latent states with disjoint support.
The weakly revealing condition is simply a robust version of the condition that the rank of the emission matrices is S-it assumes the S th singular value of emission matrix O h is lower bounded. This condition in the undercomplete setting was first identified by Jin et al. (2020a) as a technical condition to ensure the sample efficiency of their algorithms.
This condition ensures that the observations contain enough information to distinguish any two mixtures of states given a sufficiently large number of samples.
We call Assumption 1 the "weakly" revealing condition to distinguish it from the setup known as rich observation or block MDP in the literature (Jiang et al., 2017;Du et al., 2019;Misra et al., 2020). The latter setup considers the problem where the latent state can be directly recovered from any single observation and the stage h in the episode. That is, the latent state is completely revealed by the observation. Therefore, technically speaking, block MDPs are fully observable, which is in a way "diagonally opposite" to the setting we consider.
Finally, we note that since O h is a matrix of size O ×S, Assumption 1 implicitly requires S ≤ O. That is, it only holds in the undercomplete setting.

Weakly revealing condition in the overcomplete setting
In the overcomplete setting, we have S > O. It is information-theoretically impossible to distinguish any two mixtures of latent states by inspecting observations only in a single step. The key observation here is that we should instead inspect the distribution of observations for m consecutive steps. We note that the number of all possible observable sequence (o 1 , a 1 , . . . , a m−1 , o m ) of length m is O m A m−1 , which is larger than S when m ≥ Ω(log S).
To state our assumption, we define the m-step emission-action matrices as follows: For an observation sequence o of length m, initial state s and action sequence a of length m − 1, we let [M h ] (a,o),s be the probability of receiving o provided that the action sequence a is used from state s and step h: (2) Similar to the undercomplete case, the weakly revealing condition in the overcomplete setting assumes that the S th singular value of the m-step emission matrix M h is lower bounded. (2). Assumption 2 ensures that the observable sequence in the next m consecutive steps contain enough information to distinguish any two mixtures of states given a sufficiently large number of observations. Assumption 1 is a special case of Assumption 2 with m = 1.
Finally, we remark that in case that O m ≥ S, a sufficient condition to make Assumption 2 hold is that: for any stage h, there exists a (m − 1)-step action sequence such that the m-step observation sequences under this action sequence is α-weakly revealing the hidden state.

Main Results
In this section, we present our algorithm-Optimistic Maximum Likelihood Estimation (OMLE) and its theoretical guarantees for learning weakly revealing POMDPs in both the undercomplete and the overcomplete settings.

Undercomplete setting
For clarity, we first present the algorithm and results for learning undercomplete POMDPs under Assumption 1. As we will see in the later section, with a minor modification this algorithm also generalizes to learning overcomplete POMDPs under Assumption 2.
Algorithm description To condense notations, we use θ = (T, O, µ 1 ) to denote the model parameters of a POMDP and use Θ to denote the collections of all possible model parameters θ that correspond to POMDPs with S states, A actions, and O observations. To make the dependence on θ explicit, we will use V π (θ) to denote the value of a policy π, while we use P π θ (τ ) to denote the execute policy π k to collect a trajectory τ k : probability of observing a trajectory τ under policy π, when the underlying POMDP is given by θ.
We also use O h (θ) (M h (θ)) to denote the emission matrix of θ (respectively, the multistep emission matrix of θ). Algorithm 1 gives the pseudocode of OMLE. As can be seen from this pseudocode, in each episode k there are two main steps: • Optimistic planning (Lines 3-4): find the POMDP model θ k with the highest optimal value in the confidence set B k and follow the associated optimal policy π k in the episode to collect a trajectory τ k . 4 • Confidence set update (Line 5): add the newly collected policy-trajectory pair into the dataset, and then update the confidence set to include those models that assign a total log-likelihood to the data that is "close" to the maximum possible such total log-likelihood. In particular, the form of the confidence set is θ ∈ Θ : where B 1 is the initial confidence set that contains all α-weakly revealing models of a given size.
Compared to the standard maximum likelihood estimation (MLE) approach, all α-weakly revealing models with a sufficiently high likelihood are allowed and the size of this set is controlled by β ≥ 0. In particular, if β = 0, the confidence set collapses to the solutions of MLE. In our algorithm, the choice of β is governed by the magnitude of the "statistical noise" introduced by various random events. By analyzing this noise, one can choose the value of β to guarantee that the true POMDP model is always contained in the resulting confidence set with a prescribed probability (see Proposition 13 for a rigorous statement).
We emphasize that the algorithm design of MLE is considerably simpler than that of prior provably sample-efficient algorithms for learning POMDPs (see, e.g., Azizzadenesheli et al., 2016;Guo et al., 2016;Jin et al., 2020a), which rely on spectral methods.
Theoretical guarantees Our main result, which shows that OMLE will achieve small regret in any weakly revealing POMDPs (Assumption 1), is as follows: Theorem 4 (Regret of OMLE). There exists an absolute constant c > 0 such that for any δ ∈ (0, 1] and S, A, O, H, K ∈ N, if we choose β = c H(S 2 A + SO) log(SAOHK) + log(K/δ) in Algorithm 1, then, for any POMDP with S states, A actions, O observations and horizon H and satisfying Assumption 1, with probability at least 1 − δ, The proof, as well as the specific polynomial dependency, is presented in Appendix E. Note that the growth rate of regret as a function k is optimal (Auer et al., 1995).
Moreover, by the standard online-to-batch conversion (Cesa-Bianchi et al., 2004), the regret bound immediately implies the following sample complexity result: Corollary 5 (Sample Complexity of OMLE). Under the same setting as Theorem 4, when K ≥ poly(S, A, O, H, α −1 , log(ε −1 δ −1 )) · ε −2 , with probability at least 1 − δ, the uniform mixture of the policies produced by OMLE is ε-optimal. I.e., (1/ Here, theÕ(ε −2 ) dependence is also optimal up to log factors. Previous work by Jin et al. (2020a) also provides polynomial sample-complexity guarantee for learning α-weakly revealing POMDPs under Assumption 1. The present result improves over the results of Jin et al. (2020a) in the following aspects: • While the OOM-UCB algorithm of Jin et al. (2020a) heavily exploited the special structure of undercomplete POMDPs, OMLE appears in a much simpler form and the algorithm design arguably does not use this special structure. As a result, OMLE can be easily extended to learning multi-step weakly revealing POMDPs, while to the best of our knowledge OOM-UCB cannot.
• In terms of theoretical guarantees, OMLE enjoys a near-optimal √ k-regret while OOM-UCB was only shown to achieve a regret of size O(k 2/3 ). The higher regret of OOM-UCB is due to the limitation of its exploration mechanism. 5 Finally, observe that the upper bound in Theorem 4 depends polynomially on the inverse of α-an upper bound on the ℓ 1 -norm of the pseudoinverse of the emission matrices in Assumption 1. This polynomial dependence turns out to be unavoidable as is shown by the following lower bound.
Theorem 6 implies that a polynomial dependence on 1/α is in general unavoidable in the sense that any algorithm either needs to suffer a regret exponential in the horizon H, or its regret needs to be polynomially dependent on 1/α. The proof of Theorem 6 is provided in Appendix G.

Overcomplete setting
We now turn to the more challenging setting of learning in overcomplete POMDPs, where the number of hidden states can be larger than the number of observations. We show that a simple variant of OMLE is able to learn weakly-revealing overcomplete POMDPs in a polynomial number of samples. As we shall see, we pay a nontrivial price for the increased generality: while we can still achieve rate-optimal PAC-results, we compromise on the regret of the algorithm.
Algorithm description Algorithm 2 shows the pseudo-code of OMLE suitable for m-step αweakly revealing overcomplete POMDPs. While the basic structure of the method is the same as before, the general OMLE, which we call multi-step OMLE, differs from the basic version in two important aspects: • Instead of merely following the optimistic policy, Algorithm 2 adopts a more active strategy for exploration. Specifically, for each optimistic policy π k , the learner will one by one experiments with (H − m + 1) policies that are obtained by picking a within-episode time index h ∈ {0, . . . , H − m} and then following policy π k for the first h steps, and then picking actions uniformly at random in the remaining steps of the episode. We denote the resulting policy by π k 1:h • uniform(A ), which abuses notation, but should improve readability.
• When constructing the confidence set, Algorithm 2 requires the minimum singular value of the m-step emission-action matrix (defined in equation (2)) to be lower bounded by α, which enforces the multi-step α-weakly revealing condition in Assumption 2.
By trying random action sequences after executing π k for the initial h steps, the learner can gather more information about the hidden states reachable by π k at step h and therefore can better learn the system dynamics under π k . The price of trying random actions is that the algorithm as described here will in general have linear regret. Nevertheless, with an online-to-batch conversion, Algorithm 2 serves as a suitable approach to learning a good policy with low sample complexity.
Theoretical guarantees Our main result in this section bounds the total suboptimality of the policies π 1 , . . . , π k chosen by OMLE. Note that since OMLE is not following these policies, the regret of OMLE is different (in general, higher) than the total suboptimality.
The specific polynomial dependency is presented in Appendix F. This form of the result is preferred as it makes a comparison to Theorem 4 more direct and it also reveals a bit of the proof strategy. The significance of this result is that, using the standard online-to-batch conversion (Cesa-Bianchi et al., 2004), we get the following sample complexity results.
Corollary 8 (Sample Complexity of multi-step OMLE). Under the same setting as Theorem 7, Up to polylogarithmic factors, the dependence on ε in this result is unimprovable. Using an explore-then-exploit strategy, this latter result gives rise to a method that enjoysÕ(K 2/3 ) regret, where the constants hidden are still polynomial in the relevant quantities. To our knowledge, for small fixed m, this is the first sample-efficient result for learning overcomplete POMDPs in the exploration setting where the algorithm needs to reason about how to collect information efficiently.
A natural question here is whether the exponential dependence on m in Theorem 7 is necessary. We answer this question by providing the following lower bound, which rules out the possibility of an upper bound polynomial in m.
Theorem 9 (Necessity of A Ω(m) dependency). For any m, A ∈ N + , there exists a POMDP with S, H, O = O(m) and satisfying Assumption 2 with α ≥ 1 so that any algorithm requires at least Ω(A m−1 ) samples to learn a (1/2)-optimal policy with probability at least 1/2.

Proof Overview
We provide a proof overview of Theorem 4 for learning undercomplete weakly revealing POMDPs (Assumption 1). We defer the full proof to Appendix E. The proof for learning overcomplete POMDPs (Theorem 7) follows a similar strategy, which is described in Appendix F.

Observable operator models
To begin with, we introduce the observable operators (Jaeger, 2000) that provide an alternate parameterization of POMDPs. These operators will serve as intermediate quantities in our analysis: They will allow us to bound the suboptimality of the learned policies as a function of the "width" of the MLE confidence set.
It is known that the these operators give an equivalent parameterization of the POMDPs: For any policy, the distribution induced by a POMDP over the possible trajectories of observation-action pairs can be described solely using these operators. In particular, the probability of observing trajectory τ h = (o 1 , a 1 , . . . , o h , a h ) under policy π in POMDP model θ is given by where represents the part of the probability of τ h that can be attributed to the randomness of the policy and we used B j (·; θ) to denote the observable operators underlying θ. One important advantage of adopting this operator representation of POMDPs is that the linear structure facilitates us to use existing tools from matrix analysis to analyze the error of operator estimates.

5.2
Step 1: bound the regret by the error of operator estimates By analyzing the relaxed MLE condition, one can prove that the groundtruth POMDP model θ ⋆ is contained in confidence set B k for all k ∈ [K] with high probability (see Proposition 13 in Appendix A). Therefore, from now on assume that θ ⋆ ∈ ∩ k∈[K] B k holds. Now, recall that we choose the model estimate and the behavior policy optimistically in Algorithm 1, i.e., (θ k , π k ) = argmaxθ ∈B k ,π V π θ . As a result, we have where τ H = (o 1 , a 1 , . . . , o H , a H ) denotes a whole trajectory and the second inequality uses the fact that the cumulative reward of each trajectory is bounded by H. Therefore, to prove Theorem 1, it suffices to bound the total cumulated error in estimating the probability of the individual trajectories, cf. the RHS of (6). By using the OOM representations in (5), it turns out that we can bound the RHS of (6) by the error in estimating each observable operator. To simplify notation, we abbreviate With this notation, we have the following result: Lemma 10. For any k ∈ N, the RHS of (6) is upper bounded by In Equation (7) we abused notation in a few ways: In the innermost sum over the observationaction trajectories τ h of length h, τ h−1 refers to the prefix of τ h where the last observation-action is dropped. Also, in this sum, o h , a h refer to the last observation-action pair of τ h .
Lemma 10 is obtained from Lemma 27, which states the same result for an arbitrary sequence of observable operators. As a result, in order to control the regret, it suffices to control the estimation error of each operator. Importantly, here we do not need to recover the operators accurately at all entries, which, in general, is also impossible when there are hard-to-reach latent states. Instead, we only care about the projections of the errors onto the belief vectors, which are further reweighted by the probability of the behavior policies. Therefore, it suffices to learn the operators accurately only in those directions that are adequately covered by the reweighted belief vectors.

5.3
Step 2: derive constraints for the operator estimates from OMLE Now let us make a detour to see what guarantees OMLE can provide for our operator estimates. As a result of the classic MLE analysis (e.g., Geer et al., 2000), we can show under the same choice of β as Theorem 4, with high probability (Proposition 14 in Appendix A gives the precise result.) In brief, this means the model estimate in the k th iteration, that is θ k , can be used to predict the behavior of the policies followed before the k th iteration to a certain accuracy. To proceed, we represent the probabilities in equation (8) by products of operators using equation (5) and perform further algebraic transformations, which eventually leads to the following lemma for our operator estimates. The proof of this lemma is given in Appendix E.2.
Lemma 11. Suppose the relation in equation (8) holds, then for all Intuitively, the constraints above imply the operator estimates in the k th iteration are close to the true operators when being projected onto the belief vectors that are reweighted by the historical policies. However, a careful examination shows that (9) cannot be directly used to control (7) because (7) involves the operator error of θ t reweighted by π t that is the behavior policy in the same iteration. This is very different from (9). We deal with this problem in Step 3.

5.4
Step 3: bridge Step 1 and 2 via ℓ 1 -norm eluder dimension To prove the sample efficiency of optimistic algorithms, one needs to argue that, after a sufficient number of iterations, the size of the maintained confidence set is small enough to guarantee nearoptimality of the learned policy. This is typically achieved by resorting to the pigeon-hole principle in the tabular setting (e.g., Azar et al., 2017;Jin et al., 2018), or to the elliptical potential lemma in the linear setting (e.g., Lattimore and Szepesvári, 2020).
In the context of this paper, by further algebraic transformations, we reduce the problem of bounding (7) by (9) to proving the following algebraic inequality, which plays a similar role as the elliptical potential lemma. The full inequality is more involved (see Proposition 22 in Appendix C); here we present a simplified version for the sake of simplicity.
, where ζ is a parameter that depends on d only.
At a high level, the precondition and the target in Proposition 12 correspond to equation (9) and (7), respectively (see Appendix E.3 for details). In the special case of m = n = 1, Proposition 12 reduces to We compare this with the standard elliptical potential lemma in linear bandit literature (e.g., Lattimore and Szepesvári, 2020), which is typically of the form: We remark that the precondition in (11) directly implies the precondition in (10) by the Cauchy-Swartz inequality. That is, Proposition 12 is stronger than the standard elliptical potential lemma, and we need to develop new techniques to prove Proposition 12.
Noting the close relation between the elliptical potential lemma and the framework of eluder dimension (Russo and Van Roy, 2013) (in its original ℓ 2 -norm form), we develop a new framework based on the ℓ 1 -norm counterpart of eluder dimension, and adapt corresponding techniques to prove that in (10) and Proposition 12 we can allow the choice of ζ = d 2 which is one d factor worse than the standard elliptical potential lemma. We defer the details of this framework to Appendix C.

Conclusion
In this paper, we identified a new rich class of POMDPs, which we call weakly revealing POMDPs. Weakly revealing POMDPs subsume a majority of existing POMDPs that are known to be sampleefficiently learnable, and include both undercomplete and overcomplete POMDPs. We further propose a new simple algorithm, OMLE, which combines optimism with maximum likelihood estimation. We prove that OMLE can learn a near-optimal policy for any weakly revealing POMDP using polynomial samples. We complement our positive results with two lower bounds to justify the necessity of the appearance of certain problem-dependent quantities in our upper bounds. Finally, while our work shows that sample-efficient learning is possible in large classes of POMDPs, computationally efficient learning of POMDPs remains challenging, which we leave for future work.

A Maximum Likelihood Estimation
In this section, we analyze the maximum likelihood estimation (MLE) approach for the following meta-algorithm. Since Algorithm 1 and 2 can be viewed as special cases of Algorithm 3, all the results developed in this section directly apply to their analysis.
Algorithm 3 Meta-algorithm for t = 1, . . . , T do choose policy π t as a deterministic function of {(π i , τ i )} t−1 i=1 execute policy π t and collect a trajectory τ t For the reader's convenience, we recall the definitions of the following notations: (a) θ = (T, O, µ) denotes the ensemble of all the parameters of a POMDP model, (b) Θ denotes the collections of all such POMDP parameter ensembles, and (c) θ ⋆ denotes the parameter ensemble of the groundtruth POMDP that we are interacting with. We will view Θ as a subset of a Euclidean space; in particular, Θ ⊂ R H(S 2 A+SO)+S , so θ, θ ⋆ ∈ R H(S 2 A+SO)+S .
The first proposition shows that, up to certain error, with high probability, the log-likelihood of the groundtruth model computed using the historical data is close to the maximum log-likelihood.
Proposition 13. There exists an absolute constant c such that for any δ ∈ (0, 1], with probability at least 1 − δ: the following inequality holds for all t ∈ [T ] and all θ ∈ Θ Our second claim shows that any POMDP model, whose log-likelihood on the historical data is comparable to that of the groundtruth model, will produce similar distributions of trajectories as the groundtruth model under historical polices.
Proposition 14. There exists a universal constant c such that for any δ ∈ (0, 1], with probability at least 1 − δ for all t ∈ [T ] and all θ ∈ Θ, it holds that The proofs of Proposition 13 and 14 can be found in Appendix B.

B Proofs for Maximum Likelihood Estimation
In this section, we prove the two propositions stated in Appendix A. For technical purposes, we introduce the concept of optimistic ε-discretization. Specifically, we denoteθ as the optimistic ε-discretization of θ so thatθ i = ⌈θ i /ε⌉ × ε for all coordinate i. We comment that althoughθ is not a legal POMDP parameterization, it can still be used to compute the probability of observing any trajectory τ under any policy π by simply replacing θ i withθ i in the computation. In particular, for θ = (T, O, µ 1 ) ∈ R d with d = H(S 2 A + SO) + S, given a trajectory τ = (o 1 , a 1 , . . . , o H , a H ) and a policy π we define Note that the right-hand side gives a probability measure over the trajectories when θ ∈ Θ, but not in general. To simplify the language, we will still call P π θ (τ ) the "probability" of τ no matter whether this is indeed a probability. The significance of using optimistic discretization is that for any θ ∈ Θ and trajectory τ , we always have that We denote byΘ the collections of all suchθ, i.e.,Θ = {θ : θ ∈ Θ}. Throughout this section, we will choose a fixed ε satisfying that for any θ ∈ Θ and any policy π, It is not hard to see that one can choose ε ≤ 1/(C(S + O + A)HT ) for this condition to be satisfied where C is some large absolute constant. Sinceθ belongs to [0, 1] d with d = S + H(S 2 A + SO), the log-cardinality ofΘ defined by this particular ε is at most O(H(S 2 A + SO) log(T SAOH)).

B.2 Proof of Proposition 14
The proof in this section largely follows Agarwal et al. (2020), which is inspired by Zhang (2006). We start by recalling the meta-algorithm (Algorithm 3): in each iteration t ∈ [T ], we pick π t deterministically based on denote the sequence of policy-trajectory pairs observed within the first t iterations, and denote byD a "tangent" sequence {(π i ,τ i )} t i=1 whereτ i ∼ P π i θ ⋆ . Note that D and D share the same policy parts and their trajectories are independently sampled from the same distributions.
Lemma 15. Let ℓ := ℓ(π, τ ) be a real-valued function that maps a policy π and a trajectory τ to R . Let L(D) = t i=1 ℓ(π i , τ i ), and L(D) = t i=1 ℓ(π i ,τ i ). Then, Proof. Before proving the lemma, we remark that all the expectations considered above and below always exist because each τ i and π i can only take finitely many different values. It is direct to see τ i only has finitely many possibilities since the number of observations and actions are finite. As for π i , notice that π i is a deterministic function of {(π j , τ j )} i−1 j=1 in Algorithm 3, so it follows by induction that π i also only takes finitely many different values. Now we prove Lemma 15. .
Our goal is to show that u t = 1. Owning to the definition of {τ i } i , some calculation gives Plugging this into the last expression obtained for u t and using the tower rule with D t−1 = (π 1 , τ 1 , . . . , π t−1 , τ t−1 , π t ) we get Plugging this back into our previous expression, where the second equality used that For anyθ ∈Θ, we define ℓθ(π, τ ) := and ℓθ(π i ,τ i ).
By Lemma 15, Chernoff's method and the union bound, with probability at least 1 − δ, for all θ ∈Θ we have Then, by the definition of Lθ and by the inequality − log Recall that for any θ ∈ Θ and any policy π, P π θ − P π θ 1 ≤ 1/T. As a result, by algebra, where the last inequality follows from the Cauchy-Schwarz inequality. Putting all relations together, we have that with probability at least 1 − δ, for allθ ∈Θ Finally, notice that for all θ ∈ Θ, we have −Lθ(D) ≤ −L θ (D).

C ℓ 1 -norm eluder Dimension
In this section, we introduce the framework of ℓ 1 -norm eluder dimension, and present the corresponding pigeonhole-style regret guarantee. All the proofs for this section are deferred to Appendix D.

C.1 Definitions and properties of ℓ 1 -norm eluder Dimension
To begin with, we define the ε-independence relation between a point and a set of points with respect to a function class under the ℓ 1 -norm.
then we say that this sequence is witness to the ℓ 1 -norm eluder dimension of F.
The difference between the ℓ 1 -norm eluder dimension defined here and the original eluder dimension (Russo and Van Roy, 2013) is that in the definition of independence our ℓ 1 -version evaluates the ℓ 1 -norm of the function on the dataset instead of the ℓ 2 -norm as in the original definition. Therefore, we will refer to the original eluder dimension as ℓ 2 -norm eluder dimension throughout this paper, while we will drop the "ℓ 1 -norm qualifier" whenever it is clear from the context. Proposition 19. The ℓ 1 -norm ε-eluder dimension is always upper bounded by the ℓ 2 -norm ε-eluder dimension.
By combinining the upper bound for the ℓ 2 -norm eluder dimension of d-dimensional linear function classes with Proposition 19, we immediately obtain that the ℓ 1 -norm eluder dimension of any bounded d-dimensional linear function class is at mostÕ(d).

C.2 The pigeonhole principle for the ℓ 1 -norm eluder dimension
Similar to ℓ 2 -norm eluder dimension, we can also prove a pigeonhole-style regret gurantee for the ℓ 1 version. This will play a key role in deriving the final regret bound from the MLE guarantee.

Proposition 21. Let Φ be a set of real-valued functions sharing the domain X and bounded by
Then for all k ∈ [K] and ω > 0, Finally, we instantiate Proposition 21 on a linear function class with Corollary 20, and obtain the following ℓ 1 -norm pigeonhole regret bound.
Then we have D Proofs for ℓ 1 -norm eluder dimension In this section, we provide the proofs for the results in Appendix C.

D.1 Proof of Proposition 19
Proof of Proposition 19. Let x 1 , . . . , x n be an ℓ 1 -norm ε-independent sequence. By definition, there exist f 1 , . . . , f n ∈ F such that for all k ∈ [n] Since ℓ 1 -norm is always an upper bound for the ℓ 2 -norm, we also have for all k ∈ [n] Therefore, x 1 , . . . , x n is also an ℓ 2 -norm ε-independent sequence. Hence, the ℓ 2 -eluder dimension of F is at least as large as the ℓ 1 -eluder dimension of F since any witness of the ℓ 1 -eluder dimension at some scale is a witness of the ℓ 2 -eluder dimension for the same scale.

D.2 Proof of Proposition 21
The proofs in this subsection follow the arguments developed for the analogous statements for the ℓ 2 -norm eluder dimension in Appendix C of Russo and Van Roy (2013). We first prove a few auxiliary claims.

Claim 2. Let Φ be an arbitrary class of real valued functions sharing the common domain
Proof of Claim 2. Let L be defined as in the statement of the claim. If L = 0, there is nothing to be proven. Otherwise we argue as follows.
Initialize the sequences B 1 = {z 1 }, . . . , B L = {z L }, and let j = L + 1. Now, consider the following process: if at any point, z j is ε-dependent on all of the B 1 , . . . , B L , then the claim is proven and we terminate the process. Otherwise, we pick an i ∈ [L] such that z j is ε-independent of B i and update B i := B i ∪ {z j }. Then we increment j by 1 and continue this process if j ≤ κ.
It remains to be proven that the process is terminated before j gets to κ + 1. We prove this by contradiction: Assume that j gets to κ + 1. Let j be the index of a sequence from {B i } i∈ [L] that has the most elements (in case of ties, chose arbitrarily).
. But B j is an ε-eluder sequence by construction, which contradicts that d E (Φ, ε) is the length of longest ε ′ -eluder sequences with ε ′ ≥ ε.
With this, we are ready to prove Proposition 21.
where the one but last inequality follows from Lemma 23 and the monotonicity of ℓ 1 -norm eluder dimension.

D.3 Proof of Proposition 22
Proof. Given v ∈ [Kn], denote p v = ⌊ v−1 n ⌋ + 1 and q v = v − n⌊ v−1 n ⌋. Note that 1 ≤ p v ≤ K and 1 ≤ q v ≤ n. We introduce the following two auxiliary sequences: By the definition of (ζ v,j ),(z j ) and precondition (15), Notice that for all k ∈ So in order to prove Proposition 22, it suffices to upper bound the value of the following optimization problem: Now, we make the observation that the above optimization problem has the same optimal value as the following one (we assume all vectors in this section have the same dimension): It is direct to see the optimal value of Problem (22) is always no larger than that of Problem (21). Kn] are optimal solution to Problem (21). Consider One can easily verify {φ ⋆ k } k∈ [K] and {z ⋆ v } v∈ [Kn] are feasible solution to Problem (21) by triangle inequality. Moreover, its objective value is which is equal to the optimal value of Problem (21). Therefore, it suffices to upper bound the optimal value of Problem (22). Finally, by applying Proposition 21 to d-dimensional linear function class, we can upper bound the optimal value of Problem (22) by We conclude the proof by choosing ω = R w R x /(kn).

E Proofs for Undercomplete POMDPs
In this section, we prove Theorem 4 with a specific polynomial dependency as stated in the following theorem.
Theorem 24 (Regret of OMLE). There exists an absolute constant c > 0 such that for any δ ∈ (0, 1] and S, A, O, H, K ∈ N, if we choose β = c H(S 2 A + SO) log(SAOHK) + log(K/δ) in Algorithm 1, then, for any POMDP with S states, A actions, O observations and horizon H and satisfying Assumption 1, with probability at least 1 − δ, To begin with, we recall (or introduce) some notations that will be needed in the proof.
Notation Denote by τ h = (o 1 , a 1 , . . . , o h , a h ) a trajectory up to step h. (That is, for a natural number h, τ h ∈ (O × A ) h , by convention.) Given a policy π and a trajectory τ h , define π( . This is the part of the probability of τ h that can be attributed to the policy π. We use θ ⋆ = (T, O, µ 1 ) to denote the parameters of the groundtruth POMDP that the learner interacts with, and denote by B the observable operators corresponding to θ ⋆ and by b 0 the initial observation distribution. Formally, where O h (o | ·) is the o th row of the observation matrix O h and diag(O h (o | ·)) is a diagonal matrix with diagonals equal to O h (o | ·). We use θ k to denote the optimistic estimate of the POMDP model in the k th episode of Algorithm 1, and denote by π k the optimal policy of model θ k , i.e., (θ k , π k ) = argmax θ∈B k−1 ,π V π 1 (θ). Finally, we will use B k and b k 0 to denote the operators corresponding to θ k .
For a matrix A, p ≥ 1, let A p = sup x: x p≤1 Ax p . We start with a lemma that bounds B h (o, a) 1 as a function of α: Lemma 25. Under Assumption 1 it holds that for any (o, a, h, k)

Proof. By definition,
where the last inequality uses Assumption 1. The same arguments also give B k h (o, a) 1 ≤ √ S/α.
Computing probabilities using the operators As it is well known (e.g., Jin et al., 2020a), given a set of POMDP parameters θ, its corresponding operators satisfy the following relations for any policy π and trajectory τ h = (o 1 , a 1 , . . . , o h , a h ): where P π θ (τ h ) denotes the probability of observing τ h under policy π in the POMDP model defined by θ, and ({B h (o, a; θ)} (o,a,h)∈O×A ×[H−1] , b 0 (θ)) denote the operators corresponding to θ (Equation (5) in the main body is the first case in Equation (24).) Proof roadmap The proof consists of three main steps. In the first step, we upper bound the distribution estimation error by the operator estimation error. The proof of this follows arguments similar to those used by Jin et al. (2020a). Then we leverage the MLE guarantee developed in Appendix A to derive certain constraints satisfied by the operator estimation error. Finally, we use the ℓ 1 -norm eluder dimension framework developed in Appendix C to bridge the results in the first two steps and obtain the desired regret guarantee.

E.1 Step 1: bound the regret by the error of operator estimates
We first present a lemma that upper bounds the cumulative suboptimality of π 1 , . . . , π k by the cumulative density estimation error.
Lemma 26. In Algorithm 1 and 2, if we choose β according to Theorem 4 and 7 respectively, then with probability at least 1 − δ, Proof. By the choice of β and Proposition 13, we have θ ⋆ ∈ B t for all t ∈ [K] with probability at least 1 − δ. In what follows, we assume that the event θ ⋆ ∈ ∩ t∈[K] B t holds. On this event, by the optimism of θ t and π t for t ∈ [k], Because the cumulative reward of each trajectory is bounded by H, we conclude As a result, to prove Theorem 4, it suffices to upper bound the RHS of Equation (25).
To begin with, we represent the probability of observing τ H by the product of operators using Equation (24), which gives By using the lemma below, we can further control the difference between two products of operators by the difference between each pair of operators. The proof of a more general version of this lemma is given in Section F.4.
As noted in the main text, this lemma abuses notations in a few ways: In the innermost sum over the observation-action trajectories τ j of length j, τ j−1 refers to the prefix of τ j where the last observation-action is dropped. Also, in this sum, (o j , a j ) refer to the last observation-action pair of τ j .
Putting things together, we get Step 2: derive constraints for the operator estimates from OMLE ≤ β. Therefore, by Proposition 14 and the choice of β, we have with probability at least 1 − δ, for all k ∈ [K]: In the rest of the proof, we assume that the event above is true. By the Cauchy-Schwarz inequality, Since marginalizing two distributions will not increase their distance, from the previous inequality we also have that for all (k, h) By equation (24), we can replace the probability with the product of operators and obtain for all where we used that the initial distributions over the observations are independent of the policies used and where (29) shows that the parameter estimates are improving in terms of how well the initial observation distribution is estimated (which is unsurprising). Our goal now is to use the first part of this equation to show that the estimated observable operators are also getting closer to their groundtruth counterparts. To show this, first notice that by the triangle inequality, for any (k, h)

The second part of Equation
In the last display, the second term is at most O( √ kβ) by (29). For the first term, we can apply Lemma 32 and obtain Putting things together, we conclude that with probability at least 1 − δ:

E.3
Step 3: bridge Step 1 and 2 via ℓ 1 -norm eluder dimension By Step 1 (in particular, by Equation (28)), to control the total estimation error of the distributions over trajectories, it suffices to upper bound the following quantity for all k ∈ [K]: Target:

By
Step 2, we have that with probability at least 1 − δ: for all (k, h) From now on, we assume that the two conditions of the last display hold and will show that this suffices to bound the "target" above. By using the first inequality in the condition, the summation of the second term in the target is upper bounded by O( k t=1 β/t) = O( √ kβ). It remains to control the summation of the first term in the target. Now let us consider an arbitrary fixed triple 1]. Denote by X l the l th row of matrix X. The condition implies that To further simplify the notations, for (t, l) We have three observations about the x, w sequences: • The vectors {w t,l } O l=1 satisfy O l=1 w t,l 1 ≤ 1 for all t. By definition and Lemma 25, As a result, we can invoke Proposition 22 and obtain Translating the above inequality back to the operator language gives that for an arbitrary fixed Therefore, we conclude that with probability at least 1 − δ, for all k ∈ [K], Combining the above equality with Step 1 gives: Remark 28. We remark that the regret above can be improved by a factor of O if we adopt a more active strategy for exploration in OMLE. The modified algorithm is a special case of Algorithm 2 with m = 1, which we decribe in details in Section 4.2.

F Proofs for Overcomplete POMDPs
In this section, we prove Theorem 7 with a specific polynomial dependency as stated in the following theorem.
The proof follows a similar three-step recipe to the undercomplete case: first we show that to control the regret it suffices to control the operator estimation error, then we derive some constraints for the operator estimation from the MLE guarantee, and finally we utilize the constraints to upper bound the estimation error with the help of the ℓ 1 -norm eluder dimension framework. The main difference to the previous proof is only that the data generated for building the confidence sets is based on adding exploration to the policies π 1 , . . . , π K .
The reader may find it useful to first read Appendix E before reading this section as we will heavily reuse the notations and techniques developed there.
Notation As usual, we start by introducing (or recalling) the definitions of several notations that will be used in the proofs. Recall we define the m-step emission-action matrices With slight abuse of notations, we reuse B and b to denote the operators for the general setting. Specifically, the operators corresponding to the groundtruth model θ ⋆ is defined as: where the only difference from the undercomplete version (equation (23)) is that we replace the single-step emission matrices with the m-step emission-action matrices. We use θ k to denote the optimistic estimate of the POMDP model in the k th iteration of Algorithm 2, and denote by π k the optimal policy for model θ k , i.e., (θ k , π k ) = argmax θ∈B k−1 ,π V π 1 (s 1 ; θ). We use B k and b k 0 to denote the operators corresponding to θ k . To simplicity the notation, throughout this section, we will use u ∈ (O × A ) m−1 × O to denote a length-(2m−1) observation-action sequence (the observations are interleaved with actions in u). We use u a ∈ A m−1 to refer to the action part of u and u o ∈ O m for the observation part. We further define U := (O × A ) m−1 × O to be the collections of all the (2m − 1)-length action-observation sequences.
Computing probabilities using the operators Similar to the undercomplete case, several useful relations hold for the newly defined operators. In particular, for any policy π, trajectory τ h (with h ≤ H − m ) and observation-action sequence u ∈ U, it holds that where e u is the standard basis vector in R |U| corresponding to u, denote the operators corresponding to θ, and P θ (o h+1:h+m = u o | τ h , a h+1:h+m−1 = u a ) denotes the probability of observing u o at steps h + 1 to h + m conditioning on the first-h-steps history τ h and the player following fixed action sequence u a from step h + 1 to h + m − 1. For a matrix A, p ≥ 1, let A p = sup x: x p≤1 Ax p . We start with a lemma that bounds B h (o, a) 1 as a function of α: Lemma 30. Under Assumption 2 it holds that for any (o, a, h, k We omint the proof of Lemma 30 here since it is basically the same as that of Lemma 25.

F.1 Step 1: bound the regret by the error of operator estimates
To begin with, we upper bound the cumulative regret by the summation of density estimation errors using Lemma 26, As a result, to prove Theorem 7, it suffices to upper bound the RHS of equation (37). Using the first relation in equation (36), we can represent the probability of observing a trajectory by the product of operators, which gives By Lemma 31 (a general version of Lemma 27), we can control the difference between the products of operators by the difference between each pair of operators.
Step 2: derive constraints for the operator estimates from OMLE In what follows we assume the above equation holds. By the Cauchy-Schwarz inequality, Because marginalizing distributions cannot increase their distance, and using the definition of µ t,h , the above relation implies that for any (k, h) By using the two relations in Equation (36), we can replace the probability with the product of operators and obtain that for any (k, h) For the first term in the RHS of Equation (39): where the last equality uses the first relation in Equation (38). For the second term in the RHS of Equation (39): by the second relation in Equation (38).
Therefore, we conclude that for all (k, h) F. 3 Step 3: bridge Step 1 and 2 via ℓ 1 -norm eluder dimension By Step 1, to control the density estimation error, it suffices to upper bound the following quantity for all k ∈ [K]:

By
Step 2, we have with probability at least 1 − δ: for all (k, h) βkH .
Below, we will carry on the proof conditioning on the event that the above relations hold. The summation of the second term in the target can be upper bounded by using the first condition: It remains to control the summation of the first term.
Let's consider an arbitrary fixed h ∈ [H − m]. Denote by X l the l th row of matrix X. The second condition is equivalent to Translating the above guarantee back using the operator language gives that for all k ∈ [K], Combining the above equality with Step 1 gives: k t=1 V ⋆ − V π t ≤Õ S 2 A 3m−2 α 2 k(S 2 A + SO) × poly(H) for all k ∈ [K].

F.4 Auxiliary lemmas
We prove the following auxiliary lemma for general POMDPs. The definitions of the notations can be found in the beginning of Appendix F.
Proof of Lemma 31. To reduce clutter, we abbreviate B k h (o h , a h ) as B k h and denote B k h:j := B k h × · · · × B k j . By triangle inequality, So it suffices prove the following Lemma: Lemma 32. For any index j < h ≤ H − m, trajectory τ j ∈ (O × A ) j , vector x ∈ R O m A m−1 , policy π, and operatorB ∈ {B, B k }, we have Proof of Lemma 32. We only prove the lemma forB = B k since the other case follows exactly the same arguments. By the definition of B k j+1 , we have that the row space of B k h:j+1 belongs to the column space of M k j+1 , which implies Moreover, for any standard basis e i ∈ R S τ h:j+1 B k h:j+1 M k j e i 1 × π(τ h:j+1 | τ j ) = a∈A m−1 o∈O m τ h:j+1 P π θ k (τ h:j+1 | s j+1 = i, τ j ) · P θ k (o h+1:h+m = o | τ h , a h+1:h+m−1 = a) =A m−1 .
Combining all relations together, we obtain where the final inequality follows from Assumption 2.

G Proofs for Lower Bounds
In this section, we prove the two lower bounds presented in Section 4.

G.1 Proof of Theorem 6
Proof of Theorem 6. We construct the hard instance based on combinatorial lock, which we define formally as follows.
1. STATE: We have 2 states, with 1 "good state" s g and 1 "bad state" s b . In other words, at each step h ∈ [H − 1], with probability α we observe the current latent state, and with probability 1− α we receive a dummy observation. That is, with probability α we find out what state we are currently at, and with probability 1 − α, we learn nothing. But at step H, we always directly observe the current latent state. By standard linear algebra, one can verify min h σ S (O h ) ≥ α.

OBSERVATION
3. ACTION AND TRANSITION: There are A different actions and the initial state at step 1 is fixed as s g . We now define the transitions as follows. For every h ∈ [H − 1], we designate one of these actions to be "good", the others"bad". If one is currently in the"good" state and takes the "good" action, then the agent will transition to the "good" state. Otherwise, one will always transition to the "bad" state. For each h ∈ [H − 1], the good action is chosen uniformly at random from A . The current episode terminates immediately after o H is received.
4. REWARD: Viewing every observation at the first H − 1 steps yields a reward of 0. At step H, viewing o g yields reward 1 while viewing o b yields reward 0. As a result, the agent receives reward 1 only if the state s g is reached at step H, i.e., if the good action is taken at every step in the POMDP.