Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
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. 

Weakness: the motivation for using future observations feels a bit unclear to me. 
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
Determinism and Conditional Embeddings"?
limitations: The result still has an exponential dependence on the memory size M.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: **Strengths:**
- 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.
- 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.
- 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.

**Weaknesses:**
1. 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?
2. 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.
3. The sample complexity results rely on an assumption of uniform convergence. What specifically is ensuring that Assumption 2 holds?

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


**Minor Points:**
- Line 29: "middle ground" typo
- Line 145: "optimality" typo
- Line 151: "Given a" typo
- Line 209: "undercompleteness" typo
- Line 228: seems like $K_h$ is missing a `\bar`?
- Line 7 of Algorithm: unbalanced `{`
- Line 305: should be $J(\pi)$, not $J(\pi^\*)$
- Lines 370 and 374: $M$ is overloaded, since it is also used to refer to M-memory policies. I suggest using another symbol here.
- 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.

-----

**Review Summary:**

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

questions: (See numbered items above.)
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems
This 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.
strengths_and_weaknesses: 
* Strength:
    - A framework that unify existing POMDP formalisms.
    - The proposed actor critic in which the critic is a function of both history and future observations. This critic function is an interesting idea.
    - Derivations for different special cases, e.g. tabular POMDPs, PSRs, LQG.

* Weaknesses:
    - Lacking of discussions or motivations for the importance of the proposed idea
    - Empirical results: Can be on toy tasks
questions: See below
limitations: 
The 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.
	- 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)?
	- How can one understand agnostic learning?
In Algorithm, is z just defined as historical observations? Or is it in the form of belief?
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
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. 

Overall, I would like to leave it to the other reviewers to judge this work. 
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.
review_title: null

Meta-review: metareview: This paper contributes to advancing our understanding on when and how sample efficient learning is possibly in partially observable dynamical systems. The authors introduces a framework that encompasses a wide range of relevant settings (e.g., LQG, POMDPs, PSR) and propose a general algorithm to solve this general setting and derive theoretical guarantees on its sample complexity. Overall the contribution is novel, non-trivial, and interesting. I encourage the authors to include part of the rebuttal, which effectively clarifies some aspects of the paper and makes it accessible to a broader audience.
confidence: Certain
Decision: Accept