Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of provably efficient reinforcement learning on predictive state representations (PSRs) with function approximation. The main contribution of the paper is a PAC algorithm for PSRs with polynomial sample complexity when competing with the globally optimal policy. Although sharing similar design principles with traditional optimism based methods on POMDPs such as the OMLE algorithm, this work extends the scope of OMLE to a larger set of models (PSRs) featured by direct prediction of the future given the past trajectories. The more general model classes includes several examples including the $m$-step weak-revealing POMDPs, the $m$-step decodable POMDPs, etc. Moreover, the result can also be applied to POMDPs equipped with function approximations such as the low-rank structure, the linear structure, etc.

Overall, the proposed algorithm OptimistiC PSR leArniNg with MLE (CRANE) achieves polynomial sample complexity on a subset of PSR problems with a regularity condition. The $\alpha$-regularity condition on PSR is defined upon the core matrix and is a generalization of the weakly revealing condition. When instantiated to POMDPs, the algorithm can not only solve $m$-step weakly revealing POMDPs but also $m$-step decodable POMDPs, etc.
strength_and_weaknesses: The main strength of this paper is that it provides the first sample-efficient algorithm in learning PSRs, although under an additional regularity assumption. While previous work depends on latent states, this work uses  $M_{o, a, h}, q_0$  that is free from latent spaces. Technically, it leverages the properties of the core matrix $K_h$ to control the product of $M_{o, a, h}$ and thus controls the error induced by the estimation error of $M_{o, a, h}$ and $q_0$. This technique allows the CRANE algorithm to work on a more general PSR classes that subsume both weak-revealing settings as well as decodable settings.

There are a few weaknesses and questions:

- The regularity assumption (Assumption 1) is defined on the core matrix $K_h$ and seems to have limited applicability.  Are there any cases belonging to POMDPs that does not satisfy Assumption 1? The authors could better discuss the applicability of Assumption 1 by providing some counterexamples that violates the regularity condition. 
- The work focuses on providing a polynomial sample complexity, but omits the specific dependency parameters in the main theorems.  Although providing the first polynomial complexity under a more general setting is significant, it is hard to compare the sample complexity result with previous results when restricted to specific instances. Such as, how to compare CRANE with Liu et al. under $m$-step weak-revealing POMDPs?
- In Liu et al. that proposed OMLE, they uses a generalized eluder-type dimension to bound the regret. What is the relationship of the complexity measure used in this paper ($d_{PSR}$) with the eluded-type dimension? Is it possible to extend complexity measure $d_{PSR}$ to a more general one?
- Since no experiments are provided, is CRANE applicable to real-world problems and computational efficient?
- Is there a specific reason that the authors focuses on the model-based setting? Is it possible to extend the optimism-based algorithm on POMDP to model-free settings?

clarity,_quality,_novelty_and_reproducibility: The work is clearly written, the technical novelty seems limited but provides significant results.
summary_of_the_review: This paper provides the first polynomial sample complexity result for PSRs and is thus a solid contribution. The applicability of the assumption is limited, the sample complexity is not sharp, and the empirical impact is unclear. But it is in general a good submission.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of RL with PSRs. The PSR setting is first motivated by its generality and structural properties. Then, a new algorithm, CRANE, is proposed, which is an optimistic MLE algorithm. It takes as input a model class (to represent a class of PSR) and solves an MLE objective to maintain an uncertainty set. Applications of the results are presented on existing problem settings such as weakly revealing POMPDs and decodable POMDPs.
strength_and_weaknesses: Strengths:
- Few papers have studied efficient methods for RL in the PSR setting. This seems to be the first to do this comprehensively.
- A new OMLE algorithm is presented to work with PSR models generally, which encompass many other partially observable models.
- The paper does a good job of demonstrating how their methods can be applied to many existing problem settings.
- The beginning discussion is both clear and well-written and contextualizes the work.
- The theory seems good.
 
Weaknesses:
- The algorithm is pretty similar to existing “OMLE” style algorithms, so the algorithmic novelty is limited.
- To implement the algorithm, it seems a large amount of information must be known about the given problem such as the core test set, the singular value, preconditions in Assumption 3, etc. This begs the question of whether it might just be practically easier to implement existing algorithms for a specific problem, given that one essentially has to know the problem setting anyway. 
- The main selling point of this paper is the generality of PSRs. However, it’s unclear whether this generality affords significantly new insights into the problem. All of the examples given are settings for which efficient, simple algorithms already exist. The result would be stronger if there are interesting, new problems settings where this generality produces new, previously unknown results or much better results than the existing literature. But so far this evidence is either not provided or it is not clear.


