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 studies a transfer learning setting, where the agent wishes to learn in a block MDP target environment with the help of an approximated latent simulator. This paper proposed an algorithm that achieves sample efficient learning in such a setting given that
(1) the latent simulator is deterministic while still achieving a small approximation error. In other words, the target environment is nearly deterministic.
(2) the learner must know the approximation error of the simulator or at least a tight upper bound.
(3) the learner has access to a realizable function class of the block MDP non-latent dynamics.
strengths_and_weaknesses: The setting studied in this paper appears to be new, at least in the theoretical literature, and has some practical motivation. However, the assumptions required by the proposed algorithm to work is too strong comparing to recent literature on sample efficient learning in block MDPs.
questions: 1. What is the technical barrier that requires the deterministic latent transition assumption? Overall I feel the proposed approach can sometimes be very suboptimal. If the real environment has high stochasticity, forcing a deterministic approximation and then looking for a robust policy to the approximation error doesn't seem to be a good idea, since the resulting suboptimality gap will be very large.

2. The learner requires the knowledge of the approximation error of the simulator, which further weakens the problem setting and makes it even less practical.

3. Why does the algorithm attempt to learn a non-Markovian decoder when the ground-truth decoder is in fact Markovian?

4. While the paper is only concerned with block MDPs, it makes a rather strong model-based realizability assumption (Assum. 3) which has been shown to be unnecessary for block MDPs, e.g. [1]. This assumption seems to be needed mainly to use the inverse dynamics model techniques. It's not obvious to me whether such an assumption, along with (1) deterministic simulator and (2) known approximation error are necessary or not for the particular setting this paper considers. For example, one could potentially apply the representation learning subroutine in [1] and then call the robust latent policy on top of the learned representation for exploration, which is a much simpler approach both conceptually and computationally.

[1] Zhang, Xuezhou, Yuda Song, Masatoshi Uehara, Mengdi Wang, Wen Sun, and Alekh Agarwal. "Efficient reinforcement learning in block mdps: A model-free representation learning approach."

Overall, I am most concerned with the strong assumptions required for the proposed approach to work. Without further justification, e.g. lower bounds, it's hard to appreciate the theoretical contribution of this paper.

limitations: the assumptions are not adequately discussed and justified.
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 an offline control algorithm for finite-horizon time-inhomogeneous block MDPs. The agent is given observations at each state and an approximate deterministic simulator is available. The agent first infers a nearly-optimal policy the simulator that is robust to perturbations (and so is nearly optimal for the underlying MDP as well) and then, through interaction with the environment, learns a decoder that maps histories of observations to states. Sample complexity of the algorithm is studied and experiments on a synthetic MDP and a gridworld are provided.
strengths_and_weaknesses: Strengths:

The paper is clearly written and well organized. It studies a novel setting (to the best of my knowledge) and provides a sound algorithm along with theoretical and empirical results. Altogether I am in favor of acceptance.

The most interesting contribution is the use of eta-perturbation to model the simulator's inaccuracies. Robust dynamic programming with this perturbation and the guarantees in this paper may have other applications in reinforcement learning in the future. The discussion on this perturbation is however limited and it is not clear how strong or practical this measure of perturbation is.

Weaknesses:

1. The paper would greatly benefit from situating its sample complexity against related settings or algorithms. Some questions that such discussion could answer are: (a) If other algorithms have been proposed for this setting, what is their sample complexity? (b) What lower bounds and upper bounds for other types of perturbations and how does eta-perturbation make the problem simpler or harder? (c) If we knew that such deterministic approximate simulator exists for the MDP but it was not available, how would the bounds change?

2. The paper mentions multiple times that the sample complexity of the proposed algorithm is independent of the size of the state space. While this is true, it is mostly a result of restrictive assumptions on the problem rather than the algorithmic contributions of the paper and the statements can be misleading. The problem is assumed to have a fixed start state, a finite horizon, and transition dynamics that are close to a deterministic simulator. These three conditions limit the number of states that often appear in trajectories, which is independent of the size of the total state space. In fact replacing the fixed start state with a set of possible start states (in the appendix) brings the cardinality of this starting set into the sample complexity. More generally if the starting distribution is over all the states then the size of the state space will appear in the sample complexity.

3. One of the functions approximators is assumed to be large enough to satisfy a realizability assumption (Assumption 3). It is said that the assumption can be satisfied with a deep neural network but the size of this function class appears as a logarithmic factor in the sample complexity. Is this factor finite for a deep neural network and does it depend on the size of the state space or the space of observations?

Typos:
- line 93: q(s|x) -> q(x|s)
- line 134: "at eta-perturbation" -> "an eta-perturbation"
- line 179: instantiating

