Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms
Authors: Fan Chen
Yu Bai
Song Mei
Venue: ICLR 2023 notable top 25% (2023)
Keywords: reinforcement learning theory
POMDPs
predictive state representations
partially observable reinforcement learning

Abstract: Partial Observability---where agents can only observe partial information about the true underlying state of the system---is ubiquitous in real-world applications of Reinforcement Learning (RL). Theoretically, learning a near-optimal policy under partial observability is known to be hard in the worst case due to an exponential sample complexity lower bound. Recent work has identified several tractable subclasses that are learnable with polynomial samples, such as Partially Observable Markov Decision Processes (POMDPs) with certain revealing or decodability conditions. However, this line of research is still in its infancy, where (1) unified structural conditions enabling sample-efficient learning are lacking; (2) existing sample complexities for known tractable subclasses are far from sharp; and (3) fewer sample-efficient algorithms are available than in fully observable RL.

This paper advances all three aspects above for Partially Observable RL in the general setting of Predictive State Representations (PSRs). First, we propose a natural and unified structural condition for PSRs called \emph{B-stability}. B-stable PSRs encompasses the vast majority of known tractable subclasses such as weakly revealing POMDPs, low-rank future-sufficient POMDPs, decodable POMDPs, and regular PSRs. Next, we show that any B-stable PSR can be learned with polynomial samples in relevant problem parameters. When instantiated in the aforementioned subclasses, our sample complexities improve substantially over the current best ones. Finally, our results are achieved by three algorithms simultaneously: Optimistic Maximum Likelihood Estimation, Estimation-to-Decisions, and Model-Based Optimistic Posterior Sampling. The latter two algorithms are new for sample-efficient learning of POMDPs/PSRs.
We additionally design a variant of the Estimation-to-Decisions algorithm to perform sample-efficient \emph{all-policy model estimation} for B-stable PSRs, which also yields guarantees for reward-free learning as an implication.

