Represent to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency
Authors: Lingxiao Wang
Qi Cai
Zhuoran Yang
Zhaoran Wang
Venue: ICLR 2023 poster (2023)

Abstract: Reinforcement learning in partially observed Markov decision processes (POMDPs) faces two challenges. (i) It often takes the full history to predict the future, which induces a sample complexity that scales exponentially with the horizon. (ii) The observation and state spaces are often continuous, which induces a sample complexity that scales exponentially with the extrinsic dimension. Addressing such challenges requires learning a minimal but sufficient representation of the observation and state histories by exploiting the structure of the POMDP.

To this end, we propose a reinforcement learning algorithm named Represent to Control (RTC), which learns the representation at two levels while optimizing the policy.~(i) For each step, RTC learns to represent the state with a low-dimensional feature, which factorizes the transition kernel. (ii) Across multiple steps, RTC learns to represent the full history with a low-dimensional embedding, which assembles the per-step feature. We integrate (i) and (ii) in a unified framework that allows a variety of estimators (including maximum likelihood estimators and generative adversarial networks). For a class of POMDPs with a low-rank structure in the transition kernel, RTC attains an $O(1/\epsilon^2)$ sample complexity that scales polynomially with the horizon and the intrinsic dimension (that is, the rank). Here $\epsilon$ is the optimality gap. To our best knowledge, RTC is the first sample-efficient algorithm that bridges representation learning and policy optimization in POMDPs with infinite observation and state spaces.

Published as a conference paper at ICLR 2023
REPRESENT TO CONTROL PARTIALLY OBSERVED Sys- TEMS: REPRESENTATION LEARNING WITH PROVABLE SAMPLE EFFICIENCY
Lingxiao Wang Qi Cai
Department of Industrial Engineering and Management Sciences
Northwestern University
(Lingxiaowang200 qicai
cai 2022) @ortthesteen.ncc.
Zhuoran Yang
Department of Statistics and Data Science
Yale University
zhuoran. yanggyaln..eeeee .ddu
Zhaoran Wang
Department of Industrial Engineering and Management Sciences
Northwestern University
zhaoranwand haarrnnaang@gaii.. com
ABSTRACT
Reinforcement learning in partially observed Markov decision processes (POMDPs) faces two challenges. (i) It often takes the full history to predict the future, which induces a sample complexity that scales exponentially with the hori- zon. (ii) The observation and state spaces often continuous, which induces sample complexity that scales exponentially with the extrinsic dimension. Ad- dressing such challenges requires learning minimal but sufficient representation of the observation and state histories by exploiting the structure of the POMDP.
To this end, we propose a reinforcement learning algorithm named Represent to Control (RTC), which learns the representation two levels while optimizing the policy. (i) For each step, RTC learns to represent the state with a low-dimensional feature, which factorizes the transition kernel. (ii) Across multiple steps, RTC learns to represent the full history with a oow-dimessional embedding, which as- sembles the per-step feature. We integrate (i) and (ii) in unified framework that allows a variety of estimators (including maximum likelihood estimators and gen- erative adversarial networks). For class POMDPs with low-rank structure the transition kernel, RTC attains an O(1/e²) sample complexity that scales poly- nomially with the horizon and the intrinsic dimension (that the rank). Here is the optimality gap. To our best knowledge, RTC is the first sample-efficien al- gorithm that bridges representation learning and policy optimization in POMDPs with infinite observation and state spaces.
INTRODUCTION
Deep reinforcement learning demonstrates significant empirical successes in Markov decision pro- cesses (MDPs) with large state spaces (Mnih et al., 2013; 2015; Silver et al., 2016; 2017). Such empirical successes are attributed to the integration of representation learning into reinforcement learning. In other words, mapping the state low-dimensional feature enables model/value learn- ing and optimal control in a sample-efficient manner. Mcanwhile, it becomes more theoretically understood that the low-dimensional feature is the key to sample efficiency the linear setting (Cai
"Equal Contribution.

---

Published as a conference paper at ICLR 2023
et al., 2020; Jin et al., 2020b; Ayoub al., 2020; Agarwal et al., 2020; Modi et al., 2021; Uehara et al., 2021).
In contrast, partially observed Markov decision processes (POMDPs) with large observation and state spaces remain significantly more challenging. Due to a lack of the Markov property, the low- dimensional feature of the observation at each step is insufficient for the prediction and control of the future (Sondik, 1971; Papadimitriou and Tsitsiklis, 1987; Coates et al., 2008; Azizzadeneshelii al., 2016; Guo et al., 2016). Instead, it is necessary to obtain a low-dimensional embedding of the history, which assembles the low-dimensional features across multiple steps (Hefny et al., 2015; Sun et al., 2016). In practice, learning such features and embeddings requires various heuristics, e.g., recurrent neural network architectures and auxiliary tasks (Hausknecht and Stone, 2015; Li et al., 2015; Mirowski et al., 2016; Girin et al., 2020). In theory, the best results are restricted to the tabular setting (Azizzadenesheli et al., 2016; Guo et al., 2016; Jin et al., 2020a; Liu et al., 2022), which does not involve representation learning.
To this end, we identify class of POMDPs with low-rank structure the state transition ker- nel (but not on the observation emission kernel), which allows prediction and control a sample- efficient manner. More specifically, the transition admits low-rank factorization into two unknown features, whose dimension is the rank. On top of the low-rank transition, we define a Bellman oper- ator, which performs forward update for any finite-length trajectory. The Bellman operator allows us to further factorize the history across multiple steps to obtain its embedding, which assembles the per-step feature.
By integrating the two levels of representation learning, that is, (i) feature learning at each step and (ii) embedding learning across multiple steps, we propose a sample-efficient algorithm, namely Represent to Control (RTC), for POMDPs with infinite observation and state spaces. The key to RTC balancing exploitation and exploration along the representation learning process. To this end, we construct a confidence set of embeddings upon identifying and estimating the Bellman operator, which further allows efficient exploration via optimistic planning. It is worth mentioning that such a unified framework allows a variety of estimators (including maximum likelihood estimators and generative adversarial networks).
We analyze the sample efficiency of RTC under the future and past sufficiency assumptions. In par- ticular, such assumptions ensure that the future and past observations are sufficient for identifying the belief state, which captures the information-theortti difficulty of POMDPs. We prove that RTC attains an O(1e²) sample complexity that scales polynomially with the horizon and the dimension of the feature (that is, the rank of the transition). Here is the optimality gap. The polynomial dependency on the horizon is attributed to embedding learning across multiple steps, while polyno- mial dependency on the dimension is attributed to feature learning each step, which is the key to bypassing the infinite sizes of the observation and state spaces.
Contributions. In summary, our contribution is threefold.
We identify class of POMDPs with the low-rank transition, which allows representation learning and reinforcement learning in a sample-efficien manner.
We propose RTC, principled approach integrating embedding and control in the low-rank POMDP.
We establish the sample efficiency of RTC in the low-rank POMDP with infinite observa- tion and state spaces.
Related Work. Our work follows the previous studies of POMDPs. In general, solving a POMDP is intractable from both the computational and the statistical perspectives (Papadimitriou and Tsitsik- lis. 1987; Vlassis et al., 2012; Azizzadeneshelii et al., 2016; Guo et al., 2016; Jin et al., 2020a). Given such computational and statistical barriers, previous works attempt to identify tractable POMDPs. In particular, A Azizzadeneshelii et al. (2016); Guo et al. (2016); Jín et al. (2020a); Liu et al. (2022) consider the tabular POMDPs with (left) invertible emission matrices. Efroni et al. (2022) considers the POMDPs where the state is fully determined by the most recent observations of fixed length. Cayci et al. (2022) analyze POMDPs where a finite internal state can approximately determine the state. In contrast, we analyze POMDPs with the low-rank transition and allow the state and observa- tion spaces to be arbitrarily large. Meanwhile, our analysis hinges on the future and past sufficiency assumptions, which only require that the density of the state is identified by that of the future and
2