--------------------------------------
Update after discussions:

Thanks for the clarifications. I increased the score to 7 as the comments 1 and 3 are addressed. I'll elaborate on the second comment:

The problem setting in this paper has two important properties. First, the environment is nearly deterministic in terms of eta-perturbation so that a nearly accurate deterministic simulator exists in the first place. Second, this simulator is available to the agent. The algorithm achieves sample complexity independent of |S| in this problem setting (which is great). Now the reader may want to know if both of these properties are essential to this sample complexity or if the first one is enough. That is, if the environment is nearly deterministic in terms of eta-perturbation, can an algorithm without access to a simulator or without learning a simulator achieve this sample complexity in a non-transfer setting? I understand that achieving this low sample complexity in a general stochastic problem is impossible, but is it also impossible in this _nearly_ deterministic environment? Also I think running some model-free baselines on the mini-grid experiment and seeing if their sample complexity grows with |S| is a good idea.

Another minor comment: Other reviews initially raised doubt about the significance of this result. I suggest referencing or bringing a lower bound from previous work that grows with |S| without the assumptions in this paper. This should better motivate this result and highlight that requiring some assumptions is inevitable for achieving this sample complexity. I can think of Theorem 2 in [1] right now but the authors have a better grasp on this topic and may find a more relevant bound.

[1] Dann, Christoph, and Emma Brunskill. "Sample complexity of episodic fixed-horizon reinforcement learning." Advances in Neural Information Processing Systems 28 (2015).

questions: See weaknesses section
limitations: For horizon H the current algorithm needs H^4 episodes (H^5 steps) but this is stated in the paper. I do not find fixing this limitation within the scope of the current paper.

The current algorithm also has large memory requirements which should be stated.
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: Paper 4378 proposes an algorithm to solve Block MDP when imperfect prior knowledge about the dynamics is available.
They encode this information in a deterministic abstract simulator, assuming the target environment to be a perturbation of it.
The optimal policy in the abstract simulator is used in the target environment with an inverse dynamic model to decode observations to latent states.
The authors provide a PAC analysis of the algorithm's sample complexity which does not depend on the size of the state and observation space.
The algorithm is tested in two environments to evaluate performance and scalability.
strengths_and_weaknesses: ### Main comment
- *Significance*: The analysis of sample complexity is interesting and the design of algorithms with guaranteed sample complexity is a highly-relevant topic for the RL community. This result relies on the assumption of a deterministic abstract simulator and perturbed target environment which is interesting as well. However, it is unclear if this assumption is realistic enough and its feasibility in more complex problems.
- *Clarity*: The paper is well written and organized, with the exception of the related work section that is too short. An extended version of it is included in the appendix. Moreover, some parts of the proofs are not clear, such as the definitions of the various probability distributions at the beginning of Algorithm 2's proof, line 577.

- *Originality*: The main criticism of this work is about novelty. In fact, it builds on top of prior works (adequately cited in the related works) and uses standard techniques, such as optimizing the policy in the abstract simulator and learning a decoder to map observations to latent states. The proof also adapts existing results (Agarwal 2020) to this work.
- *Quality*: There are some flaws and inaccuracies that make it difficult to follow some of the proofs and raise doubts about the validity of the overall claims. In particular:
	- It is not clear what are the assumptions on the function class $F$ which approximates the decoder, and if the bound holds for finite or infinite hypothesis classes.
	- In the proof of Lemma 1 (Appendix, line 497) ends with a disequality. However, in the following line (498), equivalence is stated and it is not clear why.
	- In the proof of Algorithm 2 (Appendix, line 577), the distribution $P_h(x)$ is defined referring to Algorithm 2, Line 9. However, these definitions are not formally defined.
	- In the proof of Algorithm 2 (Appendix, lines 576 and 582), the distribution $Unf(A)$ is first defined as a uniform distribution over action space, and later as uniform conditional distribution of $a$ given $x$.

### Other remarks
- *Reproducibility*: The authors provide an appendix and code as supplementary material. However, the code presents several flaws and requires a certain effort from the readers to reproduce the results. I have been able to run the code for the combination-lock, while the mini-grid gets stuck in the first iteration. It could depend on computation time but no further information is provided in the log, so it is difficult to judge. Then, I have not been able to reproduce the results. I will include hints to improve on that later on.
questions: - Mainly addressing the doubts stated in the *Quality* paragraph. 
- The sample complexity considers only the interaction with the target environment. However, what is the impact of the robust dynamic programming algorithm used to learn a policy in the abstract simulator in the overall bound? Is it still independent of the size of the state space?
- The experiment on the scalability of TASID is defined only with respect to $|S|$. However, in line $343 you claim independence on the size of the observation space. Could you provide empirical evidence of it, for example running the Visual Grid task with larger observations?
limitations: - It would be useful to extend the discussion on how the assumptions of a deterministic abstract simulator and perturbed target environment are realistic.

