Venue: NeurIPS 2022 Conference

Reviews:

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 introduces a method for approximately solving unknown POMDPs. The method relies on constructing an MDP approximation and a set of policies that incrementally improve coverage of that MDP's state space, thereby increasing the accuracy of the MDP approximation. The approach makes use of a novel exploration objective that uses the concept of barycentric spanners to ensure that every possible observation distribution can be represented as a linear combination of a small "core" set of observation distributions. The resulting algorithm has approximately optimal time complexity and quasi-polynomial sample complexity.
strengths_and_weaknesses: **Strengths:**
- The paper covers a lot of difficult theoretical ground and communicates the high-level ideas very clearly.
- The theoretical results appear to be correct, and the supplementary materials appear to be detailed enough that one could verify the claims presented in the main text, although I was only able to check them at a high level.
- The section "Overview of results" is extremely helpful for communicating the high-level ideas quickly, and for providing a roadmap of the remainder of the paper.

**Weaknesses:**

1. Lines 135-141: I'm a little worried about the way the policies are defined here. It's fine to say a general policy is a distribution over deterministic policies, but when we execute that policy, we sample a deterministic policy from it, and follow that deterministic policy for the entire episode. My concern is: does this scheme necessarily include the optimal policy for the POMDP? Are all trajectories that can be achieved with a fully stochastic policy still supported under the resulting distribution? Is this construction allowed because the policy is conditioned on the entire history?

2. I'm confused about a few things:

    a. Line 46: "A necessary first step towards solving the learning problem is having a computationally efficient planning algorithm." -> Is there a reason why a model-free approach wouldn't work?

    b. Line 120: Why is reward a function of observations $O$? I'm used to seeing it depend on states $S$.

    c. Lines 280-282: "the formal latent state distribution induced by $\pi$ is a linear combination of the formal latent state distributions with the same coefficients" -> Why is this the case?

3. In a few of the definitions and assumptions, I would have preferred to have more detail. However, I appreciate that the paper is quite short on space, so I understand that many sections have been significantly compressed already.

    a. Assumption 1.1 defines the distance between two distributions as the sum of the differences in probability for each outcome. Why use this particular definition for $\gamma$-observability?

    b. In section 2.2, while I appreciate that the notation is presented up front, it would be helpful to see an example for why we need to define the probability of an event $\mathbb{P}^\mathcal{P}_\pi(\mathcal{E})$.

    c. In section 2.4, the presentation of the product space $\mathcal{Z}$ is confusing. It took until much later for me to realize that we need this because it's the form that the POMDP -> MDP conversion requires.

    d. In Algorithm 3, lines 3-4, there are multiple definitions of $k$, which is confusing.

    e. In line 331, I could not find a definition for $e_s$ anywhere. I assumed this was a unit/one-hot vector, so the $\langle e_i, \cdot \rangle$ is equivalent to indexing the second term at position $i$. It would be helpful to have this notation explicitly defined, even if it's just in the appendix.

-----

**Review Summary:**

This paper seems useful for several reasons. First, it introduces an algorithm for learning in POMDPs that achieves optimal time complexity and quasi-polynomial sample complexity. Second, it presents a novel exploration scheme that relies on the concept of barycentric spanners, rather than the ubiquitous "optimism under uncertainty" principle. While I can only verify the correctness at a high level, the material is presented clearly and the high-level ideas are very approachable. Unfortunately, space limitations preclude a more detailed treatment in the main text, but the supplementary materials appear to more than make up for it. Accept.

questions: (See numbered items above.)
limitations: N/A
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 proposes a quasi-polynomial-time algorithm for learning in a class of partially observable Markov decision processes (POMDPs). It builds on the recent set of results that noticed the reductions in the computational complexity of planning in POMDPs that comply with an assumption on the observability in the POMDP. 
strengths_and_weaknesses: Strengths:
* The paper tackles a difficult problem and offers a novel perspective.
* The direction of understanding the implications of imposing practically viable assumptions on POMDPs on planning and learning is an emerging one. It makes sense to investigate problems in this direction. 
* It is a relatively dense yet sufficiently clearly written paper. 

Weaknesses: 
* While I am sure the authors will claim that the paper is a theoretical one, a paper that argues to be not computationally intractable should provide empirical evidence of the implied traceability. 
* It relies on assumptions similar to those in the recent literature. Nevertheless, it is necessary to provide additional and convincing evidence that the assumptions can be checked in practice and they will hold for interesting and large classes of problem instances. The lack of empirical evidence as mentioned in the previous bullet point hurts here as well. 
* While with a different perspective, there is additional recent work that aims to cope with the computational impracticality of planning in POMDPs: https://arxiv.org/abs/2009.11459, https://arxiv.org/abs/2204.00755, and https://arxiv.org/abs/1710.10294. Contrast with this work would help and may broaden the interest in the current paper. 
questions: * When is it easy to check the underlying assumptions?
* How much does the result rely on the complexity reduction in planning under the observability assumption and how much of it is specific to the learning setting? A discussion cannot hurt.
limitations: There is no explicit discussion of the limitations in the paper or an empirical study that would help the reader establish an intuition on the implications and limitations of the results.
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: This paper proposes a novel algorithm for learning tabular POMDPs based on belief contraction and barycentric spanners. 
Both its sample complexity and computational complexity scales exponentially w.r.t the observable parameter $1/\gamma$ and quasi-polynomially w.r.t $S,A,O,H$ and $1/\alpha$.


strengths_and_weaknesses: This is a nice paper with interesting results and novel analysis. I enjoy reading it.

Strength

1. To my knowledge, this is the first quasi-polynomial time algorithm for learning tabular MDPs under reasonable assumptions.

2. The application of barycentric spanners is novel and the analysis is nontrivial.


Weakness

1. The sample complexity is exponential in $1/\gamma$ and quasi-polynomially in all other parameters. If I understand correctly, the algorithms in [LCSJ22] only require a polynomial number of samples to learn a near-optimal policy under the same observable condition. (Nonetheless, the algorithms in [LCSJ22]  seem to require exponential time to implement as pointed out in this work. ) I believe these differences should be pointed out explicitly in the main paper. 

2. The observable assumption can never be satisfied when the number of states is larger than the number of observations. Any comments on how to address this limitation and generalize the results in this paper?


 [LCSJ22] Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? arXiv preprint arXiv:2204.08967, 2022.
questions: 
1.  Given that poly sample complexity is achievable  [LCSJ22], do you think one can combine the techniques in this paper and  [LCSJ22] to obtain poly sample and quasi-poly computation algorithm?

2. The belief contraction result hints that a POMDP can be approximated by an MDP by viewing the most recent M-step observations-actions as states. So I am curious in stead of using the barycentric spanners, can we simply run UCRL or other tabular MDP algorithms on this MDP? 
limitations: NA
review_title: null

Meta-review: metareview: This paper provides the first quasi-polynomial time algorithm for learning a large class of POMDPs. Part of the technics is based on a prior paper on developing quasi-polynomial time algorithm for planning in POMDPs, which achieved a subset of the tasks in this paper. Given all prior algorithms for learning POMDPs requires an exponential amount of time, we believe the contribution is significant and worth the acceptance to NeurIPS.
confidence: Certain
Decision: Accept