---

Published as a conference paper at ICLR 2023
past observations, respectively. In recent work, Cai et al. (2022) also utilizes the low-rank property in the transition. Nevertheless, Cai et al. (2022) assumes that the feature representation of state- action pairs is known, thus relieving the agent from feature learning. In contrast, we aim to recover the efficient state-action representation for planning. In terms of the necessity of exploration, Aziz- zadenesheli al. (2016); Guo et al. (2016) analyze POMDPs where an arbitrary policy can conduct efficient exploration. Similarly, Cayci et al. (2022) consider POMDPs with a finite concentrability coefficient (Munos, 2003; Chen and Jiang, 2019), where the visitation density of an arbitrary policy is close to that of the optimal policy. In contrast, Jin et al. (2020a); Efroni et al. (2022); Cai et al. (2022) consider POMDPs where strategic exploration is necessary. our work, we follow Jin al. (2020a); Efroni et al. (2022); Cai et al. (2022) and design strategic exploration to attain sample ef- ficiency in solving the POMDPs. Our work is also related to the previous study of MDP with rich observations, where the authors propose to recover a possibly finite latent state of the observations (Misra et al., 2020; Zhang et al., 2022). In contrast, we propose to recover the latent state based on interaction history. In addition, our work conducts latent recovery under the more challenging POMDP setup. See also $B for additional literature review on related study of latent state space models and MDPs
Notation We denote by R. the space of d-dimensional vectors with nonnegative entries. We denote by (P(2)) the L space of functions defined on X. We denote by A(d) the space of d-dimensional probability density arrays, namely, the d-dimensional nonnegative arrays that sums up to one. We denote by [H] = {1, ... H} the index set of size H. For a linear operator M mapping from an L" space to an L space, we denote by ||M]lmmo the operator norm of M. For a vector x E Rd, we denote by [xr]: the i-th entry of x.
2 PARTIALLY OBSERVABLE MARKOV DECISION PROCESS
We define a partially observable Markov decision process (POMDP) by the following tuple, . A, O, (Px, heE[H) (0x )e(HH) r, H, p1),
where H is the length of an episode, μ4 is the initial distribution of state $1, and S, A. O are the state, action, and observation spaces, respectively. Here PA (. is the transition kernel, O,, (-1-)) is the emission kernel, and r(-) is the reward function. In each episode, the agent with the policy π -)
{mA Jok H) interact with the environment as follows. The environment select an initial state $ drawn from the distribution P1. In the h-th step. the agent receives the reward r(o)) and the observation on, drawn from the observation density 0, sx), and makes the decision @n T& (TT²) according to the policy Th, where of = {0r, di,..... dA- 1, on.) } the interaction history. The environment then transits into the next state 8 drawn from the transition distribution PA. 8h, ux). The procedure terminates until the environment transits into the termination state sH+1-
In the sequel, we assume that the action space A is finite with capacity |A|| = A. Mcanwhile, highlight that the observation and state spaces O and are possibly infinite.
Value Functions and Learning Objective. For a given policy x = {m))eеt)) we define the following value function that captures the expected cumulative rewards from interactions,
"
Ex
Σ
r((N))
(2.1)
Here denote by Ex, the expectation taken with respect the policy æ. the transition dynamics, and the emission. Our goal is to derive a policy that maximizes the cumulative rewards. In particular, aim to derive the c-suboptimal policy such that
v V" Se.
based on minimal interactions with the environment, where n = argmax, V is the optimal policy.
Notations of POMDP. In the sequel, we introduce notations of the POMDP to simplify the discus- sion. We define
a 1++-1 = {an, a 1 of th
(on, 01, oh++}
as the sequences of actions and observations, respectively. Correspondingly, we write r(off) = Ch r(0p) as the cumulative rewards for the observation sequence off. Meanwhile, we denote by
3

---

Published as a conference paper at ICLR 2023
TA h+ the sequence of interactions from the fi-th step to the (h+ + k) step, namely,
Th l++ {on; uh...., Oh+A- 0h+k-11 0h+R) (ah ,0 )
Similarly, we denote by T h++ the sequence of interactions from the h-th step to the (h + k)-th step that includes the latest action dh+ namely,
Th - for, ah...... Oh+ On+*k } {a//* ohh thtt
In addition, with slight abuse of notation, we define IP (Th h ) = P" (oh, Oh+k Ah....................... 0h+k-1) = P (o
h+ | |az (b.tk-1),
b+t 8h) Pa (on (on....., Oh+ 8h, (hy 0h+ 1pT (0 (oht 8h, dn 1) 1. (Th
Extended POMDP. To simplify the discussion and notations in our work, we introduce an extension of the POMDP, which allows us to access steps smaller than zero and larger than the length of an episode.
In particular, the interaction of an agent with the extended POMDP starts with a dummy initial state 81-F for some t > O. During the interactions, all the dummy action and observation se- quences -i_ = {oi-e, a1-é..... Og, ao) leads to the same initial state distribution μl that defines the POMDP. Moreover, the agent is allowed to interact with the environment for & steps after ob- serving the final observation оμ of an episode. Nevertheless, the agent only collects the reward r(o)) at steps h E [H], which leads the same learning objective the POMDP. In addition, denote by [ = [1 - f,...,FF H + k} the set of steps in the extended POMDP. In the sequel, we do not distinguish between POMDP and an extended POMDP for the simplicity of presentation.
A SUFFICIENT EMBEDDING FOR PREDICTION AND CONTROL
The key of solving a POMDP is the practice of inference, which recovers the density or linear func- tionals of density (e.g., the value functions) of future observation given the interaction history. To this end, previous approaches (Shani et al., 2013) typically maintain a belief, namely, conditional density (P(,, = 7²) of the current state given the interaction history. The typical inference proce- dure first conducts filtering, namely, calculating the belief at (h + 1)-th step given the belief at h-th step. Upon collecting the belief, the density of future observation is obtained via prediction, which acquires the distribution of future observations based on the distribution of state $1+11
In the case that maintaining a belief or conducting the prediction is intractable, previous approaches establish predictive state (Hefny et al., 2015; Sun et al., 2016), which is an embedding that is suf- ficient for inferring the density of future observations given the interaction history. Such approaches typically recover the filtering of predictive representations by solving moment equations. In partic- ular, Hefny et al. (2015); Sun et al. (2016) establishes such moment equations based on structural assumptions on the filtering of such predictive states. Similarly, Anandkumar al. (2012): Jin al. (2020a) establishes a sequence of observation operators and recovers the trajectory density via such observation operators.
Motivated by the previous work, we aim to construct a embedding that are both learn-able and sufficient for control. A sufficient embedding for control is the density of the trajectory, namely,
( = )
(3.1)
Such embedding is sufficient it allows us to estimate the cumulative rewards function V of an arbitrary given policy л. In the sequel, we aims to estimate such an embedding and further conduct planning based on the estimated embedding. Nevertheless, estimating such embedding challenging when the length H of an episode and the observation space O are large. To this end, we exploit the low-rank structure in the state transition of POMDPs.
3.1 LOW-RANK POMDP
Assumption 3.1 (Low-Rank POMDP). We assume that the transition kernel IP, takes the following low-rank form for all h [
PA (a(3541| Sh, an) = (5)+)))1)) (sh, ax),
where
0% S Rd. : A A(d)
4

---

Published as a conference paper at ICLR 2023
unknown features.
Here recall that we denote by [H] (1 (1-4,.... l,..,, k} the set of steps in the extended POMDP. Note that our low-rank POMDP assumption does not specify the form of emission kernels. In con- trast, we only require the transition kernels of states to be linear in unknown features.
Function Approximation. We highlight that the features in Assumption 3.1 are unknown to us. Correspondingly. assume that have access parameter space @ that allows us fit such features as follows.
Definition 3.2 (Function Approximation). We define the following function approximation space J ( TeelH] corresponding to the parameter space O,
6), 4h E [H]*. Here, 0g S + R4 is an emission kernel and wh S + R oh S (d) are features for all h E [M]+ and E O. In addition, it holds that (sn, an) defines a probability over 8h+1 S for all h [H] and (sh, (4) E x A.
J [w 0%. 0%)
Here we denote by 4h. &h. Of, a parameterization of features and emission kernels, In practice, one typically utilizes linear neural network parameterization for the features and emission kernels. In the sequel, we write I6 and pd," as the probability densities corresponding to the transition dynamics defined by {veg, d%. 0%) Ne(H) and policy π, respectively. We impose the following realizability assumption to ensure that the true model belongs the parameterized function space F
Assumption 3.3 (Realizable Parameterization). We assume that there exists a parameter 0* E O, such that vh = - 0% = 0% and Of = O2 for all h E [M].
We define the following forward emission operator generalization of the emission kernel. Definition 3.4 (Forward Emission Operator). We define the following forward emission operator Ug L' (S) + L' (Ath Ok+!) for all h [H].
(T
Pd h+t [sh) (o00-f((nn ((hh)sss (
Vf LS),,, Wrlt E Ok+1. (3.2)
Here recall that we denote by Nh (ah - of Athy A x O++1 the trajectory of interactions.
In addition, recall that we define To (T sh) Tp ( (ot 8h; at - for notational simplicity. We
remark that here we omit the dependency of Uj, on the length & of trajectory to simplify the notation.
We remark that when applying to belief or density over state sh. the forward emission operator returns the density of trajectory - -t+t of k steps ahead of the h-th step.
Bottleneck Factor Interpretation of Low-Rank Transition. Recall that in Assumption 3.1, the feature o6 maps from the state-action pair (sh, (x) E S A to a d-dimensional simplex (d)) Equivalently, one can consider the low-rank transition as latent variable model, where the next state 8h+1 is generated by first generating a bottleneck factor qh ~ (ss,,, as) and then generating the next state 5h-1 by [+]" (-)l.. In other words, the probability array of (s(s an) A(d) induces transition dynamics from the state-action pair (sy, an) to the bottleneck factor gn E [d] as follows,
(g 8h, an)
[0] (sh, a4)] qs> 4gh. [d].
Correspondingly, write PA (sh41 (q:) [ (sN+1) qm the transition probability from the bottle- neck factor E [d] to the state 8h+1 E S. See Figure for an illustration of the data generating process with the bottleneck factors.
Understanding Bottleneck Factor. Utilizing the low-rank structure of the state transition requires us to understand the bottleneck factors {gh JeeH) defined by the low-rank transition. We high- partic-
light that the bottleneck factor Qi is a compressed and sufficient factor for inference. ular, the bottleneck factor ςh determines the distribution of next state sh+1 through the feature ( ($ = FF 1 9a = -). Such property motivate us to obtain our desired embedding via decomposing the density of trajectory based the feature set { 1 hhe To achieve such a decomposition. we first introduce the following sufficiency condition for all the parameterized features vff with 0 E θ.
5

---

Published as a conference paper at ICLR 2023
Assumption 3.5 (Future Sufficiency). We define the mapping Lh A Oh+1 R for all parameter 0 E θ and E [H] as follows,
9h
0% 1 (%
where we denote by [=h the i-th entry of the mapping k > 0 that the matrix
4h for all [d]. We assume for some
M f A*
hh Lh 1 (T dry E Rdxd
is invertible. We denote by M the inverse of Mg for all parameter 0 E θ and h E [H].
Intuitively, the future sufficiency condition in Assump- tion 3.5 guarantees that the density of trajectory T h+b in the future captures the information of the bottleneck variable ςh-1- which further captures the belief at the h-th step. To see such a fact, we have the following lemma.
Lemma 3.6 (Pseudo-Inverse
Forward Emission). We define linear operator U : L' L' x O++1) (S) for all 0 E θ and E [H] as follows,
(0%)))(s)) = A (sn) MM ( h+k)
Figure I: Directed acyclic graph (DAG) of POMDP with low-rank transition. Here {sh, $1+1h. for, 9++1}, ah, Th are the states, observations, action, and reward, respectively. In addition, we denote by Qh the bottleneck factor induced by the low-rank transition, which depends on the state and action pair (*), aA) and deter- mines the density of next state 84+1. In the DAG, we represent observable and un- observable variables by the shaded and un- shaded nodes, respectively. addition, we use the dashed node and arrows for the la- tent factor y, and its corresponding transi- tions, respectively.
((TT**)d77
(3.3)
where f E L'Ah x is the input of linear opera- tor 1 and 9% is the mapping defined in Assumption 3.5. Under Assumptions 3.1 and 3.5, it holds for all [H], 0 E O, and II that Uf (IP) PP"...
Here pf." (S)S) maps from all state 8; S to the probability Ph (sa), which is the probability of visiting the state 8h in the h-th step when following the policy π and the model defined by parameter 0.
Proof. See $D.1 1 for a detailed proof.
By Lemma 3.6, the forward emission operator Ug defined in Definition 3.4 has a pseudo-inverse f under the future sufficiency condition in Assumption 3.5. Thus, one identify the belief state by inverting the conditional density of the trajectory fh4k given the interaction history T/ More importantly, such invertibility further allows us decompose the desired embedding ( in (3.1) across steps, which we introduce in the sequel.
3.2 MULPII-TEEP EMBEDDING DECOMPOSITION VIA BELLMAN OPERATOR
To accomplish the multi-step decomposition of embedding, first define the Bellman operator as follows.
Definition 3.7 (Bellman Operator). We define the Bellman operators (a on) L (A4 x OL-1 + (At x Ok+1) for all (an, on) E A x O and h E [H] as follows,
(annn (++1 h+1
h+k+1)= / | (T s2) (Uhtt (sw)dss)
Wrhtk+1 E AA Ok+1
Here recall that we denote by TA h+++1
tott a Atky and 1d ( h+t+t | (h)
pd (o h+++1 8h: ah b+t+t) for notational simplicity.
We call 18) (as, on) in Definition 3.7 Bellman operator it performs a temporal transition from *+++11 and the observation os, given that the density of trajectory n/ to the density of trajectory T411

---

(3.8) Published as a conference paper at ICLR 2023
one take action dn at the h-th step. More specifically, Assumption 3.5 guarantees that the density of trajectory Th A+ identifies the density of Sn, in the f-tth step. The Bellman operator then performs the transition from the density of sp, to the density of the trajectory Th+1 *h+++1 and observation o% given the action ag. The following Lemma shows that our desired embedding (T{"') can be decomposed into products of the Bellman operators defined in Definition 3.7.
Lemma 3.8 (Embedding Decomposition). Under Assumptions 3.1 and 3.5, it holds for all the pa-
rameter 0 E ④ that
po (T
[ (oH, az) ...)...... (o1, an )1 ( (++1
[
#+*+1 #
AR
Here recall that we denote by -H+1 _H+++1 = ( oH+1 while, we define the following initial trajectory density,
H++++] the dummy future trajectory. Mean-
(+ = Uyh1 = (rt), Vo E A x ok+l.
Proof. See $D.3 for a detailed proof.
By Lemma 3.8, can obtain the desired representation ((( - ) based the product of the Bellman operators. It now remains to estimate the Bellman operators across each step. In the sequel, we introduce an identity that allows us to recover the Bellman operators based on observa- tions.
Estimating Bellman Operator. In the sequel, we introduce the following notation to simplify our discussion,
Ch+k-1, 0x++] E A² x OK+1 24 = h+t = for, -
(3.4)
-0 0h-1) E A x Of. We first define two density mappings that induce the identity of the Bellman Operator. We define the density mapping x : A x Of + L" Ok+z) follows,
Wh- 1 Ih-f
h-1 = {on-e, -h--,,00----0 C.. Oh-1,
(3.5)
x (wh-1) 18 (wn-1 24 = -), vwn-1 E O
(3.6)
Intuitively, the density mapping x maps from an input trajectory Wh-1 to the density of 2h. which represents the density of ki-ttes interactions following the input trajectory wh-1- Similarly, define the density mapping v AR+1 0++1 b (A* Oh+1) follows,
v (wpp1,, ah on) 1p (w)== :r Oh 2h+11 ,), v(wn-1, ah on E A x of+1 (3.7) Based on the two density mappings defined (3.6) and (3.7), respectively, we have the following identity for all h [H] and 0 E O,
B (an, on xx (w)-1) 1 (wn-,,, an on), W4a-1 E A x O++1
See $D.2 for the proof of (3.8). We highlight that the identity in (3.8) allows to estimate the Bellman operator B8. (an, σι) under the true parameter 0" e. In particular, both x and whf , are density mappings involving the observations and actions, and can be estimated based on observable variables from the POMDP. Upon fitting such density mappings, we can recover the Bellman operator B (an, oR.) by solving the identity in (3.8).
An Overview of Embedding Learning. We now summarize the learning procedure of the embed- ding. First, we estimate the density mappings defined in (3.6) and (3.7) under the true parameter 0* based on interaction history. Second, we estimate the Bellman operators (Te (ax, ) based on the identity in (3.8) and the estimated density mappings in the first step. Finally, we recover the embedding a (TH by assembling the Bellman operators according to Lemma 3.8.
4 ALGORITHM
In what follows, we present Represent to Control (RTC), an online learning algorithm that iteratively learn the embedding and conduct control based on the embedding learned. In particular, RTC iteratively fits the density mappings defined in (3.6) and (3.7) with respect to the sampling policy, and fit the Bellman operators by the identity in (3.8). Finally, RTC conducts optimistic planning by the confidence set identified in embedding learning. See $C for the detailed procedure and Algorithm for summarization of RTC.
7

---

Published as a conference paper at ICLR 2023
4.1 DENSITY ESTIMATION
In the embedding learning, we need and estimator recover the density mappings defined in (3.6) and (3.7). In practice, various approaches are available in fitting the density by observations. In what follows, we unify such density estimation approaches by a density estimation oracle.
Assumption 4.1 (Density Estimation Oracle). We assume that have access density estima- tion oracle (()). Moreover, for all > and dataset D drawn from the density of size n following martingale process, assume that
(E) pll S C' VV'e log(1/5)/n
with probability at least 1 - 6. Here C' > is absolute constant and we is parameter that depends on the density estimation oracle e(-).
We highlight that such convergence property can be achieved by various density estimations. In particular, when the function approximation space P of E(-) is finite, Assumption 4. holds for the maximum likelihood estimation (MLE) and the generative adversial approach with we log (Pl (Geer et al., 2000; Zhang. 2006; Agarwal et al., 2020). Meanwhile, we scales with the entropy integral of P endowed with the Hellinger distance if P is infinite (Geer et al., 2000; Zhang, 2006). In addition, Assumption 4. holds for the reproducing kernel Hilbert space (RKHS) density estimation (Gretton al., 2005; Smola et al., 2007: Cai et al., 2022) with we = poly (d), where d is rank of the low-rank transition (Cai et al., 2022).
Upon fitting the density mappings Xi, and Y7 in the t-th iterate, we estimate the Bellman operators by minimizing the following objective,
/
(0)
sup 0f EACL1 o++1
|B On ) (wn-1) 17A (wn-1, an 0n) on)l
(4.1)
Here recall that we define the shorthand wh-1 {on-es an ah--....... ...... oh 0h 12
in (3.5).
4.2 OPTIMISTIC PLANNING
The learning of Bellman operators allows to identify confidence interval for the parameter and the associated embedding. In particular, we define the following confidence set,
C³ {o e θ max |66 i |12 (0)) s 3 vl/t, vh E [m]]
(4.2)
where is the tuning parameter in the t-th iterate. To conduct optimistic planning, we seek for the policy that maximizes the return among all parameters 0 E C² and the corresponding features. The update of policy takes the following form,
a' + argmax max (0). #Ell BEC*
Here (²(()) is the cumulative rewards estimated based the embedding induced by 0. See &C for the details. ANALYSIS
In what follows, present the sample complexity analysis of RTC presented in Algorithm 1. Our analysis hinges on the following assumptions.
Assumption 5.1 (Bounded Iscuuo-Inverse). We assume that [|0%/11114 S for all 0 e θ and [H), where v > is an absolute constant.
We remark that the upper bound of the pseudo-inverse Assumption 5.1 quantifies the fundamental difficulty of solving the POMDP. In particular, the pseudo-inverse of forward emission recovers the state density the h-th step based on the trajectory 7 hith from the /-th step the (h + k)-th step. Thus, the upper bound v on such pseudo-inverse operator characterizes how ill-conditioned the belief recovery task is based on the trajectory " sufficiency assumption.
what follows, we impose a similar past
8

---

Published as a conference paper at ICLR 2023
Algorithm Represent to Control
Require: Number of iterates T. set of tuning parameters deterministic policy. Set the dataset (a as empty set for
1: Initialization: Set
all (h,
k) (+))) :) [H] x _
2: for E [T'] do
3: for (h,ak=t) a [H] A do
4: Start a new episode from the (1 f)-th step.
5: Execute policy x'~1 until the (h - f)-th step and receive the observations of h+* 6: Execute the action sequence nn-t regardless of the observations and receive the observa-
tions h+++1 h--+1l
7: Update the dataset Dj h + (a [-- 1
( Estimate the density of trajectory PA (-(1//tt))
8:
end for
9:
ox-2) ((D'(a) for all h [H].
10:
Update the density mappings X and Y/ as follows,
X1 (wx-1) = Pt (wh-1, = )),
Y (1p-1 Oh, oh)
PA (wa-1, ah. Oh 2h+1 .).
11:
Update the initial density estimation of (Tf') + (T
11:
12:
Update the confidence set C' by (4.2).
13:
Update the policy n' + argmax maxgee (T))..
14:
end for
15:
Output: policy set {x (*' hemm-
Assumption 5.2 (Past Sufficiency). We define for h E [H] the following reverse emission oper-
ator F0.- Rd - (O" A for all h [H) E II, and 0 E θ (F ()))))
b
Σ [o p0. (oh qn-1, +/)))) Ve E R
2h 9k-1E
where (I)=)) A x O We assume for some >> 0 that the operator R is left invertible for all E [H]. π E II, and 0 E O We denote by -.. the left inverse of F6.. We assume further that 1-1 $ y for all h E [H] II, and O, where y > 0 is an absolute constant.
| 8 n.
We remark that the left inverse 8.... of reverse emission operator FA, recovers the density of the h-1 bottleneck factor qh-1 based on the density of trajectory - from the (h-t)-th step to the (h-1)- step. Intuitively, the past sufficiency assumption Assumption 5.2 guarantees that the density of trajectory = from the past captures sufficient information of the bottleneck factor Q4-1, which further determines the state distribution at the h-th step. Thus, similar to the upper bound in Assumption 5.1, the upper bound y Assumption 5.2 characterizes how ill-conditioned the belief recovery task based on the trajectory z z/-1 generated by the policy n.
In what follows, we analyze the mixture policy म" of the policy set (r')e returned by RTC in Algorithmn 1. In particular, the mixture policy x" is executed by first sampling policy æ uniformly from the policy set (T') )te(T) in the beginning of an episode, and then executing throughout the episode.
Theorem 5.3. Let T be the mixture policy of the policy set { he(ry returned by Algorithm 1.
Let 3, (v 1) 2 Vwee (I + log(H H A T) for all t [T] and
T = 0( v d² we H² 2 (K- e) log H A/c)/e²).
Under Assumptions 3.1, 3.5, 4.1, 5.1, and 5.2, it holds with probability at least 8 that # is e-suboptimal.
Proof. See $E.3 for detailed proof.
In Theorem 5.3, we fix the lengths of future and past trajectories and l. respectively, such that Assumptions 3.5 and 5.2 holds. Theorem 5.3 shows that the mixture policy m' of the policy set

---

Published as a conference paper at ICLR 2023
{i² hejm returned by RTC is e-suboptimal if the number of iterations T scales with ((1/c²). We remark that such dependency regarding é is information-therotiene learning in MDPs (Ayoub et al., 2020; Agarwal al., 2020; Modi et al., 2021: Uchara et al., 2021), which is a special case of POMDPs. In addition, the sample complexity on the length of horizon H, number of actions A, the dimension d of the low-rank transition in As- sumption 3.1, and the upper bounds // and 7 in Assumptions 5.1 and 5.2, respectively. We highlight that the sample complexity depends on the observation and state spaces only through the dimension d of the low-rank transition, extending the previous sample efficiency analysis of tabular POMDPs (Azizzadenesheli et al., 2016; Jin et al., 2020a). In addition, the sample complexity depends on the upper bounds of the operator norms and in Assumptions 5.1 and 5.2, respectively, which quantify the fundamental difficulty of solving the POMDP. See $G for the analysis under the tabular POMDP setting.
optimal for reinforcement
depends polynomially
REFERENCES
Agarwal, A., Kakade, S., Krishnamurthy, A. and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank MDPs. Advances in Neural Information Processing Sys- tems.
Anandkumar, A., Hsu, D. and Kakade, S. M. (2012). A method of moments for mixture models and hidden markov models. In Conference on Learning Theory. JMLR Workshop and Conference Proceedings.
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M. and Yang. L. (2020). Model-based reinforcement learn- ing with value-targeted regression. In International Conference Machine Learning.
Azizzadenesheli, K., Lazaric, A. and Anandkumar, A. (2016). Reinforcement learning of POMDPs using spectral methods. In Conference Learning Theory.
Cai, Q., Yang, Z.,, Jin, and Wang. (2020). Provably efficient exploration policy optimization. In International Conference on Machine Learning.
Cai, Q., Yang, Z. and Wang. Z. (2022). Sample-efficient reinforcement learning for POMDPs with linear function approximations. arXiv preprint arXiv:2204.09787
Cayci, S., He, and Srikant, R. (2022). Learning to control partially observed systems with finite memory, arXiv preprint arXiv:2202.09753.
Chen, J. and Jiang, N. (2019). Information- considerations batch reinforcement learning. In International Conference on Machine Learning.
Coates, A.. Abbeel, and Ng, A. Y. (2008). Learning for control from multiple demonstrations, In International Conference on Machine Learning.
Efroni, Y.. Jin, C., Krishnamurthy, and Miryoosefi, S. (2022). Provable reinforcement learning with a short-term memory. arXiv preprint arXiv:2202.0398.
Geer, S. A., de Geer, S. and Williams, D. (2000). Empirical Processes in M-estimation, vol. 6.
Cambridge university press.
Girin, I.,, Leglaive, S., Bie, X., Diard, J., Hueber, T. and Alameda-Pineda, X. (2020). Dynamical variational autoencoders: A comprehensive review. arXiv preprint arXiv:2008. 12595.
Gretton, A., Bousquet, O., Smola, A. and Schölkopf, B. (2005). Measuring statistical depen- dence with Hilhert-Schmidt norms. In International conference on algorithmic learning theory. Springer.
Guo, Z. D., Doroudi, S. and Brunskill, E. (2016). A PAC RL. algorithm for episodic POMDPs. In Artificial Intelligence and Statistics.
Hausknecht, M. and Stone, P. (2015). Deep recurrent Q-learning for partially observable MDPs, In 2015 aaai fall symposium series.
10

---

Published as a conference paper at ICLR 2023
Hefny, A., Downey, C. and Gordon, G. J. (2015). Supervised learning for dynamical system learn- ing. Advances in Neural Information Processing Systems.
Jin, C., Kakade, S. M., Krishnamurthy, A. and Liu, Q (2020a). Sample-efficient reinforcement learning undercomplete POMDPs, arXiv preprint arXiv:2006. 12484.
Jin, C., Netrapalli, P., Ge, R., Kakade, S. M. and Jordan, M. I. (2019). A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint urXiv:
Jin, C., Yang, Z., Wang, Z. and Jordan, M. I. (2020b). Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory.
Li, X., Li, L., Gao, J., He, X., Chen, J., Deng, L. and He, J. (2015). Recurrent reinforcement learn- ing: A hybrid approach. arXiv preprint
Liu, Q. Chung, A., Szepesvári, C. and Jin, C. (2022). When is partially observable reinforcement learning not scary? arXiv preprint arXiv:2204.08967.
Mirowski, P., Pascanu, R., Viola, F., Soyer. H., Ballard, A. J., Banino, A., Denil, M., Goroshin, R., Sifre, L.,, Kavukcuoglu, K. al. (2016). Learning navigate in complex environments. arXiv preprint 161iv:661..0300
Misra, D.,. Henaff, M.. Krishnamurthy, A. and Langford, J. (2020). Kinematic state abstraction and provably efficient rich-observation reinforcement learning. International conference on ma- chine learning. PMLR.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I,, Wierstra, D. and Riedmiller, M. (2013). Playing Atari with deep reinforcement learning. arXiv preprint arXiv:
Mnih, V. Kavukcuoglu, K., Silver, D., Rusu, A., Veness, J., Bellemare, M. G., Graves, Riedmiller, M., Fidjeland, A. K., Ostrovski, G. et al. (2015). Human-level control through deep reinforcement learning. nature, 518 529-533.
Modi, A., Chen, J., Krishnamurthy, A., Jiang, N. and Agarwal, A. (2021). Model-free representation learning and exploration in low-rank MDPs. arXiv preprint arXiv:2102.070533
Munos, R. (2003). Error bounds for approximate policy iteration. In ICML, vol. 3.
Papadimitriou, C. H. and Tsitsiklis, N. (1987). The complexity of Markov decision processes.
Mathematics of operations research, 12 441-450,
Rosencrantz, M., Gordon, G. and Thrun, S. (2004). Learning low dimensional predictive represen- tations. International Conference on Machine Learning.
Shani, G., Pineau, J. and Kaplow, R. (2013). A survey of point-based POMDP solvers. Autonomous Agents and Multi-Agent Systems, 27 1-51.
Silver, D.,. Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M. al. (2016). Mastering the game of go with deep neural networks and tree search. nature, 529 489.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, I.,, Lai, M., Bolton, A. et al. (2017). Mastering the game of go without human knowl- edge. nature, 550 359.
Smola, A., Gretton, A., Song, L. and Schölkopf, B. (2007). A Hilbert space embedding for distribu- tions. In International Conference on Algorithmic Learning Theory.
Sondik, J. (1971). The optimal control of partially observable Markov processes. Stanford Uni- versity.
Sun. W., Venkatraman, A., Boots, B. and Bugnell, J. A. (2016). Learning to filter with predictive state inference machines. In International Conference Machine Learning.
11

---

Published as a conference paper at ICLR 2023
Uehara, M., Zhang, X. and Sun, W. (2021). Representation learning for online and offline RL in low-rank MDPs. International Conference on Learning Representations.
Vlassis, N., Littman, M. L. and Barber, D. (2012). On the computational complexity of stochastic controller optimization in POMDPs. ACM Transactions on Computation Theory (TOCT), 1-8.
Zhang. (2006). From c-entropy to KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 34 2180-2210.
Zhang, X., Song, Y., Uchara, M., Wang, M., Agarwal, A. and Sun, W. (2022). Efficient reinforce- ment learning in block MDPs: A model-free representation learning approach. In International Conference Machine Learning. PMLR.
12


Reviews:
[{"review_id": "rH5qLwITPQ", "reviewer": "Reviewer_nfDQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents an approach for learning POMDP models from data based on the idea of factoring the transition function of the POMDP into a product of two mappings, going trough a low-dimensional bottleneck layer that will effectively represent the hidden state. Although this is a sound idea, there is no empirical verification of how it might work in practice, in comparison with other existing methods for learning POMDPs.", "summary_of_the_review": "Although based on an appealing idea, it is hard to say if this method would be useful in practice. Some kind of empirical evaluation would help a lot to persuade readers to adopt this method.", "strength_and_weaknesses": "The paper addresses a central problem in learning suitable models of partially observable environments, particularly when the observation space is large and there is reason to believe that the actual system's state is relatively low dimensional. The presented approach revolves around learning low-level representations of the state, and is thus very suitable for this conference. The idea to factor the transition function into a product using a bottleneck layer (a low-dimensional probability simplex) is appealing, and reminiscent of subspace identification algorithms in the area of linear system identification that use SVD to factor observed data. \n\nHowever, there is no empirical evaluation of the advantages of the proposed approach, so we cannot be sure how effective or even feasible this idea is. Absent such a verification, readers would have very little incentive to understand the mathematical analysis and implement the idea in practice. Because of this, I think the paper is still unfinished.\n\nSome minor typos:\n\nP.4 \"a embedding\" -> \"an embedding\"\nP.4 \"learn-able\" -> \"learnable\"\nP.4: \"we aims\" -> \"we aim\"\nP.5: \"a property motivate us\" -> \"a property motivates us\"\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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": "caXcB6fnPB3", "reviewer": "Reviewer_iXuJ", "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": "The authors propose a reinforcement learning algorithm named Embed to Control (ETC), which learns the representation at two levels while optimizing the policy.\n(i) For each step, ETC learns to represent the state with a low-dimensional feature, which factorizes the transition kernel. (ii) Across multiple steps, ETC learns to represent the full history with a low-dimensional embedding, which assembles the per-step feature. Using the two approaches, they developed RL algorithms that is scalable, and the corresponding sample complexities are obtained.", "summary_of_the_review": "The paper seems to contain useful results. \nThe authors adopted several assumptions that are not clear to figure out how strong they are. \nTherefore, it would be better to discuss more about the assumptions. \nSome efforts are needed to improve readability of the paper.\n", "strength_and_weaknesses": "The strength of the paper is it obtained an RL algorithm for POMDPs, and obtained the corresponding sample complexity. \nWeaknesses: The paper introduces several assumptions, and these assumptions seem to strong. Therefore, some discussions would be helpful. \nMoreover, sufficient discussions on comparison with existing results are also lacking. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RkLuWyOCsO", "reviewer": "Reviewer_reeX", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 sample-efficient learning of POMDPs. The paper considers POMDPs with infinite (continuous) state and observation spaces and admitting low-rank latent transitions with features belonging to a certain feature set. The main result is the identification of a sufficient condition called past- and future-sufficiency, along with an algorithm Embed-To-Control (ETC) that achieves sample-efficient learning in this setting.", "summary_of_the_review": "The paper provides results for sample-efficient learning of POMDPs with continuous state/observation spaces with unknown features, though it may be a more direct extension of recent works along this line than currently claimed. ", "strength_and_weaknesses": "Strengths:\n* POMDPs is a challenging problem that received a lot of recent attention in the RL theory community, where additional tractability assumptions are required in order to achieve sample-efficient learning even in the basic tabular setting. The paper generalizes such studies into the infinite-state and observation setting and provides a set of sufficient conditions and a sample-efficient algorithm. This could serve as a starting point of future studies on the same topic.\n\n* The past- and future-sufficiency conditions are tailored to the continuous setting, and are new to my best knowledge. The future-sufficiency condition is similar as the multi-step revealing condition of (Liu et al. 2022), but is slightly different in the choice of the norm ($1\\to 1$ instead of $2\\to 2$) on the matrix pseudo-inverse, which in my opinion is a better choice for the continuous setting (where $L_1$ norms have probabilistic meanings whereas $L_2$ norms may blow up). \n\n* The algorithm achieves sample complexity that is polynomial in $A^{k+l}$ and all other problem parameters including the feature dimension and the past- and future-sufficiency parameters.\n\n* The problem setting allows unknown features, generalizing the recent work of Cai et al. (2022) which assumes known features. This improvement is more minor though as now it is pretty well-understood how to do this in a modular fashion, e.g. in fully-observed MDPs by any algorithm for the Bellman rank or FLAMBE setting. Further, everything about function class is wrapped into the density estimation oracle in this paper. \n\nWeaknesses:\n\n* Despite the paper considers the continuous setting, it feels like the actual algorithm builds upon many existing algorithms, which does not seem to be adequately discussed in the main text. For example, the overall algorithm using confidence set (4.2) sounds like a global optimism algorithm similar as the OMLE algorithm of (Liu et al. 2022), where the risk functional (4.1) looks like the OOM-UCB type per-step risk function of (Jin et al. 2020a). It may be good to expand on these similarities in the paper, and what are the differences in the algorithm / analysis required in the current setting. In turn, maybe some current discussions like the “bottleneck factor interpretation” can be put into the appendix (it feels secondary, though I do like that discussion). \n\n* Could the authors provide more intuitions on why the past-sufficiency parameter? The past-sufficiency looks a bit like the decodability condition (Efroni et al. 2022) for me, whereas future-sufficiency looks like the revealing condition. In tabular POMDPs, either one itself is sufficient for sample-efficient learning. Why does the present approach require both past- and future-sufficiency? Is it an artifact of the algorithm (in which case, pointing out why that is the case would be good for future understandings of this approach). \n\n* Minor point: In the sample complexity, capacity of the function class is wrapped entirely in the density estimation coefficient $w_{\\mathfrak{C}}$. For example, when $|\\Theta|$ is finite, is it the case that we can always get $w_{\\mathfrak{C}}\\le \\log|\\Theta|$ automatically by MLE?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "DxqJXk_z87U", "reviewer": "Reviewer_6Ax4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work identifies four structural assumptions of low-rank POMDPs that allow for designing algorithms\nwith sample complexity that scales:\ni) polynomially in the intrinsic dimension $d$ (transition kernel's rank) and the horizon length $H$; and \nii) *exponentially* with the past and future window sizes $\\ell$ and $k$, respectively.\n\nIn essence, these assumptions ensure that the belief state can be recovered,\ngiven past and future observation windows of sufficient length.\n\nThe proposed theory and algorithmic result (ETC) appear to be novel. \nYet, this work should be taken with a grain of salt (see Weaknesses), as it involves:\ni) several strong assumptions; and\nii) the ETC algorithm has prohibitively large (exponential) sample complexity.\n\nNo empirical evidence is provided.", "summary_of_the_review": "The paper is well written and contributes to the better tackling of POMDPs. However, it remains unclear to me to which extent this paper is a big step forward. The theoretical results are missing the set of parameters where all assumptions hold, and no empirical evidence is provided.\n\n-- post rebuttal update -- \nThanks for the clarifications. I increased my score to 6. ", "strength_and_weaknesses": "Strengths\n\nMakes a step towards building the foundations of a formal framework for analyzing POMDPs \nunder the assumptions that the transition kernel admits a low-rank decomposition with\ni) past and future sufficiency; and ii) bounded norms of certain pseudo-inverses.\n\n\nWeaknesses\n\n1. There are several strong assumptions, see below. Further, *no argument is given to show \nthe existence of a range of parameters for which these assumptions are mutually satisfied*.\n\nAssumption 3.5 (Future Sufficiency)\n - there exists $k>0$ such that $M$ is invertible\n\nAssumption 5.1 (Bounded Pseudo-Inverse)\n - the norm of pseudo-inverse of $U$ is bounded ($\\nu$)\n\nAssumption 5.2 (Past Sufficiency)\n - there exists $\\ell>0$ such that $F$ is left invertible\n - the norm of pseudo-inverse of $F$ is bounded ($\\gamma$)\n\n2. Under these assumptions, the ETC's algorithm scales *exponentially* with\nthe past and future window size. Namely, the term $|A|^{ O(k + \\ell) }$ in Thm 5.3.\n\nThe ETC's sample complexity is prohibitively expensive, unless both $k$ and $\\ell$ are either \ni) constants independent of the horizon $H$; or\nii) are bounded by a slowly growing function of the horizon $H$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster