Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems
Authors: Masatoshi Uehara
Ayush Sekhari
Jason D. Lee
Nathan Kallus
Wen Sun
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement learning theory
Provably efficient RL
POMDPs
PAC RL

Abstract: We study Reinforcement Learning for partially observable systems using function approximation. We propose a new PO-bilinear framework, that is general enough to include models such as undercomplete tabular Partially Observable Markov Decision Processes (POMDPs), Linear Quadratic Gaussian (LQG), Predictive State Representations (PSRs),  as well as a newly introduced model Hilbert Space Embeddings of POMDPs. Under this framework, we propose an actor-critic style algorithm that is capable to performing agnostic policy learning. Given a policy class that consists of memory based policies (i.e., policy that looks at a fixed-length window of recent observations), and a value function class that consists of functions taking both memory and future observations as inputs, our algorithm learns to compete against the best memory-based policy among the policy class. For certain examples such as undercomplete POMDPs and LQGs, by leveraging their special properties, our algorithm is even capable of competing against the globally optimal policy without paying an exponential dependence on the horizon.

Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems
Masatoshi Uehara Cornell University mm223@cornell.dd
Ayush Sekhari MIT Sechari@mit.o edu
Nathan Kallus Cornell University
kallus@cornell.cm edu
Jason D. Lee
Wen Sun
Princeton University
Cornell University wB4550corne11 edu
jasoulee@princeeonn edu
Abstract
We study Reinforcement Learning for partially observable dynamical systems using function approximation. We propose a new Partially Observable Bilinear Actor-Critic framework, that is general enough to include models such observable tabular Partially Observable Markov Decision Processes (POMDPs), observable Linear- Saaeeu-uuurrttaaauuuaeea Gaussia (LQG), Predictive State Representations (PSRs), as well as a newly introduced model Hilbert Space Embeddings POMDPs and observable POMDPs with latent low-rank transition. Under this framework, we propose an actor-critic style algorithm that is capable of performing agnostic policy learning. Given a policy class that consists of memory based policies (that look at fixed-length window of recent observations), and a value function class that consists of functions taking both memory and future observa- tions as inputs, our algorithm learns to compete against the best memory-based policy in the given policy class. For certain examples such as undercomplete observable tabular POMDPs, observable LQGs and observable POMDPs with latent low-rank transition, by implicitly leveraging their special properties, our algorithm is even capable of competing against the globally optimal policy without paying an exponential dependence on the horizon its sample complexity.
Introduction
Large state space and partial observability are two key challenges of Reinforcement Learning (RL). While recent advances in RL for fully observable systems have focused on the challenge of scaling RL large state space in both theory and in practice using rich function approximation, the understanding of scage RL under partial observability is still limited. In POMDPs, for example, core issue is that the optimal policy is not necessarily Markovian since the observations are not Markovian.
common heuristic to tackle large-scale RL with partial observability in practice to simply maintain time window of the history of observations, which is treated policy and the value function. Such a window of history can be often maintained explicitly via truncating away older history (e.g., DQN
state feed into the
window with length 4 for playing video games 52]: Open AI Five uses a window with length 16 for LSTMs (5)). Since even for planning under partial observations and known dynamics, finding the globally optimal policy conditional on the entire history is generally NP-hard (due to the curse of the history) 46
(5 23 searching for short memory-based based policy can be understood as reasonable middle ground that balances computation and optimality. The impressive empirical results of these prior works also demonstrate that in practice, there often exists high-quality policy (not necessarily the globally optimal) that is only a function of a short window of recent observations. However, these prior works that search for the best memory- based policy unfortunately cannot ensure sample efficient PAC guarantees due to the difficulty of strategic exploration in POMDPs. The key question that we aim to answer in this work is:
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

Can we design provably efficient RL algorithms that agnostically learn the best fixed- memory- policy with withftion approximation?
We provide affirmative answers to the above question. More formally, we study RL for partially observable dynamical systems that include not only the classic Partially Observable MDPs (POMDPs) [5]] 58), but also more general model called Predictive State Representations (PSRs) 45). We design model-free actor-critic framework, named PO-Bilineur Actor-Critte Class, where we have a policy class (i.e., actors) that consists of policies that take a fixed-length window of observations as imput (memory-basee policy), and a newly introduced future-dependent value function class (i.e.. critics) that consists of functions that take the fixed-length window of history and (possibly multi-step if the system is overcomplete) future observations as inputs. A future-dependent value function class is an analog of the value function class tailored to partially observable systems that only relies on observable quantities (i.e.. past and future observations and actions). In our algorithm, we agnostically search for the best memory-basee baased policy from the given policy class.
Our framework is based on the idea of a newly introduced notion of future-depedden value function equipped with future observations. While the idea of using future observations has been used in the literature on POMDPs, our work is the first to use this idea learn a high-quality policy in model-free manner. Existing works discuss how to use future observations only in a model-based manner 88] [7]. By leveraging these model-based viewpoints, while recent works discuss strategic exploration to learn near-optimal policies. their results are either limited to the tabular setting (and are not scalable for large state spaces) 36 24 74 47 or are tailored to specific non-tabular models and unclear how to incorporate general function approximation 60) 42 99. We break these barriers by devising a new actor-critie-based -bsed model-free view on POMDPs. We demonstrate the scalability and generality of our PO-bilinear actor-critic framework by showing PAC- AAC-guarantee on many models as follows (see Table for a summary).
In tabular observable POMDPs, i.e., POMDPs where multi- step future observations retain information about latent states, the PO-bilinear rank decomposi- tion holds. We can ensure the sample complexity is Poly(S. A OM,,,,,, , H,H,,,HHHHH,,.. 1H.1/a1) where 01 = ming |/0r||//||a (O is an emission matrix),and S, A, O are the cardinality of state, action, observation space, respectively. H is the horizon, and K is the number of future observations In the special undercomplete (O 2 S) case, our framework is also flexible enough to set the mem- ory length according to the property of the problems in order to search for the globally optimal policy. More specifically, using the latest result from (23] about belief contraction, we can set M =0((//))) In(SH/e) with e being the optimality threshold. This allows us to compete against the globally optimal policy without paying an exponential dependence on H.
Observable Tabular POMDPs.
Observable Linear Quadratic Gaussian (LQG). In observable LQG a classic partial observable linear dynamical system, our algorithm can compete against the globally optimal policy with a sample complexity scaling polynomially with respect to the horizon, dimensions of the state, observation, and action spaces (and other system parameters). This is achieved by simply setting the memory length M to H. The special linear structures of the problem allow us to avoid exponential dependence on H even when using the full history as a memory. While the global optimality results in tabular POMDPs and LQG exist by using different algorithms, to the best of our knowledge, this is the first unified algorithm that can solve both tabular POMDPs and LQQ simultaneously without paying an exponential dependence on horizon H.
Observable Hilbert Space Embedding POMDPs (HSE-POMDPs), Our framework ensures the agnostic PAC guarantee on HSE-POMDPs where policy induced transitions and omission distributions have condition mean embeddings I8 77. This model naturally generalizes tabular POMDPs and LQG. We show that the sample complexity scales polynomially with respect to the dimensions of the embeddings. This is the first PAC guarantee in HSE-POMDPs.
Predictive State Representations (PSRs). We give the first PAC-guarantee on PSRs. PSRs model partially observable dynamical systems without even using the concept of latent states and strictly generalize the POMDP model. Our work significantly generalizes a prior PAC learning result for
Section we discuss how to get rid of O OK using a model- based learning perspective. The intuition is that a tabular POMDP's model complexity has nothing to do with M or K, i.c., number of parameters in transition and omission distribution is 5² " + O.A (even if we consider the time temiiioooogeeous setting, it scales with (S* A OA), but no O and O*) ) and the PO-bilinear rank is still S.