Other:
- In the beginning it’s motivated that PSRs can be solved via spectral methods in contrast to difficult to optimize EM-style algorithms, but Alg 1 looks like a very difficult MLE problem. Can the authors comment on this?
- It claimed that Liu et al’s algorithm needs the latent state representation known, but I doubt this is actually a fundamental limitation of their algorithm and analysis and it is more so done for simplification. The concurrent work of Liu et al (2022) seems to support my suspicion as well.
- I do not think it is sufficient to state the main results as just poly( problem inputs ). This makes it very hard to compare across papers.
- How large can we expect U_A to be in general?
- “Assumption 3 can be easily satisfied by eliminating those functions which do not satisfy the regularity or validity.” I’m not confident this is an easy task in practice.
- On Page 6 in the justification of the bracket, it says P is lipschitz but with what constant?

Liu et al “Optimistic MLE—A Generic Model-based Algorithm for Partially Observable Sequential Decision Making”

clarity,_quality,_novelty_and_reproducibility: The problem of partial observability is well motivated and discussed. The paper does a pretty good job of discussing and contrasting itself with related work. However, the clarity could be improved in some parts.
- The notation is very complicated and hard to follow. I’m not sure if there is a good solution for this problem setting, but it should be noted at least. However, there are some obvious things that should be fixed like overloaded $K$.
- Various minor claims throughout seem to have insufficient justifications (see previous section)
- The spacing seems way too compact for the ICLR format. 
- There are some typos throughout the paper. Examples: Contribution 2, ‘Theorem 1 indicate’, ‘wealy-revealing’, etc.
summary_of_the_review: This paper has a lot of potential, but there are still shortcomings in the significance, algorithmic novelty and overall clarity in its discussions. In particular, it’s unclear what analytic insights can be gleaned from the PSR analysis over existing work.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The submission considers a sample-efficient learning for PSRs. The nature of the problem is similar to (Liu et al. 2022), and previous algorithmic framework is extended from POMDPs to PSRs. This generalization to PSR seems relatively easy since the core test-set is provided a priori, and the construction of confidence set based on log-likelihood values can remain the same (as long as we know some rough upper bounds of the rank of PSRs). Results for the most general framework PSR can imply several previous results including tabular POMDPs (Liu et al., 2022) and m-step decodable POMDPs (Efroni et al., 2022), and low-rank POMDPs. Proof ideas and techniques are mostly adopted from (Liu et al., 2022), though it is not entirely straight-forward to make things work for PSRs. 
strength_and_weaknesses: *Strength*

- The paper extended a recent breakthrough in POMDPs to a more general framework, which is a good addition to literature.  

- The positioning of the paper is good -- well-explained related works, how the more general framework can imply previous results, etc. 


*Weakness*

- Given the work by (Liu et al., 2022), it is predictable that the same idea would work in the PSR framework. All POMDP systems are equivalent up to some similarity transformation of belief states (say, as argued in (Boots et al., 2011)), and in a slightly older work by Liu (Liu et al., 2020), the PSR representation of POMDPs was explicitly used. The scope presented in (Liu et al., 2022) is not really because it can only work for POMDPs -- confidence set based on MLE can naturally cover all equivalent systems up to the belief state transformation. So novelty of the paper is limited.  

- It would have been helpful how the authors could get around the issue that there is actually no concept of latent states "S". In (Liu et al., 2022), it seemed that anchoring to latent states helps a lot to make analysis easier. I could imagine that such concept might not be necessary, but it would have been nice if the authors could elaborate more kindly and crisply how they could get around the issue. 

clarity,_quality,_novelty_and_reproducibility: The paper is quite well-written and studies an important and under-explored problem. 
summary_of_the_review: Overall, despite some concerns on technical novelty, I think that this paper makes a good contribution, and could be a nice addition to POMDP literature.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the problem of efficiently learning a nearly optimal policy for PSRs with function approximation. In particular they give an algorithm with polynomial sample complexity. Their algorithm, CRANE, is an optimistic MLE algorithm. Furthermore they give applications to weakly revealing POMDPs and decodable POMDPs. The main selling point of this paper is the generality of PSRs. However the quantity $1/\alpha$ which plays a key role in the bounds is difficult to interpret. Indeed even for simple POMDP settings which were already known to be learnable from previous work, the quantity $1/\alpha$ need not be bounded. The paper also assumes the existence of "core histories" which seems like a natural surrogate for the latent states in a POMDP. 
justification_for_why_not_higher_score: PSRs are a general and powerful model, but the assumptions needed in this paper are difficult to interpret. A cursory reading of Table 1 could leave the reader thinking that the results here subsume all previous work, but even in settings where POMDPs were previously known to be learnable, they do not necessarily satisfy the requirements here. 
justification_for_why_not_lower_score: Nevertheless this paper is an important contribution. It shows how to extend the optimistic MLE framework to a richer class of models that extends and generalizes previous work along some interesting directions.
Decision: Accept: poster