- Improvement on reproducibility: 
	- Include instruction on installation requirements. I set up the environment by my own, looking at the missing dependencies and appropriate versions. A simple file "requirements.txt" would make the installation straightforward.
	- Include instructions on how to run the code. A readme file with a few commands to reproduce the main experiments is essential. In the current status, I run the scripts in the "experiments" directory without any knowledge of any input parameters.
	- Include information on expected computing time. Comments on the expected time (and associated platform) to complete each experiment is helpful. For example, running the mini-grid experiments does not show any progress after 15 minutes of execution. Since there is no further information on the current status of the run, I killed the process.
	- Include parameter configuration. Use configuration files to exactly reproduce each experiment.
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 authors present TASID, an algorithm which leverages knowledge of an abstract MDP (through an abstract simulator) to efficiently solve a more difficult MDP, using standard assumptions in the block MDP framework. They illustrate the benefits of their method in a synthetic toy problem and a slightly more challenging MiniGrid environment.
strengths_and_weaknesses: Strengths:
- the paper addresses a relevant problem, for instance when a robot but navigate a complex environment but is given a simplified map.
- it looks technically sound (I'm not expert enough of the domain to spot potential flaws)

Weaknesses:
- although the target application is complex robotics navigation problems, the method is demonstrated with toy environments that are not representative of the targeted complexity. We would like to see something closer to the "running example" put forward at the beginning of the problem statement...
- being naive on block MDPs, I had to read other papers to better understand the relationship to POMDPs. A few points could be clarified, see below.
- rejecting part of the related work in appendices is not a good practice. I understand that it is difficult to fit this paper into 9 pages. Maybe the authors could rather move Algorithm 2 to the appendix? 
questions: In Section 2.1, two things could be done to help the reader better understand the level of difficulty of the approach.
- from one side, it must be made clear why solving block MDPs is less daunting than solving full POMDPs. If I understoos correctly the literature, block MDPs are "one-step decodable POMDPs", so a memory of size one is enough. Still if I'm correct, this is why learning an inverse dynamics model with x_h and x_{h+1} is enough to efficiently decode the latent state. I think making this relationship to POMDPs would help non-expert readers like me.
- from the other side,  it must be made clear why solving block MDPs is not trivial. From the current description one may understand that, since two states cannot emit the same observation, one can trivially recover the state from the observation. I think it should be made clear that the "perfect decoder" needs some memory (actually, one-step memory if I'm correct).

Another unclear point is related to exploration and the difficulties it raises in the framework. In particular, lines 268-269 state "We theoretically showed that TASID can solve problems that require performing strategic exploration using a small number of episodes." but the word exploration does not appear at all in the methods. So somehting is not explicit enough here. More precisely, it is unclear to me whether considerations on the perturbation level \eta is related to exploration or more to environment noise.

limitations: Does not apply
review_title: null

Meta-review: metareview: This paper studies how to improve learning efficiency in settings where the agent has access to an abstract, simplified model of the world. 

All the reviewers voted to accept and each pointed out useful clarifications and improvements to the paper. The main contributions of this work are the novel problem setting, algorithms proposed and theoretical results. There are some proof of concept experiments included as well.

The paper is not without flaw though:
- the intro dismisses two related works because those algorithms were "very different". This is either a communication problem or a bad excuse
- the proof of concept experiments don't really match the motivation of the paper well. The toy environments are not representative of the targeted complexity (this is not to say they must be messy, high-dim real sensor data.)

Most importantly the paper has basic correctness issues with the experiments provided:
- reporting results from five runs (seeds) in toy domains and reporting standard deviation (which is likely not well estimated from 5 runs) instead use a more conservative measure of confidence such as student-t CI or bootstrap intervals
- no clear discussion of how the baselines where tuned (they all use the same step-size in each experiment. With Adam the step-size is less sensitive, but its very unlikely that the values of alpha used (and other hypers) were best. We need a clear description of the empirical methodology used here; researcher descent is a very biased process and not good enough
--> This is particularly problematic because the abstract claims the new method outperforms the baselines

These empirical issues are common practice in the field but poor none the less. It is very likely all could be addressed and the main messages of the paper continue to hold. The empirical writeup of this work significantly weakens an otherwise strong paper.
confidence: Less certain
Decision: Accept