---

Model
Observable
POMDPs
Observable
LQG
Lou-rank M--seep decodable POMDPs
Oiserrable HSE-POMDPS
PSRs
observable POMDPs
Low rank
PO- 30-Bilincrr Rank
[0.4"*(() (Can be St
O(M
Bank (1)
Festure dimencion on (2.6)
(0.4)* x of core tests
Rank (-)
PAC Leurning
Knows
Known
Known
New
New
New
Table 1: Summary of settings that are from PO-Bilinear AC class. The 2nd row gives the parameters that bound the PO-Bilinear rank. Here M denotes the length of memory used to define memory-based policies T( =--12x) where žn = (oh- M 0h-M::h11 M:h-1) denotes the M-step memory. In the 3rd row, "known" means that sample-efficiet algorithms already exist. " New" means our result gives the first sample-efficient algorithm. However, even in "known" case, agnostic guarantees are new; hence, when the policy class is small, we can gain some benefit. The symbol i means we can compete with the globally optimal policy without paying an exponential dependence on horizon H. For the tabular case, the PO-bilinear rank can be improved to when we use the most general definition (Refer to [Section G| For LQG, da and dg are the dimension of action and state spaces. For PSRs, O and A denote the size of observation and action spaces.
reactive PSRs (i.e., reactive PSRs require a strong condition that the optimal policy only depends on the latest observation) which is a much more restricted setting [3).
M-step decodable POMDPs [19]. Our framework can capture M-step decodable POMDPs where there is (unknown) decoder that can perfectly decode the latent state by looking at the latest M- memory. Our algorithm can compete against the globally optimal policy with the sample complexity scaling polynomially with respect to horizon H. S. AM, and the statistical complexities of function classes, without any explicit dependence on O. This PAC result is similar to the one from [9].
Observable POMDPs with low-rank latent transition. Our framework captures observable POMDPs where the latent transition is low-rank. This the first PAC guarantee in this model. Under this model, we first show that with M = Ô ((1/of) In(dH/c) where is the rank of the latent transition matrix, there exists an M -mmeorry policy that is e-near optimal with respect to the globally optimal policy. Then, starting with a general model class that contains the ground truth transition and omission distribution (i.e., realizability in model class), we first convert the model class to a policy class and a future-dependent value function class, and we then show that our algorithm competes against the globally optimal policy with sample complexity scaling polynomially with respect to H, d, (A((1/{f) In(dlt/c), 1//o, and the statistical complexity of the model class. Particularly, the sample complexity has no explicit dependence on the size of the state and observation space, instead it just depends on the statistical complexity of the given model class.
1.1 Related Works
We discuss related works about online RI. for POMDPs. Additional works related to system identification, generalization and function approximation of RL. in MDPs, PSRs and future-dependent value functions are provided in [Section A
Prior works 38 20 showed A -type sample complexity bounds for general POMDPs. Exponential
dependence can be circumvented with more structures. First, in the tabular setting, under observability assumptions, in spectral learning technique 229 (see section 1.1 in 34 for an excellent summary). Second, in LQG, which is partial observable version of LQRs, in 60), sub-linear regret algorithms are proposed. These works use random policies for exploration, which is sufficient for LQG. Since random exploration strategy not enough for tabular POMDPs, is unclear if the existing techniques from LQG can be applied to solve general POMDPs. Third, the recent work [19] provides new model called M -tep decodable POMDP (when M = 1, it is Block MDP) with an efficient algorithm.
47 22. favorable sample complexities are obtained by leveraging the
Our framework captures all above mentioned POMDP models. In addition, we propose a new model called HSE-POMDPs which extends prior works on HSE-HMM[7 POMDPs and includes LQG and tabular POMDPs. Our algorithm delivers the first PAC bound for this model. Finally, we remark it is unclear whether our framework can capture several existing POMDP models 9
2 Preliminary
We introduce the background for POMDPs. We consider an episodic POMDP specified by M
(S. O, A, H, T, 0) where S is the unobserved state space, O is the observation space, AA is the action space, H is the horizon, T: A -> A(S) is the transition probability, O : S - A(O) is the emission probability, and r O x A + R is the reward. Here, T, O are unknown distributions.
3

---

For notation simplicity, we consider the tine-homogeneous case in this paper; Extension to the ummeinnomogeneeus setting is straightforward.
In our work, we consider M-memory policies. Let 2
(O A)miu(h,Ar) and Zn = 2n-1 x O. An element En E
25
2% is represented as 2/ [0max(h- 14),, MM and element Σn E Zn is represented (m.xx(h-M.1:th--- (thus, Eh. = [zn-1, o..)) Fig- ure 2 illustrates this situation. An M M-memory policy is defined as π = [TA where each TT is a mapping from 2n, to a distribu- tion over actions ((A).
En
23
044 05 0g
(nnxx(k-MM11))))
Figure 1: Case with M- 3. A 3-memory policy determines action ag based on &g.
In a POMDP, an M - policy generates the data as follows. Each episode starts with the iniiill state $1 sampled from some unknown distribution. At each step E [H) from Sp. E S, the agent observes og (-1|s)), executes action On FA (-)=),), receives
reward r(8,, an). and transits to the next latent state 8h+1 ~ T(-|sh: an). Note that the agent does not observe the underlying states but only the observations (on (on)ngH We denote (TT) the value of the policy n, i.e. E| the policy म. emissions distribution O and transition dynamics T.
h= Th: 01:H ~ x where the expectation is taken w.r.t. the stochasticity of
We define a value function for policy w at step to be the expected cumulative reward to go under the policy starting from z E - and 8 E S, i.e. Vi2 - x S - T where (2, =
E Th/ | 2h-1 = 2, 8t, = 8: 0h:H ~ æ.. The notation E[|; ahsH ~ TI means the expectation is taken under policy x from h to H. Compared to the standard MDP setting, the expectation is
conditional on not only sp, but also 2 since we consider M M-memory policies. The corresponding
Bellman equation for Vg is Vi (z (2 8h) E [rk + VM41 8h+1) 2h-1, 885 2h-1,8h;00 an ~ π
The Actor-critic function approximation setup. Our goal is find near optimal policy that maximizes the policy value J(r) in an online manner. Since any POMDPs can be converted into MDPs by setting the state at level h to the observable history up to h, any off-the-shelf online provably efficient algorithms for MDPs can be applied to POMDPs. By defining Hr. as the whole history up to step E [H] (i.e., a history Ty E Hr is in the form of 01:A, d1:b-1). 1), these naïve algorithms ensure that output policies can compete against the globally optimal policy Ti argmax (() where
π = [ II, = [H4, - (.))]. However, this conversion results in the error with exponential dependence on the horizon H, which is prohibitively large in the long horizon setting.
Instead of directly competing against the globally optimal policy, we aim for agnostic policy learning, i.e, compete against the best policy in given M-memory policy class. Our function approximation setup consists of two function classes, (a) A policy class TT consisting of M M-memory policies 11 == [1I h=1 where 1I, C 1Z + (JAA (i.e., actors), (b) A set of value future-dependent value functions G = (G |i= where G, C [2, + RJ, whose role is to approximate V (i.e., critics). Our goal is to provide an algorithm that outputs a policy = { that has a low excess risk, where excess risk is defined by R(TT)= == (+) - J(r') where x² argmax ((T) is the best policy in class II. To motivate this agnostic setting, M -mmmorry policies are also widely used practice, e.g., DQN [52 sets M 4. Besides, there natural examples where M memory policies are close to the globally optimal policy with M being only polynomial with respect to other problem dependent parameters, e.g., observable POMDPs 23 and LQG 42 60 48). We will show the global optimality in these two examples later, without any exponential dependence on H in the sample complexity.
Remark (Limits of existing MDP actor-critic framework). While general actor-critic framework proposed in MDPs (33) is applicable to POMDPs via the naïve POMDP to MDP reduction, is unable to leverage any benefits from the restricted policy class. This naive reduction (from POMDP MDP) uses full history and will incur sample complexity that scales exponentially in the horizon.
Give matrix A, we de- note its pscudo inverse by A and the operator norm by ||A||. We define the & norm ||A|]] maXx:ag00 ||Az]]|/ /|||///11 [11] The outer product is denoted by @. Let (-)(-) E Zn x S be the marginal distribution at f and 8()) be the Dirac delta function. We denote the policy 8(a = a') by do(a'). We
Additional notation. Let [H] (1,.... H. and [1] (I,...,,,.. ,4..
denote a uniform action by ((A). Given a function class g, we define ||[|| = supyeg llglloo.

---

3
Future-Dependent Value Functions and the PO-bilinear Framework
Unlike MDPs, we cannot directly work with value functions V, (s) s) in POMDPs, since they depend on the unobserved state To handle this issue, below we first introduce new future-dependent value functions by using future observations, and then discuss the PO-bilinear framework.
3.1 Future-Dependent Value Functions
Definition 1 (K-step future-dependent value functions). Fix set of policies yout (mppat K
Fi=l
where nuu O - (AA). Value future-depente at step for policy ι are defined as the solution to the following integral equation:
value functions 9h, 2n-1 x OK x xAR RR
Mzz-1 Zh-1. Sh S:
Elgi (zh-1, MhchhK-111 0h:h+ O1:hhk
2h-1: SK5 alch+K22
Toul] Vi (1)
where the expectation is taken under the policy x out.
Future-dependent value functions do not necessarily exist, nor are needed to be unique. At an intuitive level. K-step future-dependent value functions are embeddings of the value functions onto the observation space, and its existence essentially means that K-step futures have sufficient information to recover the latent state dependent value function. The proper choice of nut would depend on the underlying models. For example, LQG. For notational simplicity, we mostly focus on the case of K = 1, though we will also discuss the general case of K 2. The simplified definition for 1-step future-dependent value functions is provided in the following. Note that this definition is agnostic to x gu.! Definition 2 (1-step future-depende gh : Zn-1 x O + R at step h E [H] for a policy x are defined as the solution to the following:
uniform policy in the tabular case, and 5(a 0) in
value functions). One-step deeree-de value functions
vzh-1 E 2h- 84 E S:
Elgg (2h-1, 0n. 2h- snl = Vi (h)-11
(1)
In |Section we will demonstrate the form of the future-dependen value function for various examples. The idea of encoding latent state information using the statistics of (multi-step) futures have been widely used learning models of HMMs 63 29]. PSRs (8 7 27 67 and system identification 772 Existing provably efficient (online) RL works for POMDPs elaborate on this
viewpoint [36 24 Compared to them, the novelty of future-dependent value functions is that it is introduced to recover value functions but not models. This model-fire view differs from the existing dominant model-based view in online RL for POMDPs. In our setup, we can control systems if we can recover value functions on the underlying states even if we fail to identify the underlying model.
3.2 The PO-Bilinear Actor-critic Framework for POMDPs
With the definition of future -eeundee value functions, we are now ready to introduce the PO-bilinear actor-critic (AC) class for POMDPs. We will focus on the case of K here. Let g = (9 _ where Gb [Z,, + RJ. be class consisting of functions that satisfy the following realizability assumption w.r.t. the policy class 11.
Assumption 1 (Realizability). We assume that G is realizable w.r.t the policy class II. i.e VT I1, h E [H) there exists at least one 9% E 9n, such that 9%. is a w.r.t. the policy æ. Note that realizability implicitly requires the existence of (9%)-
value function
We next introduce the PO-Bilinear Actor-critic class. For each level h E [H], we first define the Bellman loss:
Br (T, g: "") := (Zg)((n)) - 13 : 01:h-1 ~ tm oh T]]
given M-memory policies π {mA), m7 (ar=") and g = {gx]. ). Letting g" = )= be a future-dependent value function for æ, our key observation is that future-dependent value functions satisfy = Bry (T,, g "T"" for any M memory roll-in policy z' = =m and any evaluation pair (T.9*). This is analog of Bellman equations on MDPs. The above equation tells us that 7 is a right loss to quantify how much the estimator g is different from 9h When Bra g: ot ") has a low-rank structure in proper way, we can efficiently learn near-optimal M memory policy. The following definition precisely quantifies the low-rank structure that we need for sample efficient learning.
(T.9; Bra(T. Br
Definition& 3 (PO-bilinear AC Class, K = 1). The model is a PO-bilinear Actor-critic class of rank d if G is realizable, and there exist Wa II G - Red and X - Rd such that for all n', E 11, g E G and h [H],
5

---

1. Elgh (2h) - Th - 9h+1 (2h+1(2)1));) 019h11 ~ T ~ ~ (W)(
2. WA (A( 0 for any E 11 and the corresponding futrrreeeenttureeedeeedddddd value finction
g" E 9.
We define d as the PO-bilinear rank.
Remark 2 (Two Important Extensions). While the above definition is enough capture most of the examples we discuss later in this work, including undercomplete tabular POMDPs, LQG, HSE- POMDPs, we provide
useful extensions. The first extension incorporates discriminators into the framework, which can be used to capture the M-step decodable POMDPs and POMDPs with low-rank latent transition (see Section F}. The second extension incorporates multi-step futures, which can be used to capture overcomplete POMDPs and general PSRs (see Section B
4 Examples of PO-Bilinear Actor-critic Classes
We consider three examples (observable tabular POMDPs, LQG, HSE-POMDPs) that admit PO- bilinear rank decomposition. Our framework can also capture PSRs, M-step decodable POMDPs and low rank observable POMDPs, of which the discussions are deferred to SSection E G. and G.2 respectively. We mainly focus on one-step future, i.e., K and briefly discuss the extension to K' > in the tabular case. In this section, except for LQG, we assume rh E [0, 1] for any E [M]. All the missing proofs are deferred /eection C
4.1 Observable Undercomplete Tabular POMDPs
Example 1 (Observable undercomplete tabular POMDPs), Let O E R O|x|si where the entry indexed by a pair (o, s) is defined as Oo.s O(ols). Assume that rank (0) S) which we call observability. This requires undercompletenes O 2 |S)
The following lemma shows that O being full rank implies the existence of future-dependent value functions 9%.
Lemma 1. For Example 1 there exists 9% satisfying Definition 2 for any π 11 and h E [H].
Proof. Consider any function : Zn-1 x S R (thus, this captures all possible V.a Denote 1(2) as the one-hot encoding of over 2n-1 (similarly for (s)). We have f(z, = (f, @ (s)) (f. 1(z) (OIO1(s))), where we use the assumption that rank(O) = -SS] and thus 0 1. Then,
f(z,s) ( (z) X (o))))))(()))) = Es)o(s) (f. 12) @ 0' (()).
(2)
which means 9% (z, (V (2) 8 (f1())).
We next show that the PO-Bilinear rank (Deiinition 3 is bounded by |S(((O|AA))M
Lemma 2. Assume O is full column rank. Set the future-dependens value function class Gr. [Zn-1 x O + J0, Cg]] [ for certain Cg E R, and policy class 1I, = [2, - A (A)). Then, the model a PO-biliner AC class (Definition 3) with PO-bilinear rank most [S](|)) AA) M
Later, we will see that the PO-bilinear rank in the more general definition just |S] Section This fact will result in a significant improvement in terms of the sample complexity, and will result in a sample complexity that does not incur (O)
Lastly, we touch on overcomplete POMDPs (O) < <SS) when we use multi-step futures. For details, refer Section C.2 In this case, the existence of future-dependent value function ensured when |O| K [A|K-1 x [S] matrix with entries equal to F(Onh K K-24K-2 sh; aha K ~ (())..
4.2
Observable Linear Quadratic Gaussian
The next example is Linear Quadratic Gaussian (LQG) with continuous state and action spaces. The details are deferred to cofSection M Here, we set M = H - so that the policy class II contains the globally optimal policy.
Example 2 (Linear Quadratic Gaussian (LQG)). Consider LQG:
As + Ba + E, o Cs + r= -( Qs 1ss+a a TRa)
Ra)
where T, are Gaussian distribution with mean 0 and variances Ex, and E,,, respectively, and E dd. 0 E Rdo and a E dd, and Q, R. are positive definite matrices.

---

We define the policy class as the linear policy class II, = {ō(an = KT K₁ E BlA[xds)) ) where dz, is a dimension of Σn E 2n. This choice is natural since the globally optimal policy is known to be linear with respect to the entire history [ Chapter 4]. We define two quadratic features,
on (2h-211 8h.) = (1. -1 s0 -/,)) with 2/-1 E 2 8/1 E S, and t/ (2h-1,00) 0h) = 12,1%1-111 1 & 1) with 2n-1 E 2n-1, ON E O. We have the following lemma.
Lemma 3 (PO-bilinear rank of observable LQG). Assume rank(C)) = dg- Then, the following holds. (1) For any policy a linear in Thi a one-step future-dependent value function gh (-) exists, and is linear
(.)(.)) (2) Letting dæn be the dimension of th. we set Gr. {0 4/n (-)0 Rd } and II being linear in En. Then LQG sutisfies Desinition 3 with PO-bilinear rank at most O(11 + (H (H- + do) + d,)²)
We have two remarks. First, when m. = 8(a- = 0), K-step future-dependent value functions exist when [CT, (CA) ,...., (CAK-I)T) is full raw rank. This assumption referred to as observability in control theory (28) Secondly, the PO-bilinear rank scales polynomially with respect to H, do da. d2 even with M H 1. As we show in [Section M due to this fact, we can compete against the globally optimal policy with polynomial sample complexity.
4.3 Observable Hilbert Space Embedding POMDPs
We consider HSE-POMDPs that generalize tabular POMDPs and LQG. Proof' here are deferred to Section C.4 Consider any h E [H] Given policy m 2n A. we define the induced transition operator Tn = {TT If
h=1 as (Zh, Sh+1) ~ Tw. (Zh-1. where we have on ~ O(sp), as ~ TA (2+,, sh+1 T(s,, ag.). Namely, TT is the transition kernel of some Markov chain induced by the policy ग. The HSE-POMDP assumes two conditional distributions (-1ss) and (5,(11z,, 8) have conditional mean embeddings.
Example 3 (HSE-POMDPs). We introduce features Oh : - X - RR Zn-1 O
Rdvs, We assume the existence of the conditional mean embedding operators: (1) there exists matrix K₁, such that all 2 E Zk-1, E S, Em- (n( 0) (2,00(2,66 and (2) for all π E II, there exists a matrix Tiy such that P.g..en----TTaaaae------
(Fh, 8h+1) 1) = TTi ta (2h-1, 8n).
The existence of conditional mean embedding is common assumption in prior RL works on learning dynamics of HMMs, PSRs, 164 7 and Bellman complete linear MDPs 777 18 26]. HSE- POMDPs naturally capture tabular POMDPs and LQG. For tabular POMDPs, dh and Φ) are one-hot encoding features. In LQG, Φ and th,, are quadratic features we define in [Section 4.2 Here for simplicity, we focus fimee-ddieesional features dy, and tha Extension to -ifinteedimensionall Reproducing kernel Hilbert Space is deferred to Section C.4
The following shows the existence of future-dependent value functions and the PO-bilinear rank decomposition.
Lemma (PO-bilinear rank of observable HSE-POMDPs), Assume K₁, is full column rank (observ- ability), and VØ (-) is linear in 6a for any E II, h E [H]. Then the following holds. (1) A one-step value function (. exists for any π E II, h E [H], and linear in 1/h. (2) We set a value function class Gn = (w] tht (-)w E R&v,), }. policy class II C 12 + A(A)). Then
HISE-POMPP satisfies Definition 3 with PO-bilinear rank at most [ døn.
The first statement can be verified by noting that when V. (.) = (0h, (r)())) eiture-dependen value functions take the following form Of ((K)) 0₂), (-)) where we leverage the existence of the conditional mean embedding operator K,, and that K₁, is full column rank (thus K. K₁, = Id., ). Note that the PO-bilincar rank depends only on the dimension of the features on, without any explicit dependence on the length of memory.
Algorithm and Complexity
In this section, we first give our algorithm followed by a general sample complexity analysis. We then instantiate our analysis to specific models considered in Section
5.1 Algorithm
We first focus on the cases where models satisfy the PO-bilinear AC model (i.e., Defiiitonn 3) with finite action and with one-step future-dependent value function.
7

---

Algorithm 1 PaRtially ObserVAble BiLinEar (PROVABLE) # multi-step version is in Algorithm 2
1: Input: Value class G = [,
2 + RR,, Policy class II [1la), II C [2h-1 - R..
parameters E N, R E IR, Initialize T E II
2: Form the first step dataset D = {o') I= with of ~ ((1181) do 4: For any h E [H]. collect m i.d tuple as follows: (žh, 5h) ~ dh , ~ T(A), =
3: for t = + T
ru(on, (4), -h++ T(sk, ag)) 0+41 0(11sx+))-
5: Define D/ = {(2) 4 rh. (1+1))
# note latent state 8 is not in the dataset
6: Define the Bellman error V(T, g) E I g.
of, 9) EDg (an EN A| + +mh 9h (3h)).
7: Select policy optimistically as follows
(n . gg+h)== = argmax [o) s.t. 4h E [H] Vi (o) (z)g))) R.
8: end for
9: Output: Randomly choose स from (T
We present our algorithm PROVABLE in Algorithm 1 Note PROVABLE is agnostic to the form of X and Wh. Inside iteration t, given the latest learned policy n², we define Bellman error for all pairs (T,,g) where the Bellman error is averaged over the samples from n¹. Here, to evaluate the Bellman loss for any policy π E 11, we use importance sampling by running (AA) rather than exccuting a policy и that we can reuse samples [ A pair (T, that has small total Bellman error intuitively means that given the data so far, could still be a value future- deeenddd value function for the policy x. Then in the constrained optimization formulation, Bellman errors are small so far. Among these (H, g) pairs, we select the pair using the principle of optimism in the face of uncertainty. We remark the algorithm leverages some design choices from the Bilinear-UCB algorithm for MDPs [6]. The key difference between our algorithm and the Bilinear- UCB that we leverage the actor-critic framework equipped with value denended value functions to handle partially observability and agnostic learning.
only focus on (.,, 9) pairs whose
Remark 3 (Three Important Extensions). By extending Algorithm 1 we can consider more general algorithms to include three important cases. The first extension is the minimax version with discriminators to capture low-rank observable PMODPs and M-step decodable POMDPs. The detail in Section Secondly, although algorithms so far implicitly assume the action is finite, we can consider LQG with continuous action by employing a G-optimal design over actions. The detail in Section D.2 The third extension the multi-step step future case, which can capture overcomplete POMDPs and general PSRs. The discussion is deferred to Section D
5.2 Sample Complexity
We show sample complexity result by using reduction to supervised learning analysis. We begin by stating the following assumption which is ensured by standard uniform convergence results.
Assumption 2 (Uniform Convergence). Fix h E [H]. Let D/, be a set of m i.i.d tuples following (2 8h. 0n) ~ di ag ~ L(A), 8h-1 ~ T(s,, az), 0141 ~ ((s41). With probability - 6,
sup [(ED, [T En En)AA199 (Zh+1) + Tn. - (2+)]l S Egen,h (m, 11, 9,
For 1, we also require sup E. |ED; (si (o1)) - EiE,, [9 (Il) S E (m, G)
Remark 4 (Finite function classes). The term Egen depends on the statistical complexities of the func- tion classes 11, G. As simple example, consider the case where 11 and G are discrete. In this case, have Egen, II, G. 8) O( [[II[[[ [elii/////// Gl)))/m), and c (m, G, 8) O PlVIn(( ( which are standard statistical complexities for discrete function classes II and g. Achieving this result simply requires standard concentration and union bound over all functions in 11, G.
Under Assumption 2. when the model is PO-bilinear with rank d. we get the following.
"This choice might limit the algorithm to the case where A is discrete. However, for examples such as LQG, we show that we replace (AA) by a G-optimal design over the quadratic polynomial feature of the actions.
8

---

Theorem 1 (PAC guarantee of PROVABLE). Suppose we have PO-bilinear AC class with rank
d. Suppose Assumption suP (x)(l I Bx and suPrell,yes [W, (T,9)l I Bw for any
E [H] By setting T = 2Hd 4Hd B& nly +1)) R = Egen where
gen
Cgen = max, gen,, (m. II, 1, (TH + 1)), Egen == max,, Cgen,h (m. G,8HH
With probability at least 1 - 8, letting xt = argmax EEll J(T"), we have
J(x²) - J(A) S gen dH² In (4Hd (B BW P2pe + +1) 1 G,8 1))- The total number of samples used in the algorithm is m.TH.
Informally, when Egen Ó(1//m), to achieve c-near optimality, the above theorem indicates that we just need set m Ó(1/²)) which results a sample complexity scaling ((1/e²) (since T only scales O(dH)). We give detailed derivation and examples in the next section.
5.3
Examples
Hereafter, we show the sample complexity result by using Theorem
For complete results, refer to
Section IN
5.3.1
Finite Sample Classes
We consider the case where the hypothesis class is finite and admits PO-bilinear rank decomposition.
Example 4 (Finite Sample Classes). Consider the case when and G are finite and the PO-bilinear rank assumption is satisfied. When II and are infinite hypothesis classes, [FI and [g] replaced with their L -covering numbers, respectively.
Theorem 2 (Sample complexity for discrete II and G (informal)). Let 11 S Ca Th E [0, for any h E [H] and the PO-bilinear rank assumption holds with PO-biliear rank d. By letting mmxx = max, [1,] [Smax = max: (9n,), with probability 1 - we can achieve ( S
when samples
Ô Ód max AA? In( m00) (B
Here, Polylog(d, H, |A], (n(())),,(((())))) (BB))) are omitted.
5.3.2 Observable Undercomplete Tabular POMDPs
We start with tabular POMDPs. The details here deferred to Section K
Example (continuing from p. 6 In tabular models, recall the PO-bilinear rank is at most d = JO| M0 [ We suppose Th [0, 1] for any h E [H]. Assuming O is full-column rank, to
satisfy the realizability, we set Gr = {0, 12) & (+)( ||01loc I H} where |0+|| & 1/0, and 1[z), 1()) are one-hot encoding vectors over Zn-1 and O, respectively. We set II, [Z, - A(A)).
Then, the following holds.
Theorem (Sample complexity for undercomplete tabular models (Informal)). With 6, we can achieve J(T") J(t) I when we use samples
probability
Ô ([SP|A|3a [| (5 (1/e)) (2 Here, polylog([S], IO), A|, 1/11 (n(1/)) are omitted.
Firstly, while the above error incurs |0] [ we will later see in Section G.2.2 when we use the more general definition of PO-bilinear AC class and combine model-based perspective, we might be able to remove O from the error bound. The intuition here is that the statistical complexity still scales with | + |O]A and does not incur OO), At the same time, although PO-bilinear rank show that it can be just [S] with more refined definition. Secondly, |[O+|] < 1/a can be replaced with other analogous conditions ||0t||2 S 1/02. Here, note ||0 || = 1/ / ||Ox]]] 1 /||x=|]
currently scales with OO || (S).
}. ||0i|| = 1/ 4/mmnn [[x]]/// | The reason why we use 1-norm to invoke the result (23) achieve the near global optimality as in the next paragraph.
Near global optimality. Finally, consider the PAC guarantee against the globally optimal policy. As shown in 123), is enough to set M = (((10(((())))) In (SSH)))) to compete with the globally optimal policy T... Thus achieve quasipolynomial sample complexity when competing against TtJ-

---

Theorem 4 (Sample complexity for undercomplete tabular models (Informal) competing against With probability 6, we can achieve ( J(t) S e when we use samples at most
De).
poly([S], |A In[[S H//)/ai, ||11///////// H. 1/1 1/c, l/c,))(
Remark (Overcomplete Tabular POMDPs). We can similarty consider the sample complexity of overcomplete POMDPs. We would incur the additional [A|*. The detail is in Section
5.3.3 Observable LQG
Now let revisit LQG. The detail here is deferred to Section M We show that PROVABLE can compete against the globally optimal poliey with polynomial sample complexity.
Example 2 (continuing from p.O.. In LQG, by setting H = M we achieve a polynomial sample complexity when competing against the globally optimal policy Tda--
Theorem 5 (Sample complexity for LQG (informal) competing against "g))= Consider a linear
policy class II = {8(an = Rnžz) Rall S O). and assume max (I A||, B|] [[C'I, [| ||]] s @ and all policies induce a stable system (we formalize in [Section M. With probability 1 6, we can achieve J (m()) (+t S e when we use samples at most
poly(H, da, dos du. 1I, x (1/e)².
5.3.4 Observable HSE-POMDPs
Next, we study HSE-POMDPs. The details here is deferred to Section J
Example 3 (continuing from p- In HSE-POMDPs, PO-bilinear rank is at most max, den- Suppose I| I 1 and (- = (0%, (-)) such that ||o%]| I Oy for any h E [H] Then, to satisfies the realizability, we set Gr [10, (n)) |10|| s Oy (m/nmn(K))
(K)) where a (K) = minne(H) 1/1[K,,1 ll- Theorem 6 (Sample complexity for HSE-POMDPs (Informal)). Let dg. = max, (d do = max; (d } mmaxx maxx [TT,, ( )- Suppose ra lies in [0, 1) [oofaray/// h [H] Then, with probability
1 - 8, we can achieve J(TT) J(+)= S 6 when we use samples
δ (dH max (ds + In([umma (0llaa/al//////////////////)))// (1)mmm/m
(K))² (K)))-(1/6))))
Here, polylog (d. dg. (A), Ov. In( (mmama 1/0minn ( (K), 1/c, ln(1/5), maxx (T), Tmax mm)x(()) are omitted and I (K) [ax [[K]]], O (T) MaX [T
Note that the sample complexity above does not explicitly depend on the memory length M, instead it only explicitly depends on the dimension of the features Φ, vb In other words, if we have a feature mapping 1h, that can map the entire history (i.e.. M H) low-dimensional vector (e.g., LQG), our algorithm can immediately compete against the global optimality T
5.4 PSRs, M- M-step decodable POMDPs and Low-rank Observable POMDPs
The result of PSRs is deferred to Section Section E. Besides, our generalized framework can capture two models: (1) M-step decodable POMDPs, and (2) observable POMDPs with the latent low-rank
transition. The discussion is deferred to Section The summary of the results is stated in Section I
6 Summary
We propose a PO-bilinear actor-critic framework that the first unified framework for provably efficient RL on large-scale partially observable dynamical systems. Our framework can capture not only many models where provably efficient learning has been known such as tabular POMDPs, LQG and M-step decodable POMDPs, but also models where provably efficient RL is not known such as HSE-POMDPs, PSRs, and low-rank observable POMDPs. Our unified actor-critic based SoorrttmmPRRvABLL.
algorithm PROVABLE provably performs agnostic learning by searching for the best memory-based policy. For special models such as observable tabular POMDPs, LQG, and low-rank POMDPs, by leveraging their special properties, i.e., the exponential stability of Bayesian filters in tabular and low-rank POMDPs, and existence of a compact featurization of histories in LQG, we are able to directly compete against the global optimality without paying an exponential dependence on horizon.
Acknowledgement
We thank Nan Jiang for the valuable discussions on PSRs. MU and NK acknowledge funding support from NSF IIS-184621 and Masason Foundation. WS acknowledges funding support from NSF IIS 155711.
10

---

References
[1] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in Neural Information Processing Systems, 33:13399-13412, 2020.
[2] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20115 2020.
[3] Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of pomdps using spectral methods. In Conference on Learning Theory, pages 193-256. PMLR, 2016.
[4] Andrew Bennett and Nathan Kallus. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. 2021.
[5] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota with large scale deep reinforcement learning. arXiv preprint arXiv: 2019.
[6] Dimitri Bertsekas. Dynamic programming and optimal control: Volume I, volume Athena scientific, 2012.
[7] Byron Boots, Geoffrey Gordon, and Arthur Gretton. Hilbert space embeddings of predictive state representations. arXiv preprint 1xXiv:3309.68) 2013.
[8] Byron Boots, Sajid M Siddiqi, and Geoffrey J Gordon. Closing the learning-plannn loop with predictive state representations. The International Journal of Robotics Research, 30(7):954-966 2011.
[9] Qi Cai, Zhuoran Yang, and Zhaoran Wang. Sample-efficient reinforcement learning for pomdps with linear function approximations. arXiv preprint 09777 2022.
[10] Jinglin Chen and Nan Jiang. Information-theorte considerations in batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051, PMLR, 2019,
[11] Sayak Ray Chowdhury and Rafael Oliveira. No-regret reinforcement learning with value function approximation: kernel embedding approach. arXiv preprint arXiv:2011.07881, 2020.
[12] Yifan Cui, Hongming Pu, Xu Shi, Wang Miao, and Eric Tchetgen Tchetgen. Semiparametric proximal causal inference. arXiv preprint arXiv:201 2020.
[13] Ben Deaner. Proxy controls and panel data. arXiv preprint arXiv:1810.0022 2018.
[14] Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax estimation of conditional moment models. In Advances Neural Information Processing Systems, volume 33, pages 12248-12261 2020.
[15] Carlton Downey, Ahmed Hefny, Byron Boots, Geoffrey J Gordon, and Boyue Li. Predictive state recurrent neural networks. Advances in Neural Information Processing Systems, 30, 2017.
[16] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference Machine Learning, pages 1826-2836. PMLR, 2021.
[17) Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674. PMLR, 2019.
[18] Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709. PMLR, 2020.
11

---

[19] Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforce- ment learning with a short-term memory. arXiv preprint vrXiv:2202.03983, 2022.
[20] Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Reinforcement learning in pomdps without resets. 2005.
[21] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13887 2021.
[22] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in observable pomdps, without computationally intractable oracles. arXiv preprint arXiv:2206.03446, 2022.
[23] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Planning in observable pomdps in quasipoly- nomial time. arXiv preprint XxXi:2201.004355, 2022.
[24] Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A pac algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pages 510-518. PMLR, 2016.
[25] William L Hamilton, Mahdi Milani Fard, and Joelle Pineau. Modelling sparse dynamical systems with compressed predictive state representations. In International Conference on Machine Learning, pages 178-186. PMLR, 2013.
[26] Botao Hao, Yaqi Duan, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Sparse feature selection makes batch reinforcement learning more sample efficient. In International Conference on Machine Learning, pages 4063-4073. PMLR, 2021.
[27] Ahmed Hefny, Carlton Downey, and Geoffrey J Gordon.
Supervised learning for dynamical system learning. Advances in neural information processing systems, 28, 2015.
[28] Joao P Hespanha. Linear systems theory. Princeton university press, 2018.
[29] 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-148,, 2012.
[30] Masoumeh T Izadi and Doina Precup. Point-based planning for predictive state representations. In Conference of the Canadian Society for Computational Studies of Intelligence, pages 126-137. Springer, 2008
[31] Herbert Jaeger. Discrete-time. discrete-valued observable operator models: a tutorial. GMD- Forschungszentrumm Informationssechhiik Darmstadt, Germany, 1998.
[32] Herbert Jaeger. Observable operator models for discrete stochastic time series. Neural computa- 2000.
lion,
[33] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. Contextual decision processes with low bellman rank are pac-lcarnable. In International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
[34] Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforce- ment learning of undercomplete pomdps. Advances in Neural Information Processing Systems, 33:18530-18553 2020.
[35] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34, 2021.
[36] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[37] Nathan Kallus, Xiaojie Mao, and Masatoshi Uehara. Causal inference under unmea- sured confounding with negative controls: A minimax learning approach. arXiv preprint 10X1v:210..4402, 2021.
12

---

[38] Michael Kearns, Yishay Mansour, and Andrew Ng. Approximate planning in large pomdps via reusable trajectories. Advances Neural Information Processing Systems, 12, 1999.
[39] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[40] Alex Kulesza, Nan Jiang, and Satinder Singh. Spectral learning of predictive state representa- tions with insufficient statistics. Twenty-Ninth AAAI Conference on Artificial Intelligence. 2015.
[41] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shic Mannor. RI for latent mdps: Regret guarantees and a lower bound. Advances in Neural Information Processing Systems, 34, 2021.
[42] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Regret min- imization in partially observable linear quadratic control. arXiv preprint arXiv:2002.00082 2020.
[43] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[44] Tianyu Li, Bogdan Mazoure, Doina Precup, and Guillaume Rabusseau. Efficient planning under partial observability with unnormalized functions and spectral learning. In International Conference on Artificial Intelligence and Statistics, pages 2852-2862. PMLR, 2020.
[45] Michael Littman and Richard S Sutton. Predictive representations of state. Advances in neural information processing systems, 14, 2001.
[46] Michael Lederman Littman. Algorithms for sequential decision-making. Brown University, 1996.
[47] Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? arXiv preprint arXiv:2204.0896; 2022.
[48] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalent control of lqr is efficient. arXiv preprint wwXivv1902.0720 000826 2019.
[49] Afsaneh Mastouri, Yuchen Zhu, Limor Gultchin, Anna Korba, Ricardo Silva, Matt J Kusner, Arthur Gretton, and Krikamol Muandet. Proximal causal learning with kemels: Two-stage estimation and moment restriction. arXiv preprint 21X15:2105.04544, 2021.
[50] Wang Miao, Xu Shi, and Eric Tchetgen Tchetgen. A confounding bridge approach for double negative control inference causal effects. arXiv preprint arXiv:1808 180.001808.044455. 2018.
[51] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient tich-observation reinforcement learning. In International conference on machine learning, pages 6961-6977 PMLR, 2020.
[52] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, arXiv preprint 13X1v:13 2013.
[53] Kevin P Murphy. A survey of pomdp solution techniques. enviroument, 2(10), 2000.
[54] Yu Nishiyama, Abdeslam Boularias, Arthur Gretton, and Kenji Fukumizu. Hilbert space embeddings of pomdps. arXiv preprint 121.4:1210.4887, 121111000.472111111 2012.
[55] Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):441-43 1987.
[56] Josep M Porta, Nikos Vlassis, Mathiij TJ Spaan, and Pascal Poupart. Point-based value iteration for continuous pomdps. 2006.
[57] Matthew Rosencrantz, Geoff Gordon, and Sebastian Thrun. Learning low dimensional predictive representations. Proceedings of the twenty-first international conference on Machine learning, page 88, 2004.
13

---

[58] Guy Shani, Joelle Pineau, and Robert Kaplow. A survey of point- pomdp solvers. Au- tonomous Agents and Multi-Agent Systems, 27(1):1-51, 2013.
[59] Chengchun Shi, Masatoshi Uehara, and Nan Jiang. A minimax learning approach to off-policy evaluation in partially observable markov decision processes. arXiv preprint arXiv:2111.066 2021.
[60] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[61] Rahul Singh. finite sample theorem for longitudinal causal inference with machine learning: Long term, dynamic, and mediated effects. arXiv preprint #rXiv:2112.142499 2021.
[62] Satinder Singh, Michael R James, and Matthew R Rudary. Predictive state representations: a new theory for modeling dynamical systems. In Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 512-519, 2004.
[63] Le Song, Byron Boots, Sajid Siddiqi. Geoffrey J Gordon, and Alex Smola. Hilbert space embeddings of hidden markov models. 2010.
[64] Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu. Hilbert space embeddings of conditional distributions with applications to dynamical systems. In Proceedings of the 26th Anmual International Conference on Machine Learning, pages 961-968, 2009.
[65] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
[66] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference learning theory, pages 2898 2933..93. PMLR, 2019.
[67] Wen Sun, Arun Venkatraman, Byron Boots, and J Andrew Bagnell. Learning to filter with predictive state inference machines. In International conference on machine learning, pages 1197-1205. PMLR, 2016.
[68] Guy Tennenholtz, Uri Shalit, and Shie Mannor. Off-policy evaluation partially observable environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10276-10283, 2020.
[69] Michael R Thon and Herbert Jaeger. Links between multiplicity automata, observable operator models and predictive state representations: unified learning framework. J. Mach. Learn. Res., 16:103-147,24 2015.
[70] Masatoshi Uehara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint 212iv:2102.02981,,22 2021.
[71] Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. arXiv preprint arX1v:2110.04652, 2021.
[72] Peter Van Overschee and Bart De Moor. Subspace identification for linear systems: The- Springer Science & Business Media, 2012.
ory poo-lmmlemmenattio--Apppiiil
[73] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Embed to control partially ob- served systems: Representation learning with provable sample efficiency. arXiv preprint 2XXv:2205.133776 2022.
[74] Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps. arXiv preprint arXiv:2107.03635, 2021.
[75] Liyun Xu, Heishiro Kanagawa, and Arthur Gretton. Deep proxy causal learning and its application confounded bandit policy evaluation. Advances Neural Information Processing Systems, 34:26264-26222 26275, 2021.
14

---

[76] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
[77] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages (0978-10989) PMLR, 2020.
[78] Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Wen Sun, and Alekh Agarwal. Efficient reinforcement learning in block mdps: A model-free representation learning approach. arXiv preprini 2000:222222000303,. 2022.
15


Reviews:
[{"review_id": "lPgY2bGpKyi", "reviewer": "Reviewer_6BgD", "summary": "The paper describes a class of models for decision making under partial observability. It introduces the concept of \"value bridge functions\", which take both history and future observations as inputs as a means to resolve state uncertainty. Then it defines a model class such that the bridge-function analog of Bellman equations has error bounded by a low-rank inner product. The paper shows that this model class captures several common types of POMDPs and PSRs, and provides an algorithm for near-optimal decision making that has polynomial sample complexity.", "questions": "(See numbered items above.)", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The concept of value bridge functions is interesting and novel, and is a nice way to resolve state ambiguity using only observable quantities. It feels akin to value-preserving vs. model-preserving abstractions in the state aggregation literature.\n- The theoretical results appear to be correct, although I don't have the background to be able to check them as thoroughly as I would like.\n- The paper does a great job of clearly communicating the simplest results in the main text, with references to extended versions in the supplementary materials.\n\n**Weaknesses:**\n1. The argmax in step 8 of the algorithm seems extremely expensive. Is it really searching over all M-memory policies and all value bridge functions? What's the runtime?\n2. It's unclear how much of the theoretical results hinge on being able to collect IID samples. This criticism is of course not unique to this paper, as most theoretical results rely on similar assumptions. Nevertheless, it may limit how effective the approach can be in practice.\n3. The sample complexity results rely on an assumption of uniform convergence. What specifically is ensuring that Assumption 2 holds?\n\n**Comments:**\n- The paper presents the theoretical results quite well, but all the examples are purely abstract. It would be helpful to have a concrete example, such as the Tiger problem (which does not have a full-column-rank observation matrix), to help ground the discussion.\n\n\n**Minor Points:**\n- Line 29: \"middle ground\" typo\n- Line 145: \"optimality\" typo\n- Line 151: \"Given a\" typo\n- Line 209: \"undercompleteness\" typo\n- Line 228: seems like $K_h$ is missing a `\\bar`?\n- Line 7 of Algorithm: unbalanced `{`\n- Line 305: should be $J(\\pi)$, not $J(\\pi^\\*)$\n- Lines 370 and 374: $M$ is overloaded, since it is also used to refer to M-memory policies. I suggest using another symbol here.\n- I'm not a huge fan of the name of the algorithm, as \"PROVABLE\" isn't especially descriptive and it seems like it would be hard to search for.\n\n-----\n\n**Review Summary:**\n\nThis paper seems valuable for two reasons: the concept of value bridge functions is a useful way to address state uncertainty without relying on unobservable quantities like states; and the PO-bilinear model class is a concise way to describe a wide range of related partially observable decision problems. While I can only assess the correctness of the approach at a high level, the results seem likely to be of interest to anyone studying sample efficiency under partial observability. Accept.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZbazTRI_-Js", "reviewer": "Reviewer_JmWL", "summary": "This paper proposed a model-free actor-critic framework for POMDPs, where the critic is a value bridge function class that uses fixed memory and future observations as inputs, and obtained PAC-guarantees for models such as HSE-POMDPs, and PSRs. ", "questions": "Is it necessary to include an actor-critic with future observation for solving HSE-POMDP? Could you give a comparison with the method that is used in the paper \"Computationally Efficient PAC RL in POMDPs with Latent\nDeterminism and Conditional Embeddings\"?", "limitations": "The result still has an exponential dependence on the memory size M.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: theoretical results for interesting models such as HSE-POMDPs and PSRs. Also, sample complexity does not have exponential dependence on the horizon. \n\nWeakness: the motivation for using future observations feels a bit unclear to me. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KdK8uKTlzub", "reviewer": "Reviewer_KJ4g", "summary": "The paper derives a bound on the performance error of a POMDP algorithm, where the policy of the algorithm uses a memory-limited observation-action history.", "questions": "- Something I would like to ask the authors, would be: How is the presented result useful, when solving a POMDP in practice?", "limitations": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Unfortunately, I expected something completely different when reading the abstract. I was expecting a new algorithm to solve POMDPs using an actor-critic framework with function approximation. The paper, however, comes from the direction of learning theory, where I have hardly any experience. For me coming from a bit more applied research on POMDPs I was very surprised that there was no numerical evaluation at all for this algorithm. The paper was very hard to read for me and I did not understand very much. As such, I can not judge the significance in the area of learning theory, however, from an applied standpoint, I, unfortunately, could not make out any useful thing from this work. Something I was surprised about was, that there was no discussion on optimal filtering, as usual analysis of the POMDP setup transforms the POMDP to an MDP in belief space. \n\nOverall, I would like to leave it to the other reviewers to judge this work. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AAcMDmi1yMs", "reviewer": "Reviewer_q8PL", "summary": "Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems\nThis paper proposes a new POMDP formulation that can unify different existing formalisms, e.g. tabular POMDP, observable LQG, and PSRs, and HSE-POMDPs.  This unified formulation can be used with an actor-critic algorithm where a policy is a mapping from history to actions, and critics receives as input both history and future observations. The proposed algorithm PO-bilinear actor-critic framework (PROVABLE) is shown to perform agnostic learning by searching for the best memory-based policy. The paper also provides sample complexity analysis.", "questions": "See below", "limitations": "\nThe paper pursues an interesting research direction, which tries to unify existing POMDP formalisms. The approach looks very promising. The proposed design of the critic is very interesting. It would become very interesting if the paper can provides some basic empirical results on toy tasks to show all important claim in practice.\n\t- As the unified framework can now obtain provably efficient learning for most POMDP formalisms. Is there any limitations of its, e.g. can it do the same for any general POMDP formulations (continuous or infinite spaces)?\n\t- How can one understand agnostic learning?\nIn Algorithm, is z just defined as historical observations? Or is it in the form of belief?", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n* Strength:\n    - A framework that unify existing POMDP formalisms.\n    - The proposed actor critic in which the critic is a function of both history and future observations. This critic function is an interesting idea.\n    - Derivations for different special cases, e.g. tabular POMDPs, PSRs, LQG.\n\n* Weaknesses:\n    - Lacking of discussions or motivations for the importance of the proposed idea\n    - Empirical results: Can be on toy tasks", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept