Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Hi,

First I want to thank authors for putting this together, I enjoyed reading it. 

*Summary* Authors propose mixing Block MDP and Hidden Parameter MDP, and offer and algorithm (loss function) to learn this model that they claim to be useful for sample complexity and transferability among environments (that share state and action space). The proposed method showed promising results in experiments. 

In general I enjoyed reading the paper, and I believe the idea is novel, a good step toward multi-task learning and well-written. My main concern is the validity of Block MDP assumption in real world. 
1. Authors have to be more upfront on why this assumption is needed, it's hard now to exactly find why do we need Block MDP assumption, what would break if we were to relax this?
2. Authors have an experiment for this, but I would like to see how much p- probability of sticky observation would actually affect the performance, for example what would happen if we increase p, and what point the algorithm will break down? (Basically, I'm asking how sensitive the algorithm is to Block MDP assumption)

In general I enjoyed the paper, I'd like the theory part. 
It seems like some notational clarity can help the paper, for example what is \Phi in the definition of \epsilon_T? Or what is Z in definition of \phi ? 

review_title: Good Paper

final_score: rating: 7: Good paper, accept
review_content: Summary:
This paper combines representation learning via approximate bisimulation with the HiP-MDP framework for representing multiple tasks. The result is multi-task and meta-RL algorithms that operate from images and in the meta-RL case adapt to changes in the dynamics of the environment.

Pros:
Combines HiP-MDP and block MDP formalisms
Evaluates resulting method on a set of multi-task and meta-RL problems operating from image observations
Cons:
Not clear (to me) if any insight is gained from the theoretical analysis (the derivation of value and sample complexity bounds for approximate bisimulation was performed in Gelada et al. 2019)
Empirical gains are modest and it’s not clear if they are due to the image representation learning component of the loss or other aspects of the method.

Detailed Comments:
I think this paper would be relevant to cite: Learning an Embedding Space for Transferable Robot Skills (Hausman et al. 2018).

One thing that stood out to me was the very small number of training tasks used - only 4! I wonder if using more training tasks improves the generalization of single-task methods like DeepMDP that might be able to simply generalize over the dynamics changes given more examples. How much overfitting to the training tasks do you observe for these baseline methods versus HiP-BMDP?

It seems like there might be a baseline missing - generic multi-task algorithm that conditions on the environment ID but does use the bisimulation loss to help process the image observations. From my understanding, all baselines have no image representation learning component except DeepMDP which is not a multi-task or meta-RL algorithm.  I am a bit concerned that the gains we are seeing here have more to do with image representation learning than the structural assumptions employed by the algorithm. 

I think that for the meta-RL setting, “environment ID” is replaced everywhere by experience seen so far in the task - is that correct? It would be good to make that clear, or if environment IDs are being used in meta-RL, how they are being used.

I’m a bit confused why there’s a gap between your method in the multi-task experiments but not in the meta-RL ones. Do the meta-RL experiments use image observations? If so, how is the PEARL baseline adapted to handle images? If not, why not?

Why does HiP-BMDP handle the sticky observation setting better than the baselines? Isn’t it impossible for it to persist state information over time steps?

Recommendation:
Borderline
I think the strong point of this paper would be the theoretical contribution of connecting bisimulation to HiP-MDPs. As I’m not very familiar with bisimulation theory, I cannot comment with confidence on the value of this contribution. It is not clear to me what new insights are gained from this extension.
Empirically, I am not convinced that the structural assumptions on the MDP used by the proposed algorithm yield performance improvement. For example, one assumption is that the reward function won’t change across tasks, but the method doesn’t really outperform a baseline that doesn’t make that assumption. I am concerned that the gains that are observed come from image representation learning via approximate bisimulation, and that this combined with any multi-task or meta-RL algorithm might achieve the same results.

---**Update**---
Increased score 5 -> 7 thanks to clarifications from authors.

review_title: Nicely connects two formalisms, but insight isn't clear and empirical results not convincing

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies a family of Markov Decision Process (MDP) models with a low-dimensional unobserved state, called the block MDP. The authors assume that system dynamics of the underlying MDP is sufficiently summarized by a parameter $\theta$. This learning setting could be seen as a combination of Block MDP and the Hidden Parameter MDP; hence the name HiP-BMDP.

The authors then propose algorithms to learn parameters $\theta$ of HiP-BMDP from observed trajectories of the system. The authors derive the error bounds over between the Q-value parametrized by the learned $\theta$ and that of the actual parameter $\theta^*$. The authors then apply these results to the transfer learning settings where one applies the learned parameter $\theta$ to a different but somewhat similar environment parametrized by $\theta_i$. The error bound over Q-values in such a transfer learning settings is also provided. These results, including Theorems 2 and 3, seem sensible, while I haven't checked the details of the proof. Finally, the authors validate the proposed method through extensive simulations.

Overall, I believe this paper is well written and well organized. The assumptions of HiP-BMDP seem sensible and the derived error bounds look promising. These results are applicable in multi-taks learning settings. They explicate a set of parametric conditions under which one could accelerate the learning process of a future task from prior knowledge derived from previous tasks.
review_title: Hidden Parameter Block MDPs

final_score: rating: 7: Good paper, accept
review_content: ### Summary

The authors combine hidden-parameter MDPs and state abstractions to model multi-task problems with dynamics parameterized by some latent variables and where the agent receives high-dimensional observations whose corresponding low-dimensional states, on which dynamics are defined, are unobserved (as in block MDPs). They provide both a theoretical analysis and an empirical evaluation of the proposed method, showing that it performs better than competitive baselines on complex continuous control domains.

### Pros

- The idea of combining HiP-MDPs with state abstractions seems interesting and relevant. One of the limitations of HiP-MDPs is indeed that they do not easily handle high-dimensional observations and the proposed approach overcomes this limitation. 
- The method seems also quite general, in the sense that it can be applied in multi-task/meta-RL settings and combined with existing algorithms.
- Experiments are conducted on complex tasks and show convincing results.

### Cons

- I found the paper quite hard to read in its core parts (e.g., Sec. 3). This is in part due to a complex/confused notation, which overall made it hard for me to go through the theoretical part (and proofs). See detailed comments below.
- The theoretical results focus on assessing the value-function errors for fixed abstractions/dynamics-structure rather than on the errors in learning the abstractions/structure themselves (and learning these components seems to be one of the primary concerns here).
- The requirement that task IDs are known could be a potential limitation for applying this method

### Detailed comments

1. Are the environment labels/ids used only for communicating to the learner that the task changed or could they provide more information? For instance, if we face the same task twice in two non-consecutive episodes, are the corresponding labels equal?

2. What makes these state abstractions "robust" (as in the title)? Is there any particular theoretical or empirical evidence that justifies this term?

3. Existing analyses of multi-task settings, including the one of Brunskill and Li [1] and others [2,3,4], provide guarantees for task-structure (e.g., dynamics models) learned from data, while here the focus seems to be on guarantees for arbitrary abstractions/structures as a function of their errors, without considering how they are learned. This makes it difficult to interpret the results in the context of the proposed approach

4. Regarding the statement: "sample complexity bounds that depend on the aggregate number of samples across tasks, rather than the number of tasks, a significant improvement over prior work", the bounds derived in [4] depend only on a number of abstract "transition templates" that they define, while those derived in [3] depend on the minimum between the number of tasks and the number of states.

5. To be clear, the notation \| x - y \|_1 is used for the Wasserstein distance and not l1-norm, right? In such a case, the sentence "We omit d but use d(x, y) = \|x − y\|_1 in our setting" is quite confusing.

6. The definitions of the terms \epsilon_R, \epsilon_T, \epsilon_\theta could be moved to the theoretical analysis since they are introduced early and never used before Sec 3.3

7. Sec. 3.2: the definition of \phi maps S to Z. Isn't it X to Z?

8. In Sec. 3.2, the 2-Wasserstein distance is used, while the 1-Wasserstein distance was introduced earlier. Which one is used?

9. In Eq. 3, it was not clear to me why the "model learning error" term uses the MSE for two different environment labels (isn't one enough)?

10. What is exactly the "evaluation of the optimal Q function of \bar{M} on M" in Theorem 2? Do you mean that we take the optimal policy of \bar{M} and test it on M?

11. [if the above comment is correct] Theorem 2 was slightly weird to me: it takes the optimal policy of \bar{M}, evaluates it on M_{\theta_i}, and check how much the corresponding Q function differs from the optimal Q function of M_{\theta_j}. If we wanted to figure out the transfer error of the optimal policy of \bar{M} on M_{\theta_j}, shouldn't we compare the optimal Q function of M_{\theta_j} with the Q function of the policy on the same MDP (rather than on M_{\theta_i})?

12. How exactly is the "empirical measurement of Q^*_{\bar{M}} over D" computed?

13. In Th. 4, the last term bounds the concentration of expectations of Q functions (which are bounded by rmax/(1-\gamma). Shouldn't there be a multiplicative rmax in front of the sqrt?

14. Page 6: "We compare the our method" -> "We compare our method"

15. In the multi-task experiments, it was not clear what method was used in combination with HiP-BMDPs to learn policies (though it is in appendix).

16. How many adaptation steps for "few-shot generalization" were used in Figure 5?

17. Below Figure 5: "and use a behavior policy to collect transitions." What is the behavior policy exactly and how was it chosen?

Some minor comments/questions:

- Page 1: "This additional structure gives us better sample efficiency, both theoretically and empirically." Better than what algorithm?
- Page 2: "don't" -> "do not"
- Page 2: "which naturally leads to a gradient-based representation learning algorithm." Why is it natural to use a gradient-based algorithm in this setting?
- Background: you could mention that the finite-MDP assumption is only for deriving the theoretical results, while the method can be applied in continuous domains (right?)
- Page 2: "a unobservable "-> "an unobservable"
- Page 3: "where l2 distance corresponds to d" Why? d isn't the l2 distance, right?
- Sec. 3.1: \phi in \epsilon was never defined.

### Overall comment

Overall I believe that the paper is interesting and the results significant. However, at the present time, I have too many doubts to vote for acceptance. I will be happy to increase my score after the authors have clarified them.

### Update

I have increased my score to 7 after reading the authors' response and the updated paper.

### References

[1] Brunskill, Emma, and Lihong Li. "Sample complexity of multi-task reinforcement learning." UAI (2013).
[2] Liu, Yao, Zhaohan Guo, and Emma Brunskill. "Pac continuous state online multitask reinforcement learning with identification." AAMAS (2016).
[3] Tirinzoni, Andrea, Riccardo Poiani, and Marcello Restelli. "Sequential transfer in reinforcement learning with a generative model." ICML (2020).
[4] Sun, Yanchao, Xiangyu Yin, and Furong Huang. "TempLe: Learning Template of Transitions for Sample Efficient Multi-task RL." arXiv (2020).
review_title: Interesting paper which requires some improvements/clarifications

Meta-review: The paper addresses the problem of learning and exploiting common (latent) task structure in multi-task reinforcement learning settings. The authors introduce a new formalism for capturing this type of structure and derive a gradient-based learning algorithm. They provide novel theoretical insights and strong empirical results.

Reviewers initially raised several concerns, regarding assumptions and especially accessibility of the paper (and in particular theoretical discussions). The majority of these concerns have been addressed in the detailed rebuttal. The resulting consensus is to accept the paper. Authors are encouraged to continue to improve accessibility of the paper for the camera ready submission.
Decision: Accept (Poster)