Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper identifies a technical issue when integrating state abstraction and model-based reinforcement learning, namely that obtaining iid samples for the next-state distribution may not be feasible in general. To resolve this issue, the paper suggest, unsurprisingly, that a simulator could be employed.
main_review: The paper explores the space in the intersection of model-based RL and abstraction, two key ideas for sample efficiency in RL. A model-based algorithm is defined as one that constructs a transition model of the MDP (could be base or abstracted MDP), and state abstraction is defined, as far as I can say, as an aggregation function.

In order to apply existing model-based RL machinery, it is imperative to get iid samples of the next-state distribution. The nice insight of the paper is to show, concretely, and via a counter example, that such a luxury may not always be available. Intuitively, the fact that the first transition into an abstract state has occurred may give us some clue about the probability of the next transition into the said abstract state, which highlights a dependence between the two samples.

Even though I really value the observation made here, I have two concerns which I list below:

1- The negative result is very narrow. First, it is debatable if the concept of abstraction should just be restricted to state aggregation. It seems to me that the counter example could have been presented for a broader definition of "abstraction", for example, at least get extended to those that probabilistically map to abstract states. Now, even when restricting to the aggregation class, the presented result seems to have a narrow scope. For example, the kind of state abstraction chosen here is obviously not the one and only abstraction function used for RL, or model-based RL for that matter. This particular state abstraction function is, for example, not transitive. Having a low L1 loss is also unnecessarily specific, and could really be generalized to arbitrary f-divergences and/or IPMs, which facilitate the generalization of this result to continuous state spaces (not just tabular problems).

2- The provided remedy, i.e., using a simulator is quite anticlimactic. Notice that the sample efficiency analysis of model-based RL with abstraction may fail for reasons other than iid issue, but if the iid issue is the only hurdle, i believe there are ways to work around the independent samples and still get concentration inequalities using martingales. So I feel like the first half of the paper, namely identifying the problem is nicely done and complete, but a more advanced analysis using independent samples could have really nicely complement the first half.


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: In this work the authors present a theoretical analysis of the problems which arise when applying model based RL methods to abstracted MDPs. An abstracted MDP is obtained by mapping each state of the original MDP to a new abstract state. Subsequently, a model of the
transition dynamics of this abstracted MDP can be learned. This learned model can be used to solve the abstracted MDP and the resulting policy can be applied to the original MDP. The authors,  examine whether there are any theoretical guarantees regarding the quality of the learned model of the abstracted MDP and of the produced policy. They conclude that collecting data in an online fashion can break the independence assumption made by most MBRL methods in the abstracted case. 
main_review: The paper examines the interesting problem of learning models of abstracted MDPs. Many popular MBRL methods use deep neural network function approximators to learn models of the MDP dynamics, and can be considered as models of abstracted MDPs. 

The analysis presented in the paper separates the abstraction and model learning parts, which is not the case in most real world methods. Moreover, it is not clear how the conclusions drawn by the paper can be used to inform the design of better MBRL algorithms in abstracted MDPs.  The authors show that having access to a perfect simulator to sample independent transitions is necessary in order to have theoretical guarantees, but do not propose any methods for achieving the same effect in the online setting which is mostly used in real-world problems. 

There is room for improvement in terms of how the ideas are presented in the paper.

Minor comments:
line 57, 58: Could be rephrased
line 78 - 82: Could be rephrased
Whole paper: Fix the notation of the for every symbol so that the arguments are not subscripts.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper deals with model learning when given access to a specific type of abstraction, model-irrelevance (or bisimulation). It states the when the data is collected online, learning an accurate model in the abstract MDP is not possible since the samples are no longer independent (as required by MBRL methods that use concentration inequalities to bound the error of the estimated model). It then shows that given simulator access, this problem no longer exists as samples can be collected from anywhere in the state space. 
main_review: Originality: I really like the motivation of this work, but I think the writing eventually ends up confusing the reader more than highlighting the main problem. To me, the motivation seems to be to show why/when model learning guarantees can fail when using function approximation (a general state abstraction technique). That, I think is a good question to ask. And it in the context of independence of samples, it would then lead to the following question: Even in the case of iid data, can function approximation (or state abstraction) induce dependence in the samples and thus rule out guarantees for methods that learn a model in the abstracted space? However, the authors stick to the case of online data collection, which in and of itself leads to dependence in samples. Therefore, I believe the working of the paper from that point on does not shed much insight. In other words, now irrespective of whether we are in the original MDP or in the abstract MDP, the samples are dependent in both cases. I don't think the authors' motivation stems from this setting. Rather, the setting should be about the dependence in samples induced by abstraction even when the data is iid. 

Quality and Clarity: Unfortunately, the paper lacks massively in these two regards. It is hard to follow, sometimes due to bad/nonintuitive notation and sometimes due to sloppy writing. I think improving in this regard can help bring out the right motivation of the paper, which I think holds good value.

Significance: In it's current state, I do not think the paper is significant enough. However, if the authors can clarify the motivation, improve the writing, and slightly change the main question they try to ask (as detailed above), I think the paper and the negative result could be extremely valuable to both the theoretical and empirical RL communities. 

Questions/Clarifications:

My main question is regarding the following statement + on the above comments:

"Other related work is in the area of MDPs with rich observations or block structure [4, 10]. However, in that setting each observation can be generated only from a single hidden state, which means that the issue of non-i.i.d. data due to abstraction does not arise."

It seems to me that here the authors are trying to say that the abstraction property is key to dependence in samples. However, I cannot gather what exactly they are referring to. Why is the state abstraction non-stationary? Why do the authors call the abstract MDP as a POMDP? What is so special about bisimulation that results in dependence? Looking at the counter examples given in the paper, it seems like the dependence is simply because of the online data collection procedure, and not due to the state abstraction itself. I think clarifying this really holds the key to the contributions of this paper. 


--------------- Score updated from 4 to 7 after multiple discussions with the authors ---------------
limitations_and_societal_impact: Suggestions: My suggestion would be to bend the main problem the authors try to answer here. This is again pointed to in my comments in the 'originality' section. I think doing that can push this paper towards a clear acceptance. 

I do not think there any explicit negative societal impacts of this work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the transition model accuracy guarantee in model-based RL on abstract (tabular) MDP is discussed. 

The problem that the sample independence assumption, which is important for guaranteeing meaningful model accuracy bound, is not always valid when the state is abstracted by approximate model similarity abstraction.  

To address this problem (to realize i.i.d sampling), 
the use of a simulator, which can re-start from arbitral state-action pair, is proposed. 

main_review: Key strength:  
The key insight "the simulator in which the agent can restart from any state-action pair" is interesting.  
In the general RL setting (even if the simulators are used), the agent collects trajectory starting from the initial states, and the use of the "restart" function is not focused on.  
The insight of this paper promotes utilizing the restart function. 
(For now, the insight is for MBRL setting on certain abstract MDP, but the insight of the paper motivates post cursors to conduct a discussion about the benefit of the simulator equipped with the restart function.)  

Key weakness:  
No empirical result is provided. I understand the paper is a theoretical one, but the quality of the paper should be much improved if the empirical result (even in a simple grid-world case) to support the authors claim or insight is provided (e.g., is Algorithm 3 actually works well?).  

Typo: 
Line 374: rl -> RL  
Line 397: q-learning -> Q-leanring  

limitations_and_societal_impact: yes
review_title: null

Meta-review: The paper discusses the issue of independence of samples when abstractions are used with online exploration in RL, and the central result is a negative result, that these samples cannot be treated simply as iid and concentration bounds designed for such settings such as Hoeffding's (with union bound to handle L1 error) do not apply. 

The authors are noted, however, that formal negative results take the form of impossibility results and/or lower bounds which *do not depend on a specific approach to analysis*. Even better, they should be algorithm independent, or at least apply to a wide range of algorithms. In fact, such negative results in RL are frequently published in top conferences in recent years, and the authors can consult the works of authors like Andrea Zanette, Ruosong Wang, Gellert Weisz, etc., as examples. In contrast, the "negative result" of the current paper is specific to an algorithm (model-based, which is fine as it is simple and representative) and a specific type of approaches to analysis (assuming iid and applying concentration bounds when the conditions are violated). This makes the negative result relatively weak and informal. (Sometimes these informal negative results can be useful and insightful, but they usually appear as a side discussion and cannot serve as the main result of a paper, particularly because the insights they offer are often speculative due to the informal nature of the results.)

Besides, there is a plethora of positive results and analysis techniques that potentially apply to the setting studied in the paper, which the paper fails to discuss. In particular, martingale concentration bounds, law of iterated logs, and a few other techniques come to mind when there is dependence between samples (e.g., when the number of samples is a stopping time that depends on the outcomes of random state transitions); https://arxiv.org/pdf/1708.07367.pdf has used quite a few of such techniques and can be a good reference to study. While it is true that few of existing works consider abstractions, the complication introduced by the abstraction is that different samples from the same abstract state are not identically distributed (the second "i" in "iid"), but advanced concentration bounds (e.g., Freedman's) usually don't assume identically distributed variables and can readily handle them. (Authors also made a similar point in Lemma 3, which directly follows from Hoeffding + union bound.) 

Furthermore, one can also think of abstractions as a special case of function approximation: for example, on a given dataset, model-based RL with an abstraction is exactly equivalent to Fitted-Q using a corresponding "piecewise constant" function space. To this end, existing analyses that handle generic function approximation need to be discussed. Instead of proving concentration for each abstract state, you would use uniform convergence argument over the entire function space to handle concentration; a good reference is Antos et al (https://link.springer.com/content/pdf/10.1007/s10994-007-5038-2.pdf) which assumes beta-mixing data. It is true that this paper assumes a fixed behavior policy and does not consider changing policies (the authors emphasized this in post-rebuttal discussions), but there are other more recent results that consider specifically online exploration with generic function approximation; see https://arxiv.org/pdf/1610.09512.pdf and follow-up works.

Finally, a reviewer mentioned the lack of experiments. While that is certainly not a weakness of the paper, the authors can consider this as a way to strengthen their negative result. As of now, it is unclear what happens if one uses the "wrong" algorithm in practice, even if we know it is not theoretically sound. It may perform very well in practice and can be a hard-to-beat baseline compared to more sophisticated techniques that are theoretically sound. If degenerate empirical performance can be demonstrated, the issue will draw more attention and convince the community to treat the problem more seriously. 
Decision: Reject