Published as a conference paper at ICLR 2023
PARTIALLY OBSERVABLE RL WITH B-STABILITY:
UNIFIED STRUCTURAL CONDITION AND
SHARP SAMPLE-EFFICIENT ALGORIHTMM
Fan Chen
Yu Bai* Salesforce Research yu. yp.baa@saaeesforee.. com
Song Mei
Peking University cwwpn@pku.edu.cmm
UC Berkeley a scngmei eengmme@@eereeeyy..om edu
chernêpku. edu. cn
ABSTRACT
Partial Observabilit--wher agents can only observe partial information about the underlying state of the system-is ubiquitous in real-world applications of Reinforcement Learning (RL). Theoretically, learning near-optimal policy un- der partial observability known be hard in the worst case due to an exponen- tial sample complexity lower bound. Recent work has identified several tractable subclasses that are learnable with polynomial samples, such as Partially Observ- able Markov Decision Processes (POMDPs) with certain revealing or decodability conditions. However, this line of research is still in its infancy, where (1) unified structural conditions enabling sample-efficient learning are lacking; (2) existing sample complexities for known tractable subclasses are far from sharp; and (3) fewer sample-efficiee algorithms are available than in fully observable RL.
This paper advances all three aspects above for Partially Observable RL in the general setting of Predictive State Representations (PSRs). First, we propose a natural and unified structural condition for PSRs called B-stability. B-stable PSRs encompasses the vast majority of known tractable subclasses such as weakly re- vealing POMDPs, low-rank future-sufficient POMDPs, decodable POMDPs, and regular PSRs. Next, we show that any B-stable PSR can be learned with polyno- mial samples in relevant problem parameters. When instantiated in the afore- mentioned subclasses, our sample complexities improve substantially over the current best ones. Finally, our results are achieved by three algorithms simultane- ously: Optimistic Maximum Likelihood Estimation, Estimation-to -o-eeiiiooss,, and Model-Based Optimistic Posterior Sampling. The latter two algorithms are new for sample-efficient learning of POMDPs/PSRs. We additionally design variant of the iilimation-to-ecciiionn algorithm to perform sample-efficient all-policy model estimation for B-stable PSRs, which also yields guarantees for reward-free learning as an implication.
INTRODUCTION
Partially Observable Reinforcement Learning (RI.)-herre agents can only observe partial infor- mation about the true underlying state of the system-is ubiquitous in real-world applications of RL such as robotics (Akkaya et al., 2019), strategic games (Brown Sandholm, 2018; Vinyals et al., 2019; Berner et al., 2019), economic simulation (Zheng et al., 2020), and so Partially observable RL defies standard efficient approaches for learning and planning in the fully observ- able case (e.g. those based on dynamical programming) due to the non-Markovian nature of the observations (Jaakkola et al., 1994), and has been a hard challenge for RL research.
Theoretically, it is well-established that Icarning in partial observable RL is statistically hard in the worst case-In the standard setting of Partially Observable Markov Decision Processes (POMDPs), learning near-optimal policy has exponential sample complexity lower bound in the horizon length (Mossel & Roch, 2005; Krishnamurthy et al., 2016), which in stark contrast to fully observ- able MDPs where polynomial sample complexity possible (Kearns & Singh, 2002; Jaksch al.,
$ Equal contribution.

---

Published as a conference paper at ICLR 2023
Table 1: Comparisons sample complexities for learning an near-optimal policy POMDPs and PSRs. Detinitions of the problem parameters can be found in Section 3.2. The last three rows refer to the m-sttep versions of the problem classes (e.g. the third row considers sestep Ore--revealing POMDPs). The current best results within the last four rows are due to Zhan al. (2022); Liu et al. (2022a); Wang et al. (2022); Efroni al. (2022) respectively'... All results are scaled to the setting with total reward in [0, 1].
Problem Class
Current Best
Ours
Ag-Stable PSR
Ô (desk AUa H log.No No. Ag/e²)
Opurtegular PSR
Ô (dosRAU 3 log Ne/ (cppn=))
revelllg labular POMDP
Ô (st A0m 11th log, No/ (o/((e/)e)))
Ö AT 1f log, No./ / (a
u-futurc-suff. rank-deass POMDP
Ô (drmms A A H (log,
No) .' /E")
(derama pm H log No v² /s")
decodable rank-drans POMDP
Ô (deaae 112 log No/=²)
Ô (dears TM 112 log No//²"
2010: Azar et al., 2017). A later line of work identifies various additional structural conditions or alternative learning goals that enable sample-efficient learning, such as reactiveness (Jiang et al., 2017), revealing conditions (Jin et al., 2020a; Liu et al., 2022c; Cai et al., 2022; Wang et al., 2022), decodability (Du et al., 2019; Efroni et al., 2022), and learning memoryless or short-memory poli- cies (Azizzadenesheli et al., 2018; Uchara et al., 2022b).
Despite these progresses, research on sample-efficient partially observable RL is still at an early stage, with several important questions remaining open. First, to a large extent, existing tractable structural conditions are mostly identified and analyzed in case-by-case manner and lack a more unified understanding. This question has just started to be tackled in the very recent work of Zhan al. (2022), who show that sample-efficient learning is possible in the more general setting of Predictive State Representations (PSRs) (Littman & Sutton, 2001)-which include POMDPs as a special case-with a certain regularity condition. However, their regularity condition is defined in terms of additional quantities (such as "core matrices") not directly encoded in the definition of PSRs, which makes it unnatural in many known examples and unable to subsume important tractable problems such as decodable POMDPs.
Second, even in known sample-efficient problems such as revealing POMDPs (Jin et al., 2020c; Liu et al., 2022a), existing sample complexities involve large polynomial factors of relevant problem parameters that are likely far from sharp. Third, relatively few principles are known for designing sample-efficient algorithms in POMDPs/PSRRs such as spectral or tensor-based approaches (Hsu ct al., 2012; Azizzadenesheli et al., 2016; Jin et al., 2020c), maximum likelihood or density esti- mation (Liu et al., 2022a; Wang et al., 2022; Zhan et al., 2022), or learning short-memory poli- cies (Efroni et al., 2022; Uehara et al., 2022b). This contrasts with fully observable RL where the space of sample- sample-efficiett algorithms is much more diverse (Agarwal et al., 2019). It is important question whether we can expand the space of algorithms for partially observable RL.
This paper advances all three aspects above for partially observable RI. We define B-stablility, natural and general structural condition for PSRs, and design sharp algorithms for learning any B-stable PSR sample-efficiently. Our contributions can be summarized as follows.
We identify new structural condition for PSRs termed B-stability, which simply requires its B- representation (or observable operators) be bounded in suitable operator norm (Section 3.1). B-stable PSRs subsume most known tractable subclasses such as revealing POMDPs, decodable POMDPs, low-rank future-sufficien POMDPs, and regular PSRs (Section 3.2).
We show that B-stable PSRs can be learned sample-efficiently by three algorithms simultane- ously with sharp sample complexities (Section 4): Optimistic Maximum Likelihood Estimation (OMLE), Explorative Estimation-to tosioon-t--eeiiiosss (EXPLORATIVE E2D), and based Opti- mistic Posterior Sampling (MOPS). To our best knowledge, the latter two algorithms are first shown to be sample-efficient in partially observable RI.
Our sample complexities improve substantially over the current best when instantiated in both regular PSRs (Section 4.1) and known tractable subclasses of POMDPs (Section 5). For ex- ample, for m-step Creev reveallng POMDPs with S latent states, our algorithms find an E near- optimal policy within δ A Log.N((afe
episodes of play (with S² replaced by
For s-ffture-sufficien POMDPs, Wang et al. (2022)'s sample complexity depends on 7, which is addi- tional l-step post-sufficiency parameter that they require.
2

---

Published as a conference paper at ICLR 2023
SA if measured in B-stability), which improves significantly over the current best result of ① (5+) 46m-4 N/ N((ofeu=))) A summary of such comparisons is presented Table 1.
As a variant of the E2D algorithm, we design the ALL-POLICY MODEL-ESTIMATION E2D algo- rithm that achieves sample-efficien. all-policy model estimation- and as an application, reward- free learning- for B-stable PSRs (Section 4.2 & Appendix H.2).
Technically, our three algorithms rely on unified sharp analysis of B-stable PSRs that involves a careful error decomposition in terms of its B-representation, along with a new generalized fy-type Eluder argument, which may be of future interest (Appendix B).
Related work Our work is closely related to the long lines of work on sample-efiiciet learning of fully/partially observable RL (with/without function approximation), especially the lines of work on POMDPs and PSRs. We review these related works in Appendix A due to the space limit.
2 PRELIMINARIES
Sequential decision processes with observations An episodic sequential decision process is spec- ified by a tuple H,, O, A, [ where H Z is the horizon length; O is the observa- tion space with [0] O: A is the action space with |A| = A: P specifies the transition dynam- ies, such that the initial observation follows 01 ~ Po(.) E A(O), and given the history Th :=
(o), 01,'. , oh, a₂) up to step h, the observation follows 0h-1 ~ P(-(T))) ry O x A - [0, 1] is the reward function at h-th step, which we assume is a known deterministic function of (on, an).
A policy (TT (O A)^ x O - | is collection of H functions. At step h [M]]
an agent running policy æ observes the observation on and takes action an ~ (- o5.) E ((A)
based on the history (T) (01, (01,a1,.... ai...... 0h-1, a4-1, 0%). The agent then receives their reward
To,on, an), and the environment generates the next observation 0 ~ IP(IIT.) based on Th =
(01, 01,''.. .h; On)) The episode terminates immediately after the dummy observation 0H+1
Odum is generated. We use II to denote the set of all deterministic policies, and identify ATII as both the set of all policies and all distributions over deterministic policies interchangeably. For any (h, Th). let P(Tx)) := It gh P(oz/ (Tw-1), π (TT)) := I IN Th (axe Tw- ow and let (TT(T)) := P(Tx) x (TT) denote the probability of observing тh (for the first h steps) when executing т. The value of a policy is defined as the expected cumulative reward V(z) := ET [>>L (o(on, an)].
We assume that _ (h (o,,,, aa) almost surely for any policy m.
POMDPs A Partially Observable Markov Decision Process (POMDP) is special sequential de- cision process whose transition dynamics are governed by latent states. An episodic POMDP is specified by tuple S,,,OO,A, (TT))
! 1-1 (0x) h- (rn) 11), where S is the latent state space A(O) is the emission dynamics at step h (which we identify as an A - A(S) is the transition dynamics over the latent states (which we identify as transition matrices Tx(-I.,a) E SxS for each a E A), and μ1 E ASS) specifies the distribution of initial state. each step h, given latent state 8h (which the agent cannot observe), the system emits observation O₁ ~ O2, (-Iss), receives action on E A from the agent, emits the reward rh (oR, as) and then transits the next latent state 8h41 Ta ax) in Markov fashion. Note that a POMDP can be fully described by the parameter 0 == (T, (1)..
1
with [S] S. C (++-) emission matrix C E RO .-).-) S
2.1 PREDICTIVE STATE REPRESENTATIONS
We consider Predictive State Representations (PSRs) (Littman & Sutton, 2001), a broader class of sequential decision processes that generalize POMDPs by removing the explicit assumption of latent states, but still requiring the system dynamics to be described succinctly by a core test set.
PSR, core test sets, and predictive states A test t is sequence of future observations and actions (i.e. E I := Uwez., OW AW-1) For some test t, = (о)>भ -- am*+W-2) with length W > 1, we define the probability of test tg. being successful conditioned on (reachable) history Th-1 as PP(t (Ttx) := Poo -1 Th-1; do -2),, i..., the probability of observing 0h-h+W-1 the agent deterministicalyy executes actions aish+ conditioned on history Th-1- We follow the convention that, if TPx (7h-1) 0 for any म, then P( 0.
3

---

Published as a conference paper at ICLR 2023
Definition 1 (PSR, core test sets, and predictive states). For any h [H] we say set Ub, I a core test set at step h if the following holds: For any W E Zzi, any possible future (i.e., test) tn (Ohsh -1, ah:h+ W OW AW there exists a vector bt,,, R44. such that
P(ta/Ta-1) = (be (P(())
1 :- (0 A)
(1)
We refer to the vector q ((Th-1) == [PPt)|T- as the predictive state at step h (with convention q(Th-1) = ih-1
Th-1 1 is not reachable), and qu == [P(t)) as the initial predictive state. A (linear)
PSR is a sequential decision process equipped with a core test set {L4 be().
The predictive state q(7h-1) E R44h in PSR acts like "latent state" that governs the transition F(-Im-1)) through the linear structure (I). We define UA.A == {a (o, a) E Un. for some o E Uwex+ O as the set of action sequences (possibly including an empty sequence) in Uh. with Ua:= maX | Further define UH+1 := {Odum) for notational simplicity. Throughout the paper, we assume the core test sets (44 [e[ are known and the same within the PSR model class.
B-representation We define the B-representation of PSR, a standard notion for PSRs (also known as the observable operators (Jaeger, 2000)).
Definition 2 (B-representation). A B-representation of a PSR with core test set (Ux) is a set of matrices² {B,,, an) E R i1 (1*31,, )h.on,an. qo E RM4 such that for any 0 < h & H, policy π, history = (01sh, a1sh) E Th and core test f4+11 = (on+1<h quantity P( (h: 11+1), iee. the probability of observinn 01: upon taking actions 01sh+ 1ash+W-11 admits the decomposition
b.+1:h+-1 E Uh+1. the
P( tR+1) P(on
wdw(((/.+0(www)) o (TA qo
where C1 B.lia is the indicator vector of f1+1 E Uh+1. and
(T)(TT) == BB,(o,, a; BB-)) an-1) (..-))..BBB(....
It is a standard result (see e.g. Thon & Jaeger (2015)) that any PSR admits a B-representation, and the converse also holds-any any sequential decision process admitting a B-representation (2h ((e))e(z) is PSR with core test set (24) ke[r]] (Proposition D.1). However, the B-representation of given PSR may not be unique. We also remark that the B-representation is used the structural conditions and theoretical analyses only, and will not be explicitly used in our algorithms.
test sets
Rank An important complexity measure of PSR is its PSR rank (henceforth also "rank").
Definition 3 (PSR rank). Given PSR, its PSR rank is defined as desR == maXhe[in] rank Di), where Dj, = [q [q(TT)]rAATT E 11 is the matrix formed by predictive states at step h e [H].
The PSR rank measures the inherent dimension" of the space of predictive state vectors, which always admits the upper bound desR & maxke[[]] (4), but may in addition be much smaller.
POMDPs as low-rank PSRs As primary example. all POMDPs are PSRs with rank at most S (Zhan et al., 2022, Lemma 2). First, Definition can be satisfied trivially by choos- ( [h+W-1)] as the set of all possible tests, and b =
ing Un = Uisw=HHhH4 {(on, Ch...., et, Rdth indicator vectors. For concrete subclasses of POMDPs, we will consider alter- native choices of (M)))e(H)) with much smaller cardinalities than this default choice. Second, compute the rank (Definition 3), note that by the latent state structure of POMDPs, have for any (h, Th t1+1). Therefore, the associated ma- trix Dj [P( (T)) Jell TT always has the following decomposition:
((tx+1/Th) S1 1))t:ssss1111(sssss.
D [P 1s) ( )84. [TP(s (hh) (1 (
which implies that desR [ rank( S.
Learning goal We consider the standard PAC learning setting, where we are given a model class of PSRs θ and interact with ground truth model 0* E O. Note that, we do not put fur- ther restrictions on the parametrization, this setting allows any general function approximation for
This definition can he generalized to continuous Un, where Ba an) C(T (Unn), I. (U++1)) are linear operators instead of (fiite-dimensional) matrices.
"This definition using matrix ranks may be further relaxed, e.g. by considering the effective dimension.
4

---

Published as a conference paper at ICLR 2023
the model class. For any model class θ define its (optimistic) covering number Ne for > 0 in Definition C.4. Let (T(T) denote the value function of policy æ under model 8, and To == arg maXzen Vo(T) denote the optimal policy of model 0. The goal is to learn policy â that achieves small suboptimality V. Vg. (+) within as few episodes of play as possible, where V. Vo- (TT=).. We refer algorithm as sample-efficient if it finds e-near optimal policy within poly(relevant problem parameters, 1/e)* episodes of play.
PSRS WITH B-STABILITY
We begin by proposing natural and general structural condition for PSR called B-stability (or also stability). We show that B-stable PSRs encompass and generalize a variety of existing tractable POMDPs and PSRs, and can be learned sample-efficienty as we show in the sequel.
3.1 THE B-STABILITY CONDITION
For any PSR with associated B-representation, we define its B-operators (Bushhhem as
BиΛ R g(OxA)"=>*)
[BHa(THeH) () 611.
Operator Виt maps any predictive state q q(Th-1) at step h to the vector B = (P (T-))) which governs the probability of transitioning all possible futures, by proper- ties of the B B-representation (cf. (17) & Corollary D.2). For each h E [H] we equip the image space of Brah with the I--orm:: For a vector indexed by Th. E (O A) -h+1, we define
| = max; Z...EE T ((T:.)) [b(TT:H]]
(3)
where the maximization is over all policies मे starting from step / (ignoring the history Th-1) and o (Th.B) - Ry Saraaloo low, -1) We further equip the domain F.4. with a fused-norm le. which defined as the maximum of (1, -nom and 11' no'm::
Iall = mlx[[1/ll,22111/// Ilall:
(4)
Ial 1.2 (Eaettan (Eorooajeu, 19(0, 3)??
aaln == max Exsth #() [q((),
(5)
where Un == (t Un $t' e Uh such that is prefix of t'}.
We now define the B-stability condition, which simply requires the B-operators ( he(m]] to have bounded operator norms from the fused-norm to the NT-orm.
Definition 4 (B (B-stability). PSR is B-stable with parameter Ag (henceforth also Ag-stable) if it admits B- B-representation with associated B-operators (B such that
sup max he[H] !q/+=1 |B & AB.
(6)
When using the B-stability condition, we will often take q= qi - to be the dif- ference between two predictive states at step Intuitively, Definition 4 requires that the propagated II-norm error [| 42) n to be controlled by the original fused-norm error q 92ll
The fused-norm ||-1,, is equivalent the vector 1-norm up to A
1/2 1/22 -actor (despite its seemingly [ql 1 & |Ma,a 1/2 ||]|= (Lemma D.6), and thus assuming relaxed A will also enable sample-efficien learning of PSRs. However, we consider the fused-norm in order to obtain the sharpest possible sample complexity guarantees. Finally, all of our theoretical results still hold under more relaxed (though less intuitive) weak B-stability condition (Definition D.4), with the same sample complexity guarantees. (See also the additional discussions in Appendix D.2.)
involved formj: We have |///
condition max 1
*For the m-step versions of our structural conditions, we allow an exponential dependence on m hut not H. Such dependence is necessary, e.g. in m-step decodable POMDPs (Efroni et al., 2022). 'The norm is in general semi-norm.
5

---

Published as a conference paper at ICLR 2023
3.2 RELATION WITH KNOWN SAMPLE- SUBCLASSES
We show that the B-stability condition encompasses many known structural conditions of PSRs and POMDPs that enable sample-efficient learning. Throughout, for a matrix A e Rmx", we define its operator norm
Allp- == max]jal lp = ||
and use || ||, == -I| || p- for shorthand.
Weakly revealing POMDPs (Jin et al., 2020a; Liu et al., 2022a) a subclass of POMDPs that assumes the current latent state be probabilistically inferred from the next emissions.
Example (Multi-step weakly revealing POMDPs), A POMDP is called m-step Orev-Weakly re- vealing (henceforth also "Crev- revealing") with Orev < if [H--m [M 12-2 & o where for h E [H| - m + 11. Mn E OR A is the m-step emission-action matrix at step h, defined as (o.)), :- P P(onchtm-1 o/8h 8, am a), V(o, O AA--11, 8
e S. (7)
We show that any m-step Grev- weakly revealing POMDP is a Ag-stable PSR with core test sets Ur -Ox x m)) x O, and AB & VS (Proposition D.7). A similar result holds for the & variant of the revealing condition (see Appendix 1.3.1). )
When the transition matrix T the POMDP has a low rank structure, Wang et al. (2022) show that a subspace- aware generalization of the f-rrevealing condition the future-sufficiency condition- enables sample-efficient learning of POMDPs with possibly enormous state/observation spaces (see also Cai et al. (2022)). We consider the following generalized definition of anture-sufficiency.
Example 6 (Low-rank cuture-sufficias POMDPs). We say a POMDP has transition rank dirans ffr each & [H - 11, the transition kernel of the POMDP has rank at most derans (i.e. max, rank(TT)) & derans). It is clear that low-rank POMDPs with transition rank dranns has PSR rank dpsR & dirans-
A transition rank-durans (henceforth rank-derans) POMDP is called m-step s-futtue--ufficient with 1, if for h [H- 1]. there exists Mf, RSX such that MI, MI, Tn-1- = Th-1 and MM, |1-1 & v, where M,, is the m-step emission-action matrix defined in (7).
We show that any m-step v-future sufficient rank-derams POMDP a B-stable PSR with core test sets Un = (O x mij x O, dpsR & derans, and Ar & Vmmm1y (Proposition D.12). O
Decodable POMDPs (Efroni al., 2022), multi-step generalization of Block MDPs (Du al., 2019), assumes the current latent state can be perfectly decoded from the recent m observations.
Example 7 (Multi-step decodable POMDPs). A POMDP is called m-step decodable if {0% such that for every reachable trajectory (81, 01, 01, ... -h,, 0n) we have 8h. = 0% (zn), where 2n = (0m(k). Oma());"" ,0)) and m(h)
there exists (unknown) decoders o"
max(h - m + 1, We show that any m-step decodable POMDP is a B-stable PSR with core test sets U4, = (O x A) miimmm-11,1 1,M1- x O and Ag (Proposition D.17). +
Finally, Zhan al. (2022) define the following regularity condition for general PSRs.
Example (Regular PSRs). A PSR is called regular if for all h [H] there exists a core matrix K₁ E Bl Krank(Ds), which is a column-wise sub-matrix of Dj, such that rank Kn) = rank( Dr)) and maX |K] 1- & Orpsr- We show that any Op--regular PSR is Ag-stable with Ag VU (Proposition D.18). O
We emphasize that B-stability not only encompasses Opsr regullaty,, but is also strictly more expres- sive. For example, decodable POMDPs are not Opar-regular unless with additional assumptions on K (Zhan et al., 2022, Section 6.5), whereas they are B-stable with Ag = 1 (Example 7). Also, any Crev-revealing POMDP is deaa-regullrr with some opst < oc, but with apst potentially not poly- nomially bounded by and (and other problem parameters) due to the restriction of K₁, being a column-wise sub-matrix of Da: By contrast it is B-stable with AB & /5.m (Example 5).
4 LEARNING B-STABLE PSRS
In this section, we show that B-stable PSRs can be learned cample-efficient achieved by three model-based algorithms simultaneously. We instantiate our results to POMDP' Section 5.
It is straightforward to generalize this example to the case when S and O are infinite by replacing vectors with L, integrable functions, and matrices with linear operators hetween these spaces.

---

Published as a conference paper at ICLR 2023
Algorithm OPTIMISTIC MAXIMUM LIKELIHIOD ESTIMATION (OMLE)
1: Input: Model class θ parameter / >> 0.
2: Initialize: O² , = ().
3: for iteration k 1,.... K do
4: Set (0%, ) = arg maX ot VO(T).
5: for f 0, ..... H do
6: Set exploration policy <xpe == T on Uni o1+1 Unif(MA,(+1)
7: Execute o.. exp to collect trajectory tkih, and add (Th, Rhih) into D.
8: Update confidence set
g
+
D (DDT)DD log Pg 2 maX (EDD) log -3]
Output: nout
Unif((==*) Re((K)
4.1 OPTIMISTIC MAXIMUM LIKELIHOOD ESTIMATION (OMLE)
The OMLE algorithm is proposed by Liu et al. (2022a) for learning revealing POMDPs and adapted" by Zhan et al. (2022) for learning regular PSRs, achieving polynomial sample complex- ity (in relevant problem parameters) in both cases. We show that OMLE works under the broader condition of B-stability, with significantly improved sample complexities.
Algorithm and theoretical guarantee The OMLE algorithm (described in Algorithm 1) takes in a class of PSRs θ, and performs two main steps in each iteration E [K]:
1. (Optimism) Construct a confidence set O S θ, which is superlevel set of the log- ligllikl of all trajectories within dataset DD (Line 8). The policy T² is then chosen as the greedy policy with respect to the most optimistic model within @* (Line 4).
2. (Data collection) Execute exploration policies (* "=fh,exp0=hhssH-1 where each "hes is defined via the Oh notation as follows: Follow z² for the first 1 steps, take a uniform action (ni at step h, take an action sequence sampled from (ni at step h + 1, and behave arbitrarily afterwards (Line 6). All collected trajectories are then added into D (Line 7).
Intuitively, the concatenation of the current policy x² with (Aif(A) and Unif((AA,++11 in Step 2 above is designed according to the structure of PSRs to foster exploration.
Theorem 9 (Guarantee of OMLE). Suppose every 0 θ is Ag-stable (Definition 4) and the true model 0* E è has rank dpsR & Then, choosing 3 = C (oggN(( for some absolute constant C > O, with probability at least 1 d, Algorithm outputs a policy Tout AlII such that V. - Vo- (Rott) & E, as long as the number of episodes
T KH > O (dAU, log(Ne Ag/62).
(8)
where: 1 log (1 + K AARRR) with Rg == max, (1, max [ull, Σ... a)
Theorem 9 shows that OMLE is sample-efficient for any B-stable PSRs- broader class than in existing results for the same algorithm (Liu et al., 2022a; Zhan et al., 2022)-022ii with much sharper sample complexities than existing work when instantiated to their settings. Importantly, we achieve the first polynomial sample complexity that scales with A dependence B-stability parameter (or regularity parameters alike*). Instantiating to Operrrguular PSRs, using AB & VUAopst (Exam- ple 8), our result implies a ÖddAU? log Na sample complexity (ignoring and 29). the Ö(d A (ag( result of Zhan al. (2022).
This improves significantly
Nameed CRANE (Zhan et al., 2022).
'Uehara et al. (2022b) achieves an A - dependence for learning the optimal memory-M policy in (their) reveealinn POMDPs, which is however easier than learning the globally optimal policy considered here. 'The lactfactor i contains additional parameter Re that is not always controlled by As; this quantity also appears in Zhan et al. (2022); Liu et al. (2022b) but is controlled by their apr yr respectively. Nevertheless, for all of our POMDP instantiations, Rs is polynomially bounded by other problem parameters so that is mild lag-foctor. Further, our algorithm EXPLLORATIVE E2D avoids the dependence Rs (Theorem 10).
7

---

Published as a conference paper at ICLR 2023
Overview of techniques The proof of Theorem 9 (deferred to Appendix G) builds upon sharp analysis for B-stable PSRs: 1) We use a more delicate choice of norm for bounding the errors (in the B operators) yielded from performance difference arguments; 2) We develop generalized ty-type Eluder argument that is sharper than the & Eluuder argument of Liu et al. (2022a); Zhan et al. (2022). A more detailed overview of techniques is presented in Appendix B.
4.2 EXPLORATIVE ESTIMATION TO--ONNSIOO-EIIION (EXPLORATIVE E2D)
Estimation- To- fo-Deeissions (F2DD is a general model-based algorithm that is sample-efficient for any interactive decision making problem (including MDPs) with a bounded Decision-Fstimation Co- efficient (DEC), established in the DEC framework by Foster et al. (2021). However, the E2D algorithm has not been instantiated on POMDPs/PSRs. We show that B-stable PSRs admit a sharp DEC bound, and thus can be learned sample-efficiently by suitable E2D algorithm.
EDEC EXPLORATIVE E2D algorithm We consider the Explorative DEC (EDEC) proposed in the recent work of Chen al. (2022), which for PSR class θ is defined
edec, (9)
inf sup, Ex-pone Pont [Vo(Ta) - Vo(T)] -YB, -Pop Peop B (+) Peop EXIII BEB
sup
D (PT (PD.PT))
((T)
where DP 1P3) == Enn (P7 1T2) ( denotes the squared Hellinger distance be- tween 17 and g. Intuitively, the EDEC measures the optimal trade-off on model class between gaining information by "exploration policy" Pexp and achieving near-optimality by "out- put policy" π ~ Pout- Chen et al. (2022) further design the EXPLORATIVE E2D algorithm, general model-based RI. algorithm with sample complexity scaling with the EDEC.
We sketch the EXPLORATIVE E2D algorithm for a PSR class θ as follows (full description in Al- gorithm 2): In each episode t [T]. we maintain distribution μ² e A(O)) over optimistic cover (P. On) with radius 1/ 1/T (ef. Definition C.4), which we use to compute two policy distributions (Pexp:Pon by minimizing the following risk:
arg min Woor: Pexp) (oons:Pex))AAAT dE
sup ET (Vo(TT) Vo(m)] - > Egt u [DR (IPT Pg.)].
Then, we sample policy n² P'espy execute n² and collect trajectory rf, and update the model distri- bution μ' using Tempered Aggregation scheme, which performs Hedge update with initialization 4² = Unif( Op). the log-likelihode loss with P7 (.) denoting the optimistic likelihood associated with model A e Ou and policy n² (cf. Definition C.4), and learning rate n 1/2:
*+ (0) xe (0) exp (n log Pan (T9).
After I' episodes, we output the average policy nout := $ ΣT Pont-
Theoretical guarantee We provide a sharp bound on the EDEC for B-stable PSRs, which implies that EXPLORATIVE E2D can also learn them sample-efficient efficiently.
Theorem 10 (Bound on EDEC & Guarantee of EXPLORATIVE E2D). Suppose θ is PSR class
with the same core test sets (4n [e[] and each 0 θ admits a B- B-representation that is Ag-stable and has PSR rank at most d. Then we have
edec,, (0) & O(dAUAAZH*/))
As corollary, with probability at least 1 - 8, Algorithm 2 outputs policy Rout E A(II) such that V. Vo (Rout) & E, as long as the number of episodes
T = OdAU logg
The sample complexity (9) matches OMLE (Theorem 9) and has a slight advantage in avoiding the log factor / therein. In return, the in Theorem 10 needs to upper bound the PSR rank of all models in O whereas the d in Theorem 9 only needs to upper bound the rank of the true model 6* We also remark that EXPLORATIVE E2D explicitly requires an optimistic covering of as an input to the algorithm, which may be another disadvantage compared OMLE (which uses optimistic covering
8

---

Published as a conference paper at ICLR 2023
implicitly in the analyses only). The proof of Theorem 10 (in Appendix 1.2) relies on mostly the same key steps as for analyzing the OMLE algorithm (overview in Appendix B).
Reward-free learning & All-policy model estimation Chen al. (2022) also de- sign the ALL-POLICY MODEL- ESTIMATION E2D algorithm for reward-free RL (Jin et al., 2020b) and (a harder related task) all-policy model estimation, with sample complexity scaling with the All-policy Model-estimation DEC (AMDEC) of the model class. We show that for B-stable PSRs, the AMDEC (43) can be upper bounded similar to the EDEC, and thus ALL-POLICY MODEL- ESTIMATION E2D (Algorithm 3) can be used to learn stable PSRs in a reward-free manner (Theo- rem H.4 & Appendix H.2).
Extension:
4.3 MODEL-BASED OPTIMISTIC POSTERIOR SAMPLING (MOPS)
Finally, we show that MOPS general model-based algorithm originally proposed for MDPs by Agarwal & Zhang (2022) can learn B-stable PSRs with the same sample complexity as OMLE and EXPLOR ATIVE E2D modulo minor differences (Theorem H.6 & Appendix H.3). The analysis is parallel that of EXPLORATIVE E2D, building on insights from Chen et al. (2022).
5 EXAMPLES: SAMPLE COMPLEXITY OF LEARNING POMDPS
We illustrate the sample complexity of OMLE and EXPLORATIVE E2D given in Theorem 9 & 10 (with MOPS giving similar results) for learning an e near-optimal policy in the tractable POMDP subclasses presented in Section 3.2, and compare with existing results. (Obtaining the rates for OMLE also require bounds on the factor Rg, which can be found in Appendix D.)
Weakly revealing tabular POMDPs m-step Brev-Weakly revealing tabular POMDPs are B-stable PSRs with Äg vSorev dPsR & S. and UA A (Example 5). Therefore, both Theo- rem 9 & 10 achieve sample complexity (S5 ATh H loglloo////ooo Ne/(( This improves substamtially over the current best result Ö(5* A6m-4 log Ne/ (a = =))) of Liu et al. (2022a, Theorem 24). For tabular POMDPs, we further have log.ee Ö (H SO)).
Low-rank future-sufficient POMDPs m-step
rank- POMDPs are B-stable PSRs with Ag & VUAV, desR dirans, and UA = A (Example 6). Therefore, Theorem & 10 achieve sample complexity O(drrans A2m H log No =²/=²). This improves substantially over the A + (log No) v²>2/6²) achieved by Wang et al. (2022), which requires an extra 1-step t-past-sufficieng assumption that we do not require.
Decodable low-rank POMDPs m-step decodable POMDPs with transition rank derans are B-stable PSRs with AB = 1, dpsR & dtranss and UA = A (Example 7). Therefore, Theorem 9 & 10 achieve sample complexity Ö ((drrans H2 log No/s/// Compared with the sample complexity up- per bound Adderans 2 log. Ng//²) of Efroni et al. (2022), the only difference is that their cov- ering number Ng is for the value class while We is for the model class. However, this difference nontrivial the model class admits a much smaller covering number than the value class re- quired for a concrete problem. For example, for tabular decodable POMDPs, using drrans & S and Noe & (S A+ SO)). we achieve the first O(A'' S, sample complexity, which resolves the open question of Efroni et al. (2022).
Besides the above, our results be further instantiated latent MDPs (Kwon et al. (2021), special case of revealing POMDPs) and linear POMDPs (Cai et al., 2022) and improve over existing results, which we present in Appendix D.3.2 & D.3.4.
6 CONCLUSION
This paper proposes B-stability-a new structural condition for PSRs that encompasses most of the known tractable partially observable RL problems- -nd designs algorithms for learning B-stable PSRs with sharp sample complexities. We believe work opens up many interesting questions, such as the computational efficiency of our algorithms,, alternative (c.g. model-free) approaches for learning B-stable PSRs, extensions to multi-agent settings.

---

Published as a conference paper at ICLR 2023
REFERENCES
Alckh Agarwal and Tong Zhang. Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. arXiv preprint arXiv:2206. 226,09920600669, 2022.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle. WA, USA, Tech. Rep, pp. 10-4, 2019.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural com- plexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20107 2020.
Igge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's 's cube with robot hand. arXiv preprint 11X1v:1910.07113. 2019.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learn- ing of pomdps using spectral methods. In Conference on Learning Theory, pp. 193-256, PMLR, 2016.
Kamyar Azizzadenesheli, Yisong Yue, and Animashree Anandkumar. Policy gradient in partially observable environments: Approximation and convergence. arXiv preprint arXiv:1810.07900, 2018.
Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu. Efficient Ø-regret minimization in extensive-form games via online mirror descent. arXiv preprint 2tti::2205./5294 2022a.
Yu Bai, Chi Jin, Song Mei, and Tiancheng Yu. Near-optimal learning extensive-form games with imperfect information. arXiv preprint wwxxi:2202.0/752: 2022b.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung. Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 19/2.06680 2019.
Byron Boots, Sajid M Siddiqi, and Geoffrey J Gordon. Closing the learning planeilllnnngggnn loop with predictive state representations. The International Journal of Robotics Research, 30(7):954-90) 2011.
Byron Boots, Geoffrey Gordon, and Arthur Gretton. Hilbert space embeddings of predictive state representations. arXiv preprint 1rXiv:1309.6811 2013.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-424 2018.
Dima Burago, Michel De Rougemont, and Anatol Slissenko. On the complexity of partially ob-
served markov decision processes. Theoretical Computer Science, 157(2):111-183, 1996.
Qi Cai, Zhuoran Yang, and Zhaoran Wang. Reinforcement learning from partial observation: Linear function approximation with provable sample efficiency. In International Conference on Machine Learning, pp. 2485-2522 PMLR, 2022.
Fan Chen, Song Mei, and Yu Bai. Unified algorithms for rl with decision--stimation coefficients: No-regret, pac, and reward-free learning. arXiv preprint arXiv:2209 2022. URL https: org/ abaaaasss/220 /209. 11745v2.
Fan Chen, Huan Wang, Caiming Xiong, Song Mei, and Yu Bai. Lower bounds for learning in revealing pomdps. arXiv preprint arXiv:2302.01333, 2023.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient ıl with rich observations via latent state decoding. In International Conference Machine Learning, pp. 1665-1674. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2023
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in In International Conference on Machine Learning, pp. 2826-28366 PMLR, 2021.
Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforcement learning with a short-term memory. arXiv preprint arXiv:2202.03983, 2022.
Eyal Evenn-Dar Sham M Kakade, and Yishay Mansour. Reinforcement learning in pomdps without resets. 2005.
Gabriele Farina, Robin Schmucker, and Tuomas Sandholm. Bandit linear optimization for sequential decision making and extensive-fore form games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp- 5372-5380, 2021.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint 1:Xiv:2112.134933 2021.
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in observable pomdps, without com- putationally intractable oracles. arXiv preprint arXiv:2206.03444 2022a.
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Planning in observable pomdps in quasipoly- nomial time. arXiv preprint arXiv:2201.04735 2022b.
Yuri Grinberg, Hossein Aboutalebi, Melanie Lyman-Abren Abramovitch, Borja Balle, and Doina Precup. Learning predictive state representations from non- non-uniform sampling. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A pac rl algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pp. 110.518. PMLR, 2016.
William Hamilton, Mahdi Milani Fard, and Joelle Pineau. Efficient learning and planning with compressed predictive states. The Journal of Machine Learning Research, 15(1):3395-3499 2014.
Ahmed Hefny, Carlton Downey, and Geoffrey J Gordon. Supervised learning for dynamical system learning. Advances in neural information processing systems, 28, 2015.
Daniel Hsu, Sham M Kakade, and Tong Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 78(5):1460-15 1480, 2012.
Tommi Jaakkola, Satinder Singh, and Michael Jordan. Reinforcement learning algorithm for par- tially observable markov decision problems. Advances in neural information processing systems, 7, 1994.
Herbert Jaeger. Observable operator models for discrete stochastic time series. Neural computation, 127611177 2000.
Mehdi Jafarnia Jahromi, Rahul Jain, and Ashutosh Nayyar. Online learning for unknown partially observable mdps. In International Conference on Artificial Intelligence and Statistics, pp. 1712- 1732. PMLR, 2022.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1563-1600 2010. URL http:// jmlr. httgg//ppexs//ll///aeeee
html.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire, Con- textual decision processes with low bellman rank are pac-leamable. In International Conference on Machine Learning, pp. 1713- PMLR, 2017.
Nan Jiang, Alex Kulesza, and Satinder Singh. Completing state representations using spectral learn- ing. Advances in Neural Information Processing Systems, 31, 2018.
Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete pomdps. Advances in Neural Information Processing Systems, 33: 18530-18539, 2020a.
11

---

Published as a conference paper at ICLR 2023
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870 4879. PMLR. 2020b.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 1137.2143.
PMLR, 2020c.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406 1134406-1448,,. 13418. 2021.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine learning, 49(2)2099-232, 2002.
Michael Kearns, Yishay Mansour, and Andrew Ng. Approximate planning in large pomdps via reusable trajectories. Advances in Neural Information Processing Systems, 12, 1999.
Tadashi Kozuno, Pierre Ménard, Remi Munos, and Michal Valko. Learning in two-player zero- sum partially observable markov games with perfect recall. Advances in Neural Information Processing Systems, 34:1 1987-11998, 2021.
Akshay Krishnamurthy, Alckh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016.
HW Kuhn. Extensive games and the problem of information. kuhn hw, tucker aw, eds., contributions to the theory of games, vol ii, 193-216, 1953.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Regret guarantees and lower bound. Advances in Neural Information Processing Systems, 34: 24523-24534, 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Michael Littman and Richard S Sutton. Predictive representations of state. Advances in neural information processing systems, 14, 2001.
Michael L Littman. Memoryless policies: Theoretical limitations and practical results. In From
Animals to Animats 3: Proceedings of the third international conference simalation adaptive
behavior, volume 3, pp. 238. MIT Press Cambridge, MA, USA, 1994.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforce- ment learning not scary? arXiv preprint arXiv:2204. 08967, 2022a.
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle-a a generic model-based algorithm for partially observable sequential decision making. arXiv preprint arXiv:2209. 14997, 2022b.
Qinghua Liu, Csaba Szepesvári, and Chi Jin. Sample-efficient reinforcement learning of partially observable markov games. arXiv preprint arXiv:2206.01315, 2022c.
Christopher Lusena, Judy Goldsmith, and Martin Mundhenk. Nonapproximability results for par- tially observable markov decision processes. Journal of artificial intelligence research, 14:83- 103, 2001.
Elchanan Mossel and Sébastien Roch. Learning nonsingular phylogenies and hidden markov mod- cls. In Proceedings of the sevethh annual ACM symposium on Theory of computing, pp. 366-375, 2005.
Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):41-450, 1987.
Pascal Poupart and Nikos Vlassis. Model-based bayesian reinforcement learning in partially observ- able domains. In Proc Int. Symp. Artificial Intelligence and Mathematics,, pp. 1-2, 2008
12

---

Published as a conference paper at ICLR 2023
Matthew Rosencrantz, Geoff Gordon, and Sebastian Thrun. Learning low dimensional predictive representations. In Proceedings of the eeent--fisst international conference on Machine learning, pp. 88, 2004.
Stephane Ross, Brahim Chaib-draa, and Joelle Pineau. Bayes-adaptive pomdps. Advances in neural information processing systems, 20, 2007.
Satinder Singh, Michael James, and Matthew Rudary. Predictive state representations: A new theory for modeling dynamical systems. arXiv preprint arXiv:/207.4100 2012.
Ziang Song, Song Mei, and Yu Bai. Sample-efficient learning of correlated equilibria in extensive- form games. arXiv preprint arXiv:2205.07222; 2022.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 2998-2933. PMLR, 2019.
Michael R Thon and Herbert Jaeger. Links between multiplicity automata, observable operator models and predictive state representations: a unified learning framework. J. Mach. Learn. Res., 16:103-147, 2015.
Masatoshi Uehara, Ayush Sekhari, Jason Lee, Nathan Kallus, and Wen Sun. Computationally efficient pac rl in pomdps with latent determinism and conditional embeddings. arXiv preprint arXiv:2206. /2081, 2022a.
Masatoshi Uehara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Provably efficient reinforcement learning in partially observable dynamical systems. arXiv preprint arXiv:2206.12022 12020, 2022b.
Sara A Van de Geer. Empirical Processes in M-estimation, volume Cambridge university press, 2000.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):500-354, 2019.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Embed to control partially observed sys- tems: Representation learning with provable sample efficiency. arXiv preprint arXiv:2205.. 13476, 2022.
Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps. arXiv preprint arXhv:2107.03635, 2021.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. Pac reinforcement learning for predictive state representations. arXiv preprint arXiv:2207.05738 2022.
Zhi Zhang, Zhuoran Yang, Han Liu, Pratap Tokekar, and Furong Huang. Reinforcement learning under a multi-agent predictive state representation model: Method and theory. In International Conference on Learning Representations, 2021.
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C Parkes, and Richard Socher. The ai economist: Improving equality and productivity with ai-driven tax policies. arXiv preprint arXiv:2004.13332 2020.
A RELATED WORK
Learning POMDPs Due to the mon-Markovian nature of observations, policies in POMDPs in general depend on the full history of observations, and thus are much harder to learn than in fully observable MDPs. It is well-established that learning a near-optimal policy in POMDPs is indeed statistically hard in the worst-case, due to sample complexity lower bound that is exponential in the horizon (Mossel & Roch, 2005; Krishnamurthy et al., 2016). Algorithms achieving such upper bounds are developed in (Kearns et al., 1999; Even-Dar al., 2005). Poupart & Vlassis (2008); Ross
13

---

Published as a conference paper at ICLR 2023
et al. (2007) develop Bayesian methods to learn POMDPs, while Azizzadenesheli et al. (2018) con- sider learning the optimal memoryless policies with policy gradient methods. Sample-efficient al- gorithms for learning POMDPs have also been developed in Hsu et al. (2012); Azizzadenesheli et al. (2016); Guo et al. (2016); Xiong et al. (2021); Jahromi et al. (2022); These works assume exploratory data reachability assumptions, and thus do not address the challenge of exploration.
For learning POMDPs in the online (exploration) setting, sample-efficient algorithms have been pro- posed under various structural conditions, including reactiveness (Jiang et al., 2017), revealing con- ditions (Jin et al., 2020a; Liu et al., 2022a;c), revealing ffuture/past-suffccinnny and low rank (Cai al., 2022; Wang et al., 2022), decodablity (Efroni et al., 2022), latent MDP (Kwon et al., 2021), learning mhort-memory policies (Uchara et al., 2022b), and deterministic transitions (Uchara et al., 2022a). Our B-stability condition encompasses most of these structural conditions, through which we provide a unified analysis with significantly sharper sample complexities (cf. Section 3 & 5). We further remark that for tabular revealing POMDPs, our sample complexities are minimax optimal in the accuracy E and the revealing constant, and have at most a small polynomial gap in S, O, A factors from the minimax optimal rate, due to the lower bounds established in the work of Chen et al. (2023) (see e.g. their Table 1) after the initial appearance of this work.
For the computational aspect, planning in POMDPs is known to be PSPACE-compete (Papadim- itriou & Tsitsiklis, 1987: Littman, 1994; Burago et al., 1996; Lusena et al., 2001). The recent work of Golowich et al. (2022b;a) establishes the belief contraction property in revealing POMDPs, which leads to algorithms with yuasi-polynomial statistical and computational efficiency. Uehara et al. (2022a) design computationally efficient algorithms under the deterministic latent transition assumption. We remark that computational efficiency is beyond the scope of this paper, but is an important direction for future work.
Extensive-Form Games with Imperfect Information (EFGs; (Kuhn, 1953)) is an alternative formu- lation of partial observability in sequential decision-making EFGs can be formulated as Partially Observable Markov Games (the multi-agent version of POMDPs (Liu et al., 2022c)) with a tree- structure. Learning from bandit feedback in EFGs has been recently studied in Farina et al. (2021); Kozuno et al. (2021); Bai et al. (2022a;b); Song et al. (2022), where the sample complexity scales polynomially in the size of the game tree (typically exponential in the horizon). This line of results is in general incomparable to ours as their tree structure assumption is different from B-stability.
Learning PSRs PSRs is proposed in Littman & Sutton (2001); Singh et al. (2012); Rosencrantz et al. (2004); Boots et al. (2013) as a general formulation of partially observable systems, following the idea of Observable Operator Models (Jaeger, 2000). POMDPs can be seen as a special case of PSRs (Littman & Sutton, 2001). Algorithms for learning PSRs have been designed assuming reachability exploratory data, including spectral algorithms (Boots et al., 2011; Zhang et al., 2021; Jiang et al., 2018), supervised learning (Hefny et al., 2015), and others (Hamilton et al., 2014; Thon & Jaeger, 2015; Grinberg et al., 2018). Closely related to us. the very recent work of Zhan et al. (2022) develops the first sample-efficient algorithm for learning PSRs in the online setting assuming under a regularity condition. Our work provides three algorithms with sharper sample complexities for learning PSRs, under the more general condition of B-stability.
A concurrent work by Liu et al. (2022b) (released on the same day as this work) also identifies a general class of "welllconddtioned"" PSRs that can be learned sample-efficient rithm (Liu et al., 2022a)) Our B-stability condition encompasses and is slightly more relaxed than their condition (consisting of two parts), whose part one is similar to the operator norm requirement in B-stability with a different choice of input norm, and which requires an additional second part.
by the OMLE algo-
Next, our sample complexity is much tighter than that of Liu et al. (2022b), on both general well- conditioneddBB-stalle PSRs and the specific examples encompassed (such as revealing POMDPs). For example, for the general class of "y well-conditioned PSRs" considered in their work, our results imply Ö (dAU 1/2 log Nog.Ne/(13 ()²))) sample complexity, whereas their result scales as Ö (of A H (oggNe((72))) (extracted from their proofs, cf. Appendix D.4). This originates from several differences between our techniques: First, Liu et al. (2022b)'s analysis of the OMLE algorithm is based on an fy-type operator error bound for PSRs, combined with an -1Euuder ar- gument, whereas our analysis is based on new stronger t2-type operator error bound for PSRs (Proposition F.2) combined with a new generalized E2-Eluder argument (Proposition E. which together results in a sharper rate. Besides, our EluEer argument also admits an in-expectation de-
14

---

Published as a conference paper at ICLR 2023
coupling form variant (Proposition E.6) that is necessary for bounding the EDEC (and hence the sample complexity of the EXPLORATIVE E2D algorithm) for B-stable PSRs; it is unclear whether their -Eluder argument can give the same results. Another difference is that our performance de- composition and Hluder argument are done on a slightly difference choice of vectors from Liu et al. (2022b), which is the main reason for better 1/7 dependency (or Åв dependency for B-stable PSRs); See Appendix B for detailed overview of our technique. Further, in terms of algorithms, Liu al. (2022b) only study the OMLE algorithm, whereas we study both OMLE and two alternative algorithms Explorative E2D & MOPS in addition, which enjoy similar guarantees (with minor dif- ferences) as OMLE. In summary, Liu et al. (2022b) do not overlap with our contributions (2) and (3) highlighted in our abstract.
Finally, complementary to our work, Liu et al. (2022h) identify new concrete problems such as ob- servable POMDPs with continuous observations, and develop new techniques to show that they fall into both of our general PSR frameworks, and thus tractable to sample-efficient learning. In partieu- lar, their result implies that this class is contained in (an extension of) the low-rank future-sufficient POMDPs defined in Definition D. if we suitably extend the formulation in Definition D.11 to the continuous observation setting by replacing vectors with L1 inteegrable functions and matrices with linear operators.
RL with function approximation (Fully observable) RL with general function approximation has been extensively studied in recent line of work (Jiang et al., 2017; Sun et al., 2019; Du et al., 2021; Jin al., 2021; Foster et al., 2021; Agarwal & Zhang, 2022; Chen et al., 2022), where sample- efficient algorithms are constructed for problems admitting bounds in certain general complexity measures. While POMDPs/PSRs can be cast into their settings by treating the history (Th-1, on) as the state, prior to our work, it was highly unclear whether any sample-efficient learning results can be deduced from their results due to challenges in bounding the complexity measures (Liu et al., 2022a). Our work answers this positively by showing that the Decision -stiimattt Coefficient (DEC; Foster et al. (2021)) ) for B-stable PSRs is bounded, using an explorative variant of the DEC defined by Chen et al. (2022), thereby showing that their EXPLOR closely related MOPS algorithm (Agarwal & Zhang. 2022) are both sample-efficient for B-stable PSRs. Our work further corroborates the connections between E2D, MOPS, and OMLE identified in (Chen et al., 2022) in the setting of partially observable RL.
E2D algorithm and the
B OVERVIEW OF TECHNIQUES
The proof of Theorem 9 consists of three main steps: a careful performance decomposition into certain B-errors, bounding the squared B-errors by squared Hellinger distances, and a generalized E2-Eluder argument. The proof of (the EDEC bound in) Theorem 10 follows similar steps except for replacing the final Eluder argument with a decoupling argument (Proposition E.6).
Step 1: Performance decomposition By the standard excess risk guarantee for MLE, our choice of 3 = O (log(Ne (1) guarantees with probability at least 1 - that 6* e e for all & E [K] (Proposition G.2(a)). Thus, the greedy step (Line 4 in Algorithm 1) implies valid optimism: V. $ Voa (T*). We then perform an error decomposition (Proposition F.1):
V. ( & (m+)) Vo- & DTV (1Pz" "egt.Pp"""
Et E Insh E (Gn (10)
where Ei, : ||B) (q) - ( Imm. and
E7 max. "
Σ x(nlow)) B (Bi on) - (i, and) q" (Th-1)lmm (11)
where for the ground truth PSR 0" and the OMLE estimates 0 from Algorithm 1, we have defined respectively (B), ) and (B), q as their B-representations, and (B and (B as the cor- responding B-operators. (10) follows by expanding the pa (7) and pT (7) (within the TV distance) using the B-representation and telescoping (Proposition F.1.. This decomposition is similar as the ones in Liu et al. (2022a); Zhan al. (2022), and more refined by keeping the B # term in (11) (instead of bounding right away), and using the II-norm (3) instead of the & norm as the error metric.
15

---

Published as a conference paper at ICLR 2023
Step 2: Bounding the squared B-errors By again the standard fast-rate guarantee of MLE in
squared Hellinger distance (Proposition G.2(b)), have Σt=1 -n=o DH for all & [K]. Next, using the B-stability of the PSR, we have for any E (Proposition F!2)
P I phhho k
< 2/
E
K that
En Eyi (T & 32A AUA Σx Di (1ehiar, pTh
(12)
Plugging the MLE guarantee into (12) and summing over E [k 1] yields that for all & [K]]
E
-H - E. ( (T- < O O AUA
(13)
(13) is more refined than c.g. Liu al. (2022a, Lemma 11). as (13) controls the second moment of Eo whereas their result only controls the first moment a similar error.
Step 3: Generalized fz-Eluder argument We now have (13) as a precondition and bounding (10) as our target. The only remaining difference is that (13) controls the error & with respect to [=') whereas (10) requires controlling the error Eg with respect to n².
To this end, perform generalized fg-Eluder dimension argument adapted to the structure of the function Ex's (Proposition E, which implies that when dpsR & d,
Σ B [E:
de
k+
ΣΣΣ B (EL 1=1==1
h( E [K] x [H]. (14)
Note that such f2-type Eluder argument allowed precisely whereas our target (10) only requires an & bound. In comparison, Liu et al. (2022a); Zhan et al. (2022) only obtain precondition in L1, and thus has to perform an &l-Eluder argument which results in an additional d factor in the final sample complexity. Combining (10), (13) (summed over l e [K]) and (14) completes the proof of Theorem 9.
precondition (13) is in &
C TECHNICAL TOOLS
C.I TECHNICAL TOOLS
Lemma C.1 (Hellinger conditioning lemma (Chen et al., 2022, Lemma A.4)). For any pair of random variable (X,Y) Y), holds that
Ex-Px [D] (Pyix. Qyxx)] 2D (Pxx Qx,)).
The following strong duality of (generalized) bilinear function is standard, e.g. it follows from the proof Foster et al. (2021, Proposition 4.2).
Theorem C.2 (Strong duality). Suppose that X, y are topological spaces, such that X is discrete and y is finite (with discrete topology). Then for a function f X x y - IR that is uniformly bounded, holds that
sup inf Xedo(X) YEA(Y)
E (sx, v)] = inf sup E (s(x,))),
YEA()) nE
where (x stands for space of the the finitely supported distribution on X.
We will also use the following standard concentration inequality (see e.g. Foster et al. (2021, Lemma A.4)) when analyzing algorithm OMLE.
Lemma C.3. For sequence of real-valued random variables (Xt)sx adapted a filtration
(Fi)sT the following holds with probability at least 1 5:
log E
& Σ X, + log (1/8), e [T].
16

---

Published as a conference paper at ICLR 2023
C.2 COVERING NUMBER
In this section, we present the definition of the optimistic covering number Ne. Suppose that we have model class O, such that each 0 @ parameterizes sequential decision process. The p-oplimistic covering number of θ is defined as follows.
Definition C.4 (Optimistic cover). Suppose that there is context space X. An optimistic p-cover of ④ is tuple (IP, Oo), where Go θ is finite set, IP === liat (-) IR Bee
specifies
optimistic likelihood function for each Oo, such that:
(1) For 0 θ there exists a 0g Og satisfying: for all E T and n, holds that Pr, (T) (T).
(2) For 0 O, max (TH = P- (TH = = & p².
The optimistic covering number (e) is defined as the minimal cardinality of Oo such that there exists IP such that (IP, Mo) is an optimistic p-cover o
The above definition is taken from Chen al. (2022); the covering argument in Liu et al. (2022a) essentially uses the above notion of covering number. Besides, the optimistic covering number can be upper bounded by the bracketing number adopted by Zhan al. (2022).
By an explicit construction, Liu et al. (2022a) show that there is universal constant C such that for any model class Ô of tabular POMDPs, it holds that
log)N((p) & CH(SS A 50)
D PROOFS FOR SECTION 3
D.1 BASIC PROPERTY OF B REPRESENTATION
Proposition D.1 (Equivalence between PSR definition and B-representation). A sequential decision process is a PSR with core test sets ([])) (in the sense of Definition 1) if and only if it admits B-representation with respect (Un) (e)))) (in the sense of Definition 2).
Proof of Proposition D.I. We first show that PSR admits B-representation. Suppose have a PSR with core test sets ([4))e[H)] satisfying Definition 1, with associated vectors (be,,h 1 ME given by (1). Then, define
[-]
(x(o,)) = bo
E 11 xuh,
qo = PP(()
E R
selli
We show that this gives a B-representation of the PSR. By (1), we have for all (h, Th-1, o, a) that
(x a)q((ng))))) 11 [IP(o, 1n- P( olTh-1) q q
Applying this formula recursively, we obtain
(T) P((T)) q(T)) [IP(Te, la+ (e+t)))nnneehe
which completes the verification of (2) in Definition 2.
We next show that process admitting B-representation is a PSR. Suppose we have se- quential decision process that admits BBrepresennation with respect to (Un) as in Defi- nition 2. Fix h [H]. We first claim that, construct vectors (bt,,t)s,, Ruth such that P(t TT-1) = (br,h, q(Th-1)> for all test ta and history Th-1 (Definition 1), we only need to con- struct such vectors for full-length
tú (Oh:H- (A.H). This because, suppose have assigned b 1R for all full-length 4 's. Then for any other 4. (Ohch+W-2 4hsh+w-2) with
W- H fengeeh..enngth...... take
b
Σ
ben.
Oh W13
17

---

Published as a conference paper at ICLR 2023
where 0/4 11:1 E AAH-h--
W-2 is arbitrary and fixed action sequence. For this choice have
(b ((Th-)))
Σ
wo J. q(Th-1))
oh+ W+++
Σ
P(tn: OhWW:H+H 2 Th-1) P(tA/Ta-1)
desired.
remains to construct b for all full-length tests. For any full-length test ln (0h.H+1, (kaH), take by, R24 with
Bи( an) ... (oh, 9n) E Rixth.
By definition of the B-representation, for any history Th = (01, a1, Oh, an), and any test t
Uh+ we have
P(Th) x P(tn-1|Th) CY BA: x qu.
or in vector form,
P(Th) x ((T)) = BA:I(Th)q.
(15)
where we recall P(T)) = P(. ... on ooldo(ar,.... (n))). Therefore, for the particular full history TH (Th-1, (n), we have by applying (15) twice (for steps H and h 1) that
((TH): = ( qo = B a..H 11
6T, (P(T)-1) x q ((T)-))).
Dividing both sides by P(Th-1) (when it is nonzero), we get
P(tA|TA-1) = ((/n) = P(TH)/ = bT.
(16)
This verifies (1) for all T that are reachable. For Th-1 1 that are reachable, (16) also holds as both sides equal zero by our convention. This completes the verification of (1) in Definition 1. 0
From the proof above, we can extract the following basic property of B-representation.
Corollary D.2. Consider PSR model with B-representation { (Bn an) ho, qo). For 0 s
& H 1, it holds that
PI) q(Th-1, Oh, Oh, an) Biilon an an)a(TT-1))
Furthermore, it holds that
(17)
D.2 WEAK B-STABILITY CONDITION
In this section, we define a weaker structural condition on PSRs, named the weak B-stability condi- tion. In the remaining appendices, the proofs of our main sample complexity guarantees (Theorem 10, H.4, H.6) will then assume the less-stringent weak B-stability condition of PSRs. Therefore, these main results will hold under both Ag-stablility (Definition 4) and weak Ag-stablility (Defini- tion D.4) simultaneously.
To define weak B-stability, we first extend our definition of I[-norm to RT for any set T of tests. Recall that in (3), have defined II-norm on ITT with T (0 A) H-h (and in (5), the nnom for T = 14)) Definition D.3 (II-norm for general set). For T I, we equip RT with I.I| defined by
|| = max max
Σ ((t))((()), TE
VERT
PET A
where maxperr taken over all subsets of such that satisfies the prefix condition: there is two of 1' T such that & is a prefix of
18

---

Published as a conference paper at ICLR 2023
It is straightforward to see that, for any R we have ||l|1 > | |
Definition D.4 (Weak B-stability), A PSR is weakly B-stable with parameter Ag 2 1 (henceforth weakly Ag-stable) if it admits a B-representation and associated B-operators (Bus)ne(M such that, for any h [H] and p. q E R2 we have
|B (p- In ABy A laln) IVp v4l2
(18)
Despite the seemingly different form, we can show that the weak B-stability condition is indeed weaker than the B B-stability condition. Furthermore, the converse also holds: the B-stability can be implied by the weak B-stability condition, if we are willing to pay 2 factor. This is given by the proposition below.
Proposition D.5. If a PSR is B-stable with parameter ΛB, then it is weakly B-stable with the same parameter Åg. Conversely, if PSR weakly B-stable with parameter Ag (cf. Definition D.4), then it is B-stable with parameter AAg.
Proof of Proposition D.5. We first show that B-stability implies weak B-stability, Fix a h E [M]. We only need to show that, for p, E 1/4 we have
Ip 1 all
v
2(1lln
(| lIv - vdl.
(19)
We show this inequality by showing the bound for the (1, 2) 2)-mmm and the IT' norm separately. First,
we have
Ip
q
2
Σ
(
Σ o:(0,))ell,
(p(o.a) - q(o, ((o,a)) 2
1.2
AE
Σ
Σ
Vp(o,a) + va(o,a) ))(o.a)))(
Σ
a)) 2 - [(0,
acUla.k
o:(o,))e4,
o((o,a)el,,
Σ
Σ
a)o.a) + q(0,aa)
Σ
I -
<
a
o:(o,a)el
o:(o,))El4
< 2[([p]]
Σ
Σ
V -qqa) a
a (o.)el
= pl (94 V
where the first inequality is due to the Cauchy- Secha-S inequality; the second inequality is due to AM-GM inequality; the last inequality because maxaslla. (o. o(o, a) < || Next, we have
p - = max
Σ x(t) x (p()) - -((t))
Σ (()((((t) q(()))
Σ T(t) - va(t)
< 2 max
te
1e7
< max
((t)(((t) + +((t))
Σ
V p(t)) v((T)²
tel4,
< 2(1ppn [[lll)) 11lll--vv val.
Combining these two inequalities completes the proof of Eq. (19), which gives the first claim of Proposition D.5.
Next, we show that weak B-stability implies B-stability to a 22U factor. Fix a h E [H]. For E IRl,, we take p [x] q [x]_ then it suffices show that
v 2( (1pl [[l1n) lVp vgll2 & 22
(20)
Heee we introduce the constant 2 in the square root in order for weak B-stability to he weaker than B- stability (Definition 4).
19

---

Published as a conference paper at ICLR 2023
Indeed, we have
IIpp vgl. |Vz
2 -VEll
Pl + |qlnn < [x]]]], + |[0]_||| = |
This implies that
V 2(Iln + (qln) lvp - vall2 & v2|=111
(21)
Applying Lemma D.6 completes the proof of Eq. (20), and hence proves the second claim of Propo- sition D.5.
Lemma D.6. Consider the fused-norm as defined in Eq. (4). For any q e R44,, we have
|q|
|all1 & [Ml 1/2 ||
and 1 |ql, On the other Proof of Lemma D.6. By definition, clearly have | lq), hand, by Schwhy-Schwarz inequality,
2
|aall
Σ
|((oa))|
< MAM
Σ
E lq(o,a)
< MuA.
(o.a)eik
a
Combining the inequalities above completes the proof.
D.3 PROOFS FOR SECTION 3.2
D.3.1 REVEALING POMDPS
4 revealing condition We first remark that, besides the revealing condition using the & norms defined in Example also consider the & version of the revealing condition, which measures the orporrrtor norm of any left inverse MI of MA. instead of the 62-operator norm of the pseudo- inverse MI Concretely, there exists matrix Mt such that M., also show that any m-step Orrev,f le-revll POMDP is Ag-stable PSR with core test sets Uh (O A) Hmm x O, and AB Am fev
say POMDP satisfies the m-step Orrevtt f-revealing condition, if
-1 / and [M 1--1 & Teev. In Proposition D.7.
We consider Example and show that any m-step revealing POMDP admit B-representation that is B-stable. By definition, the initial predictive state is given by qo = M1f1. For h & H m, we take
BB an)
Ma++ Ta diag On (oxl M)
(22)
where Th. T. a) 5 is the transition matrix of action e A, and M, is any left inverse of Ml.. When h m, we only need to take
Ba an) [1 (on, ap, t++1)
E M x2l,
(23)
where 1ttr = -On, an. 1)) is if ta equals to (0n, ah, th+1), and otherwise. Proposition D.7 (Weakly revealing POMDPs are B-stable). For m-step revealing POMDP, (22) and (23) indeed give B-representation, which is B-stable with Ag & max, [M 11 where
MI
max
MM
WER P
Therefore, any m-step Orev Crev-Weakkt weakly revaling POMDP is B-stable with As VSa (by taking = using 1l11, I. and | /S Similarly, any m-step Orev, l1-revealing POMDP is B-stable with Ag & v I [a rev,E; (using |.1,, & I. with UA Am-1).
For succinctness, we only provide the proof of a more general result (Proposition D.12). Besides, by similar argument, be bounded by Rg & a=lA" A (for ayew ayeu- wwekkly revealing POMDP) or Rg & a A (for Orev. l rereealling POMDP, e.g. Lemma 1.13).
also show that the parameter Rg that appears in Theorem 9 can
20

---

Published as a conference paper at ICLR 2023
D.3.2 LATENT MDPs
In this section, we follow Kwon et al. (2021) show that latent MDPs sub-class of POMDPs, and then obtain the sample complexity for learning latent MDPs of our algorithms.
Example D.8 (Latent MDP). A latent MDP M is specified by a tuple {S,A, (Mm) H, v). where M MN are N MDPs with joint state space S, joint action space A. horizon H. and V E A([N]) is the mixing distribution over Mj, ... My. For m e [N] the transition dynamic of Mm is specified by (TA.m S x A ((S)) along with the initial state distribution pm- and at step the binary random reward Th.m is generated according to probability RB.m : A [o. IJ.
Clearly, MM can be casted into a POMDP M' with state space S [NV] S x {0, 1] and observation space O S x {0, by considering the latent state being &6. = (#h, rh. m) E S and observation being o& (sn, Th-1) O. More specifically, at the start of each episode, the environment gener- ates a m ~ // and a state ~ pm. then the initial latent state is $1 = (m, 8, 0) and 01 = (s. 0); at each step h, the agent takes on after receiving oh then the environment generates T4 E {0, 1}, $h+1 and 0h+1 according to (5h, On): тΛ = 1 with probability ( an)) [1, Bh+1 = (m, (m, S1+1, Th) and op+1 = (5++1.7h).
sh+1 ~ TT (-15k, ax),
In a latent MDP, we denote To to be the set of all possible sequences of the form (an, Thi 8h+1, aht--1, 1ia---,,7+---- S1+)) (called a test in (Kwon et al., 2021)). For h & H ++1, t (ah, Thi Thi 8h+1, -0t---1,7+4-1111111.11 sh+1) E T₁ and S, we can define
Ph.m (t|s) = Pm (Tk, sh+1. ... 11+--11 8h+1 8/ = s, do(an, .. aa++--1));
where Pm stands for the probability distribution under MDP Mm.
Definition D.9 (Sufficient tests for latent MDP). latent MDP M said to be 1-step test-sufficient, for h E H - 1] and S, the matrix (s) given by
L = Pm (t|s) (cm))TT. E T.XN
has rank N. M is l-step a o-test-sufficient o (Lx(s)) & for all he [H -++ 1] and S. Under test sufficiency, the latent MDP is an (I + step o-weakly revealing POMDP, as shown in (Zhan et al., 2022, Lemma 12). Hence, corollary of Proposition D.7, using the fact that S 25N, we have the following result.
Proposition D.10 (Latent MDPs B-stable). For an l-step o-test-sufficiel latent MDP M, its equivalent POMDP M' is (1+t)- a-weakly revealing, and thus B-stable with AB V2SNo
Therefore, by similar reasoning to m-step revealing POMDPs in Section 5 (and Appendix D.3.1), algorithms OMLE/EXPLORATIVV E2D/MOPS can achieve sample complexity of
Sa ( 2
for learning e-optimal policy, where is the class of all such latent MDPs. Further, the opti- mistic covering number of θ can be bounded as (similar as (Liu et al., 2022a, Appendix B) and Appendix D.3.4)
log.N((p) & (NS
Thus, we achieve a Ö (S* A42 of Kwon et al. (2021) who requires extra assumptions including reachability, a gap between the N MDP transitions, and full rank condition of histories (Kwon et al., 2021, Condition 2.2). Besides, our result does not require extra assumptions on core histories-whin is needed for deriving sample complexities from the regullauy of (Zhan et al., 2022) which could be rather unnatural for latent MDPs.
sample complexity. This improves over the result
We remark that the argument above can be generalized to low-rank latent 1DPs straightforwardly. achieving a sample complexity of δ N2 2 log No/o?)?) For more details, see Ap- pendix D.3.3.
Note that under such formulation, M' has deterministic rewards.
The terminal state 8H+1 is a dummy state.
A latent MDP M has transition rank if each Mn, has rank d linear MDP (Jin al., 2020c).
21

---

Published as a conference paper at ICLR 2023
Proof of Proposition D.10. As is pointed out by Zhan et al. (2022), the (l+ 1)-step emission matrix of M' has relatively simple form: notice that for h [H [ + 11. (m,,,r) 8 and tn = (Oh, ah. ... Oh+1) U4, (with oh+1 = (9h+1.7%),- ". 0h+1 = ($h+1: Th+1-1)), we have
(l 8) 1(on (sh, Th- I)) (Th, Sh4ls" 1h4t-1, 5h+r s, do(an, (h+1-1)), where 1 (or, (sh; rn-1)) is 1 when on (8h, and otherwise. Therefore, up to some permutation, M,, has the form
L)(
To (s(1))
[n(s()))
(s(s)))
M,
L
L (s((S)))
where ( ,...,.... ,08)) is an ordering of S. Therefore, it follows from definition that 1M,1222 & maxh.a (L( a Applying Proposition D.7 completes the proof.
D.3.3 LOW-RANK POMDPS WITH FUTURE SUFFICIENCY
In this section, we provide detailed discussion of low-rank POMDPs and m-step future sufficiency condition mentioned Example 6. We present a slightly generalized version of the m-step future sufficiency condition defined in (Wang et al., 2022); see also (Cai al., 2022).
For low-rank POMDPs, we now state a slightly more relaxed version of the future-sufficiency con- dition defined in (Wang et al., 2022). Recall the m-step emission-action matrices Ml, R defined in (7).
Definition D.11 (m-step p-futtre-suuffcciet POMDP). We say low-rank POMDP is m-step v- future-sufficient ifr h [M], ming; [MM]]] u, where ming, is taken over all possible Mij,
such that M., M = Tn-1-
Wang et al. (2022) consider factorization of the latent transition: T, Un with Ur x Dy X (SxAA) for h [H], and assumes that [M 11-1 < with the specific choice MI, = nn (ML, -n-1)* (note that it taking an exact pseudo-inverse instead of any gen- eral left inverse). It is straightforward to check that this choice indeed satisfies M) M, T T, using which Definition D. recovers the definition of Wang et al. (2022). It also encompasses the setting of Cai et al. (2022) (m = 1).
We show that the following (along with (23)) gives B-representation for the POMDP:14
(x a) = MI diag ( h [ m].
(24)
This generalizes the choice of B-representation in (22) for (tabular) revealing POMDPs, as the matrix MI, can be thought as "generalized pseudo-inverse" of M, that aware of the subspace spanned by T2-1- This choice is more suitable when S or O are extremely large, in which case the vanilla
pseudo-inverse MI may not be bounded in I|-Il--. norm. In the tabular case, setting 1 t in (24) recovers (22).
Proposition D.12 (Future-sufficien low-rank POMDPs are B-stable). The operators (Ba a.. given by (24) (with the case h > H- - m given by (23)) is indeed B B-representation, and it is B-stable with Ag VAm-I max, [MM 11- As corollary, any m-step v-future-sufficint y (and also Rg & v).
low-rank POMDP admits a B-representatiio with Ag < Vmm-Ta
Combining Proposition D.12 and Algorithm 2 gives the sample complexity guarantee of Algorithm for future sufficient POMDP. For Algorithm OMLE, combining Rg & " with Theorem 9 estab- lishes the sample complexity of OMLE, as claimed in Section 5.
For simplicity, we write Tha Ta(-I, a) SxS the transition matrix of action A.
22

---

Published as a conference paper at ICLR 2023
Proof of Proposition D.12. First, verify (2) for 0 & & H m. In this case, for t4+1 Uh+1, we have 15
e e Bh:1 (Th)(T e I M Ti.or diag (Or( Min
T
(1)
Mh++1 Th,a, diag (On(onl)) Ti, diag (0) (011
(25)
(8t)
Σ
P( 18441 Th (0)+119))) ( ((11))))))(())
$1 18111
P(Th; ln+1),
where (i) is due to MTMIT, = Tr for < & h, in (ii) we use the definition (7) to deduce that the (l1+1, (h+1) of M,+1 is P(4++115411
Finally, we verify (2) for - m < < H. In this case, Un+1 OH-h x AHhh-1 and hence for Th (01,01, "1
10H-m+1,CH-me 0h, ah), th+1 (0h+1, Ch+1.-'. ,0H) Uh+1, we consider ---m+1
1 (
o mil BT P(tu-m+hh TH-m) P(tn+1,Th) mh).
remains to verify that the B-representation is Ag-stable with Ag & A and Rg & A we invoke the following lemma.
Lemma D.13. For h < e R it holds that
|Bилœ max Σ
[B an) Ba(on, )all x ((TCH) & max | || ||
Th:Mf
Similarly, we have Eo.e. (x(o,))ull & max AM M400 Al
By Lemma D.13, holds that
[HH*= IT & max [M||> [=]|m) v ||>|| & uv UA ||=|| vV Am-1 |x|
where the second inequality is because || & ||/|] and > 1, and the third inequality is due to Lemma D.6 and ||az|| > | by definition. Similarly, we have RB & A.v. This concludes the proof of Proposition D.12.
Proof of Lemma D.I3. We first consider the case h H m. Then for each h & & B, is given by (23), and hence for trajectory Th:H = (0n; az. .. ,HH an) and x Rd4,, holds that
Br.H(THHHes (00,, an. ... ,.), .0H)
This implies that |Bинжл || and Eo,a BA a)xll = A | directly.
We next consider the case h & H m. Note that for Thil (0n, ah. -OH-m- m aH ---m.... "0. ;0H)
we can denote 1 (oH (01 0H-m+1;"" ,H), then similar to (25) we have
T C My m+1
II
T diag (Oi(all)) M
H-m
PP( m+)
m+1)
11 i-h
Te. (11+1ss))))))
Sh S8
Σ P(Taalls s)c..M. Mi.
SES
Therefore, for policy at and trajectory TheH, it holds that Σ (Tunnns =) xex e.M.r
T(TaH) x (.a(THH))
SES
For the clarity of presentation, in this section we adopt the following notation: for operator (Cn) write [m Cn Li f..-
23

---

Published as a conference paper at ICLR 2023
and this gives [B < x directly. Besides, we similarly have
Σ
a),
Σ M a diag (Ox (O) & |Mattal |
The proof is completed by combining the two cases above.
D.3.4 LINEAR POMDPS
Linear POMDPs (Zhan et al., 2022) is a subclass of low-rank POMDPs where the latent transition and emission dynamics are linear in certain known feature maps. In the following, we present a slightly more general version of the linear POMDP definition in Zhan et al. (2022, Definition 5).
Definition D.14 (Linear POMDP). POMDP is linear with respect to the given set of feature maps (1hh S Rda,, Ph 8 x A - Rd ,4,,, 10 x S RR if there exists An
Rdd.a xds,2 Uh E 12,uE E Idd.. such that
(A(8'18, a) = on (s') Anth a), We further assume a standard normalization condition: For R == max (d,,1 d,,2,
(s(s) = (v, (o(s)),
On(ols) = (un, (a((()))))))))))))))))))))))))))
Σ 1bnnd))) & R,
11 (8) R
> [ob())))]1 R
A R.
||uloo R,
|unlloo R.
Proposition D.15. Suppose that is the set of models that are linear with respect to a given w and have parameters bounded by R. Then logNN((p O ((d, d.) log(d,d, H/H))))) where denote d, := d=,1
It is direct check that any linear POMDP is low-rank POMDP (ef. Example 6) with desR & derans & min (ds,1, d,,2). Therefore, by a similar reasoning to Appendix D.3.3, Theorem 9 & 10 both achieve sample complexity of Ô (min (ds,1, (ds, Ao)AU AM Age for learn- ing an E-optimal policy in Ag-stable linear POMDPs (which include e.g. revealing and decodable linear POMDPs).
This result significantly improves over the result extracted from (Zhan et al., 2022, Corollary 6.5): Assuming their regulaalr,,, we have ÄB & VU (Example 8) and thus obtain sample complexity of
δ (min (ds,1 de2) + do) (a
This only scales with d AU? (where d >/ max (d d, do)), whereas their results involve much larger polynomial factors of all three parameters. Further, apart from the dimension-dependenne. their covering number scales with an additional log O (and thus their result does not handle ex- tremely large observation spaces).
Proof of Proposition D.15. In the following, we generalize the construction of optimistic covering of θ using the optimistic covering of {0%] Jee and {T oee in Liu al. (2022a, Appendix B). Lemma D.16 (Bounding optimistic covering number for POMDPs), For θ a class of POMDPs, let us denote O (0%) see and On:o = {Thloee Then it holds that for p (0,1)." 17.""
log:N((p1) & 2H max (log Ne... (oo/3H),ooo log (pH33H)}
By Lemma D.16, we only need to verify that for all E [H].
log Ne... (p) (do log Rdo/P)) log Ne... (p) = (d, log(Rd,) pp))
Here, for h we take Ou. {14) sce
17ehe optimistic covers of the emission matrices tho and transitions O are defined as in Chen al. (2022, Definition C.5) with context æ heing and (s, a), and output being and 8, respectively.
24

---

Published as a conference paper at ICLR 2023
We demonstrate how to construct p-optimistic covering for Ob:o: the construction for O). is essentially the same. In the following, we follow the idea of (Chen et al., 2022, Proposition H.15).
Fix a he E [H] and set N [R Let R' N, f [-R', RT],, we define the p-neighborhood of u as (u, p) = p plu/p] [0, pl and let
(olu( =
(u', (o(os))))))
max weBBz(u))
Then, if u induces emission dynamic Oagur then Oncu(ols) > Ohiu(ols), and
Σ [nnu(ols) Ohiu(ols)
Σ
max Kn' u, Ellsn(olss) Rp. (u.p)(upp)
Therefore, we can pick each (n,u(+--) representative such that induce lawful emission dy- namic; there at most (2N) many elements in the set (haa(+)))
uE[-R',R and hence by
doing this, we obtain Rp-optimistic covering (0), (n of Ono such that (0.0 & (2 This proves Proposition D.15.
Proof of Lemma D.16. Fix a P1 E (0, 1] and let p P1/3H.
Note that given a tuple of parameters (71, T, () (not necessarily induce a POMDP model), we can define F as
P(TH)
Σ (oss))
$1
and [P-(TH = π (TH) x PP(H))
Then for a tuple of parameters (M1, T,O) O) that induce a POMDP
such that
[ - 1111111 p²
max s,a,
[ - T1), <p?
max 8.h
ŌŌr -w)(1s)) <
it holds that
PT() -
-PO-P(T)) PT)
Σ
P (TH) - 1pT (TH)
Σ
((TH) (s1) - (s1)) (((oolss))(((()))).aa)) ..)0ol1
81:
+ (((T)))((s)) (1(0)(s:) - (o Tr(2lss,, -._((()))))))
(((m)) (a)a)))00allllaaa(aaaaaaaaaaaa)) (1 Ö(on(sn)
+ (tT ... [(or -(onlss))C(oo|ss)]
22 & <4 & p
where (+) is because Ems., TA an)) & 1² and Eo, (n(o))s)) & 1+ 2 for all h, 8h ag.
Therefore, suppose that for each h, (T,, O,,)) is p-optimistic covering of θ and (o,, Ohyo) is p-optimistic covering of θ then we can obtain a PI optimissii covering (P, O¹) of θ where
= B,, O1,0 01 x x O'H11 H'H
This completes the proof.
25

---

Published as a conference paper at ICLR 2023
D.3.5 DECODABLE POMDPS
To construct B-representation for the decodable POMDP, introduce the following notation. For
& H m, we consider in = (on, Uh," ... 10) Un, b1++1 = (0h41) " h
Uh+1, and define
IP(o = 0h+ml9htm-1- 184mm11 = +h+m- (lx), ah+m-1), if + = 0 01+1/+m-3
PA (f(1++1(th)
and ah+1stm-2 = 01+1::h--22
otherwise,
(26)
where m is the decoder function that maps H m, t E Un tx+1 E Uh++1. we let PP (x( be if ta ends with 1441. and otherwise.
latent state 84+m-1- Similarly, for h >>
Under such definition, for all E [H, tn E Un. 1 E U,41, it is clear that (t (4.) P(tn+i|b,, Th-1)
(27)
for any reachable (7 tn), because of decodability. Hence, we can interpret (t as the probability of observing f conditional on observing t, on step h. Then, for h [H], we can take
Ba a) [1((o,a) - (n) Pn(nn( 1 (4, de)thh
(28)
where 1 a() - (4) 1 if l, starts with (o, a) and otherwise
We verify that (28) indeed gives B-representation for decodable POMDPs:
Proposition D.17 (Decodable POMDPs are B-stable). (28) gives a B-stable B-representation of the m-step decodable POMDP, with Ag
The results above already guarantee the sample complexity of EXPLORATIVE E2D for decodable POMDPs. For OMLE, can similarly obtain that Σ... [B a)=1 ||>|||, and thus can take Rg A. Combining this fact with Theorem establishes the sample complexity of OMLE as
claimed in Section 5.
Proof of Proposition D.17. We verify that (28) gives B-representation for decodable POMDP: Note that for h E [ -1, (on, an) E O x A. th-1 E Up-11 there is unique element ty. E U4p such that ln is the prefix of the trajectory (on, an, 1++1 and it holds that
1 Ba (ox, )x) (M x x044)-
Applying this equality recursively, we obtain the following fact: For trajectory Thish and f--1 Un+1s (Theks 1++1) has a prefix ty E Un, and
e,, (Tw:a = PP (4414() x x(ta))
(29)
where P( 4++ ((x)) stands for the probability of observing (Thra, (++1) conditional observ- ing ty at step h' which is well-defined due to decodability (similar to (27)).
Taking h' 1 and x qo (29), have for any history Th and t E Uh+1 that
P(Th, th+1) 1) = e,,_, (
Therefore, (28) indeed gives B-representation of the decodable POMDP.
Furthermore, can take h H in (29) obtain that: For any trajectory Tha (op, Oh, ... ,H,, (.). it has a prefix 4, Un and
B (Tr.H) = P(TrHHlth) x x(tn).
Hence, for any policy n, holds that
Σ T(Ta.))) (BirATTtatrat
Σ pa (Tharl4)) x [o((n)] Th-ll
Σ m((a) x |a((n)]
Th:H
Therefore, [ n & | always. This completes the proof of Proposition D.17.
It worth noting that the (Px) we define is exactly transition dynamics the associated megastate MDP (Efroni et al., 2022).
For h H. we understand By (o, [1] o)]est,, because 01+11 Odum always.
26

---

Published as a conference paper at ICLR 2023
D.3.6 REGULAR PSRS
Proposition D.18 (Regular PSRs are B-stable). Any Gperreggular PSR admits B-
representation (B) such that for all < h & H. |B & ||] where K₁ is any core matrix of Du (cf. Example 8). Hence, any Oearrr PSR B-stable with Ag & A byproduct, we show that the B-representation also has Rg & a AU
Proof of Proposition D.18. By (Zhan et al., 2022, Lemma 6), the PSR admits a B- representation such that rowspan(Bx(o, a)) = colspan(Dn-)) In the following, we show that such a B- B-representation is indeed what we want.
Fix matrix Ka-1 of Da-1, and suppose that Kn-1 [q(T)-1)... 9((%-1)] with d rank Dr.. Then it holds that
[B max
Σ T(Th.H) x [BHa(TT))zz)
Th:
Σ (TTaN) x Bra(TTa)) Kn- 1
max
Th:H
max
π (ThaH) x
Th:ff
d
max
K 1-
x Σ (ThcH) x
Σ
Thit
Notice that BHsh (Th:H) ((7 P( (T/-1) by Corollary D.2, and hence for any policy x, we have
Σ (TeH)) (
p (T 1
Therefore, it holds that [B < K / for h E [H] and any core matrix KA-1 of Dr-1-
Similarly, we can pick core matrix Ka-1 such that [|,% & aper then
Σ [1B = Σ
Bu(o, (k.
< & K
1/ & Oppr
Cppt AUA ||]||
o,a
0,a
This completes the proof.
D.4 COMPARISON WITH WELL-CONDITIONED PSRS
Concurrent work by Liu et al. (2022b) defines the following class of well-conditioned PSRs. Definition D.19. A PSR is neeell-condiiooee if admits B-representation such that for all h [H], policy a (that starts at step h), vector x E RRt,, the following holds:
Σ x (ThaH) [BH(H aH) ..,,,,,,,,, (o an.ar
|
(30)
?
1 Σ π (anlon) x (1) ) 7 ||l|
(31)
OK.9g
By (30) and the inequality |=]1 & VUa | (Lemma D.6), any 7-well-conditioned PSR B-stable PSR with Ag & -1 Plugging this into our main results shows that, for well- conditioned PSRs, OMLE, EXPLORATIVE E2D and MOPS all achieve sample complexity
(dAU H2 log
222
27

---

Published as a conference paper at ICLR 2023
which is better than the sample complexity ò ( log.Ne/>"=" achieved by the analysis of OMLE Liu et al. (2022b). Also, being well-conditioned imposes the extra restriction (31) on the structure of the PSR, while our B B-stability condition does not.
E DECORRELATION ARGUMENTS
In this section, we present two decorrelation propositions: the generalized é2-Eluder argument (Proposition E.1), and the decoupling argument (Proposition E.6). These two propositions are im- portant steps in the proof of main theorems (Theorem 9, 10, H.4, H.6). These two Propositions are parallel: Proposition E. is the triangulartto-diigonal version the decorrelation used in the proof of Theorem 9 (sce Appendix G for its proof), whereas Proposition E.6 is the expectation-to expectation version of the decorrelation used in the proof of Theorem 10 (see Appendix for its proof).
E.1 GENERALIZED f2-ELUDER ARGUMENT
We first present the triangulartto-iiagom version of the decorrelation argument, the generalized (2-Eluder argument.
Proposition E.1 (Generalized Eg-Eluder argument). Suppose we have sequences of vectors
(DE,d Rd,
(y43s)) Rd
where I, R are arbitrary (abstract) index sets. Coniid (fa IRd R]
fx(x) = max Σ
(x.Ukk..r)l
PER
Assume that the following condition holds:
Σ
Bing Ei [f((x))) Bk.
Vk e [K].
where (gs A(I)) [e( is a family of distributions over I.
Then for any M > O, holds that
k R3 R
M B [f((Te))] 2d 2d(MaN + Σ Br log 1
44 [K].
d M2
where R2 max Ei~ge [I 11 Ry maxk Eg 11
We call this proposition "generalized Eluude argument" because, when I is single element set and Bg 3, the result reduces to
if Sa(r)) < B, for all & [K], then Elf(aa) < <O(vBB)) tcb
(32)
which implies that the function class {.fe) has Eluder dimension δ (d). In particular, when [fk]ke[K] is given by (x) = Kyt. (32) equivalent to the stan- dard Eluder argument for linear functions, which can be proved using the elliptical potential lemma (I (Lattimore& & Szepesvári, 2020, Lemma 19.4).
long max, [ff((x))
In the following, present corollary of Proposition E.1 that more suitable for our applications.
iu al. (2022h) only asserts polynomial rate without spelling out the concrete powers of the problem parameters. This rate is extracted from Liu et al. (2022b, Proposition C.5 & Lemma C.6).
28

---

Published as a conference paper at ICLR 2023
Corollary E.2. Suppose we have sequence of functions (fx :R" - R)
fu(z)
max
Σ
Ka,yk.nn Bkidi))
reR
which is given by the family of vectors
C R". Further assume that there
exists L >> O such that fa( & L ||>||1-
Consider further sequence of vector (ri) satisfying the following condition
Σ E. a- g. [f(()))) & Bk. Ak [K]
and the subspace spanned by (II) has dimension at most d. Then it holds that
A Bi [f([+:]] [e-aa) & V 4d Ad(#++
Σ Be 1 log (1 kdl. max Imal)),
vk E [K].
We prove Proposition E.1 and Corollary E.2 in the following subsections. Remark E.3. the initial version of this paper, the statement Corollary E.2 was slightly different from above, which states that under the same precondition,
A E. [f(xx))] &
4d k
B1 Σ t-1
log (1 kdLna(X)),
vk [K],
where matrix X = [xiliez E R2=z and
xx(X) min (1) [11, F2l1, X F2, Raxd F2 RddxI.
After our initial version, we noted the concurrent work Liu et al. (2022b, Lemma G.3) which essen- tially shows that Kx(X) & d max, |z,]|| by elegant argument using the Barycentric spanner. For the sake of simplicity, we have applied their result (cf. Lemma E.5) to make Corollary E.2 slightly more convenient to
We also note that, in the initial version of this paper, in the statement Theorem 9, the sample complexity involved log factor log(1 KdAg Rgna), where Ka max, Ki(( Dx), which we then tightly bounded for all concrete problem classes terms the corresponding problem parameter. The above change makes the statement slightly cleaner (though the result slightly looser) by always using the bound K, & dUA. The effect on the final result is however minor, as the sample complexity of OMLE only depends on Ka logarithmically through e, and the sample complexity of MOPS or EXPLORATIVE E2D does not involve this factor.
E. PROOF OF PROPOSITION E.
To prove this proposition, we first show that the proposition can be reduced to the case when n = 1, extending the idea of the proof of (Liu et al., 2022a, Proposition 22). After that, invoke certain variant the elliptical potential lemma to derive the desired inequality.
We first transform and reduce the problem. For every pair of (k, i) [K] I, we take r r(k,, i) arg max, Σ Ka j.)),,,, and consider
De...jj
Veej. (K.)) v(k,i,)) e [K] I [n]]
We then define
i(k, [K] I. Under such transformation, it holds that for all k,k i,
DR. Σ Meii sign (Te.., KR.))
Ko,,,, T..>
Σ Kos (t.j. max Σ Keess Be.j.l fe(s),))
29

---

Published as a conference paper at ICLR 2023
(o,,s,Kk.r) & max Σ
K KTe,ir fa(ar,,)
1 & Ry.
3
Therefore, it remains to bound D M a Bingn Kiec Br, under the condition that for all & [K].
Eeck Ei [max./ (Zr,i Vx. & Sx.
To show this, we define D, == Binge [1, and take do
M2 Vs == Aod + Excch Lr. Then
R
M Bi-q. Koti Da min M, Bing [1 1100.0l112]
min M, / (312 + B.) 1 v.-
(M2 + Br) min { I, Li |
k Σ B1 ( (Σ min { 1, Bi-ag L 11)
< {KM +
where the second inequality is due to the fact that for all (1,
1...:lli = do 10 + Σ Ee-ag KT Dt,ii & M + Br.
Note that
Es-qc | 1] Birae tr Vo P ;)] = (vV 2 vz
In order bound the term > minf 1, tr( Vi lemma, which generalizes Lattimore Szepesvári (2020, Lemma 19.4).
1/2 4b V. 1/2)3. we invoke the following standard
Lemma E.4 (Generalized elliptical potential lemma). Let { 1ddd [R[[K] be sequence of symmetric semi- remi-positive definite matrix, and Vv == dol + Leen Do where do > O is fixed real. Then holds that
K
& 2dlog (1+ Ee tr(Ok)
min (1, tr Vi $ V +)}
1+
dda
Applying Lemma E,4 and noticing tr( tr(0.) Eing [ [1 R2g the proof of Proposition E. is completed.
Proof of Lemma E.4. By definition and by linear algebra, we have
V V/ [ i VeVe & vv and hence det(Vk+.) = det(Vv dett + V t V/ t). Therefore, have
1, V/ 1 VV $)} x
Σ 2 2oo (1 tr
tr(ve (Ve vo t))
min
(1 Vv 2 2 v
log det
=2
[log det( Vk+1) log det (Vx)]
del del(Vx+1)
2 log
Vo))
30

---

Published as a conference paper at ICLR 2023
where the first inequality is due to the fact that min {1,u} inequality is because for any positive semi-definite matrix X, it holds det([ + X) > 1 tr(X). Now, we have
2 2llo(1 + w), Vu 0. and the second
tr( ( dlog (No do + - (r(
log det(V & log
d
d
which completes the proof of Lemma E.4.
E.1.2 PROOF COROLLARY E.2
Let us take a decomposition z; = Fu,Vi E I, such that || & and ||F'11-11 & max; |
(the existence of such decomposition is guaranteed by Lemma E.5). We define fx R R as follows:
Fa(1): = fa(Ft) max Kv, F FT.FFBYA. yk..Tr)-
By definition, (v:) fI;);;) and hence our condition becomes
Σ Eiin (o:)
Bk,
vk [K],
bck
Then applying Proposition E.1 gives for all & [K].
Σ 1 ^ E. g. [fc(x:]] Σ
a Ei [(())) $1
2d 2d(k+
k+
Σ 31
log (1 + kd-1 -.. -RGR))
t-1
where R2 & max; 11:12 & Vd. and
d Σ
R1 = max
F ye.dell2 & max
Σ
F vkrf.r11
$ max
Σ
e
F
yk.jor
h.r
R,r
m-1
d Σ m=1
max R.
KFem: Me.jjr)
max Σ
(m
L Fe & FdllFi & dL max ||aall
Therefore, we have
log (1 kdd R2 log (1 ked L2 max [1x:1?) 2 log(1 + kdL max ||>;]]]),
which completes the proof of Corollary E.2.
The following lemma is immediate consequence of Liu al. (2022b, Lemma G.3).
Lemma E.5. Assume that sequence of vectors {2t]veT c I²" satisfies that span(æ; i I) Then. there exists a sequence of vectors
has dimension at most d and R max, ||=|| for)ezz = & and matrix Raxd, such that 2; Fu, Vi and |ulloz & 1, & R.
Proof. Without loss of generality, we assume that span(x; i I) has dimension at most d. Then X is a d-dimensional compact subset of R" and we take Barycentric spanner of X' to be {wi, wa). By definition, for each E Z, there exists weights (ocg ) Isjed such that ai E [--1, and Σラ OsyWy. Therefore, can take v, [aus]esee Rd and F [[1, ",, wa] paxd and they clearly fulfill the statement of Lemma E.5.
E.2 DECOUPLING ARGUMENT
Proposition E. can be regarded a triangular-to toruulaa-----dggonll decorrelation result. In this section, we present its expectation-tt--xxeeaaai analog, which is central for bounding Explorative DEC.
31

---

Published as a conference paper at ICLR 2023
Proposition E.6 (Decoupling argument). Suppose have vectors and functions
{ai)ier = IR", (So R jee
where θ, I are arbitrary abstract index sets, with functions fo given by
fo(x) max Σ Ko.
Vx E R"
where (ye.s.r (0.r) (..).))) = T is a family of bounded vectors in RR. Then for any distribution Ia over θ and probability family ?goboco c: A(I).
Ro-gBring [Fo(x:)] & Vdx Ro Bi [f(
where dx is the dimension of the subspace of Th" spanned by (xi)ter.
Proof of Proposition E.6. By the assumption that (yo.j.r(005.. is a family of bounded vectors in Rd there exists Ry op such that sups.r Ej=1 |lvo & Ry. We follow the same two steps the proof of Proposition E.I.
First, we reduce the problem. We consider r*(,,) i) arg ma Eg Krt, v0. and define the vectors
To,s.j = (0.j.++(0.5)-
39,1 Σ sign (Iz, No...) De...
Then for all i E I, E.
(ot, Do.1)
Σ Ko,, Ker, = Σ (2.. fo(x)),
(33)
Kxn, 1o w>
Kar No x3))
< fo(
and 10,.122 & E, (100.).+ & Rg. Therefore, it suffices to bound Es-nBBnge IK do xa].
Next, we define Φx X Ba- Bi-go [arar]] with À 0. Then bound the target
Eg Eg ( ;0 s Bp [xill 110o..llex.
Eg - Bsngo 1 |2:12211 1
1/2
Ee Esnga 1ie,1 1 sx
1
1/2
The first term can be rewritten
Eg Eq Bi-go
|x; 1
Beg,EEi-oo tr ④ 1/2 x, Φx 1/2)
=tr Φ 11/22
B Bi-qu [ + 1/12
1/2 20 2 1/2)
rank 2o) & dx.
The second term can be bounded as
Ex 11 12,
Evr~gEEe Ev gor 1 11e,
=EEg - SiE Ll Eo Bin
Kei, x.?"
Ilūor xx1??
XEE Bu 11:o0.11 $ <Evr, E, b [ + +RR
Eg - Eo E, Bingo
Kon Vor
where the last inequality is due to (33). Letting X 0+ completes the proof of Proposition E.6. n
32

---

Published as a conference paper at ICLR 2023
F STRUCTURAL PROPERTIES OF B-STABLE PSRS
In this section, we present two important propositions that are used in the proofs of all the main theorems (Theorem 9, 10, H.4, H.6). The first proposition bounds the performance difference of two PSR models by B-errors. The second proposition bounds the squared B-errors by the Hellinger distance of observation probabilities between [wo models.
F.1 PERFORMANCE DECOMPOSITION
We first present the performance decomposition proposition.
Proposition F.1 (Performance decomposition). Suppose that two PSR models 0, admit { Oh, Jnoo. 4o) and {[B), (on, an))n,on., Lb) as B-representation respectively, and suppose that (hehe and {B H.h hee[ are the associated B-operators respectively, Define
EB E0.h (Tn-1)
2 max Σ T(anlon)
B B9
(B) and (o, an)) q (Th-1))
B c - _
8g,0 ;
Then holds that
H1
DTV (PT, P2)) E6,0 + Σ E Ei (T--1))
where for E [H], the expectation Eg,- is taking over Th-1 under model 0 and policy n
Proof of Proposition F.I. By the definition of B-representation, we have (T = x(TH) x B (TH) 9 for PSR model 0. Then for two different PSR models 0, 8, we have
Pī (TH)
<T(nn)
B
(T
)
B B (T.H))
= =T(nn) (TT(H)) q
0
H Σ
+ T(TH)
B (
B (on, an) - (on an) Bí (
= =T(n)) B ( 9 a
((ma)) x B (T4 (on an) (o,, an) ) (Th--) x Pg (Th-1),
where the last equality is due the definition of B-representation (see e.g. (15)). Therefore, have
(T( 1- (TH))
< Σ (TT) x Ba B) - -
Σ Σ
x ((Ta)))
2 TH
TH h-1
x
Hihh (Th+1:H)
B (on, an) (o and (Th- x (Th-1)
HH: i
+
1
ps (Th-1)
2
h-
x max
Σ
T(anlon)
BBiion an) - Bo an)) (
.0
33

---

Published as a conference paper at ICLR 2023
H
= E0,0 +
Σ B c
(Tn(T)-1)
where the last inequality is due to the definition of Eg,,, and E0 (Tn-1)-
F.2 BOUNDING THE SQUARED B-ERRORS BY HELLINGER DISTANCE
In the following proposition, we show that under B B-stability or weak B-stability, the squared B- errors can be bounded by the Hellinger distance between P tt and P Here, for policy E IT and h E [H], Th.exp is defined as
h.eexp t Unif(.A) 9++1 Unif(UA,--1)
(34)
which is the policy that follows क for the first h - 1 steps, takes Unif(A) at step h, takes an action sequence sampled from (ni,((A,, step h-+ 1, and behaves arbitrarily afterwards. This notation consistent with the exploration policy in the OMLE algorithm (Algorithm 1).
Proposition F.2 (Bounding squared B-errors by squared Hellinger distance). Suppose that the B- representation of 0 is Ag-stable (cf. Definition 4) or weakly Ag-stable (cf. Definition D.4), then we have for h [H -1
c8 B0
(Ta & AAAAUA [DA (IP aep 1oo) + D4 (177 Loopp 1 1p
and
c Ex,x
88 (TH
< 2(Ag + 1) L1o , p
(2,00 < AgU (1P7 .157
where E%, (Tn-1) and E0,0 are as defined in Proposition F.I.
Proof of Proposition F:2. We first deal with the case e [H]. By taking the difference, have B (on, an) - (o an) q (m--1)
(Th-1) max Σ ((TaHt)
Thil
Σ (THCH)
(Tua)) ( (I (A 9 (T(-n_))
max
Thil
Σ (TW.H)
B (T (B (allon (Tn-I) Ba an) an) (T--1)
+ max
- -|89na (q((T)-1) q (Tn-1)
+ max Σ Oy .Ap
Tn(anlon) Baanni (Br (Th-)) (o,, an (f (T--))))
We now introduce several notations for the convenience of the proof.
1. For an action sequence of length ((a). P(-17--1, do(a)) stands for the distribution of Opsh conditional on 7h-1 and taking action a for step f to step h + ((a) -
Given a set e of action sequences (possibly of different length), punit(o stands for the distribution of observation generated by: conditional on 7h-1, first sample a Unif((AA,)) then take a and then obscrve o (of length ((a) + 1).
By the definition of Hellinger distances and by the notations above, we have
D
p Unif( (f)) (+/Th-1), Unif( af) (-17m-1))
Σ
do()))))
of
as.af
(35)
Next, we present lemmas whose proof will be deferred after the proof of the proposition.
34

---

Published as a conference paper at ICLR 2023
Lemma F.3. Suppose that B is weakly At-stable (Ag-stable is sufficient condition), then it holds that
Hith (q -
-aa-)))-((mm-))) (m(m- & 2AB MA (I (1Im,,)), ( (-IT-)))))))))
Lemma F.4. Suppose that B is weakly Ag-stable (Ag-stable is sufficient condition), then it holds that
Σ Tn(anlon) 19r:0 (B ond (o, (n
(P ( (-Im-)))))))))))..))))))))))1")) (aata-i)..eaatttaaalllluuaaaa (-1Th-1):
< 2ABB A AlHAn++|DH
Therefore, first consider the case e [H 1]. Applying Lemma F.3 and taking expectation with respect to T4-1, we obtain
18 ,
1
(7 q (Tm-1)
M Bø.n Di (ppnirrcaaa (-17--1,, p
(17R-1))
4
(36)
MAn Dj (PToN UnifiLeA, vn I Unil(te))))
8AA [ D (1P5--Lun (oAALLEND)
where the second inequality is due to Lemma C.I, and the last inequality is due to importance sampling. Similarly, applying Lemma F.4 and taking expectation with respect Th-1, 1, have
2
Σ
n (a |B9rr.. BB,(0,, an (Tn-1) By an and (Tm-
max 7h
D (pto, p Untt))aa())))
<8A A [
SA3A [A
D (177h.mmp , poTTA..p)))
The proof for h [ 1] is completed by noting that (x+ < 2x +22 and UA max, MA For the case h = H, note that by Corollary D.2,
max Σ ( (on)
(Bz (TH- - an)
Σ
(P(OHITH-1) Pa(oo)/H-))) 2Dμ (P
and by Lemma F.3 it holds that
B (T((T=L) - (((H--1))
22A | DH
(p Uniif(laa.)) ( Unit((AA..)) (1TH-1))
-2ng DH (P)((Ta-))
where the equality is due MA, f only containing the null action sequence. Therefore,
e (TH-)) (AB DH (I 1 11.0))
and applying Lemma C. completes the proof of the case h H. The case = 0 is directly implied by Lemma F.3:
Ba (a) - 4 < 41 [M4,1 D2 (pror Unif((aa.) p Uni((((a)) (80-)))
= 4A M4l11
D oo po
Combining all these cases finishes the proof of Proposition F.2.
35

---

Published as a conference paper at ICLR 2023
We next prove Lemma F.3 and F.4 that were used in the proof of Proposition F.2.
Proof of Lemma F.3. By the weak B-stability as in Definition D.4 (B-stability is also sufficient, see Eq. (19)), we have
|59.. ( - ((()-)) $2 (Ta + (((mn-)))
(a / -----V/aa VPP(Tn)))
where I-lm is defined in Definition D.3. By the definition of q (T)-),, for in (o, E Uh. have
qm( a) = Po((tlla-1) Po(Onsh+i))1 o07)),,
Hence, we have
(Te--ii)
max max
Σ
T(, a) x = 0
(o,a)et4,
max max max (T Th-1) 1,
T'clh. *
where (T) stands for the probability that some test in T is observed under 0, æ conditional on Th-1- Similarly, we have q (T) 1. Therefore, have
1 A B
(9 (Th-1) q ( [a (T
4
Σ
Σ
IVP - dol())
aEllA (o,,))El
Σ
Σ
IVPo - dooll)
a. oEOI(a)+1
Σ
aE
MA D (p.
Uniff(MA n (.Im Unif(LAs, (-1mh-))-
where in (i) we include those o such that (o, a) may not belong to uo 1 into summation, (ii) is due to the definition of IP(1I7/-1, do(a)), and (ii) follows from importance sampling (35). This completes the proof of Lemma F.3.
Proof of Lemma F.4. Similar to the proof Lemma F3, we only need to work under the weak B- B-stability condition. By Corollary D.2, for th+1 (o, a) e Uh+1, it holds that
(o, (T)-))()) a) = (o(( Po((oTT-1)) Polo, a, 11-1)7n-1),
and hence
((( T'uli11
Σ ((t+1)) Po Po(o)Ta-11)
max max
UN+IET
max max (T x Pa(o/Ta-1) < Po(o)ta--).
T'ul.11
where P. (h-, 0, a) stands for the probability that some test in T" is observed under 8, प con- ditional on observing Tr = (Th-1, o, a). Similarly, we have a)
< po( Therefore, by the weak B-stability as in Definition D.4 and combining with the inequalities above, it holds that
B () (y (
(Tn-
- (P, /112
$ 2B (o o(7a-1)
Σ
36

---

Published as a conference paper at ICLR 2023
Hence, we have
Ag max
Σ (n(anlo))
B4 (o, (x)aa(Tx-1))) - B (on, am))
an
PP - (o, t|ma 2 1/2
max
I(alo)/
Pon o|Tm-1)
Σ
vPo
teldx+1
- (Polo-/o 2
p112
Σ v 22 + Pol(on = olmm-1) Σ Σ
1E
2 2/1/2
2
Σ
Σ
|VPs - (a,,
teld++1
IIPo - a)) 271/22 2
2
Σ
(o.a)eHh
(i81)
ElvVo Pallona--t))+ (000 2212 2112
&
2
Σ
(x
(10) 2 A|MAN,+I
(p (punit(Alouaiiitanan) (.1T--1), Paiia (-1m-1)))
where (i) is due the fact that max Ene T())x(a)= (E. x(a))) (ii) is due Cauchy- Schwarz inequality, in (iii) we include those such that (o, may not belong to Uh+1 into sum- mation, (iv) is due to (35): Uni((A) Unif(Ua,,6.11 is simply the uniform policy over A x UA This concludes the proof of Lemma F.4.
G PROOF OF THEOREM
We first restate Theorem 9 follows in terms of the (more relaxed) weak B-stability condition.
Theorem G.1 (Restatement of Theorem 9). Suppose every E θ is Ag-stable (Definition 4) or weakly Ag-stable (Definition D.4), and the true model 0* E θ with rank desR & d. Then, choosing (1)1/K for some absolute constant C > 0, with probability at least 5, Al- gorithm outputs policy nout A(lI) such that V, Vg- (fout) & as long as the number of episodes
3
T T-KHa 3 OdAAUAAHH
(37)
where := log (1 AdUAAgRs) with Rg == max; (1. max| Σo,a [B)oo))))l]]
The proof of Theorem G.1 uses the following fast rate guarantee for the OMLE algorithm, which is standard (e.g. Van de Geer (2000); Agarwal al. (2020)). For completeness, we present its proof in Appendix G.I.
Proposition G.2 (Guarantee of MLE). Suppose that we choose 3 > 2 Ne(/)) log 1/8) +2 in Algorithm 1. Then with probability at least 1 - 6, the following holds:
(a) For all 1 [K] 8* E Oh:
(b) For all k E [K] and any E Ok, it holds that
H
P Thop
D
< 28.
We next prove Theorem G.I. We adopt the definitions of E (Th-1) as in Proposition F.I and abbreviate E &.
cg' We also condition the success of the event in Proposition G.2.
37

---

Published as a conference paper at ICLR 2023
Step 1. By Proposition G.2, it holds that 8* 6. Therefore, (x=())) V., and by Proposition F.1, we have
Σ V. - Va & (Vo-(T)) - VT-(TT))
Drv
poot paa') (ot
1Λ
εt, +
Σ
En E (Tn-1)
(38)
h=1
1 EnEio +
Σ
a
E
4=1
On the other hand, by Proposition F.2, we have
H-1
(07,0)² + M E. (E AUA
Σ
D 1
4=0
Furthermore, by Proposition G.2 we have
k-1 H
Σ
Σ
D
Th p"hceop .r
< 28.
1=1
h-0
Therefore, defining SI,A := Σick E [ (7)- combining the two equations above gives
H
H ΣΣ
BKA
E. < 1=0k<h
Ak E [K].
(39)
Step 2. We would like to bridge the performance decomposition (38) and the squared B-errors bound (39) using the generalized f--Eluder argument. We consider separately the case for h and h E [H].
Case 1: 0. This follows directly from Cauchy-Schwand inequality:
1/2 kk Σ IA (Eto))
&
Σ L E
& Vk(Br. + 1).
(40)
Case 2: h E [H]. We invoke the generalized Ez-Eluder argument (actually, its corollary) in Appendix E.1, restated as follows for convenience.
Corollary E.2. Suppose we have a sequence of functions (Sa R R]
fa(z) = max
Ka, Ka,uk...).
nER
which is given by the family of vectors (yk...r www.ar//....meeeeiiiee R". Further assume that there exists > such that fx(z) & L ||=|1--
Consider further sequence of vector (Iz) satisfying the following condition
Σ E ( & Skr
Vk [K],
and the subspace spanned by (xx)tez has dimension most d. Then it holds that
Σ I A BA & &
ad(k= (k Σ B,) log (I kdL max |x:
Vk e [K].
We have the following three preparation steps apply Corollary E.2.
38

---

Published as a conference paper at ICLR 2023
1. Recall the definition of Ei,, (Th-1) as in Proposition F.1 (in short 1
(Th-1) Eje, (Th-1)),
1
(T 2
Σ (TTh:)) B (T++1.))) (ox an) (on, q'' (Ta-I)]:
where we replace superscript A of by for simplicity. Let us define
Uk.j. = T( (ThTh))) Bia (Th+ B af)) Bj(o% ] e R
1
2
where (Th.h (on, ah.' ,H, (0H,HH)) a=}}}= an ordering of all possible Th.H (and hence n (OA))~h+]) ), is any policy that starts at step h. We then define
fa(x) max Σ #2
e E
follows from definition that E (T--)= = (Tn9"(T
2. We define H; q' (Th-1)) E Rlua,, where (Th-1): J is an ordering of all possible Th-1 E (O x A)4-1 Then by the assumption that 0" has PSR rank less than equal to d, we have dim span(a;; i I) & d. Furthermore, we have |x:|| & UA by definition.
3. It remains to verify that fa is Lipschitz with respect to 1-norm. We only need to verify it under the weak At-sbabilyty condition. We have
1
fx(g)
|5 H. max
Σ (alo) | a)
0,0
< 2AB |///1 + 2A max
T(alo) [o, a)all
< 2A |/ 1 + 2A Σ
B (o, 1 |ql1 < 2Aa(Ra + 1) ||ql]
0,0
where the first inequality follows the same argument as (35); the second inequality is due to B- stability (or weak B-stability and (21)); the last inequality is due the definition of B. Hence can take I 2A RB + 1) to ensure that fa(x)) & T. ||
Therefore, applying Corollary E.2 yields
k 4e kd + Σ Br
Σ
E (T)
(41)
1=1
where - log (1 + 2kdU AA Rg + 1)). This completes case
Combining these two cases, we obtain
(1) Σ (V. - Vo-
"
x
Σ
1 A E
+
Σ
Σ
1 a E. (T-n(T))))))
#=1
[-1
1/2
1 k(KKD + 1) 2Vi.
Σ
kd + d Σ
Ben
h-1
1=1
(1 (k(HId+))+ d
Σ
Brnh
h-
(181) (10)
(VAAAUAA kBC
where (i) used (38); (ii) used the above two cases (40) and (41); (iii) used (39). As consequence, whenever > OAAdAA H Bi/E2), we have n (V. Vo- (T(()) & e. This completes the proof of Theorem G.I (and hence Theorem 9).
39

---

Published as a conference paper at ICLR 2023
G.1 PROOF OF PROPOSITION G.2
For the simplicity of presentation, we consider the following general interaction process: For / =
1, T, the learner determines म², then executes H' and collects trajectory f² Pa- We
show that, with probability at least 8, the following holds for all e [T] and @ O:
(P Pp- & - 2lg.2oogN + 2log(1/)) + 2,
(42)
where Lg is the total log-likelihood (at step t) defined as
(( Σ
Pg (F*).
Proposition G.2 is implied by (42) directly: Suppose we choose 3 2 2 log 22 On the event (42), by the non-negativity of squared Hellinger distances, have for all k E [K] and 0 E θ that
Σ
log (T)
Σ
log 1o (T) - 3,
(F.7)ED
(HTT))D
where D is the dataset of all histories before the outer loter of Algorithm enters step k. Taking max over E on the right-hand side, we obtain l* O², which gives Proposition G.2(1). Furthermore, for k [K] and 0 E @&, (42) implies that
k-1 H-1
Di
P
P
log (T) (x,F)eDK
Σ
log (T( (H,F)EDE
Σ
< max
Σ
log P (T)
Σ
log P (T) + 3 28,
(D
(a,r)eDo
which gives Proposition G.2(2).
In the following, we establish (42). Let us fix a opttmiiiist covering (i,, Qy) of O such that := |9 = (1/T) We label (Pao)asee, by P,,.... Pn.. By the definition of optimistic covering, is clear that for any 0 E O, there exists [n]] such that for all n, T, holds that (T) > (T)(T) and (iP 17(1) < 1/T2. We say 0 is covered by this E [n].
Then, consider
P (Tt) e log p (7t)
EE [T]. ie [n].
By Lemma C.3, the following holds with probability at least
8: for all t [T], i [n].
1
Σ e + log(n//)))
Σ
Eg
exp
60
).
2
where E, denotes the conditional expectation over all randomness after 7 has been determined. By definition,
Tor (7t)
par
(T)
E
exp
E,
= E
Eyagt
Σv (T)
pat g-
Port
Par (7t)
pa-
Therefore, for any 0 E θ that is covered by i [12], we have
log E, exp
1 4
>1
Σ
p (T)
2
(ViPF()) - v. 105 (T)
Σ
1of (P (T)
Σ
p+ (T)
40

---

Published as a conference paper at ICLR 2023
Algorithm 2 EXPLORATIVE E2D (Chen et al., 2022)
Input: Model class θ, parameters 7 > 0, m E (0, 1/2). An 1/T opT-iitiist cover (IP, θo).
Initialize 1 Un).
2: for t = 1,..,, do
3: Set Vexp--Put arg min (Pa Vif (pexp: Pout), where P2f² is defined by
Vi (Pexp: Pout) == sup Ex Pout Pout (TT(TT)) Vo( 71E Pexep Bor [D 1P7, )] Ae
4: Sample n² ~ Pixp: Execute r' and observe T".
5: Compute 2 E A(0)) by
(0) xo (²)) exp P))))
Output: Policy Rout : T 1
ΣJ
2
1/2
1
Di [ (T= pf- (T= -= =.))
Σ P (T) -V (P (T)
1 DH (pg' (T= pp. =
| (-) pp ()) 1/2
1 DH B2 .)
T
where the first inequality is due to - log 3 1- z; in the second inequality use the definition of Hellinger distance and Cauchy inequality; the third inequality is because ( (Vi- VØ)² & |x yl for all x, y Rgo: the last inequality is due 0 e θ is covered by some e [n]. and for such i, E. E fx(0)) L.(0); therefore, holds with probability 1 - å that, for all A E t [T].
assumption that is covered by i. Notice that every
ク/ (C,(0)) - (0) + log(n/0) +
DH
p P
==1
Plugging in n = Ne(11/T and scaling the above inequality by 2 gives (42).
H EXPLORATIVE E2D, ALL-POLICY MODELIESTIMATION E2D, AND MOPS
In this section, we present the detailed algorithms of EXPLORATIVE E2D, ALI.-POLICY MODEL-- ESTIMATION E2D, and MOPS introduced in Section 4. We also state the theorems for their sample complexity bounds of learning s-optimal policy of B-stable PSRs.
H.1 EXPLORATIVE E2D ALGORITHM
In this section, we provide more details about the EXPLORATIVE E2D algorithm as discussed in Section 4.2. The full algorithm of EXPLORATIVE E2D is given in Algorithm 2, equivalent to Chen al. (2022, Algorithm 2) in the known reward setting (D becomes D since we assumed that the reward is deterministic and known, so that the contribution from reward distance in D becomes O). Chen et al. (2022, Theorem F.I) showed that EXPLORATIVE E2D achieves the following estimation bound.
Theorem H.1 (Chen et al. (2022), Theorem F.1). Given an 1/T -otoiiimiii cover (i,, Qa) (c.f. Defi- nition C.4) of the model class θ, Algorithm 2 with n 1/3 achieves the following with probability at least ō:
10y
V, Vo- (fout) & edec, (0) +
[log 10ol + 2 2log(1/8) + 3].
T
where edec, is the Explorative DEC defined in Section 4.2.
41

---

Published as a conference paper at ICLR 2023
Algorithm 3 ALL-POLICY MODEL-ESSTIMATTON E2DnC et al., 2022)
1: Input: Model class é,, parameters 7 > 0, f (0, An L/TT-optimistii cover (I", Oo).
2: Initialize 1s Un).
3: for t = 1, do
4: Set (Pexp= Mouc) arg (Perp (oon (ET)) "me,7 (Pexp: Mont), where
Vi' me,y (Pexp= Mout) = sup Eg-poo DrV (Pă. (p) Po]] - BB pap Būen Ae *e
Dj P.j p ].
5: Sample n' Pexp- Execute x' and observe
6: Compute y +2 (00)) by
(0) co (0) exp (nl (o''")
(7¹)
7: Compute Nout DZ
-1=1 P e A(H).
8: Output: 0 = arg mingee sul E BB-pou DrV (P) P.).
As we can see from the theorem above, as long as we can bound edec.,()); we can get sample complexity bound for the EXPLORATIVE E2D algorithm. This gives Theorem 10 in the main text, which we restate as below.
Theorem H.2 (Restatement of Theorem 10), Suppose a PSR class with the same core test sets (Un He and each 0 e θ admits B-representation that is At-stable (c.f. Definition 4) or weakly Ag-stable (c.f. Definition D.4), and has PSR rank dpsR Then
(e) AddAUAAHHT AAgH
Therefore, we can choose a suitable parameter y and an a /pT-miiiistt cover (P,, Ou), such that with probability at least 1 - 6, Algorithm 2 outputs policy Rout. E (III) such that V. Vo- (Rou)) & E, as long as the number of episodes
T = O(AAUAA@FFFMogNNN(((71/)
The proof of Theorem H.2 and hence Theorem 10 is contained in Appendix 1.2.
H.2 ALI.-POLICY MODEL-ESTIMATION E2D FOR MODEL-ESTIMATION
In this section, we provide more details about model-cstimation learning in PSRs as discussed in Section 4.2. In reward-free RL (Jin al., 2020b), the goal is optimally explore the environment without observing reward information, so that after the exploration phase, a near-optimal policy of any given reward be computed using the collected trajectory data alone without further interact- ing with the environment.
Chen al. (2022) developed ALL-POLICY KODEL-ESTIMATION E2D unified algorithm for soaaadd-fee/mmoeleeeeimmaaa
learning in RI, and showed that its sample complexity scales with a complexity measure named All-policy Model-Estimation DEC (AMDEC). The AMDEC is defined amdoc., (+) : (UP)ee(e)) amdoc, P), where
amdec, (O, ft) == Peep A Mome (II) 8 Rell
inf
supsup Eg Home DrV (P). yE, Peep Ban
D P P.
(43)
The ALL-POLICY ESTIMATIO E2D algorithm (Algorithm 3) for a PSR class θ is given follows: In each episode t E [T], maintain distribution μ² A(O,) over 1/T-optimistic cover (I, Qo) of (c.f. Definition C.4), which we use to compute an exploration policy distribution peep by minimizing the following risk:
(Wesp: (ou))
arg min
sup Eg- Spm [Dvv (PS PT] 7B..-P.. BBr-pt Di
P.T IP
)
(Pexp (EA()))(((XXXXC dc0 #ell
42

---

Published as a conference paper at ICLR 2023
Then, we execute policy n² Pexp- collect trajectory r', and update the model distribution using the same Tempered Aggregation scheme as in EXPLORATIVE E2D. After I episodes, we output the emipirical model 0 by computing Pou
- Mout A(O) and then projecting it into Q i.e.
arg min sup Eg BBpppom [Drv (Fo P.)]
dee
well
Chen et al. (2022, Theorem H.2) show that the output model Q of ALL-POLICY MODEL- ESTIMATION E2D has estimation error (measured in terms of the TV distance) that scales as andecy.
Theorem H.3. Given an L/T 1/T-optimistic cover (P, 4a) (c.f. Definition C.4) the class of transition dynamics O, Algorithm with 17 = 1/2 achieves the following with probability at least 6:
60y
sup DTV [
pp.
6amdec, (0) + T Dog 100l log(1/6) + +3],
where amdec,, the All-policy Model- Estimatiin DEC as defined in (43).
We provide sharp bound the AMEDEC for B-stable PSRs, which implies that ALL-POLICY MODEL-ESTIMATION E2D can also learn them sample-efficient efficiently in a model-cstimation manner.
Theorem H.4. Suppose θ is a PSR class with the same core test sets (Un (E and each 0 E O ad- mits B-repressetation that is AB-stable (c.f. Definition 4) or weakly Ag-stable (c.f. Definition 1).4), and has PSR rank dpsR= & d. Then
amdee,,(0) & 6dAU 6dAU^AHH2/7
(44)
Therefore, we can choose a suitable parameter and an 1/T L/T-optiiistic cover (P, Ou), such that with probability at least 8, Algorithm 3 outputs model 0 θ such that sup; Drv [P P.r as long as the number of episodes
$ e,
T > O
The proof Theorem H.4 contained in Appendix I.3.
H.3 MODEL. BASED OPTIMISTIC POSTERIOR SAMPLING (MOPS)
In this section, we provide more details about the MOPS algorithm discussed in Section 4.3.
We consider the following version the MOPS algorithm of Agarwal Zhang (2022); Chen et al. (2022). Similar to EXPLORATIVE E2D, MOPS also maintains posterior μ² A(O.) over an 1/T optimistic cover (P, Op), initialized at suitable prior y². The exploration policy in the 1-th episode is obtained by posterior sampling: x² Ogt Unif(.A) 94441 Unif(MA,, where H j¹' and ht Unif( 1,..., H 1}). After executing n¹ and observing T², the algorithm updates the posterior as
# (0) de (1) (Σ (Vo(T) + 1o Po (79))
Finally, the algorithm output fout := + E1=1 Dout (o (1t), where Pour (1²) E (III) is defined as (T)) = 1(10 no = m)),
VT E IT.
(45)
We further consider the following Explorative PSC (EPSC), which modification of the PSC proposed in Chen et al. (2022, Definition 4):
(8, (0,0) sup Ee ( Vo(TT) VO(TT) 7B D3 (D PFxx)) }}}, pED.(0)
(46)
43

---

Published as a conference paper at ICLR 2023
Algorithm 4 MODEL-BASED OPTIMISTIC POSTERIOR SAMPLING (Agarwal & Zhang, 2022)
1: Input: Parameters y 0. e (0,1/2). An 1/T-optimistic cover (P, Oa)
2: Initialize: j Un))
3: for 1, ,,...,,'o do
4: Sample 0c μº and ht ~ 10,, - -))).
5: Set n" Tge on Uni ow441 Unif(UA,, 1), execute x' and observe r'.
6: Compute /²+ E A(O)) by
(0) dhg (0) exp Σ Vo(To) + log Pa (f*)))
Output:
Policy Hout : + ET Pout (1²), where Pout (-) is defined (45).
where (o) is the set of all finitely supported distributions on θ Texp is defined as 1 X т on Unif(AA 91+1 Unif(MA,N+)),
Texp = 17
and we abbreviate Pout (1) to p.
Adapting the proof for the MOPS algorithm in Chen et al. (2022, Corollary D.3 & Theorem D.I) to the explorative version, we can show that the output policy nout of MOPS has sub-optimality gap that scales as psc
Theorem H.S. Given an 1/T-optimistic cover (IP, 0n) (cff. Desinition C.4) of the class of PSR models O Algorithm 4 with 1j 1/6 and 7 > achieves the following with probability at least 1- 6:
V. Vo- (Tott)
//c (
(e, 0-)
2
_ Rog Oul logg(1//)) 5].
7
where psc."" is the Explorative PSC as defined in (46).
We provide a sharp bound on the EPSC for B-stable PSRs, which implics that MOPS can also learn them samplc-efficient efficiently.
Theorem H.6. Suppose θ is a PSR class with the same core test sets (e and each e θ ad- mits B- B-representation that is AB-stable (c.f. Definition 4) or weakly Ag-stable (c.f. Definition D).4) and the ground truth model f has PSR rank at most d. Then
psc (0,0") 0*) & GAAdAU //-
Therefore, we can choose a suitable parameter 7 and an 1 1/Tooptiiiste cover (P, Oa), such that with probability at least - 6, Algorithm 4 oulputs policy Rout A(II) such that V. Vg- (Rout) & s, as long as the number of episodes
T (og
The proof of Theorem H.6 is contained in Appendix 1.2. We remark here that EPSC provides an upper bound of EDEC (c.f. Eq. (55)), So Theorem H.2 (and hence Theorem 10) directly follows from Theorem H.6.
I PROOFS FOR APPENDIX H
For the clarity of discussion, we introduce the following notation in this section: for policy w, we denote 9h be policy modification such that
(Ph
оb Unif(AA 91+1 Unif(UA,,41)
Again, here 94 means that we follow for the first h steps, takes Unif at step h, takes an action sequence sampled from Uni[(((A,N+1] at step h 1, and behaves arbitrarily afterwards. Such definition agrees with (47). We further define the policy modification as
# Ph O H on Unif(AA 9 Unif(UA,,411. 4p o π # We call to the exploration policy of
(47)
44

---

Published as a conference paper at ICLR 2023
1.1 PROOF OF THEOREM H.6
To prove Theorem H.6, due to Theorem H.5, we only need to bound the coefficients (0,
By its definition, have
esc pscy (0,0*)= sup (e)n(()
Eg (T((T)) - Vg-( - >1Bx= Dit (1 -bo-"
(48)
Ee-n (I2 PP)) BeBeEBBBrppp Di (P) ).
sup (e)
We then invoke the following error decorrelation result, which follows from the decoupling argument in Appendix E.2 and Proposition F.1.
Proposition L. (Error decorrelation). Under the condition of Theorem H.2 (the same condition as Theorem H.6), for any μ Au (e) and any reference model 0 E θ we have
Ee- Drv
& AU E0 (Pgoro' (Ppo
where dæ is the PSR rank of 0, po defined in (47) is the exploration policy of n.
Combining Proposition I.1 with (48) immediately gives the desired upper bound of psc est (o, 0*). and thus completes the proof of Theorem H.6.
We next turn to prove the Proposition I.I above. We consider the following generalized version of Proposition I.1.
Proposition I,2 (Generalized error decorrelation). Under the condition of Theorem H.4, for any 8 E L (o x II), we have
E(0, Drv (P 1P) & v 22AA Eg- (P ppo0))
where oo лt defined in (47) is the exploration policy of
Proof of Proposition 1.2. In the following, fix a 0 θ and abbreviate & E., q = qº. Then, by
Proposition F.I, we have
H Be,
B Drv
& EE
Eoo Σ
Ey
h=1
(49)
Ea-a Ena]
+
Σ
Bg,
h-1
Note that for the term EØ- [Eo.o]. we have
Ea Eaol <
Es Ea-p
E0,0
(50)
We next consider the case for h e [H] and upper bound the corresponding terms in the right- hand-side (49) using the decoupling argument introduced in Appendix E.2, restated as follows for convenience.
Proposition E.6 (Decoupling argument). Suppose we have vectors and functions
{ai)ier c R", {Fe : R" IR] R
where θ, I are arbitrary abstract index sets, with with functions fo given by
fo(z) max Σ Ke, Vo..)ol
Va E 1
where {yo.irr) (o00irr1...reex(1111 C Ra is a famiiy of bounded vectors in R", Then for any distribution over θ and probability family (gebase c A(I).
Eo-yBEigg [fo(x:)] & Fo (oo [fo
where dx is the dimension of the subspace of R spanned by (xt)iez.
45

---

Published as a conference paper at ICLR 2023
We have the following three preparation steps to apply Proposition E.6: 1. Recall that & Ed is defined in Proposition F.I. Let define
2 (T(H)
( (o (g) (o ((( ]
Rdd
yo.
where (The = d/. og a "i= is an ordering of all possible The (and hence ny = (OA) any policy (that starts at step h). We then define
fo(x) = max E, (Uo x)1;
I E RR41
Then it follows from definition (c.f. Proposition F.1) that (Th-) = fo(q(Tn-1)).
We define I; = q"(Ti--) l for E I (O x AAA where iivzz is an ordering of all possible Th- E (O x A) Then by our definition of PSR rank (c.f. Definition 3), the subspace of Rl spanned by {æ; Hez has dimension less than or equal to dg.
We take qa (Z))
go(i) Em=p(-10) -T--1-Th-111 İE (0 A)^
(51)
Therefore, applying Proposition E.6 to function family (Sofaee, vector family {ZiJieT, and distri- bution family {go lace gives
Eg Ei [fo(x;)]
(52)
E dg Bing Ban [fo();)
dg Bag RØ E (T-n(
Combining Eq. (50), (52), and (49) yields
((0,))~a Drv [Drv PP). (B [Eo +
Σ
(0 Eg,n (E
h=1
E.
2
80.0
Σ
V
dg Ro
ES E E0g1 (Th-))
11
(Hdg + +1)
Eaa~ E0,0 + Σ Eg
Eø E (Th (1n=))
#-1
(Hdg + +1)
Rgg Rg
Σ
12
A2A AUA D2 (Tigoo,, pr pighor)
12( (2 + 1)H AU AA D (TPOo proo)){ ].
where the third inequality is due to Cauchy-Schwarz inequality, and the fourth inequality is due Proposition F22 This completes the proof of Proposition I.I.
1.2 PROOF OF THROREM H.2 (THEOREM 10)
According to Theorem H.1, in order to prove Theorem H.2 (Theorem 10), we only need to bound the coefficients (9) for 7 > 0.
In the following, we bound edec by ps using the idea of Chen et al. (2022, Proposition 6). Recall that edec is defined in (4.2). By strong duality (c.f. Theorem C.2), we have
edec.((,,1)
The boundedness of (yo. is trivially satisfied, hecause no is finitely supported.
46

---

Published as a conference paper at ICLR 2023
inf sup pout [Vo(TT) Vo(T)] -11Bg-p B. prop (Pg. PrepE 6e Poutt
sup
inf Peap ((TI) A(T) Pout (III)
Eg By Brr (V((T)) - Vo(=)] - >Bu FB k- By ppop [D PP P3)]
(E)
(53)
Note that -V(()) where Pe is defined as Pm x) p((0 nh x}). Then for fixed E (0, 1), we have Eg-p Ba- [VO(TT) - [o(TT]
- Vo(TT) & Drv (Tg, Pg) & DH Pg). Therefore, we can take Pout Pp
Ra- R BTP Dit (Pö, Pog] ] + Ea- By [Vo - Vi(T)]
Ea Bg RT Di (T0 P + Bo- Vo(TT) Vo(TT)]
(54)
1
4(1 a)7 + Bo B B -p, D (Pg. (2)) Ro ~ Bo [Vo(To) Vo(mo)],
where the equality is due to choice of py: Ex-pEn~p [Va(T)] E Ex [V((T]] Eg- [Va(Te)].
and the last inequality is due to AM-GM inequality.
Therefore, can take Pexp app + (1 a. (III, where Pe is given by Pa( u((0
sp Th 12) and using this choice of Pexp and Pout in Eq. (53) and using Eq. (54), we get
(0, < sup p=d.(e)
[ (V((TT) Va(TT)]
[DH (Pgo [1
(55)
4(1 a)7
max psaepsceet an (,,)) 6c0
(11-a)7
Recall that psc has been bounded in Theorem H.6. Taking 3/4 yields edec, &
(8A3dAUAHH* + 1)/y. This completes the proof of Theorem H.2.
1.3 PROOF OF THEOREM H.4
To prove Theorem H.4, due to Theorem H.3, we only need to bound the coefficients (ondec,(O,1)) for ğ E A(O). By strong duality (c.f. Theorem C.2), we have
amdec, (0,
inf Hou (nn
sup sup EØ- [Drv 1P..P%)] p B D P Po BE Nell
inf veAn(0xII) Peap Pap AAT B(0,))= Eg Eg Nom [DTv (IF P7]] BBr B Bonr
Di
(p7. P7)
]
sup
sup inf (EAp(0xII) E B ((o DTV (187 (PT. Pep Bon DDr 19)1
E E. B [( DrV (P). F Di (To8o p (ex1(
sup
sup sup E(0. Drv (PO, []]]] - TI Eer-eEBnd Dj (poooT ,p (ppoo)) (xxIl 0e
where the first inequality is because we take poou = fi in inf inme and the second inequality is because we can take Pexp (III corresponds o with π Applying Proposition I.2 gives
613 H2 6A3dAUAHH
amdec, (0, & sup dee
7
and thus the proof of Theorem H.4.
Here, Pe is technically a distribution over the set of mixed policies A(TT), and can be identified with mixed policy in (TT).
47


Reviews:
[{"review_id": "zxmdwPz5cut", "reviewer": "Reviewer_PDoA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The submission considers a sample-efficient learning for PSRs, extending some recent works by (Liu et al., 2022) from POMDPs to PSRs. In some sense, this paper marginally extends a recent work (Zhan et al., 2022) which already claims almost the same contribution. The suggested B-stability is a slightly more general condition than the regularity condition suggested in (Zhan et al., 2022). Just like (Zhan et al., 2022), the algorithm of interest is O-MLE (Liu et al., 2022), and results obtained for PSR can imply several previous results. Proof ideas and techniques are also mostly adopted from (Liu et al., 2022), though there are some differences in technical details from (Zhan et al., 2022). \n\nI think the real contribution of this paper could be an improved sample-complexity analysis of O-MLE, which improves some polynomial factors from previous bounds. The paper also makes connection to decision-estimation coefficient (DEC) first proposed by (Foster et al., 2021), and propose another posterior-sampling based algorithm in parallel. This is also interesting on its own, though slightly off from the main flow of the paper in my opinion. ", "summary_of_the_review": "Overall, I think the paper provides very comprehensive and advanced results which could be of significant interest to RL theory community. ", "strength_and_weaknesses": "\n*Strength*\n\n- The paper is very comprehensive -- the framework is quite general and can imply many previous results with improved upper bounds. \n\n- It is interesting to see the connections with DEC. \n\n\n\n\n*Weaknesses*\n\n- In a current form, the paper sounds in nature too similar to (Zhan et al., 2022). It would have been better to position the paper by, for example, focusing more on the technical innovations to get better sample-complexity. \n\n- The term \"sharp\" is used in several places to emphasize that the upper bound analysis is improved from previous work, but I think this term is somewhat conventionally used when the upper bound matches the lower bound which is not discussed in the paper. \n\n- It is somewhat hard to appreciate the proposed B-stability condition (maybe it is too abstract? or only algebraically explained?). This is a personal opinion but impacts my overall impression of the paper. If there is a better and more intuitive explanation for this, it would be great. ", "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": "JWmXeLrf5o", "reviewer": "Reviewer_jF7R", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 addresses theoretical aspects of sample based inference in partially observable RL problems. In particular, the paper adopts PSR formalism, and proposes B-stability, a structural condition that subsumes several common tractable practically observable RL problems. The paper shows  several algorithms for B-stable PSRs and argues that they have sharp sample complexities for this class of problems.", "summary_of_the_review": "The paper is interesting, inspiring, and well written, however I am wondering whether it is the right paper for a conference. I cannot assess correctness of claims based on the paper only, and did not have enough time to go thoroughly through the proofs in the appendices. I would prefer a conference paper to be self-contained rather than an extended abstract of appendices significantly exceeding the paper in size.", "strength_and_weaknesses": "Strengths: the paper is clearly written, gives a detailed account of related work and necessary background, and introduces a new property, B-stability, which is intuitive and possessed by several important classes of partially observable RL problems. This opens up directions for research related to details of proposed algorithms, learning of B-stable PSRs, and computational issues.\n\nWeaknesses: the paper is of theoretical nature, and as such relies on definitions and proofs of theorems related to B-stability and algorithms. The proofs are not a part of the body of the paper but rather of the appendices, and the full length to be read to understand and check correctness is in excess of 40 pages. I tried to dive into the appendices but didn't have enough time and cannot confirm that the proofs are correct.  My humble opinion is that the paper, with all the contributions which it claims, is perhaps to long for a conference, either the reviewing process or presentation later on. ", "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": "Gsd70LNyP2", "reviewer": "Reviewer_PmjQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies online reinforcement learning in the general setting of Predictive State Representations (PSRs) with a finite horizon. The authors propose a unified condition for PSRs called B-stability, which encompasses the vast majority of known tractable subclasses such as weakly revealing POMDPs, low-rank future-sufficient POMDPs, decodable POMDPs, and regular PSRs. The authors then provide novel online RL algorithms that could learn B-stable PSR with polynomial samples in relevant problem parameters and can outperform existing methods in the aforementioned subclasses.", "summary_of_the_review": "This paper provides a unified theoretical framework for online learning in PSRs. The proposed framework, called B-stability, subsumes several known tractable subclasses of models in the literature. Given the importance of latent representation learning and the relevance of partially observable RL, the unified treatment presented in this paper could have an impact across different fields of machine learning.\n", "strength_and_weaknesses": "This paper provides a unified theoretical framework for online learning in PSRs. The proposed framework, called B-stability, subsumes several known tractable subclasses of models in the literature. I have not read through all details of the proof. However, the PAC results in Theorem 9 seem reasonable. Given the importance of latent representation learning and the relevance of partially observable RL, the unified theoretical framework in this paper could have an impact across different fields of machine learning.\n\nAs for the weakness, this paper is certainly notation heavy. While some of them might be inevitable given the technical nature of this paper, some of the notations are not well defined. For instance, it would be appreciated if the authors could further elaborate on Step 6 of OMLE. It is unclear how the exploratory policy is being set.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%