Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths:
* 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.

* 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). 

* 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.

* 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. 

Weaknesses:

* 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). 

* 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). 

* 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?

clarity,_quality,_novelty_and_reproducibility: Overall the paper is quite clearly presented, and the results are correct to my best effort of inspection. More detailed comments can be found in the above "strength and weaknesses" section.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work identifies four structural assumptions of low-rank POMDPs that allow for designing algorithms
with sample complexity that scales:
i) polynomially in the intrinsic dimension $d$ (transition kernel's rank) and the horizon length $H$; and 
ii) *exponentially* with the past and future window sizes $\ell$ and $k$, respectively.

In essence, these assumptions ensure that the belief state can be recovered,
given past and future observation windows of sufficient length.

The proposed theory and algorithmic result (ETC) appear to be novel. 
Yet, this work should be taken with a grain of salt (see Weaknesses), as it involves:
i) several strong assumptions; and
ii) the ETC algorithm has prohibitively large (exponential) sample complexity.

No empirical evidence is provided.
strength_and_weaknesses: Strengths

Makes a step towards building the foundations of a formal framework for analyzing POMDPs 
under the assumptions that the transition kernel admits a low-rank decomposition with
i) past and future sufficiency; and ii) bounded norms of certain pseudo-inverses.


Weaknesses

1. There are several strong assumptions, see below. Further, *no argument is given to show 
the existence of a range of parameters for which these assumptions are mutually satisfied*.

Assumption 3.5 (Future Sufficiency)
 - there exists $k>0$ such that $M$ is invertible

Assumption 5.1 (Bounded Pseudo-Inverse)
 - the norm of pseudo-inverse of $U$ is bounded ($\nu$)

Assumption 5.2 (Past Sufficiency)
 - there exists $\ell>0$ such that $F$ is left invertible
 - the norm of pseudo-inverse of $F$ is bounded ($\gamma$)

2. Under these assumptions, the ETC's algorithm scales *exponentially* with
the past and future window size. Namely, the term $|A|^{ O(k + \ell) }$ in Thm 5.3.

The ETC's sample complexity is prohibitively expensive, unless both $k$ and $\ell$ are either 
i) constants independent of the horizon $H$; or
ii) are bounded by a slowly growing function of the horizon $H$.
clarity,_quality,_novelty_and_reproducibility: Both the paper's main body and it's supplementary are well organized and clearly written.

The proposed theory and the ETC algorithmic appear to be novel. 
Yet, this result should be taken with a grain of salt, as it involves: 
i) strong assumptions; and 
ii) the ETC algorithm has prohibitively large (exponential) sample complexity.

Minor Comments:

page 2: L^p space -> L^p norm space

page 4: rephrase -- "a embedding that are"

page 4: $\phi_h^{\theta}$ has domain $\mathcal{S} \times \mathcal{A}$

page 5: after "In addition, recall that we define": $\tau_h^k$ should be $\tau_h^{h+k}$

page 8: Alg. 1. -- Notation with left super-script for observations is not defined

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.

-- post rebuttal update -- 
Thanks for the clarifications. I increased my score to 6.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
(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.
strength_and_weaknesses: The strength of the paper is it obtained an RL algorithm for POMDPs, and obtained the corresponding sample complexity. 
Weaknesses: The paper introduces several assumptions, and these assumptions seem to strong. Therefore, some discussions would be helpful. 
Moreover, sufficient discussions on comparison with existing results are also lacking. 
clarity,_quality,_novelty_and_reproducibility: The paper contains new results in the sense that they obtained an RL for POMDP with sample complexity. 
The paper seems to have low readability due to notational complexities. 
summary_of_the_review: The paper seems to contain useful results. 
The authors adopted several assumptions that are not clear to figure out how strong they are. 
Therefore, it would be better to discuss more about the assumptions. 
Some efforts are needed to improve readability of the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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. 

However, 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.

Some minor typos:

P.4 "a embedding" -> "an embedding"
P.4 "learn-able" -> "learnable"
P.4: "we aims" -> "we aim"
P.5: "a property motivate us" -> "a property motivates us"

clarity,_quality,_novelty_and_reproducibility: The paper is not written very clearly and is not easy to follow. The use of terminology does not appear to be standard. The transition probability function of the POMDP is called kernel for unknown reasons, and the two functions it is factored into are called features. Since both terms mean something else in the ML literature, their use in this sense is quite confusing.

The choice of name for the algorithm, embed to control (ETC), is also confusing, because a well known paper on a very similar topic from 7 years ago literally has this name in its title:

Watter, M., Springenberg, J., Boedecker, J., & Riedmiller, M. (2015). Embed to control: A locally linear latent dynamics model for control from raw images. Advances in neural information processing systems, 28. 

And, there is nothing to reproduce in this paper, as there are no computational experiments in it. 
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers see the paper as a step towards building a framework for analyzing POMDPs. They found its writing reasonable and the theoretical and algorithmic results satisfactory. However, there are concerns about the assumptions: how strong they are, how they are related to the assumptions used in the prior work, etc. Moreover, the lack of empirical evaluation seems to be an issue (rather a minor issue). I would suggest that the authors take these two points, especially the first one, into consideration and add a thorough discussion of the assumptions in the next revision of their paper.
justification_for_why_not_higher_score: A thorough discussion of the assumptions, their relation to those used in the prior work, and how restricting they are is missing. Moreover, there is no experimental results to support the theoretical findings. 
justification_for_why_not_lower_score: The paper is relatively well-written. It provides non-trivial and novel theoretical and algorithmic results POMDPs. It identifies four structural assumptions of low-rank POMDPs that allow for designing polynomial (in intrinsic dimension and horizon) algorithms.
Decision: Accept: poster