PAC Reinforcement Learning for Predictive State Representations
Authors: Wenhao Zhan
Masatoshi Uehara
Wen Sun
Jason D. Lee
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement learning theory (statistical learning theory)

Abstract: In this paper we study online Reinforcement Learning (RL) in partially observable dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is an expressive model that captures other well-known models such as Partially Observable Markov Decision Processes (POMDP). PSR represents the states using a set of predictions of future observations and is defined entirely using observable quantities. We develop a novel model-based algorithm for PSRs that can learn a near optimal policy in sample complexity scaling polynomially with respect to all the relevant parameters of the systems. Our algorithm naturally works with function approximation to extend to systems with potentially large state and observation spaces. We show that given a realizable model class, the sample complexity of learning the near optimal policy only scales polynomially with respect to the statistical complexity of the model class, without any explicit polynomial dependence on the size of the state and observation spaces. Notably, our work is the first work that shows polynomial sample complexities to compete with the globally optimal policy in PSRs. Finally, we demonstrate how our general theorem can be directly used to derive sample complexity bounds for special models including $m$-step weakly revealing and $m$-step decodable tabular POMDPs, POMDPs with low-rank latent transition, and POMDPs with linear emission and latent transition. 

Under review as a conference paper at ICLR 2023
PAC REINFORCEMENT LEARNING FOR PREDICTIVE STATE REPRESENTATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper study online Reinforcement Learning (RL) in partially observ- able dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is expressive model that captures other well-known models such as Partially Observable Markov Decision Processes (POMDP). PSR represents the states using set of predictions of future observations and defined entirely using observable quantities. We develop novel model-based algorithm for PSRs that can learn a near optimal policy in sample complexity scaling polynomially with respect to all the relevant parameters of the systems. Our algorithm nat- urally works with function approximation to extend to systems with potentially large state and observation spaces. We show that given realizable model class, the sample complexity of learning the near optimal policy only scales polyno- mially with respect to the statistical complexity of the model class, without any explicit polynomial dependence on the size the state and observation spaces. Notably, our work is the first work that shows polynomial sample complexities compete with the globally optimal policy in PSRs. Finally, we demonstrate how our general theorem can be directly used to derive sample complexity bounds for special models including m-sttp weakly-revealing and m-step decodable tabu- lar POMDPs, POMDPs with low-rank latent transition, and POMDPs with linear emission and latent transition.
INTRODUCTION
Efficient exploration strategies in reinforcement learning have been well investigated many mod- els from tabular models [25, 2] to models with general function approximation [10, 27, 30, 16, 42]. These works have focused fully observable Markov decision processes (MDPs); however, their algorithms do not result in statistically efficient algorithms in partially observable Markov decision processes (POMDPs). Since the markovian properties of dynamics often questionable in prac- tice, POMDPs are known to be useful models that capture environments in real life. While strategic exploration in POMDPs was less investigated due its difficulty, it has been actively studied in re- cent few years [20,3 3, 29]. In our work, we consider Predictive state representation (PSR) [36, 41, 24] that is more general model of controlled dynamical systems than POMDPs.
PSRs are specified by the probability of a sequence of future observations/actions (referred to as test) conditioned on the past history. Unlike the POMDP model, PSR directly predicts the future given the past without modeling the latent state/dynamics. PSRs can model every POMDP, but potentially result in much more compact representations; there are dynamical systems that have finite PSR ranks, but that cannot be modeled by any POMDPs with finite latent states [36, 24].
PSRs are not only general but also amenable learning and scalable. First, PSRs can be effi- ciently learned from exploratory data using a spectral learning algorithm [6] motivated by method- of-moments [23]. This learning algorithm allows us to perform fast closed-form sequential filtering, unlike EM-type algorithms that would be the most natural algorithm derived from POMDP per- spectives. Secondly, while original PSRs are defined in the tabular setting, PSRs also support rich functional forms through kernel mean embedding [4]. Variants of PSRs equipped with neural net- works have been proposed as well [43, 9, 46,44449 49].
In spite of the abovementioned advances in research PSRs made in the recent two decades, strategic exploration without exploratory data has been barely investigated. To make PSRs more practical, it is of significant importance understand how to perform efficient strategic exploration.

---

