Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The paper considers the problem of partitioning the atoms (e.g., pixels of an image) of a reinforcement learning task to latent states (e.g., a grid that determines whether there exists furniture in each cell). The number of states grows exponentially with the number of cells of the grid. So the algorithms that are polynomial in the number of states are not efficient. The paper considers the factored block Markov decision process (MDP) model and adds a few more assumptions. Generally, this model and assumptions guarantee that the cells of the grid partition the atoms (i.e., each atom depends on only one cell), the atoms in a cell are dependent (in the probabilistic sense), the conditional probability of the parent value of the states and the action given the next state is 0 or 1 is separated (i.e., the difference is bounded away from zero), and the regressor classes that are used are realizable. The paper shows that this is enough to give an algorithm that partitioned the atoms in each step with high probability and its time complexity is polynomial in the number of cells and logarithmic in the number of atoms.

The model and assumptions are very natural in many applications, and the theoretical guarantee is very nice. Moreover, the paper is very well-written and clear. However, I would like to see some experiments regarding this model. Even an experiment on a synthesized dataset with the grid and furniture example would be very interesting.
review_title: Factorized reinforcement learning

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies reinforcement learning in spaces with a large number of states by modeling the states using a factored / latent representation. This problem has been studied in the non-factored setting by Du et al (2019), and this paper extends to factored settings. This is an interesting problem.

Overall, I found the paper difficult to follow since it is not presented well. It would help to distill the novelty and main ideas in the algorithms early. Section 2 on the setting includes too many technical details that can be deferred to later sections. 

This paper also does not verify the feasibility of their algorithms through experiments. Compare this to the cited papers which include experiments to show the validity and feasibility of their algorithms.
review_title: Potentially interesting paper; needs better presentation

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##########################################################################
Summary: 
This paper studies reinforcement learning under the setting of factored block MDP, where the observations are generated from latent factors. The paper presents a framework with separate parts for learning the policy, the emission structure, and the model, respectively. The performance of the proposed framework is theoretically analyzed. 

##########################################################################
I find the paper theoretically sound but lean towards rejection at this point. 
##########################################################################
Major comments:
It is appreciated that the authors provide the complete theoretical analysis of the proposed framework, and the analysis is reasonable and sound to me.

My main concern is that the paper combines several settings together without much technical novelty. The settings are somehow artificial in the sense that a lot of assumptions are made only for obtaining theoretical results, and in addition, no experimental study was provided.

Detailed comments:

“Our goal here is to define a problem setting that …” This sounds to me that the paper aims to find a setting that can be analyzed with proofs but not the settings that are natural and have real applications. In addition, it would be good to inform the reader which settings are inapplicability or intractability. 

The discussion on the rationale of using factored transition is not necessary (as it is well-known as the basic part of graphical models).

The paper adopts many assumptions, but not all of them are well-justified. E.g., 
-	“For our purposes, we assume a deterministic start state and assume without loss generality that each state is reachable at exactly one time step” It is not clear to me what the "purposes" are. What is the consequence if the start state is not deterministic? Why do we assume that each state is reachable at exactly one time step?
-	In addition to making the problem trackable, do we have the disjointness property and Assumption 1& 2 in real applications (such as the image example in the paper)? 
-	The paper assumes two computational oracles and one planning oracle. Please provide the accessibility of these oracles so one can evaluate the feasibility of the proposed method. 



The presentation is often flowery without being clear. E.g.,
-	“There are many possible ways to add rich observations to a factored MDP resulting in inapplicability or intractability.” Please clarify with respect to what the inapplicability or intractability is taken (e.g., learnability or computability). 
-	Please be consistent. For example, “the observations are emitted by latent states” and “the observations are emitted by latent factors”; “decode the latent state” and “decode the factors”. They are making the paper hard to follow.
-	In Def 2, ch() is defined to be [d]->2^[m], making x[chi(i)] not well-defined. 
-	“An agent is responsible for mapping each observation x ∈ X to individual atom …” What is the difficulty in having such a mapping? From the paper, the atoms are simply given by the observations.

There are almost 30 pages proof in the appendix. Are all the proofs new? If not, please state clearly that which proofs can be found in the existing works and which can be obtained by adapting the proofs in other works.  Otherwise, it is hard to evaluate the contribution of this paper.  

review_title: A sound paper with limited novelty and unclear contribution

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a new result for provably efficient exploration in rich observation RL with assuming that the underlying structure is a factored block MDP. Under this setting along with some other dynamics assumptions, e.g., reachability and identifiability, the algorithm achieves a sample complexity independent of the number of latent states |S| but the number of factors d (which can be much smaller than |S|). Although the algorithm uses a similar approach as in Du et al. 2019, the adaptation is not that straightforward. I appreciate the novelty of this result in the direction of combining factored MDP with rich observation RL.

My major concerns are:
1. Since this work takes a similar approach as in Du et al. 2019, i.e., learn decoding functions and transition model level-by-level, it also requires additional dynamics assumptions e.g., reachability and identifiability which are described by hyperparameters such as \eta_{min} and \beta_{min}. And the sample complexity can still be pretty large if \eta_{min} and \beta_{min} are very small even with a small d. 
2. In one recent work by Feng et al. (https://arxiv.org/abs/2003.06898), a general framework is proposed to attack the rich observation RL problem under the block MDP setting without any dynamics assumption. It might be good to include a mention of this work and some discussions about whether the approach in Feng et al. can be extended to the factored block MDP setting (if not, what is the main challenge).
3. For the hyperparameters such as \eta_{min}, \beta_{min}, \kappa, and d, how should a practitioner select these values without any prior knowledge? Can this be done in an adaptive manner as we run the algorithm? Or must we choose very conservative values (e.g., very small \eta, \beta, and big \kappa) initially to guarantee the learning accuracy?

Minors:
- Some notations are a little bit confusing for first-time readers. More clarification can be added, e.g., 1) A parent function is a set-valued map from an integer in [d] to a subset of [d]; 2) s[pt(i)] := {s[j] | j \in pt[i]}. A simple example would be even better for readers to quickly understand.
- I appreciate this work as a theoretical result. It would be more promising if some preliminary experiments can be conducted to compare with prior works, e.g. Du et al. 2019 and Feng et al. 2020, to further demonstrate the benefit of a factored MDP setting in practice.

I would like to change my score if the authors can address my concerns.


review_title: Questions about the dynamics assumptions and hyperparameters.

Meta-review: This paper considers the reinforcement learning in rich observation setting. Concretely, the authors provide a provable sample efficient algorithm for the rich-observation factored MDP. As the majority of the reviewers commented, although the techniques used in the proof share some similarities to the existing work, the analysis for the whole algorithm is still challenging. As a theoretical oriented paper, I think this paper should have a position in ICLR. 

The major concern of the paper is the necessity of the assumptions (R2). The validation and justification of the Assumptions should be stated clearly in main text, even they are adapted from the prior work. 
Decision: Accept (Poster)