Under review as a conference paper at ICLR 2023
m-step
m-step decodable POMDPs
PSRs
weakly-revealing POMDPs
Efroni et al. [13]
+
Liu et al. [37]
Jiang al. [26]
Uehara et al. [45]
+
Our Work
Table 1: Comparison of our work with existing works. + means that algorithms can learn the near globally optimal policy with polynomial sample complexities. Our work the only work that has desirable guarantee on three models. In m-step weakly-revealing POMDPs, in Uehara et al. [45] means the sample complexity is quasi-polynomial but not polynomial. In m--tte decodable POMDPs, all of the works have certain caveats. More specifically, in Efroni et al. [13], Uchara et al. [45], it is unclear whether they can avoid ( On the other hand, our result can surprisingly avoid poly([O|m)) ())) while we need regularity assumption. For more details, refer to Section 5. In PSRs, o in Jiang et al. [26] means the guarantee is limited to reactive PSRs where the optimal value function depends on current observations. Similarly, in Uehara et al. [45] means the algorithm can compete with short-memory policies but not near globally optimal policies.
To the best of the author's knowledge, Jiang et al. [26], Uchara al. [45] tackle this challenge; however, they fail to show results with polynomial sample complexity to compete with the globally optimal policy. We aim to obtain algorithms that can compete with the globally optimal policy with polynomial sample complexity. Another desideratum for algorithms is to permit for general function approximation. This desideratum important to enjoy the scalable property of PSRs. In summary, the key question wish to address in this work is:
Can we design provably efficient RL algorithms for learning PSR with function approximation?
Contributions. Our main contributions are summarized below. This is summarized in Table 1.
1. We develop the first PAC learning algorithm for PSRs that can compete with the globally optimal policy and identify the PSR rank desR as the key structural quantity of PSR systems. Starting with realizable model class, our algorithm learns near-optimal policy with sample complexity scaling polynomially in dpsR and the statistical complexity (log bracket number of the model class), without any explicit polynomial dependence the size of state and observation space. Thus, our approach can be applied to large-scale partially observable systems.
We demonstrate how our general result can be seamlessly applied existing POMDP models with function approximation. These models include tabular m-step weakly-revealing POMDPs [37] and tabular m-step decodable POMDPs [13]. Especially, our work is the first work that ensures PAC guarantees with polynomial sample complexities for m-step weakly-revealing POMDPs and m-step decodable POMDPs simultaneously. We further show sample complex- ity results when these two types of POMDPs have additional two types of structures permit for large state/observation space: with low-rank latent transition and with linear latent transition and observation distributions, which all have desR much smaller than |S].
Notations. In this work we use [n] to denote the set f1,2.-.. .n. and [n] (0, 1.2.....,,1) n for any positive integer n. For any set C, we use (C] to denote its cardinality and [Re]eec to denote the vector whose entry is for all c E C. We also use Ac to represent the set of all probability distributions over C. For any vector x, we use || [|. || and ||
+ to denote the set
denote its é1, la and foo norm. For any matrix M, use (M),. to denote the (i. entry of M and M to denote the pseudo inverse of M. We also use |M 100,00 to denote max;,; [(M) )r and [|M 1-+1 to denote its & norm / ||Ma]] In addition, we use miia (M) to denote the minimum nonzero singular value of M and a, (M) to denote the n-th largest singular value of M.
Related works. Our work is mostly related to the literature on provable online RL algorithms for PSRs without offline exploratory data. Although there is a growing body of literature that discusses efficient online learning for POMDPs under various structures [3, 20, 34, 35, 40, 7], there are few works [26, 45] that study strategic exploration in PSRs and none of them obtain polynomial sample complexity results for learning globally optimal policies. See Appendix B for details.
2

---

Under review as a conference paper at ICLR 2023
all histories
D
Dn
core test set Un
(thi
desie) 'n
P (
APSRA) (R+1
h+1
FA
n+1
tests
Apsna
(1t1
(3h
hh+1
FA
Cn+1
m sas
P 177+)
P ( dosmn))
11thh
m hi11
x
%
x
[ (h+1 (1)
[1gezl desnet)
(++1
core test set
Minimum core histories
KR
Una1
Figure I: Illustration of the key concepts in PSRs using the system dynamics matrix Dú, indexed by all tests and all histories. Denote dPSR, as the rank of Dú. A core test set Uh+1 is a subset of tests such that the submatrix D2, whose rows are indexed by tests in Uh+1 has rank dPsR. Thus any row in Dr, can be written as a linear combination of the rows in D A core test set Uh+1 whose size exactly equal to dPSR,A is called minimum core test set. The minimum core history set is a diseR subset of histories such that the submatrix K2 of T), whose columns are indexed by the history in the minimum core history set has rank dPsR, h. Any column in Dr, can be written as linear combination of columns indexed by histories the minimum core history set.
2 PRELIMINARIES
In this section, we introduce the definition and key properties of PSRs. After that, we state our learning objective for PSRs with function approximation.
2.1 PREDICTIVE STATE REPRESENTATIONS
We consider an episodic sequential decision making process P (0, (r H). where O is the observation space, A is the action space, P is the system dynamics, Fh is the reward function at h-th step and H is the length of each episode. We suppose the reward rı at h-th step is a deterministic function of (on, an) conditioned on the history Tı where Th (01, (0,,ai,,--- , Oh, an))
We assume the initial observation on of each episode follows a fixed distribution E Ao. At step h E [H]. the agent observes the observation on and takes action On based on the whole his- tory (Th-1, on). After that, the agent receives its reward rh( (o), ax) and the environment generates 0h+1 ~ (. After the agent takes aи, we suppose the environment will only generate dummy observations Odummy no matter what actions the agent takes afterward.
Policy and value. A policy {TT (Ox A)a11 O - A specifies the action selection probability at each step conditioned on the history (Th-1,0n) Given any policy æ, its value V" is
the expected cumulative reward as defined below: V= == E. Σ
-== ri.. where the expectation is w.r.t. to the distribution of the trajectory induced by executing æ in the environment. We use p (7) to represent the probability of trajectory when executing policy æ in the environment.
2.1.1 KEY CONCEPTS IN PSRs
Tests and Linear PSRs. A test is sequence of future observations and actions. For some test t = (Onsh+w-1, 0h:h-w-2) with length W E N+, we define the probabil- ity of test to being successful conditioned on reachable history Th-1 as P(t == do -2)), i,e., the probability of observing Ph:h+W-1 by actively exe- cuting actions 01:h+ conditioned on history Th-1. When the history Th-1 unreachable, i.e.,
(oo:/T:-1, Here, we remark conditional probability of 0h.b4w-1 given 7h- is not specified not only by dynamics, but also by the policy. Given policy æ, conditional probability of om.44-11 given 7h-1 under a policy n. is -o Qh-k+W-2 ~ T) x II - ((or/re--)TTe(aa/ (e- oc). The do(ax:h+w-2 operator
'The do operator means that P -
= Ti+
(hx-1:0p0-1) -1)
can be understood as policy that deterministically picks actions a, for h < t < h W 2, i.c. (A,
(/77-1, 0.) da.-
3

---

Under review as a conference paper at ICLR 2023
PT (T)-1) 0 for all policy म, define the conditional probability P(ta/ to be O. Now, we define the one-step system dynamics matrix D,, whose rows are indexed by tests and columns indexed by histories, and the entry corresponding to the test-history pair (1++1. TA) is equal to P(14+1/TA)) (see Fig 1 for an illustration). Denote drsn, = rank(Dn), Then Linear PSRs are defined to be systems with low-rank one-step system dynamic matrices:
Definition 1. A partially observable system is called Linear PSR with rank desR if max; rank Da) = drsR-
Core tests. For time step h, consider a set of tests Uh+1 C UCEN+ Oc x AA-1. If the submatrix Dr (see the matrix inside the green box in Fig. 1) of D₁ whose rows are indexed by the tests in Uh+1 and columns are indexed by all histories, has rank equal drsR,h. then we call such set U as core test set. The key property of such core test set is that from linear algebra, for any row in DR. we can express as linear combination of the rows of Dn. This formalized as follows.
Lemma (Core test sets in linear PSRs). For any h E [ set Uh+1 UCEN+ OC AAC-1 is core test set at (h + 1)-th step if and only if we have for any W E N+,, any possible future (i.e., test) th+11 (0h+1:h+4. ah41-++-11)
OW x AW and any history The there exists
M4411h+1 E R 1il such that
P((n+117))) = (m,, 11. (P(l
The vector [uuuuu is referred as the predictive state (h + 1)-th step.
Throughout this work, use (r,, to denote [PP(((T))] Juuuu.. and qu represent the initial predictive states [P(w)]ueu, In particular, we are interested in the set of all action sequences in Ud, and denote it by 2A,.- A core test set with the smallest number of tests is called a minimum core test set, which we denote by Qn. Note that by the definition of the rank, we know that 1Qu+a| dPsR, To simplify writing, we further define [2[] == [H [4 [4 == [ax [M In this paper we assume a core test U4, (we will see that this is a natural assumption for models such as POMDPs) given while 2n unknown. This setting standard in literature on PSRs [6].
Minimum core histories. Similar to the minimum core test set, we can define the minimum core history set as well. Consider the matrix D, in Figure I. Recall that the columns of Dr, are indexed by all possible h-length histories and each column is 9T,,- Since D, has rank drsR,h, there must exist dysn, histories Th- ... ,Th dpsR.", such that any column in D₁, is linear combination of the columns in Dr, that correspond to histories ........ TTh
dpsR.A In other words, for any h-length history
The there exists a vector Un, E Rddess,. which satisfies
4T. KRUTA.
where K2 E 1 is full-rank matrix whose i-th column is Org. We call
(Th..... Th desR.A) as the minimum core histories step h and K2, the core matrix see Fig- ure for an illustration of K₁, Particularly, when h = O, we have Kg = go. Note (2) shows that all h-length histories
be captured by the core histories in the sense that the predictive states given any history can be expressed as a linear combination of the predictive states corresponding to the minimum core histories. The minimum core histories and the core matrix may not be unique given the core test set. Here we particularly define K₁, to be the core matrix with the smallest || 1|--1 to facilitate our subsequent analysis.
PSRs vs POMDPs. PSRs have much stronger expressivity than POMDPs. All POMDPs can be expressed as PSRs with the minimum core test set size as most [S] while PSRs are not necessarily compact POMDPs [36]. In Appendix D we construct a sequential decision making process where we want to formulate into a POMDP, the number of states we need will be exponentially larger than the core test set size in the PSR formulation. The key intuition behind the construction is simple: the non-negative rank of a matrix could be exponentially larger than its rank. In the literature [41], there are also some other concrete instances like probability clock which POMDPs cannot model with finite latent states while PSRs can model with finite rank.
In the following, we explain that POMDPs are PSRs. Consider an episodic POMDP OS, (T, M. (O, // (rx)[ H, n1) where S is the state space, O is the observation space, AA is h=
the action space, O, is the emission matrix h-th step, T' is the reward function at h-th step and μn
4

---

Under review as a conference paper at ICLR 2023
is the initial state distribution, Ta is the transition matrix at step where (Tn,a)a', Ps a). Then the following lemma shows that any POMDP is a PSR and its minimum core test set size is no larger than [S,, whose proof is deferred to Appendix E: Lemma 2. All POMDPs satisfy the definition of PSRs (Definition 1) such that desk S |S]
After showing any POMDP a linear PSR with rank at most [S], now we demonstrate that under what conditions we could find a core test set. We focus on 1-step weakly-revealing POMDPs [29, 37] here, i.c., the rank of O is [S] for all h, then we can show that O a core test set.
Lemma 3. When rank (Ox) |S] for all h E [H], the POMDP PSR with the core set U4 = O for all h [
We defer the proof and other examples including m-step weakly-revealing POMDPs [37], latent MDPs [34], m-step decodable POMDPs [13] and low-rank POMDPs to Appendix E and Section 5.
2.1.2 SYSTEM DYNAMICS OF PSRs
Predictive states can evolve just like the beliefs in POMDPs, which indicates that acterize the system dynamics of the PSRs via predictive states efficiently. In particular, for any E O, E A, h E [H], let Mo,a, E 11 denote the matrix whose rows are m (o.,,)), (defined in Lemma 1) for u E Uh+1 (note that o, a, u can be understood as test that starts with o, a, followed by u). Then the probability of an arbitrary trajectory can be expressed the product of Ma Mox H. as shown in the following lemma:
char-
Lemma 4, For any trajectory TH and policy n, we have
H-1 II
FaT (TH) mmn
Mon.an.h qu (TH).
where x(TH) == H aaan/Th- on) is the probability of the actions chosen in the trajectory. More generally, for any [H] and trajectory The letting Dr, = ([T Morayd 3 Jo, we have [P(ulT)))PT(TA (Th)luEtt.n = =b,, x ((T)),
(4)
The proof is deferred to Appendix Lemma 4 shows that the parameters
(Mo,a,h, Mo, H A.E
are sufficient to characterize a PSR. Here we call Mo,e, the predictive operator matrix. Recall that in POMDPs, the same decomposition holds since we can represent (Mo Mo.H, 9u using (TT: 3 as we see in the proof of Lemma However, as emphasized in Singh al. [41], the main reason PSRs are more expressive is that {Maa., Mo, 90 are not constrained to be non- negativve...
2.3.3 LEARNING OBJECTIVE
In this paper, we study online learning in PSRs and want to find the optimal policy. Suppose the output policy म. then our goal is to find an c-optimal policy with polynomial number of samples such that: V' - v < c, where V = V= = sup, V" and n7" is the optimal policy.
2.2 FUNCTION APPROXIMATION
To deal with the potentially large observation and action space, we consider learning with function approximation in this paper. We assume a function class F to approximate the true model and let (T())) denote the probability of any trajectory ти under any policy ा and model f. Here we assume that the models F are all valid PSRs with core test set {14x )e((F)) which implies that for each f E F, we can calculate its corresponding predictive operator matrices, initial predictive states and core matrices, denoted by Ma fo KEz respectively. We define V7 to be the value of policy π under model f. We also use f* to represent the true model for consistency.
Generally, put models (Mo.a,huf 90:f) since this is the most natural parametrization in PSRs. When we have more prior knowledge about models like models are POMDPs, we can also put models on (TA, Og, #1
To measure the size of F, we use |F to denote its cardinality when F is finite. For infinite function classes, we introduce the e-bracket number to measure its size, which is defined as follows:
5

---

Under review as a conference paper at ICLR 2023
Definition 2 (e-bracket and e-bracket number). A size-N c-bracket is bracket {gi 92]==1 where (96) is a function mapping any policy x and trajectory T to R such that for all i E [N] llgi (). (T, (m, S E for any policy n, and for any E F, there must exist an E [M] such that g (T, S (T((T)) I 92( TH) for all TH, n. The e-bracket number of F, denoted by (e) is the minimum size of such an e-bracket.
Although PT is an (|OI]A))" -dimensiionll vector, its log e-bracket number will not scale exponen- tially with H because PT is Lipschitz continuous with respect to (Ma,,,s.f (oo..k:ffoo..) whose dimension only scales polynomially with H. In Appendix G we show that the bracket number of can be upper bounded by the covering number of {Mo qo:f } in linear PSRs, and we provide exact upper bounds for tabular PSRs and various POMDPs.
ALGORITHM: CRANE
The statistical hardness of learning POMDPs due to the partial observability well-known in the literature [32], which also exists in PSR learning since PSRs are more general model. In addition, existing algorithms [29, 13, 37] for learning sub-classes of POMDPs require the existence of latent states since they directly put models T and O. Thus, their methods are not applicable
PSRs. That said, the existence of predictive states indeed implies the low-rank linear structure of PSRs. The trajectory probability decomposition (3) further suggests that we are able to capture a PSR completely as long as we can learn the predictive operator matrices the initial predictive state qu efficiently. Therefore, inspired from the success of maximum log- likelihood estimation (MLE) in learning weakly-revealin POMDPs [37], we propose a new MLE- based PSR learning algorithm to learn these parameters as follows.
JoED,, -1] and
CRANE. Intuitively, our algorithm an iterative MLE algorithm with optimism, where in each iteration MLE to estimate the model parameters based on the previously collected trajec- tories and choose an optimistic policy to execute. We call it OptimistiC PSR leArnigg with MLE (CRANE). CRANE mainly consists of three steps, whose details are shown in Algorithm 1:
Optimism: Since we consider the online learning problem, the unknown model dynamics force us to deal with the exploration-explotttiio tradeoff. Here we utilize the Optimism in the Face of Uncertainty principle and choose optimistic estimation f of the model parameters from the constructed confidence set 1² Our policy x² is the optimal policy under f*, ensuring that V 2 V* with high probability.
For each step h E [H - 1] and each action sequence ua in MA we collect trajectory TH A.,., by executing the policy 7 Th - ( Au (and uniform policy afterwards if the episode has not ended). This helps us obtain the required information for estimating each predictive operator matrix Mo.a, and initial predictive state go-
Trajectory collection:
Parameter estimation with MLE: Finally we need to update the confidence set with newly col- lected trajectories. We achieve this by implementing MLE on all the collected trajectories with slackness 8, as shown below:
Bb+1 {IEF: Σ (T.TH)ED
log (TH) 2 max
Σ (π,TH)ED
log PPT (TH)
3
(5)
f'EF
For example, the likelihood (TH) is specified by (3) if we model (Mo,n,h, 90} as f. In POMDPs, if we model (TT, 01. as f. the likelihood is specified by marginalizing over la- tent states. The slackness chosen appropriately such that the true parameters f E Bk++1 with high probability, which in turn guarantees optimism in the first step.
Comparison with Liu et al. [37]. The main difference is that our algorithm can allow more gen- eral models. For example, in PSRs, we can generally take (M, Yo } that depends on only observ- able quantities as a model f. On the other hand, Liu et al. [37] attempts to put models on (T,, On. that involve latent states. The practical benefit of modeling (Mo...h, }u is we don't 'on't need to specify the latent space while Liu et al. [37] needs to do. Since we often do not have good prior knowledge about latent states, our algorithm would be more practical in this scenario. Due to the generality of our algorithm, we can capture more models such as m-step decodable POMDPs and low-rank POMDPs as we will see in the following sections.

---

Under review as a conference paper at ICLR 2023
Algorithm CRANE
Input:
confidence parameter B. Initialize B +- F.D 0.
for k = 1,...................... do
Optimistic Planning: (f*, -h) + arg max Vf.
Collect samples:
for h E [H - 11 Ma,h+1 E UA do
Execute Ahi = k 1:hh1 Unif(AA o ua and collect a trajectory TH
h4t.h
Update the dataset D < D U (T (7th :T (. end for
Update confidence set: Compute Bh++ via (5). end for
MAIN RESULT
Next, we present the regret analysis for CRANE. We will utilize the fact that the core matrix K₁, is full-rank. However, matrix rank is vulnerable to estimation errors since small perturbations might change the rank drastically. Here we assume the & norm of K is upper bounded, which is more robust assumption than K2, being full rank. Note a similar assumption is often imposed in the PSR literature [27, Appendix B.4).
Assumption 1 (a-regularity of PSRs.). Assume that there exists a > such that for any h E [H - 1]+, we have || < 1/a.
Remark 1. | 111-1 can upper bounded by / / min (.)). the literature of POMDPs, many works [29, 13, 37] assume similar condition called a-weakly revealing condition. That is, the minimal singular value of the observation matrix or the multi-step observation matrix is lower bounded by Assumption can be regarded generalization of such weakly revealing condition in PSRs by viewing core histories as the "states" " and tests u E Un, as the "observations" in PSRs.
In addition, to simplify analysis, we assume all one-step observations does not harm the generality of our model since augmenting the core test set is always feasible and adding all one-step observations will most increase [Mx] by one.
O belong Un. This
Assumption 2. For all o E O, assume that E UH.
This assumption immediately implies that mo,H = Eo i.c., it a one-hot vector which indexes the observation in Un. To see that, note that o UH implies that the predictive state 9-H-1 contains the probability P(o|TT-1). Thus, when mo,11 = ea we have m. "0H4- PP(oTTn-1)- Therefore when Assumption 2 holds, we can assume that for all models induced by F, we have M. = H. for all without loss of generality.
Furthermore, we impose constraints on the function class F as follows:
Assumption 3. Assume the function class satisfies the following conditions: (I) Realizability: We have f E F, (2) Regularity: For all J E and [H - -]+ we have | S 1/a, (3) Validity: For all f E F, the model dynamics induced by f is a valid PSR with core test set (Lhn he( i.e., the trajectory probability 1777 should be valid distribution for any policy and satisfies the definition of PSRs.
The last two constraints (2), (3) in Assumption 3 can be easily satisfied by eliminating those func- tions which do not satisfy the regularity or validity.
Notice that the system dynamics in (3) only utilizes the inner product of m(o.a,.). and 4r, Lif- and fT, 1:f lives in the column space of Kn-1; (i.e., (2)), which implies there is redundancy in the choice of (o.,..))) given the model 17.. Next we show that among these possible M(). can always find one that lies in the column space of Kn-1;f- More specifically, if we replace any mio.o, w). Auf with its projection on the space spanned by {9T-1:f h (which is exactly the column space of kf-l:f), the resulting model dynamics will remain the same. Formally, we can show given such that (o..a.)))k: belongs to the column space of Kn-1;; 1:f (the proof is deferred to Appendix H). Therefore, in the following, without loss of generality.
any IP5, there exists a set of {M{o,,,a)), Jo ooEo. vEth.
let Mf Ma consist of such a))

---

Under review as a conference paper at ICLR 2023
Model
Core test set 2h,
dpsR
log. NF
tabular POMDPs
S <|8
poly (
[S], H. (og(1/<))
b Refer to Appendix A.2
low-rank POMDPs
(0 x A)
x XO
I duaan
linear POMDPs
djin
poly H, [og((0)[A[))))
Table 2: Core test sets, minimum core test size and bracket number for POMDP models. Here all the POMDPs we consider are m-step weakly-revealing or m-step decodable. The exact function classes F we use are elaborated in the following discussion.
With the above assumptions, plexity CRANE to learn a ncar-optimal policy, whose proof is deferred to Appendix
have the following theorem, which characterizes the sample com-
Theorem (Sample complexity). Under Assumption 1,2,3, for any ō E (0, 1], >> 0, if we choose
T 1/² poly(drsR, [ //, log,Nr(es); H, |A|, log (o,,1og(1/)) then with probability at least 1 8 we have
and set 3 = =looo(NN((e))HHMAA
V
V -E
where से is the uniform mixture of the output policies, i..,, == U==nni((++)))))
Theorem I indicates that the complexity of CRANE only depends polynomially on the PSR rank dPSR, the size of UA... the & fn-norm of the pscudoinverse of the core matrix 1, the log bracket number of function classes log (cb)) H and |A). CRANE avoids direct dependency and our sample complexity remains the same even if the observation parts in core test set Uh, is large. Via the relationship between POMDPs and PSRs, Theorem can be applied to m-step weakly- revealing tabular POMDPs (including undercomplete POMDPs [29] and overcomplete POMDPs [37]), m-step weakly-revealing low-rank POMDPs [47], m-step weakly-revealing linear POMDPs and m-step decodable POMDPs [13], which we will elaborate on in Section 5 and Appendix A. Our sample complexity in Theorem depends on the upper bound of 111-111111 i.e., 1/a, which is not avoidable in worst-case. We state the lower bound formally in Appendix K.
poly(|O))
Proof techniques of Theorem 1. The existing analysis for POMDPs does not apply to PSRs since we do not assume latent states in PSRs, let alone the emission matrix and transition matrix. In our proof, we utilize the linear nature of PSRs and leverage the core matrix K₁. to bound the error propagation induced by the product of predictive operator matrices, i.e., I Mo in (3). This key step enables us to bound the difference of model dynamics IP= and 1px (i.e., p.., by the estimation error of Mo.. and qo. and thus obtain a polynomial bound on the total suboptimality.
Comparison with existing works on PSRs. As far as we know, there are only two works that tackle provably efficient RL for PSRs. Jiang al. [26] shows a polynomial sample complexity result in reactive POMDPs where optimal value functions only depend on current observations. Later, Uehara et al. [45] shows a favorable sample complexity result without this assumption. However, their result is an agnostic-type result that depends on ( ((O1--)) when competing with M-memory policies. Thus, compete with the globally optimal policy, their results do not imply a polynomial sample complexity bound.
5 EXAMPLES
In this section, we illustrate the sample complexity of CRANE to learn m-step weakly- revealing/decodable tabular POMDPs and low-rank POMDPs. We defer more details (including the concrete function classes we utilize to satisfy Assumption 3 and comparison with existing works) and other examples including tabular PSRs and m-step weakky-rovealing/dccodaa to Appendix A. Note that we can identify the minimum related models, which is summarized in Table 2 and the proof is deferred to Appendix E and G.
linear POMDPs test size and the bracketing number of
5.1 M-STEP WEAKLY-REVE REVEALING TABULAR POMDPS
We first focus on m-step weakly-revealing tabular POMDPs [37] defined as follows.
Definition 3 (m-step weakly-r Tabular POMDPs). Define the m-step emission matrix Oh.m ||AA" 110 " x|5] for any H m + 1] as follows:
(Oh.m) = P(oushtmm111111 = 0)5 = s, a1:hmm22 = V(, E mm1 x O" s E S.
When rank (Dp,.. = |S) POMDPs are referred as m-step weakly-revealing POMDPs.
This assumption implies that the observations leak at least some information about the states that we can learn the POMDPs efficiently. Substituting the results in Table 2 into Theorem 1, we can obtain the sample complexity for learning m-step weakll-n tabular POMDPs as follows.
8

---

Under review as a conference paper at ICLR 2023
Corollary 1 (Sample complexity for m-step weakly-t tabular POMDPs), Suppose the POMDP is m m-step weakly-revealing and we execute CRANE with 8 = ( up the step H any 8 E (0, 1), > 0, if we choose
where Un, and ((t) specified in Table 2. Then under Assumption for
T 1/e² x poly(drsn, |A|T, 1/a, [0), [S), H, log(1/6));
then with probability at least 1 - ô we have V
2 V -6
5.2 m-STEP WEAKLY- MAAKLYREVEALING LOW-RANK POMDPS
Next, we consider m-step -reeeaire low-rank POMDPs. We first define low-rank POMDPs be special subclass of POMDPs.
Definition 4 (Low-rank POMDPs), Suppose the transition kernel Tr has the following low-rank form for all h [H]: (d (x)) T (n(8,, a), where the, - i Rederane and oN S S Rduam are unknown feature vectors. Then, we call these POMDPs as low-rank POMDPs.
The low-rank structure leads to smaller minimum we can show dpsR I derans as in Appendix E. Weakly-revealing low-rank POMDPs are defined weakly-revealing POMDPs that have this low-rank structure. For the function class F, we let it model the feature vectors, emission matrix and initial state distribution, i.e., f V supposing JF finite (the infinite case deferred Appendix A). Then substitute the results in Table 2 into Theorem I and the sample complexity for learning low-rank POMDPs is as follows: low-rank POMDPs). Suppose low-
test set size than general POMDPs since
Dy, her
Corollary 2 (Sample complexity for m-step weakly-revealle rank POMDPs are m-step weakly-revealing, and we execute CRANE with 3 = c (og( (AAl)))
up to the step H m where Un is specified in Table 2. Then under Assumption 1 and for any ò E [0,1], > 0, if we choose
T 1/e² x poly |A 1/a, log [F1, log [O), log(L/0),,
then with probability least 1 8 we have v 2 -
Notice that the sample complexity only depends on dirans rather than |S| for low-rank POMDPs.
5.3 M-STEP DECODABLE TABULAR/LOW LON-RRAKK Next, we instantiate our result on m-step decodable POMDPs [13] defined follows.
RANK POMDPS
Definition 5 (m-step decodable POMDPs). There exist unknown decoders Imshh such that for every reachable trajctory TH, we have 5h = @dee, (x) for all h S H1 where 2h. ((,.a)-m+11. 0.).
This definition says that can decode the current state with m-step history. Surprisingly, Ta- ble 2 shows that m-step decodable POMDPs can be formulated as PSRs just like weakly-revealing POMDPs, which leads to the following corollary:
Corollary (Sample complexity for m-step decodable POMDPs).
In m-step decodable tabular POMDPs, the same statement in Corollary I holds.
In m-step decodable low-rank POMDPs, the same statement in Corollary 4 holds.
Remark 2 (Tabular PSRs and linear POMDPs). We can instantiate our result on tabular PSRs. The sample complexity is polynomial in all parameters: desR. O), |AI, [24] H, 1/e, 1/a, 1))) Here, we leverage the observation of covering numbers after Definition 2. We also consider linear POMDPs where latent transitions and emissions follow linear structures. While similar models are considered [7, 47], our result is still new in that our model is more general. The details are deferred to Section A.
6 CONCLUSION
We consider PAC learning in PSRs that represent states vector of prediction about future events conditioned on histories. We propose CRANE and show polynomial sample complexities when we compete with the globally optimal policy. Our work is the first work attaining this goal. Since PSRs are more general than POMDPs, we instantiate our result to several concrete POMDPs such m-step weakly-revealing POMDPs, m-step decodable POMDPs, POMDPs with latent low-lank transition. Notably, our work the first work that simultancously achieves polynomial sample complexities in m-step weakly-revealing POMDPs and m-step decodable POMDPs.

---

Under review as a conference paper at ICLR 2023
REFERENCES
[]] Agarwal, A., Kakade. S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complex- ity and representation learning of low rank mdps. arXiv preprint arXiv:2006. 108/4.
[2] Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 263-272. JMLR. org.
[3] Avizzadenesheli, K., Lazaric, A., and Anandkumar, A. (2016). Reinforcement learning of pomdps using spectral methods. In Conference on Learning Theory, pages 193-256. PMLR.
[4] Boots, B., Gordon, G., and Gretton, A. (2013). Hilbert space embeddings of predictive state representations. arXiv preprint 1rXiv:100.68199
[5] Boots, B., Siddiqi, S. M., Gordon, G., and Smola, A. (2010). Hilbert Space Embeddings Hid- den Markov Models. In Proceedings the 27th International Conference Machine Learning.
[6] Boots, B., Siddiqi, M., and Gordon, G. (2011). Closing the leariing-paaning loop with predictive state representations. The International Journal of Robotics Research, 30(7):954-900 966.
[7] Cai, Q., Yang, Z., and Wang, Z. (2022). Sample-efficient reinforcement learning for pomdps with linear function approximations. arXiv preprint arXiv:2204.09787.
[8] Cohen, J. E. and Rothblum, U. G. (1993). Nonnegative ranks, decompositions, and factoriza- tions of nonnegative matrices. Linear Algebra and its Applications, 190:149-168.
[9] Downey, C., Hefnn,, A., Boots, B., Gordon, G. J., and Li, B. (2017). Predictive state recurrent neural networks. Advances in Neural Information Processing Systems, 30.
[10] Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: A structural framework for provable generalization in rl.
[11] Du, S. S., Luo, Y., Wang. R., and Zhang, H. (2019). Provably efficient Q-learnng with function approximation via distribution shift error checking oracle. In Advances in Neural Information Processing Systems, pages 1058-8068. PMI.R
[12] Edmonds, J. (1965). Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, (9(125-130):55-5
[13] Efroni, Y., Jin, C., Krishnamurthy, A., and Miryoosefi, (2022). Provable reinforcement learning with short-term memory. arXiv preprint arXhv:2202.03983.
[14] Even-Dar, E., Kakade, S. M., and Mansour, Y. (2005). Reinforcement learning in pomdps without resets.
[15] Fiorini, S., Kaibel, V., Pashkovich, K., and Theis, D. O. (2013). Combinatorial bounds nonnegative rank and extended formulations. Discrete mathematics, 313(1):67-83.
[16] Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. (2021). The statistical complexity of interactive decision making. arXiv preprint 2r.iv:21
[17] Golowich, N., Moitra, A., and Rohatgi, D. (2022a). Learning in observable pomdps, without computationally intractable oracles. arXiv preprint arXiv:2206.0344 03446.
(18) Golowich, N., Moitra, A., and Rohatgi, D. (2022b). Planning in observable pomdps in quasipolynomial time. arXiv preprint arXiv:2201.04735.
[19] Grinberg. Y.. Aboutalebi. H., Lyman-Abramovitch. M.. Balle, B., and Precup, D. (2018). Learning predictive state representations from non-uniform sampling. In Proceedings of the AAAI Conference on Artificial Intelligenee, volume 32.
[20] Guo, Z. D., Doroudi, S., and Brunskill, E. (2016). A pac rl algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pages 510-518. PMLR.
10

---

Under review as a conference paper at ICLR 2023
[21] Hamilton, W., Fard, M. M., and Pineau, J. (2014). Efficient learning and planning with com- pressed predictive states. The Journal of Machine Learning Research, 15(1):3395-344
[22] Hefny, A., Downey, C., and Gordon, G. J. (2015). Supervised learning for dynamical system learning, Advances in neural information processing systems, 28.
[23] Hsu, D., Kakade, S. M., and Zhang, (2012). A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 160--4446)
[24] Jaeger, H. (1998). Discrete-time, discrete-valued observable operator models: a tutorial. GMD-Forschungszentuu Informationstechnik Darmstadt, Germany.
[25] Jaksch, T., Ortner, R., and Auer, P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research.
[26] Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2016). Contextual decision processes with low bellman rank pac-learnable. arXiv preprini arXiv:1610.09512.
[27] Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017). Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, volume 70, pages 1704-1713. PMLR.
[28] Jiang, N., Kulesza, A., and Singh, S. (2018). Completing state representations using spectral learning, Advances in Neural Information Processing Systems, 31.
[29] Jin, C., Kakade, S., Krishnamurthy, A., and Liu, Q. (2020). Sample-efficient reinforce- ment learning undercomplete pomdps. Advances in Neural Information Processing Systems, 33:18530-1883
[30] Jin, C., Liu, Q.. and Miryoosefi, S. (2021). Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34.
[31] Kearns, M., Mansour, Y., and Ng. A. (1999). Approximate planning in large pomdps via reusable trajectories. Advances in Neural Information Processing Systems, 12.
[32] Krishnamurthy, A., Agarwal, A., and Langford, J. (2016). PAC reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1840-1848.
[33] Kulesza, A., Rao, N. R., and Singh, S. (2014). Low-rank spectral learning. In Artificial Intelligence and Statistics, pages 522-530.
[34] Kwon, J., Efroni, Y., Caramanis, C., and Mannor, S. (2021). RI for latent mdps: Regret guarantees and a lower bound. Advances in Neural Information Processing Systems, 34.
[35] Lale, S., Azizzadenesheli, K., Hassibi, B., and Anandkumar, A. (2020). Regret minimization in partially observable linear quadratic control. arXiv preprint arXiv:2002.0008:
[36] Littman, M. and Sutton, R. S. (2001). Predictive representations of state. Advances in neural information processing systems, 14.
[37] Liu, Q., Chung, A., Szepesvári, C., and Jin, C. (2022). When is partially observable reinforce- ment learning not scary? arXiv preprint arXiv:2204.0 009667.
[38] Rosencrantz, M., Gordon, G., and Thrun, S. (2004). Learning low dimensional predictive representations. In Proceedings the twenty-first international conference Machine learning, page 88. ACM.
[39] Rothvoß, T. (2017). The matching polytope has exponential extension complexity. Journal of the ACM (JACM), 64(6):1-19.
[40] Simchowitz, M., Singh, K., and Hazan, E. (2020). Improper learning for non-stochastic con- trol. In Conference Learning Theory, pages 3320-3436. PMLR.

---

Under review as a conference paper at ICLR 2023
[41] Singh, S., James, M. R., and Rudary, M. R. (2004). Predictive state representations: A new theory for modeling dynamical systems. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pages 512-519. AUAI Press.
[42] Sun, W., Jiang, N., Krishnamurthy, A., Agarwal, A., and Langford, J. (2019). Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933. PMLR.
[43] Sun, W., Venkatraman, A., Boots, B., and Bagnell, J. (2016). Learning to filter with pre- dictive state inference machines. In International conference machine learning, pages 1197- 1205. PMLR.
[44] Thon, M. R. and Jaeger, H. (2015). Links between multiplicity automata, observable operator models and predictive state representations: unified learning framework. J. Mach. Learn. Res., 16:103-147.
[45] Uchara, M., Sekhari, A., Lee, J. D., Kallus, N., and Sun, W. (2022). Provably efficient rein- forcement learning partially observable dynamical systems. arXiv preprint arXiv:2206. /2020.
[46] Venkatraman, A., Rhinehart, N., Sun, W., Pinto, I.., Hebert, M., Boots, B., Kitani, K., and Bag- nell, J. (2017). Predictive-state decoders: Encoding the future into recurrent networks. Advances Neural Information Processing Systems, 30.
[47] Wang, L.,, Cai, Q., Yang. 7., and Wang, Z.. (2022). Embed to control partially observed systems: Representation learning with provable sample efficiency. arXiv preprint D.Xiv:2205.134777
[48] Yang, L. and Wang, M. (2020). Reinforcement learning feature space: Matrix bandit, ker- nels, and regret bound. In International Conference on Machine Learning, pages 10756-10756. PMLR.
[49] Zhang, Z., Yang, Z., Liu, H., Tokekar, P., and Huang, F. (2021). Reinforcement learning under multi-agent predictive state representation model: Method and theory. In International Conference on Learning Representations.
12

---

Under review as a conference paper at ICLR 2023
A EXAMPLES: MORE DETAILS AND MODELS
In this section, supplement the details in Section 5 and illustrate the sample complexity of CRANE to learn tabular PSRs and several other POMDPs in comparison with existing algorithms. We con- sider two types of POMDPs: m-step reakly-revealing POMDPs and m-step decodable POMDPs. Assumptions like weakly-revealing property and decodability allow us to identify core test sets.
A.1 m-STEP WEAKLY-REVEAIE TABULAR POMDPS
We first give more details about the discussions of m-step weakly-revealing tabular POMDPs.
Core test sets and function classes. In this case can choose Un to be the set of all m-step futures (O x A)m-1 x O. For the function class F, we first let it model the pa- directly, lift weakly-revealing POMDPs and then pre-process it to satisfy Assumption 3. The corresponding e-bracket number (c) shown in Table
rameters (Thef, Of:f-/M:fhhet
PSR formulation,
Besides, since now the core test set (O x A)m 1 x O, we let Mios m 118,888 8,88 mi11 -). E(og milHa in 11:8 H)+ i.e., it is a one-hot tor which indexes the future (OH (0H-m+1:H aH (H in Ug-m+1- Then from Lemma 4 know for any trajecotry TH.
(TH)
II Mo ((TH)-
Note that here UH does not contain the observation space. Nevertheless, we can replace (17) with
H
V
H
II
M M ag.h
%
II
Mo 20 (TH--))
h=1
and follow the same proof to show that Theorem 1 still holds even though Assumption 2 is not satisfied.
Remarks about Corollary 1. By executing CRANE to the step - m we mean that when col-
lecting trajectories, we only execute k.i.h and collect Tи k. for h E [H -H]++ Wa,f+1 MA,4+1 Since we have üpsR I [S], we can obtain that the sample compleixty will not larger than poly([S), H, [A|" 1/a, 1/e, JO log(1/8)) from Corollary 1. This indicates that CRANE is able to achieve polynomial sample complexity for m-step weakly-revealing tabular POMDPs.
Comparison with [37]. In m-step weakly revealing tabular POMDPs, CRANE similar to the algorithm OMLE proposed in [37] and their analysis leads sample complexity similar to Corol- lary 1. However, their algorithm has a pre-processing step on the emission matrix O while we have a step formulate POMDPs into PSRs for pre-processing. thus the algorithm is still different. Further, they assume an upper bound on ||0,,, ll h- while we assume | S 1/a in Assump- tion 1. For tabular POMDPs, our assumption slightly stronger since we have K₁-1 = Oh.m where (S)
P(()))_-) and thus miin (Kn-1) S dpsnomin (0m,m.) That said, the analysis and algorithm in [37] is specially tailored to m-step weakly reavling POMDPs and relies on the existence of latent states. In contrast, our algorithm and analysis can be applied to any PSR models including m-step decodable POMDPs.
Comparison with [34]. [34] deals with latent MDPs but they require either proper initialization or other assumptions including Sufficient Tests, Sufficient Histories, strong separation of the MDPs and reachability of the states. In contrast, we show in Appendix E that LMDP with Sufficient Tests can be formulated into (I + step weakly-revealing POMDP, therefore CRANE is capable of tackling LMDP with sample complexity 1/e² x poly SS), |Al' 1/a, H. log (16)) under only Sufficient addition, the sample complexity in [34, Theorem 3.5] will scale with the initialization error while CRANE eircumvents such dependence completely.
Tests and Assumption
13

---

Under review as a conference paper at ICLR 2023
A.2 m-STEP REVEAL-E LOW-RANK POMDPS
Next, we supplement the details about m-step weakly-revealing low-rank POMDPs.
Core test sets and function classes. For weakly-reveallngg low-rank POMDPs, we can still choose U4, to be the set of all m-step futures (O x (=)AA""mi x O due to the weakly-revealing property. For the function class F. we let model the feature vectors, emission matrix and initial state distribution,
i.., 1 f, L f. f. f hre where f S x A [H] + Rduaw v S x
[ + Rd 0g :
O x M] + [0, 15
[0, such that
(n. a) ( a, (hns V h). Onas(ols) Oy(s, M), (i)(()) 1s((s)-
Here F can be infinite. Denote the -nom covering number of y v 0 ps by (c))
Then we have
log s log 3' (GLR/derans) + log Y' (ELR/ + log (OLE)) + log y (CLR),
where En. := O 0(</110(++1))))) The proof is deferred Appendix G. To make Assumption hold, we only need to assume the feature vector classes satisfies realizablity;
Assumption 4. Suppose that there exsits f E F such that for all s E S,a E A,h [H] we have 6 (s (5, a, h), (s) V f- h).
Then we can lift low-rank POMDPs to PSR formulation, and then pre- pre-process it to satisfy Assump- tion 3.
Remarks about Corollary 2. Corollary only considers finite function class F. With the above discussion, we can extend to infinite function classes as follows:
Corollary 4 (Sample complexity for m-step weakly-revealing low-rank POMDPs). Sup- pose low-rank POMDPs are m-step weakly-revealing. and we execute CRANE with 3 (log(Ns(e,)THHuu)) up to the step Then under Assumption I and 4, for any 8 E 10, 0, if we choose
m where Un, and Ny((() are specified Table 2.
T 1/2²
|A|m 1/a, log Y' (ELR/// (drans)) log VVLER///uaan log Vo(ERR) log 1 (<LR), H, log O0, log(1 (1)))
then with probability at least 1 - 8 we have V 2 V
Comparison with [47]. In Corollary 4, we do not specify the function class and keep the bracket number to facilitate the comparison with [47]. [47] also tackles the online learning problem of m- step weakly-revealing low-rank POMDPs and our sample complexity only has an additional log |O] factor compared to theirs. However, the model they have considered is less general than ours in the sense that they require the feature vectors 6% (s, a) to be a diraus dimensioonl probability distri- bution to guarantee the existence of some bottleneck variables. Besides, their analysis depends on some possibly complicated assumptions to recover the bottleneck variable like "past sufficiency". In contrast, CRANE only requires | X I1a-1 to be upper bounded and does not assume the existence of bottleneck variables.
Comparsion with [45]. They show favorable sample complexity results in weakly-revealing low- rank POMDPs. However, their sample complexity results are guasi-polynomial. On the other hand, our results are polynomial while we have an additional log [O] factor.
A.3 TABULAR PSRS
Notice that in Theorem the log bracket number log (Eb)) is abstract. Here we consider tabular PSRs a speical case to provide an intuition how large the bracket number will be in general. In tabular PSRs we directly use {Mo,a,h, MaMaaaa.goheo..ee.ee... a.eEO,,EA.. as the parameters of F and assume for all we have
Ils S 11 S
,EO, al
14

---

Under review as a conference paper at ICLR 2023
Then following the arguments in Appendix G, we have
logWN((c) O(14 (og/]/))AA ((ce))))
By substituting the above results into Theorem I, we have the following corollary which character- izes the sample complexity to learn tabular PSRs:
Corollary 5 (Sample complexity for tabular PSRs). Execute CRANE with 3 clog(Nr((G)) MAl/6) where (G(()) are specified in (6). Then under Assumption 1,2 and 3, for any å E (0, 11, 0, if we choose
T 1/e² x poly(dpSR, [al 1/a, [u, OO) IAI, H, (og()
then with probability at least 1 - we have
v 2 V
From Corollary 5 can see that CRANE is capable of learning tabular PSRs efficiently, with sample complexity polynomial in all relevant parameters. Here, though we have poly([ dependency in learning PSRs (since our model parameters Ma. have degree of freedom scaling in poly( we will show that we would not incur (oly(14() in the log e-bracket number when PSRs are POMDPs. This is because we can directly model the latent transition and omission distribution when we know it is POMDP.
A.4 m-STEP
LINEAR POMDPS
In low-rank POMDPs the bracket number is still somehow abstract because we do not specify the function class { y O j. Next we consider linear POMDPs and illustrate a more concrete result. Here we assume that linear POMDPs possess linear structure in both the transition kernel and emission matrix. More formally, we can generalize the linear MDPs in [48] and define linear POMDPs as follows:
Definition (Linear POMDPs). POMDP linear with respect to the given feature vectors (on a) E Rd, (s) E IRd2 o E IRds Re vn(o) E ((s) E Rdb )eES,
where (s, llo I 1, 11,11)((8))ll S 1, (s, a) S 1, (o) 1, 11)(((s) I 1or all S. E A, o E O E [4] if there exists a set of matrices {Bi,1 E Rddaxd, BTr E Rdixds besxdsJeed ]Ne[H] where l 1, 22 $1 for all h E [H] and 6* Rdds where 110"11>0 such that
for any 8, s' E8 A, o A, [H]] we have
Tn(5'(s,a) = (s)(('')) BB, 1n a), a), = ( 2
TT(s).
Denote diin max(di d2, d3 da, ds.. Notice that since Ta (s(''|s, a) = (Na(s')) (BB()) BE, POMDPs are also low-rank POMDPs with dimension min d2} and thus for linear POMDPs we have
Bn (n a). lin-
dpsR S dun-
We further define the function class be { (Br,1 E Rddaxd, BA,2 E Rdixds xxs, E R&)) 1l,,0000.00 I 1, B I 1, 110loo I 1, [H] such that for any o E O, A,
[ m]
Thss(''(s,a)) = (snn('')) 1n Oh.r(ols) = (o)( (s) = T(s).
This enables us to bound (F(()) as in Table 2. Note that this function class satisfies realizability and can pre-process it to make Assumption 3 hold.
Finally, we assume m-step weakly-r property. this case, we can still choose the same 24, as in tabular POMDPs. Using the above models and formulating POMDPS into PSRS for the pre- processing step to satisfy Assumption 3, we can run CRANE. The sample complexity for learning linear POMDPs will scale with din rather than poly(|O),11) (ST) as follows.
15

---

Under review as a conference paper at ICLR 2023
Corollary 6 (Sample complexity of m-step weakly- linear POMDPs), Suppose the linear POMDP is mtstep weakly- revealin and we execute CRANE with 3 = clog(N>(ee)TT (44/88) up the step H m where UI, and N (E6) are specified in Table 2. Then under Assumption for any
E (0, 1), > 0, if we choose
T= 1/e² x poly(dimm |A| 1/a, H, log OO| log(
then with probability least? 1 ō we have
v 2V
Comparison with [7]. From Corollary 6, we can see that the linear structure helps us circumvent the polynomial scaling with [O] and |8]. [7] also discusses linear POMDPs and achieves similar polynomial sample complexity. However, they only consider undercomplete setting (i.e., |O| 2 (S)) and assume (( (s)) a distribution
S for any E [d2]. In addition, they only assume the transition and emission are linear, but also impose a linear structure on the state distribution conditioned on future observations such as Cai al. [7, Assumption 2.2]. Therefore our model is more general and requires fewer assumptions.
A.5 m-STEP DECODABLE MABULAR/LOW-RANK/LEE
POMDPS
Next, we supplement the discussion about m7-tte decodable POMDPs in Section 5,
Core test sets and function classes. Like m-step weakly-revealing POMDPs, m-step decodable POMDPs can be formulated as PSRs where core tests are m-step futures and the PSR rank is [S] in the tabular case and diraus in low-rank POMDPs. Intuitively, this is proved by the observation that m-step futures can decode the latent state m-step ahead, i.e., 8m by treating "histories" in the definition as "futures". In Appendix we have a more detailed discussion. We also utilize the same function classes as m-step weakly-revealing POMDPs for m-step decodable POMDPs.
Remarks about Corollary Note that the discussion about m-step weakly-revealing linear POMDPs also holds for m-step decodable POMDPs, therefore can extend Corollary 3 to the following corollary:
Corollary (Sample comlexity for m-step decodable POMDPs).
In m-step decodable tabular POMDPs, the same statement in Corollary I holds.
m-step decodable low-rank POMDPs, the same statement Corollary 4 holds.
In m-step decodable linear POMDPs, the same statement in Corollary 6 holds.
Comparison with [13]. [13] works on m-step decodable tabular POMDPs and show sample com- plexity polynomial in (S), H, [A 1/e, log(1/8) and log covering number of a value function class. They also provide a result on m-step decodable low-rank POMDPs where the sample complexity scales with derans rather than (8). However, there some differences between their results and Corollary 7. First, the log covering number the value function class in their results will typically scale with (ol)( Our results, the other hand, only scale with poly([O)) since the log bracket number of our function classes only scales with poly((Ol). Secondly, the analysis in [13] does require the regularity-type assumption (Assumption 1). This is because their algorithm is tailored to m-step decodable POMDPs. The lower bound in Theorem has shown that the scaling with the regularity parameter 1/a a inevitable in PSRs, highlighting the necessity of such regularity in general.
B RELATED WORKS
We discuss related works to paper in this section.
16

---

Under review as a conference paper at ICLR 2023
PSRs and its learning algorithm PSRs represent states vector of predictions about future events [36, 41, 38, 21, 44, 19]. Importantly, compared to well-known models of dynamical systems like HMMs that postulate latent state variables that are never observed, we do not need to refer to la- tent state variables and every definition relies on observable quantities. While PSRs were originally introduced in the tabular setting, PSRs be extended to the non-tabular setting using conditional mean embeddings [4]. Using data obtained by exploratory open-loop policies such as uniform poli- cies, Boots al. [6: 4]. Zhang al. [49] proposed a learning algorithm for dynamics by leveraging spectral learning [33. 23, 28). Later, Hefny et al. [22] pointed out an insightful connection between spectral learning and supervised learning (more specifically. instrumental variable regression when histories are instrumental). Based on this viewpoint, Hefny et al. [22] proposed two-stage regres- sion learning algorithm. Compared to these settings, our setting is significantly challenging. This because their goal is learning system dynamics with exploratory offline data while we want to learn the optimal policy when we don't 't have access to such exploratory data.
Provably efficient RL for POMDPs and PSRs.
Seminal works [31, 14] obtained -type sample complexity bounds for POMDPs. We can avoid exponential dependence with more structural assumptions. Recently, there is a growing body of literature that discusses provably efficient RL in the online setting under various structures.
In the tabular setting, one of the most standard structural assumptions is an observability (i.e., weakly-revealing) assumption, which implies that observations retain information about latent states. Under observability and various additional assumptions, in Azizzadenesheli et al. [3], Guo al. [20], Kwon et al. [34], favorable polynomial sample complexities are obtained by leveraging the spectral learning technique [23]. Later, Jin et al. [29], Liu et al. [37] improve these results and obtain polynomial sample complexity results under only observability assumptions. Golowich al. [17; 18] develop algorithms with guasi-polynomin sample and computational complexity under observability properties.
In the non-tabular POMDP setting, several positive results are obtained. One of the most investigated models linear quadratic gaussian (LQG), which a partial observable version of LQRs. Lale al. [35], Simchowitz et al. [40] proposed sub-linear regret algorithms. Polynomial sample complexities are obtained on other various POMDP models such as M-step decodable POMDPs [13] where we can decode the latent state by m-step back histories (when
1, it is Block MDP), weakly- revealing linear-mixture type POMDPs [7] where emission and transition are modeled by linear mixture models, weakly-revealing low-rank POMDPs [45] where latent transition have low-rank structures. Our proposed algorithm can capture all of the abovementioned models except for LQQ.
There are few works that discuss strategic exploration in PSRs. None of them obtain polynomial sample complexity results for learning approximate globally optimal policies [26, 45]. For details, refer Section 4.
C NOTATIONS
We sum up the notations in PSRs in Table
D EXPRESSIVITY OF PSRS
In this section, we will construct a sequential decision making process to illustrate the superior expressivity of PSRs with respect POMDPs. In short, will show that if we formulate the process into a POMDP, the number of latent states we need can be exponentially larger the core test set size in PSRs. The construction leverages existing results in perfect matching polytope and largely follows the arguments in [1].
First, let n be even and K₂ be the complete graph on n vertices. Consider vector x E (5) that associates a weight to each edge and we denote its entry by Ny,v where u # v E [n]] are the vertices.
Let 1 E (G) denote the adge-indicator vector for a subset of edges M. Then [12] shows that the convex hull of all edge-indicator vectors corresponding to perfect match, which we also call the
17

---

Under review as a conference paper at ICLR 2023
Table 3: Notations PSRs. We also refer readers Figure I for an illustration of the notations such as Un, Di, Dh. and Ki.
Notation
Definition
V
E
Σ Σ Th
(P Th-1)
P( 7h do 2))
Uh
core test set at step h the set of all action sequences in Un predictive states
UAA
4r
Th- (m,,,, (T, minimum core test size at step h
dpsn,b
brn.
unnormalized predictive state {II-_ 1400
Dp
system dynamics
Dp
predictive state dynamics whose columns are dr, core matrix at step h
K
Mo,a.
predictive operator matrix
perfect matching polytope, can be expressed with a number of constraints as follows:
Pn == conv { Im R( M is perfect matching in K
f 122000000 0: Σ Fu. 1; C [n] and [U] odd ΣE Lu, 2 1
U&EU NEU
There are = nl/(22/3 (n/2))) vertices in Pa and the number of constraints is C := 20(n). We denote the vertices by [v1,". ,r and the constraints by , cC-- We further add an- other dimension to 0z(i E [V]) to account for the offsets in the constraints and obtain vectors
of E (i E [V]). Then we have (ci, uf) 2 0 for all i E [C],j E [V]. Now we can de- fine the slack matrix for the polytope P,, to be Z E RCCV where Z (ca, 1zy).
Notice that the rank of is O(n²). However, since P,, has extension complexity 20(x) [39] and the extension complexity of polytipe is the non-negative rank of its slack matrix [15]. know the non-negative rank of Z is at least 20(x)
Now we can construct our sequential decision making process. Suppose for the step S S H -1 the process behaves according to POMDP with state space S', action space A, observation space O, initial state distribution fl,, emission matrix On and transition kernel TT. At step though, the one-step system dynamics DH-1 is given by associating each pair (0H-1, with a constraint c; and each future test t E O (which is one-step observation now) with vertex v/ such that for any history -H-1 that ends with (0 aH we have
Il
(ce, ve
P(t[TH-1)= = Ek (g)
Now we fix history TH-2 2 with length H - and consider the matrix D (R(0)((1011)) where the rows are indexed by the test E O. the columns are indexed by the history (TH-2, o, a) for all
E O,a a E A and (D==))).ttx-o.a) = F( o, a). Since the non-negative rank is preserved under positive diagonal rescaling [8]. we know the non-negative rank of DJ is at least 20(x), Then for the above sequential process, if we formulate it into a POMDP with state space S, then we have
P(1) = Σ
#HES
Notice that for a rto-htcchatic matrix DT= the non-negative rank equal to the smallest number
of factors use write D H RS where both R, S row-stochastic [8]. This implies
18

---

Under review as a conference paper at ICLR 2023
all histories
F ( ((
all tests
P(thtileh)
P(t)+1l())
... p (th- ( (
Dn
i (ca+1 (he1)
((
((shhalth)) :
(sh++ In Lonn-
P(tiealshe) p(thaalshea))
I (ch+1
Sh+1 Sh+1)
151
p (( ((s
:
DI.
DAZ
Figure 2: For any POMDP, the system dynamics matrix Dj, can always be factorized using the latent states. This factorization implies that the rank of D₁ is no larger than the number of latent states, which implies that POMDP is a linear PSR with rank at most equal to the number of latent states. Note that here D and D,.2 both contains non non-negative entires. In contrast, from Figure 1, the low-rank factorization of D₁, in PSR can have negative entries (i.e., and can have negative entries).
that we must have |S] not smaller than the non-negative rank of D therefore we have
S|| 2 20())
On the other hand, if we formulate the above process into a PSR, step = H. since the rank of Dи-1 is equal to the rank of Z, we know the rank of Dи 1 is not larger than O ). which implies that there exists a core notice that for any test = {or-H, (h:H-1) and history 7h-1 we have
Uh whose size is not larger than O(n)). When 1 S S H
P(( = Σ
P(omm (0 1(onlon
ELES!
where 1A-1-1 ( Notice that P(4 Ponn a,,--)))) only depends on I and P(5x/Tx-1) only depends on Th-1- This implies that there exists a core test set Un. whose size not larger than [8'] for all < h S 1. Therefore, the core test set size of the PSR can be smaller than max))((n), [S']]. This shows that PSRs can express this sequential decision making process exponentially more efificient than POMDPs.
E EXAMPLES OF PSRS
In this section we present the proofs of Lemma 2 and Lemma 3, and then formulate m-step weakly- revealing POMDPs, m-step decodable POMDPs and low rank POMDPs into PSRs and analyze their core test set and minimum core test set size.
E. PROOFS OF LEMMA 2 AND LEMMA 3
We first prove Lemma 2. Consider the one-step system dynamics D2 shown in Figure whose rows indexed by all possible future tests f4+1 and columns are indexed by all histories Tr, h-th step. Each entry of D,, is the successful probability of the test, i.e., (Di)ta+1.7. = -P(tt+1/7H)) Since we know Pf( (T.) Es,, les PP 88h () 1 (Tx) (where we also define P(s (m)) = 0 for unreachable Ti.), we can decompose Dj, into the product D and Db,2 as in Figure 2, where (Di.1)ta t. [t Sk+1) and (Dr,2 22.1..7 = P(sh411Th) This implies that the rank of Da not larger than (S), which proves that it is linear PSR with rank no larger than (S].
Now we prove Lemma 3. Consider any h E [H) let 9 (P(o/T--))oEc) Then the belief state of the POMDP S [P(sh) (hh-)) can be expressed as:
0 1T,--
8T
19

---

Under review as a conference paper at ICLR 2023
Here, use 0,,0 On is an [S] [S] identity matrix, which is verified by the assumption. Then for any test = (Old++Ws Whch--11), we know P(t(T--1) = S where
h+W-1
m4,6 = O0+w(oo4w))
II
Tra, diag((r((r))))).
where (ol-) [2|l| is vector whose s-th entry is (ols)) and Ti,a; is [8] [8] matrix with entry (Ti, = Ti(s'|s, (ssssssa)))) at).
Therefore we have ((((/=--)) the probability of any test / is a linear combination of the probabilities of the tests o E O (the linear combination weights m4,1 only depends on test but is independent of history). This indicates that O is a core test set for 1-step weakly-revealing POMDPs.
mme.h.9T.-11 where Ma,h (m OT) Thus we have shown that
E.2 M-STEP WEAKLY-REVEALING POMDPS
Recall the definition the m-step emission matrix Dn,m E 10141~"111" x|S| for any E [H
+ 1] is as follows:
(an)))a,,o). = PP olsh 0h:h+mm-m----- a), V() Am=1 O" S.
Then m-step weakly revealing condition [37] means that the rank of Oh.m [S] for h E [H m + 1]. From Lemma 2, we know that drsn S |S). In addition, the following lemma suggests that
a general core test set for m-step weakly-revealing POMDPs is the set of all m-step futures:
Lemma 5. When Ohm fill rank for all [H m + 1]. the POMDP a PSR with the core test set Un O (A x mm for all h [H + 1].
Proof. The proof is similar to 1-step reakly-revealing POMDPs, Consider any h E [ - m + 1]. let d [P(u///-i))lexxxxxxr0 Then the belief state 8T,-1 = (T-),,, can be expressed as:
8T Jmmmtn. IT--1
8ra- where Then we know for any test t (onsh+ ah:h-W-1) we know P(((TT-1) m4,n 8
h+W-1
m4, = (n+w(on+wl))
II 1=h
Tra, diag(Cr((r))))..
Recall that here (ol-) E (1 is vector whose s-th entry is (ols)) and Ti is [S| matrix with entry (Tr, ) (s(s'ss,a))
|8|
Therefore have P(t(Th-1) (me, I where m4a (m 0/ TT This indicates that Ur O x (Ax 0 is a core test set for all h E [H m + 1].
of m-step weakly-revealing POMDPs up step H m + 1. However, this is sufficient to charaterize the whole POMDP. From Lemma 4 we know that for any trajectory Th. Pa (Tн) one of the entries H- Mo,.a. x ((TH). Therefore, with parameters ho J ae..eee-mm (which only depends on Un where h E [H] [ 1)) we can recover the POMDPs easily.
Notice that here only show the core
E.3 LATENT MDPs
Next we consider the Latent MDP (LMDP) model in [34]. Supoose there are M MDPs and each MDP mn is characterized by (S,A, Tm. Rm,h, HI pm) where S is the common state space, A is the common action space, Tm. is the transition probability at step of MDP m, Rm.h : S x A x (0, 1) + [0, is a probability measure for rewards at step h of MDP that maps state-action pair and binary reward to probability, H is the horizon and fmm is the initial state distribution of MDP At the start of every episode, MDP m [M] is randomly chosen with some probability w..-
20

---

Under review as a conference paper at ICLR 2023
[34, Theorem 3.1] shows that with no further assumptions, learning instance of the above LMDP requires at least (((()])AA))) episodes at worst. A number of assumptions are consid- ered to circumvent this lower bound and of them is called Sufficient Tests. More specifi- cally, for each step h E [H + 1), consider all possible length-! aetion-reward-sttate sequences ah, Th; Sh+t1,'. ... 11-+--11111 1. Fh+1-1, 8h-1 and denote the set of all such sequences by Th- Then sup- pose that the successful probability of Th under different MDPs given any 8n E S has rank M:
Assumption 5 (Sufficient Tests, [34, Condition IJ). For any h E [H - 1 1], 8n E S and any t (of h -/111-- s)+1)))))))))) E The we define
(t(ss))) = = Pm " 1 do(ah,. ... a
where Pm denotes the probubility under MDP m. Let Lan, = (18a(()))) "FaMr"""""MMM)))))) (Far((oo))eem.b) then a (Ies..) 2 a for all 8s. S with some a >>
The following lemma indicates that LMDPs with Assumption can be formulated into an + 1)- step weakly-revealing POMDP and thus a PSR with the core test set being all (z + 1)-step futures:
Lemma 6. Under Assumption S, the LMDP can be formulated into an (1+ -)-step weakly-revealing POMDP.
Proof. First notice that the LMDP can be formulated into a POMDP with state space S = S x {0, 13 [M] and observation space O S x 10, At each step h, the latent state 34 S is (Sk: Th-1. where $) is the current observed state, Th-1 is the reward of last step and I is the index of the underlying MDP. On the other hand, the observation on is (sh, Th-1). Then for any h E [H -++1+11 1], any latent state Th-1 and (1+ s)-ste test I = (oh, " 1444) we have
P(( 1(0h = (sh, Th rh-1)) (1(())))
where t = (ah " ' ,hor))) Therefore, the (1 + 1)-step emission matrix can be written as follows:
L
0
0
0
Ligh
0
0
...
0
L
Oh,141
0
D
0
L
Since the rank of L.s, M for any 84. E S, we know the rank of 0r.41 is 2M|S| for all h E
[H - -H--+11 1]. This implies that the POMDP satisfies the (1+ 1)-step wevelig condition. D
E.4 m-STEP DECODABLE POMDPS
Recall the definition of m-step decodable POMDPs [13] is that there exist unknown decoders (
Ódec, (Zz) for all such that for every reachable trajetory TH, we have 0n). From Lemma 2, we know that drsn I [S].
m < S where 2₁ = ((o, a) 1:h Further, the following lemma suggests that a general core test set for m-step decodable POMDPs is the set of all m-step futures:
Lemma 7. m-step decodable POMDP a PSR with the core test set U₁ 0 () for all h [ m + 1).
Proof. Consider any h E HH - m 1], let 9T--, = [F(ulm-))llexxxxxoo Then for any test 1 (Ohch w. ahih W -1), when W m 1, we have for any length- W) action sequence
a.
P(1[T--1)
Σ
P(u(Th--);
well.
21

---

Under review as a conference paper at ICLR 2023
where Ue, denotes the set of all length-m tests whose action sequence is (ohch+W-1, a) and the first W + 1 observations Oks+-W This implies P(t()h-1) m, -1 where ma, sets the entries corresponding to the tests in Ui, as and the others as O.
When W m 1, we denote f4:h+m-1 to be (0hth+m-1, -hhhm-mm1 and th-m be (Oh-m:h+W ,, mm+ W- w-). Then we have
P(4(T-1) P(Ina Th- (mo 12
-
ht 12h+ a f0 (0
Notice that P(0 (ew.mmh-W-oooo.ttmm.mm Ado.. (2 :
only depends on therefore we have P(4 = men07. where myyh sets entry corresponding to
(on:h4m-1+ a/:h+m-2 as Po(h+mmh+ wode:t/oooeehtm (000::/tmmm(00-m-m)))e---------- (0 -: (:0t:mmmm-m(((00-m-------- and the others as 0. This concludes our proof.
Similar to the discussion for m-step weakly-revealing POMDPs, is suffcient to show the core test set of m-step decodable POMDPs up step H m m++1
E.5 LOW-RANK POMDPS
Next we consider low-rank POMDPs. Recall that for low-rank POMDPs, the transition kernel Tr has the following low-rank form for all [H]:
T a) = (2hn (s')) (s,
where 4hh. S - Reaa and Φn S A + Rddeaas The next lemma indicates that for low-rank POMDPs, the minimum core test set size will be not larger than drrans, which can be potentially much smaller than SS)
Lemma 8. For any low-rank POMDP, its minimum core test set size will be not larger than dranns
Proof. First notice that we have for any test and history Th:
T) = ((P(()st+ Sr,))
Besides, notice that from the low rank structure (4), we have for any 8h+1 E S,
P(s (T)) = thn ($1+1)) T
Σ
dn a, ((NN)TT.)
This implies that
P(([Th)
Σ PP P(t/s=+1)W((sot)) ES
Σ BAES
This implies that the rank of the one-step system dynamics D₁ is not larger than duans for all [H). Therefore we have desR dirans-
F PROOF OF LEMMA 4
We first prove (4). Notice that we have
p. (Tr)gm. [P(u)T.)) (T.))(TTT) PUW.hhaeaaa...Po.//rrrarrooaaaa. (Th-1)
= (P(on, (T do(a,, a(u)))) T(an (P
Mo (1n, pa (Th- ())- (aa (1)
II Mo (TTh)= br, (TT))
1=1
where the third step comes from the definition (1). particular, for any trajectory TH, we have
H-1
PP (TH) = t (aau ( TH o0) (m 1ITH PP (TH-)- = m
II
Mon 9o T(TH).
h=1
22

---

Under review as a conference paper at ICLR 2023
G G-BRACKET NUMBER OF F
In this section we introduce some basic properties the e-bracket NumberrN==ee We first consider PSRs and then take POMDPs special examples.
G.1 PSRS
For PSRs, let us define the covering number for the parameters (Mo 90:5 as follows:
Definition 7 (c-covering number). The e-covering number of F, denoted by Zx(c), is the minimum integer v such that there exists a function class F with |Fl = n and for any J E there exists [[ :) 1loo S and 1/
I' E F' such that 40:f 11 6.
Here F' does not need be valid PSR model classes and (),,,,,a) does not need to belong to the column space of KN-f. That said, we still use Py. (TH to denote the product m mo I Ao 9 (TH) where Meg, = Cog H. although this might no longer be valid distribution. Then the following lemma shows that the bracket number can be upper bounded by the covering number, whose proof deferred Appendix G.3.
Lemma 9, Given F and any > 0, suppose Assumption 1,2 and 3 hold, then we have Nx(e) s Zz (8)00 (
Since the log covering number log Ze(e) typically scales with log(1/e), Lemma 9 shows that (og also scales with polynomial in general.
Tabular PSRs. Let us consider the tabular cases for example where we directly use (Mo,a, Yo MMM as the parameters of F and assume for all f F we have
max OEO..EA.MEEFF [M- ||
I 1111000sl|l S
without loss generality. Then we know
log (a(e (8| #+1 |A|" H((()) S SOT///OOIIIIFP/////OOAAAAAAAAAAA
which implies that
G.2 POMDPS
For POMDPs, we can obtain a more efficient function class by modeling the emission matrix On transition kernel Tr and initial state distribution μn instead of (Mo,a,hff 90:f). Let us define the covering number for the parameters {Taf Oue Pidf JhElH] as follows:
The e-covering number of (Theft Ohe fi,f HE(H, denoted by Vv(c), is the minimum integer such that there exists function class F with IF and for any f F there exists f E F' such that maxhe[M-I).es, A [[Th, Th 1o0,00 I c, (,maXne(m] ||0n: Opar'lloc,s and [|w1: - P1;f 1loc Se.
Definition 8.
Then we have the following lemma: Lemma 10. For any E F and 0 6 S 1, suppose I' satisfies MaX-k((-I)aEE. |[ Th, 1000,00 I Cop: maX [|Ohe On. /00,00 I Cop and || M1. Ilo Cop. where
cap = (14()))))))
Then for any policy have
Σ TW
$ e1-
The proof is omitted here since it follows similar arguments in the proof of Lemma 11. Therefore, following the arguments in the proof of Lemma 9, we know
NF(() < (=((/(28)))*+2 H
23

---

Under review as a conference paper at ICLR 2023
Tabular POMDPs. For tabular POMDPs where {Tu:f, Ouef M1:5 he(m is modeled directly, it be observed that log Vc(() [(H]0))5S)1)])l Therefore have
log))((e) - (o |-0,, [S), H, log(1/e)).
Low-rank POMDPs. For low-rank POMDPs, when utilizing the function class introduced in Sec- tion 5, we can obtain that log V=(c)= I log V' (f/ (3dhrra))))) + log Vu (e/((////ann))) + log (c/3) + log (c), which implies that
log (ggNs(c)>> - log 34 (CLR//erande log V' (CLR/derans) + log (o(ELR) + log J (CLR),
where ELR (({(((0)*+)111)))
Linear POMDPs. For linear POMDPs, when utilizing the function class introduced in Section 5, it can be calculated that log V=(E) O(H II d, (og( dc/e)), which implies that
log.Nz(e) (0 II de log( (1IA)))))
G.3 PROOF OF LEMMA 9
First let us prove that (-) is Lipschitz continuous with respect to aao (0.5) for any policy π, as shown in the following lemma:
Lemma 11. For any f F and < S MA) suppose f' satisfies
max -MM [ (i lox S cop, 11 20:0 S cops
where
Cop = =0G((44144/
Then for any policy we have
Σ - - TH
Sc.
Now consider the minimum Cop covering net of F, denoted by F. Then by the definition of mini- mum covering net, we know for any f F., there exists f' E F such that
max ,E0,,EAA.EEIF -I [I, M(o,a,)) lloo S cops Illool q0::/looo S Cop-
Using Lemma 11, we know for any policy and trajectory TH. (TT) c - (TH) < IP5, (TH) + 61.
Therefore, let us define of (T, P7 e and 05 = (.) + e1, then the set {lo] 9 I' E F is a 2el (IO])A))) -racket J where we use the fact that there are at most (AO many trajectories. Let 2e ([O]|A]) and then we have
Nx(e)) Zy(ae/ (7(0c/(800)* A H()))
G.4 PROOF OF LEMMA 11
We use Lemma 16 to prove this lemma via induction. First notice that we have for any E O e
A, E [ 1], a Uh+1.
[ Mo).a..).M;::lle cops
l1 00:111a Cop.
(8)
24

---

Under review as a conference paper at ICLR 2023
In the following discussion, Mo.a,hsf: and %/- (o.,,,)) My o,a,h by to denote 20:f' ho M bo Draff sim- plity writing, Next we use induction to prove the lemma.
Qu, ().,, Mo,a,i D7, denote 90.f ho...a)).:fff
For the base case, we have bro = q0, b% = %. Therefore from (8) we have
110 1/ 11 Kppp 61
Now suppose for any h' S h where [ 2 and policy т, we have ΣnH |lbr b ll2 x (TA:) S e1. Notice that here f' might not satisfy Assumption 3, but from the proof of Lemma 14 we can see that Lemma 14 still holds since f E F. Therefore we have for any policy n,
Σ
B ll2 x (TT++1)
The11
A+1
MA
Σ
Σ
[[Morand - My aa l12 x क(π) + 1190 %61l1)
(9)
a
1=1 71
From (7), know for any E [/1 1].
Σ
Mo Morar..
M Mr // T(n)
71
I Cop (1) Σ
11b ,1l1 x ((T)
"
= <ople1|10
1l/ (T-
S (opp
Σ (1lbmalll x ((T-1) + [bb - -b, x (TT-1))
I 2op11111
Σ (Ktll) + _1b___ - (TT-1))
S (1 [Mal)-
(10)
Here the first step comes from from the fact that (b (Ti-))) (y (1 and thus En, ||,,,, (
inequality and (7). The fourth step comes
En_, 1197-1//11 (T-1) & Mu E... (T-1) = [M The last step comes from the induc- tion hypothesis.
Substituting (8) and (10) into (9), we have
Σ |bro4s B |la ((Th+)) S 61.
Th+
Therefore, have for all h [H 1] and policy n,
Σ lbr, byz ll x ((T)) E1.
(11)
Notice that from Lemma 4 and Assumption 2 (where we let m Mon Cog, we have for any policy
Σ -P < Σ I|bm_ - b' b 1h x T(TH-1).
(12)
Combining (11) and (12), we have for all policy x
Σ (T)) - P7 (TH) & e1.
7B
This concludes proof.
25

---

Under review as a conference paper at ICLR 2023
H REDUNDANCY OF Mo
In Section we mention that there redundancy in the choice a)) given the model Pj and we can replace any ()) with its projection on the space spanned by {4m, istr 1 The following lemma characterizes this formally:
Lemma 12. Suppose Assumption 2 holds. Given any parameter aM buf
(.0.::g900)))) g0.5),
suppose for an-
other set of parameters (Mo,o.h;f' qu:f we have for all o E O, A, H -1, E Uh+1
().. Projcol(Kn-nI))) (m)..,)))
Then for any trajectory TH and policy n. we have (TH) (T)()). This means that (o. y also valid set of predictive parameters for the y
Proof. We first show that byas = b for any h E [H - 1] and trajectory The We prove this via induction. For the base case where h = O, braef Diuif' 90:f- Next for any h H 2]+, suppose oraesf = b for any h' E [h]+ and trajectory Th-- Then for any trajectory Th+1, let Th. denote the policy that always takes the action sequence in Th. From (4) in Lemma
have Uratsi/ = Mo.-1 Mos = Mon-ianntiie / TTg (Tr)
(Tp)
Juetfi Pata (Tn).
(13)
Similarly, since braif' brn.f, we have
bratsif'
(m (1) woth 11 (Tn).
(14)
From (2), know dyaf belongs to the column space of Kn,f. This implies that for any Uh+2
(on+1 (0)+ m "I(oo 1841 ah41 1:f 1n.f
(15)
Combining (13) and (15), have
Therefore, for any [H - -1] and trajectory The we have
braif braeft
This suggests that for any policy æ and trajctory TH-1, we have
(PP (1f()/==-)PP((=-))))))))) - (1 (TH--) ()) Therefore with Assumption we have for any policy æ and trajectory TH. we have (T())) (T))
I PROOF OF THEOREM
1
In this section we present a proof sketch for Theorem 1. Note that to prove Theorem 1, we only need show that CRANE can achieve sublinear total suboptimality, which is stated in the following theorem:
Theorem Under Assumption 1,2,3, there exists an absolute constant e such that for any d E (0, 1], T E N. if we choose e Log(Nr(ee)THHUuA)) in CRANE where eb 1//TH then with probability at least - 5, we have:
T
Σ(v - va*) < ((pSR H MA 2A 1og[THN)(())))]44100)
26

---

Under review as a conference paper at ICLR 2023
The VT bound the regret in Theorem 2 suggests that the uniform mixture of the output policies
मे Unif (==))=)))) is e-optimal policy when T O(1/e²), leading to Theorem 1 directly.
Therefore we only need to prove Theorem now.
Note that we can decompose the total suboptimality into the following terms:
T
Regret(7) Σ (V--vV =
Σ V
Vzx")
(V - -VT)))
(16)
k=1
(1)
(2)
Our proof bounds these two terms separately and mainly consists four steps:
1. Prove y is optimistic estimation of V for all & [T]. which implies that tenm (1) S 0.
Decompose term (2) into the estimation error of the parameter Mo,a, via the system dynamics
(3).
3. Bound the cumulative estimation error using the property of MLE.
4.
Bound term (2) by connecting the results in the second and third step.
1.1 STEP 1: PROVE OPTIMISM
First we can show that the constructed set B contains the true model parameter f with high prob- ability:
Lemma 13. With probability least 1 6/2, we have for all k E [T], f E B*.
Proof. See Appendix J.1.
Then since fj max VJ. know for all [7],
V 2f="==
Thus, Lemma 13 implies that V is optimistic estimation of V for all k and therefore term (1) in (16) is non-positive.
1.2 STEP 2: DECOMPOSE THE PERFORMANCE DIFFERENCE
Next aim to handle term (2) in (16) and show the estimation error ΣT_ (Vz* - VV*) is small. First need to decompose the performance difference V y** into the estimation error of the parameters Mo,a,h in order apply the property of MLE later. Notice that we have,
VJ V*
Pp (TH) P7. (TH)l
H-1
H II h=
H
(m
oz
II h=1
M an.h go mon H
Mo on go
x th (TH)
TM
1
H-1
II Mk
9
II
Mon go
n" ("(H-11))
(17)
TH
where
we use
& on, H M
on.
denote
Mox Hifk , Mon. hifk 9o and
Moy, H, Mo h. hn; go denote Mon Hiff, bo 90.f-- The second step is due to Lemma and the last step is because based Assumption 2 we have set m H. Mon, H Con H-
The following lemma bridges the term in (17) and the estimation error of Ma whose proof is deferred to Appendix J.2:
27

---

Under review as a conference paper at ICLR 2023
Lemma 14. For any & E [T], h [H] and policy have
Mor and 80
Σ
M
a1 and 90
πI
x (((T))
7h
1=1
A
Σ
II aa Morar x (T)) + 11 qull1)
(18)
a
72
where bn = -I1=1 Moj 2
Remark 3. From the proof of Lemma 14, can that Lemma 14 only utilizes the proper- ties of {M 01 21 40 JeIN- Therefore Lemma 14 still holds even if the system dynamics induced by {Mor qo he( is invalid. We will use this fact in the analysis about the e-bracket number.
Therefore, substituting Lemma 14 into (17), can bound the performance difference by the cumu- lative estimation error:
V*y)
MAll
H
Mol all1 x π *T() + +11 soll1) ) (19)
[[
os
h=1
1.3 STEP 3: BOUND THE ESTIMATION ERROR
Now we need to bound the estimation error in (19). First we introduce the following guarantee of MLE from the literature, which connects the log- ligeliood ratio log (og(P7 (TH)) and the total variation Σng (TH) - (TH)l:
Lemma 15 (137, Proposition 14]). There exists a universal constant e such that for any ō E (0, 1].
for all k E [T) and F, have with probability least 1 - 5/2 that
Σ
Σ
Σ
(TH) PJ- (TH)i)
1=1 AE(H -1] 1) Maakt EMAAht1
(TH S.a.
S co Σ
Σ
log
+ (og(M((())THHHA1()))
(T h
NE(H 1]+ Ma, Eu
Combining Lemma 15 and the fact that both f and 1 belongs to Bk, we have with probability at least 1 that for all & E (7).
Σ
Σ
Σ
(TH) -PP""
i - (TH)l) (
(20)
h Ma.h44 E4A,44
The following discussion is conditioned on the event in (20) being true. Then by Cauchy-Schwer inequality we have for all & E [T].
Σ
Σ 1= h 1 TH
Σ
j Maahh
(TH) PT i (TH) S O(VKH)(Al)) (21)
Suppose the length of the longest action sequence in MAA.A is lg- Then since the environment will only generate dummy observations Odummy after an, we have for any policy म and f E F.
Σ
(TT444)))) - IPJ. -PJ- (TH+4,+1))
Σ (P((t))(on
Odummny
TH
28

---

Under review as a conference paper at ICLR 2023
(rr((a))(lon--ur-tt Odummy ) [w) (T((n) - ())((TH)) -P.
Therefore, we can marginalize the distribution 17) (TH) and 17. (TH) in (21) and have for all & (T) E IK
11,
|| -0-1] 1
Σ
Σ
IP b (TH) p..
aiuhh (TH)
Ua, E41 TH
Σ
IP io
(Thy 0a Pj. pplluuhii (Thy 2a,1, 0)
MaMh:1MMA,ht To (ua
= Σ
Σ
- -Py (Th (o))))
x x a (M (uan+11Th))
Σ
do(uattt)) 1P (o) p (ol))yoo))
Th Mach 11 IHl 1.00((u.R1))
Σ
Py (T))
Ps. (T.)P)((uln))-
MEllit1
Here in the first step (ua,)+4) denote the set observation sequences that occur together with Ua in U441 and (T (Th, Mo,t+1, o) denotes the joint probability of observing the trajectory (Th, o, (o,4+1). ). the third and fourth step we utilize the fact that k. a -f Unif(AA) ua and we define n i.h = -ish1 Unif(A). Then based on Eq. (4) and Eq. (21), we have for all E
1Jt.
n (Th) 1 - b,, S ((
Thus via importance weighting, we have for all & E [T], E [ - 1]t
n ('(n)) 110. -b,, O(IA /HH/AA))))
(22)
x (Th 11t5 - b. s (ILAIIHH
(23)
In partieular, when h we have
11 9ol12 S OO (3/B//)
(24)
Now for all & [T], h e [H 1], we can bound the estimation error as follows:
k
[| on
Mo M. lll x n (T)-
Th
aM Mon bon (((Tn-1)
Th
M aM br.-lll1 x o (Th-2)-
(25)
1=1
29

---

Under review as a conference paper at ICLR 2023
For the first term in (25), we have
[ an 12 0m- Mon bil (Th-1)
7h
k-1
π (Th-1) 110 - bTa 1 S01A kH)
(26)
t=1 7h
where the second step is due to (23).
To bound the second term, we need to bound M,, first, which given in the following lemma:
Lemma 16. For any 1 S ji S j2 S H - trajectory Tj J policy f E F and x E Rl have
Σ T2
II j=h
M Mo
<T( S a ||
The proof of the above lemma uses the regularity condition in Assumption 3 and Lemma 12. Naively, the product 11;= Maj.ay.iff may indicate that the norm may grow exponentially. How- ever, the condition that Ma,a, row span belongs to the column span of Ka-1;f (which is dereived from Lemma 12) and the fact that -
1;f exists, we have:
jn II jーh
j2 Mo, a = II j=
Mo, Jy K,, K,,-1, 1:
Thus, can bound || I1; Mo, Mo Ji -:feellaa by using the fact that K 1:fe; is predictive state 9-), -iyi corresponding to one of the minimum core histories T/ - and I Moyaayii wElf where Tr de-
dr if x क (1)3)113)))) = [P(ulr),-1: Ti ) (Tiisaa (r/ (
note the policy T( -1) Note that the proof of the above lemma differs from the one in POMDPs since here we leverage the concept of minimum core histories and the core matrix which are unique to PSRs. The details are deferred to Appendix J.3.
Therefore, using Lemma 16 with via--1 Unif(AA, we have
Σ
Σ
M on
1 An-1 xT(-11
on
1-1
Σ
Σ
n (Th-1)
11b - bm S S(AA (HFAAA/)HH
(27)
74-1
where the last step comes from (22).
Combining (26) and (27), we have for all k E [T], h E [ - 1].
Σ
[[M Molb 1l x (Th & OHHAAP//HHR
(28)
1.4 STEP 4: CONNECT STEP AND STEP
Recall that Step we want to bound
T
#
[| on
M
Mon.an. ll1 x x x(())) + 11 - 80ll1
.h
A=
Th
30

---

Under review as a conference paper at ICLR 2023
First, for the second term, can bound via (24):
l 2olli S HTVHT))))))
(29)
Now we only need to bound the first term. Notice that in (28) we have bounded this cumulative estimation error weighted by (Th-)) rather than x² (Th-1). Here we introduce the following lemma from [37] to bridge these two summations with different weights:
Lemma 17 ([37, Proposition 22]). Suppose (Jn.s) (wk, (a.)) E R satisfy
for all k E [T]
Ei=1 Di=1 Eez Ttal S nh.
Ea |a0 S Rx,
Ei ||Wx; S Rw-
Then have for all [T]:
w T -t,l = =0({(Ru Rv + max 7t log (Tn)))
To apply Lemma 17, for any fixed h E [H - 1], we rewrite (28) in the following way:
k-1 [ht1l
Σ
[(M o.a.h Mo,a,h KA 1 x a' (Ta-))l)
0,0
S
<OIA AKHUAABBB)))))
(30)
where X. is the u-th row of the matrix X. Here we utilize the fact that by x ("h- = (PlulT--][P* [m-11)) belongs to the column space of K due to the definition of core his- tory.
Then for any E [T), u U1+1, O, A, let at,a denote [(Mo,.. Mo,a,h) Kn-1] and - denote K{ drn-s x xT(Tn-1). then (30) can be written for any A: E [T]
Σ
Σ
Σ
IuKu...T Tt S (114AA/))))))3/0))
(31)
t=l wwt.
Now only need to bound Enpn, 11 and Eneth,, ||W..ooll.. For
Em. | we have
Σ 1 Σ bon Th (Th-1)l2= Σ (h (Tn-1)luEuall ll2
Th-1
Th-1
Th-
|| 1|2p=* (fh-1) S max 12l2, Σ
Th-1
The-
where the third step comes from the definition of core matrix (2).
Notice that we have KB-1UT,-1 [P(w|/r- for any Th-1 and ill-o1 S 1/a, which implies
UA
[0,, .lla 110T .ll1 [Pugt, < (((u(TT-)))EEEA
a
Therefore we have for all & E [T].
Σ 1 112 MA
(32)
31

---

Under review as a conference paper at ICLR 2023
For DE ||
we have
Σ
|
Σ
Neth, 12:
dPsR
Σ
II(
Moa.A)Kn-eelll
oEO,aEA
dPER.N-1
A|
2|Al||Aa| d
Σ
|kn-1e111 -
(33)
a
a
where the third step utilizes Lemma 16 with uniform policy and the last step utilizes the fact
dPSR,A-1 S desR and | 11 S [al.
Invoking Lemma 17 with (32),, we can obtain for all & E [T], I - 1].
Σ E
|| on. Mon an - x Th (Th-1)
OddrRR M
A| |AA desn hoggo//oooooooooCC////CCC/////// 1og[THN((()))00111/)))
(34)
Substituing (29),33) into (19), we have
T
Σ (V V=*)= I OlBBR HiMaaRHHAMMMMAAPP2aa (
1=1
Combining the above result with Step 1, we have
-(r S O(ppsR H un " -3. -og(THN)/())00111100)
vn
This concludes our proof.
J PROOFS OF LEMMAS IN APPENDIX I
J.1 PROOF OF LEMMA 13
To prove f* E BC, need to show that (( log P7- (TH) is large. To simplify writing, we denote the TH) pairs D at the end of T-th iteration by ((*", o TH, which are indexed by their collection order. Notice that nr < TH MAl To deal with potentially infinite function clas F. we first consider its minimum bb-bracket net G where Eb all upper bound functions in G. i.e., G, = {f' 3f, such that [" E 9). Then bound the difference bewteen E(TTT)ED log 1P-. (TH) and (G.TH)ED log (T())) for any f E F via
H(TH(AA) and the set of able to
's method as in [37].
Fix any I' Gu, & [nr] and let 3. denote the filtration induced by ((T), 7 M (m*). We have:
P.J (TH) P.i
E
exp
log
1=1
PF (TH
I yr
(Ti
I
exp
log
E
exp
log
PT (TH)
pot (T
(T)
P (TA)
exp
log
E
Fr
P.z (TH)
P. (Th)
IP7' (TH) p7 (TZ/
exp
log
Σ
PF (TH)
TM
32

---

Under review as a conference paper at ICLR 2023
P (rin) P7. (T(+)
(1+
E
exp
log
THRA
where the last step is due to the fact that G is the minimum cb-bracket net, which implies that there exists f E F such that (-) 1-) (-)ll S eb. for any policy π and thus (-11 S 11+b. Repeat the above arguments and we have
E
exp
log
Se.
(TH)
i=1
Then by Markov's incquality we have for any (0, 1].
pf (TH) pa.. (Tf+)
log
1og(1/6)
PT (Ti)) PT-
S exp
log
s ed.
Therefore by union bound, have for all f' Gus [nr]]
P (Tin)
P log
clog(Ns(6))TH/A111)) 5
(+i)
where è a universal constant.
Finally, due to the definition of e-bracket net, we know for all F, there exists f Gu such that P7 (TH) S (TH) for any trajectory тh and policy æ. Therefore we have for all f E F, F. E [nr],
(TH))
P
log
clog(N3()))HHHAA/0)) 5/22,
pot
(Th)
1=1
which implies that f E B* for all & [T] with probability at least - 8/2, This concludes
proof.
J.2 PROOF OF LEMMA 14
First, notice that decompose the left hand side of (18) into the following sequence of terms via triangle inequality:
h II Mon 2o/| x (TT)))
Σ 74
M on
and
go
Mr
aa (M (M
Mos,ass b
x (T()))
1=j+1
di (0--so) <(()).
M
(35)
Then fix j E [h] and consider the term Σn, Mi Mr ar (M Majaasa Monaays) -r,- /1, x ( in (35). We have
Σ
M
Mos
brg-a x x((T)
1=j+1
Σ
x (Tg)
Σ
II
Mo
M M
Mosays) br-- (
i=++1
33

---

Under review as a conference paper at ICLR 2023
UA a
Σ T
Mor - Mosiess) 0rg =(T)),
(36)
where the last step comes from Lemma 16.
Similarly, apply Lemma 16 to the second part of (35) and we have
h
( 20)) s0)l x x(((T))
[M
Σ
M
11 qull1-
(37)
Substituting (36) and (37) into (35), we can obtain
Σ
M
on ana
4o
II Mor ar. s0 x x(T))
Th
[I aa. Monar, ll2 x ( + 1 =0ol11
1=1
This concludes our proof.
J.3 PROOF OF LEMMA 16
First, based on Lemma 12, we have chosen (l(o, to belong to the column space of Kj -iff which implies that
h
Σ 12
II
Monayziit
M
jm
(x))))))))) x ( ( TTi-1).
Σ
II f=
M Mo
Note that since the (-th column of -1f is 4rg, 1,iif model induced by f, we have for any e (1:s
the L-th core history step ji under the
I(
f2 II
Σ
Mo Mon
x (T
j=h
ja
Σ
Σ
II
Mo Ke a((onssn
j=h
Σ
Σ
Ossi Riis2 NEMlgttt
Σ ΣΣ
Σ
(y Ojri:: (n:s)a) (()b))))) Py Py do) ajvs))) (1
V5 9h132 aElli2+1
[Al Σ
Σ
031332 431322
[al-
Here in the second step T(O) (1 denotes IT (aylTT -1 Ojrs i) and the third step comes from Lemma 4.
34

---

Under review as a conference paper at ICLR 2023
Therefore we have
jf
Mosaan aasaiii kz- ) Ky (x2 |
Σ
II
j=
UA
s
[uil
KJ 1=
|,11|,,
where the third step comes from Assumption 3. This concludes our proof.
K NECESSITY OF 1/a IN THEOREM 1
In this section we show that the polynomial dependence on 1/a in Theorem is inevitable in general. More specifically, we have the following theorem:
2\2 and H, |A| E N there exists a PSR with core test set U₁ O for h E [H] and [S] = 10| = O(1) which satisfies Assumption I so that any algorithm requires at least Q ((min{ aH (All-1)) samples to learn a (1/2)-optimal policy with probability 1/6 or higher.
Theorem 3. For any <
Theorem 3 indicates that scaling with 1/a is unavoidable else the algorithm will require exponential number of samples to learn a near optimal policy. The proof is deferred to Appendix K.I.
K. PROOF OF THEOREM 3
We leverage the hard instance constructed in [37] prove the lower bound, which is based combinatorial lock. More specifically, we define a POMDP as follows:
State space: There are two states, S { $6}.
Observation space and emission matrices: There are three observations, O {oag Ob, Odummy } For E [H - I], we define the emission matrix as follows:
22a
On
V 2a
22a
V2a
For h = H, we have
(1 0
Of
0 1
0 0
This means that with probability we can observe the current state and with probability a only receive dummy observation at step h E [H - 1]. At step H, though, we are able to observe the current state.
Action space and transition kernels: There are |A] actions and the initial state is fixed 8g- For each step h E HH 1), there exists a good action ag.h E A which is chosen uniformly at random from A such that if the agent is currently in 8h. = 8g and takes 0g. it will stay in 8g. i.e., Sg. Otherwise, the agent will always go to 8h+1 Sb.
Sh+1
Reward: We define ro( for all h [ 1] and o E O. At step H, (o while (=(0s)= = 0. This indicates that the agent will receive reward 1 iff the agent takes ag along its way.
Since this POMDP satisifes weakly-revealing condition, we know O is its core test set. Next we show that this POMDP satisfies Assumption 1. First it is can be observed that Ko = qo =
(V2a, 0,1 -2a) and we can verify that
|K & 1/a.
Then for any h E [H 1] and reachable history The if a1:h = Ag.1:h, we have
(P(5h-1 sy(Th) 1, PP(8+1 sulTh) 0,
35

---

Under review as a conference paper at ICLR 2023
which implies that
P(oo+1 = 0glTh) (2a,,((o+1
P(on+1 = ob(Th) 0, Po Odummy ( = V2a.
Otherwise, if there exists h/ [h) such that on # 0g,h', then have
P( = sp(Th) 1(544 sylT)) 0,
which implies
P(on+1 Tb(TT) V2a, P(on 0y(Th) 0, 0( Odummy (h) V2a.
This suggests that Kn = Oh+1 for h E I| - 1]. On the otherhand, since Tmin (Kn) miin (0n+1) 2 V2a, we have for h E [H 1),
|Kll $ V2I S v2/(V2a) = 1/a.
This shows that the constructed POMDP satisfies Assumption 1.
Now we only need to show that the constructed POMDP attains the lower bound in Theorem This has been proved in [37] and we include the proof here for completeness.
Suppose we can only interact with the POMDP for T Σ 1 12/2aH episodes. Then we know the probability that both 89 and St only emit Odummy in the first H 1 steps for all T episodes is lower bounded by (1 12o))///2aa 1((2a) since
L2 (H 1) s 1/(v2o).
Now conditioned on the event that both 8g and Sy only emit Odummy in the first H 1 steps for all T episodes, we can only random guess the optimal action sequence -g.1:H-1. Then if s ||| 1110, the probability that we fail to guess the optimal action sequence is
(L-I--111 1)
A
2 0.9,
T
1/6, the agent can only learn that the action sequences it chooses in these episodes is incorrect, which implies that the agent can only random guess from the remained action sequences. Therefore, if T 111*-/10. /10, the policy that the agent outputs will be worse than 1 1/2-optimal, which concludes our proof.
Therefore, with probability 0.9 x (1 1/(va) >
|A|
36


Reviews:
[{"review_id": "tI62UyVpiBQ", "reviewer": "Reviewer_gdmT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The submission considers a sample-efficient learning for PSRs. The nature of the problem is similar to (Liu et al. 2022), and previous algorithmic framework is extended from POMDPs to PSRs. This generalization to PSR seems relatively easy since the core test-set is provided a priori, and the construction of confidence set based on log-likelihood values can remain the same (as long as we know some rough upper bounds of the rank of PSRs). Results for the most general framework PSR can imply several previous results including tabular POMDPs (Liu et al., 2022) and m-step decodable POMDPs (Efroni et al., 2022), and low-rank POMDPs. Proof ideas and techniques are mostly adopted from (Liu et al., 2022), though it is not entirely straight-forward to make things work for PSRs. ", "summary_of_the_review": "Overall, despite some concerns on technical novelty, I think that this paper makes a good contribution, and could be a nice addition to POMDP literature. ", "strength_and_weaknesses": "*Strength*\n\n- The paper extended a recent breakthrough in POMDPs to a more general framework, which is a good addition to literature.  \n\n- The positioning of the paper is good -- well-explained related works, how the more general framework can imply previous results, etc. \n\n\n*Weakness*\n\n- Given the work by (Liu et al., 2022), it is predictable that the same idea would work in the PSR framework. All POMDP systems are equivalent up to some similarity transformation of belief states (say, as argued in (Boots et al., 2011)), and in a slightly older work by Liu (Liu et al., 2020), the PSR representation of POMDPs was explicitly used. The scope presented in (Liu et al., 2022) is not really because it can only work for POMDPs -- confidence set based on MLE can naturally cover all equivalent systems up to the belief state transformation. So novelty of the paper is limited.  \n\n- It would have been helpful how the authors could get around the issue that there is actually no concept of latent states \"S\". In (Liu et al., 2022), it seemed that anchoring to latent states helps a lot to make analysis easier. I could imagine that such concept might not be necessary, but it would have been nice if the authors could elaborate more kindly and crisply how they could get around the issue. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "rU9_H2-fMe", "reviewer": "Reviewer_XgNc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers the problem of provably efficient reinforcement learning on predictive state representations (PSRs) with function approximation. The main contribution of the paper is a PAC algorithm for PSRs with polynomial sample complexity when competing with the globally optimal policy. Although sharing similar design principles with traditional optimism based methods on POMDPs such as the OMLE algorithm, this work extends the scope of OMLE to a larger set of models (PSRs) featured by direct prediction of the future given the past trajectories. The more general model classes includes several examples including the $m$-step weak-revealing POMDPs, the $m$-step decodable POMDPs, etc. Moreover, the result can also be applied to POMDPs equipped with function approximations such as the low-rank structure, the linear structure, etc.\n\nOverall, the proposed algorithm OptimistiC PSR leArniNg with MLE (CRANE) achieves polynomial sample complexity on a subset of PSR problems with a regularity condition. The $\\alpha$-regularity condition on PSR is defined upon the core matrix and is a generalization of the weakly revealing condition. When instantiated to POMDPs, the algorithm can not only solve $m$-step weakly revealing POMDPs but also $m$-step decodable POMDPs, etc.", "summary_of_the_review": "This paper provides the first polynomial sample complexity result for PSRs and is thus a solid contribution. The applicability of the assumption is limited, the sample complexity is not sharp, and the empirical impact is unclear. But it is in general a good submission.", "strength_and_weaknesses": "The main strength of this paper is that it provides the first sample-efficient algorithm in learning PSRs, although under an additional regularity assumption. While previous work depends on latent states, this work uses  $M_{o, a, h}, q_0$  that is free from latent spaces. Technically, it leverages the properties of the core matrix $K_h$ to control the product of $M_{o, a, h}$ and thus controls the error induced by the estimation error of $M_{o, a, h}$ and $q_0$. This technique allows the CRANE algorithm to work on a more general PSR classes that subsume both weak-revealing settings as well as decodable settings.\n\nThere are a few weaknesses and questions:\n\n- The regularity assumption (Assumption 1) is defined on the core matrix $K_h$ and seems to have limited applicability.  Are there any cases belonging to POMDPs that does not satisfy Assumption 1? The authors could better discuss the applicability of Assumption 1 by providing some counterexamples that violates the regularity condition. \n- The work focuses on providing a polynomial sample complexity, but omits the specific dependency parameters in the main theorems.  Although providing the first polynomial complexity under a more general setting is significant, it is hard to compare the sample complexity result with previous results when restricted to specific instances. Such as, how to compare CRANE with Liu et al. under $m$-step weak-revealing POMDPs?\n- In Liu et al. that proposed OMLE, they uses a generalized eluder-type dimension to bound the regret. What is the relationship of the complexity measure used in this paper ($d_{PSR}$) with the eluded-type dimension? Is it possible to extend complexity measure $d_{PSR}$ to a more general one?\n- Since no experiments are provided, is CRANE applicable to real-world problems and computational efficient?\n- Is there a specific reason that the authors focuses on the model-based setting? Is it possible to extend the optimism-based algorithm on POMDP to model-free settings?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oWZIuwq5bqh", "reviewer": "Reviewer_YxZB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of RL with PSRs. The PSR setting is first motivated by its generality and structural properties. Then, a new algorithm, CRANE, is proposed, which is an optimistic MLE algorithm. It takes as input a model class (to represent a class of PSR) and solves an MLE objective to maintain an uncertainty set. Applications of the results are presented on existing problem settings such as weakly revealing POMPDs and decodable POMDPs.", "summary_of_the_review": "This paper has a lot of potential, but there are still shortcomings in the significance, algorithmic novelty and overall clarity in its discussions. In particular, it’s unclear what analytic insights can be gleaned from the PSR analysis over existing work. ", "strength_and_weaknesses": "Strengths:\n- Few papers have studied efficient methods for RL in the PSR setting. This seems to be the first to do this comprehensively.\n- A new OMLE algorithm is presented to work with PSR models generally, which encompass many other partially observable models.\n- The paper does a good job of demonstrating how their methods can be applied to many existing problem settings.\n- The beginning discussion is both clear and well-written and contextualizes the work.\n- The theory seems good.\n \nWeaknesses:\n- The algorithm is pretty similar to existing “OMLE” style algorithms, so the algorithmic novelty is limited.\n- To implement the algorithm, it seems a large amount of information must be known about the given problem such as the core test set, the singular value, preconditions in Assumption 3, etc. This begs the question of whether it might just be practically easier to implement existing algorithms for a specific problem, given that one essentially has to know the problem setting anyway. \n- The main selling point of this paper is the generality of PSRs. However, it’s unclear whether this generality affords significantly new insights into the problem. All of the examples given are settings for which efficient, simple algorithms already exist. The result would be stronger if there are interesting, new problems settings where this generality produces new, previously unknown results or much better results than the existing literature. But so far this evidence is either not provided or it is not clear.\n\n\nOther:\n- In the beginning it’s motivated that PSRs can be solved via spectral methods in contrast to difficult to optimize EM-style algorithms, but Alg 1 looks like a very difficult MLE problem. Can the authors comment on this?\n- It claimed that Liu et al’s algorithm needs the latent state representation known, but I doubt this is actually a fundamental limitation of their algorithm and analysis and it is more so done for simplification. The concurrent work of Liu et al (2022) seems to support my suspicion as well.\n- I do not think it is sufficient to state the main results as just poly( problem inputs ). This makes it very hard to compare across papers.\n- How large can we expect U_A to be in general?\n- “Assumption 3 can be easily satisfied by eliminating those functions which do not satisfy the regularity or validity.” I’m not confident this is an easy task in practice.\n- On Page 6 in the justification of the bracket, it says P is lipschitz but with what constant?\n\nLiu et al “Optimistic MLE—A Generic Model-based Algorithm for Partially Observable Sequential Decision Making”\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster