Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces Adversarial Surprise, a new approach for unsupervised reinforcement learning in stochastic BMDPs, where the goal is to explore an environment without rewards. The algorithm uses a single agent with two policies, an Explorer and a Controller, which switch during an episode with opposite rewards: to maximize and minimize "surprise". The method is supported by a theoretical argument under the assumptions of the stochastic BMDP. When these are present in an environment, the empirical results are strong. The method is also tested in Atari and Doom. 
main_review: Overall this is a neat idea, related to but distinct from previous works. The problem setting of a stochastic block MDP (BMDP) is well motivated although not frequently encountered in RL. The strongest results come from a new custom environment in MiniGrid, which clearly motivates the switching mechanism to discover interesting behaviors and fully explore the environment. In other environments the results are less compelling: in Doom the AGAC baseline is not included, while the Atari experiments are hard to interpret due to the choice of the four games, which is not clear. While I like the paper, I am voting for weak reject primarily because of the reporting protocol, only showing the top 3 seeds. This is known to be bad practice and does not seem justified, at least without presenting full results in the Appendix. As with any review it is possible I missed something, in which case I can change my score to reflect this during the discussion.

More Detailed Comments:

1. One of the greatest strengths of this work is that is it well motivated, and thorough. The related work section for instance positions the paper effectively within the literature, which is surprisingly rare. The flip side of this, is that the specific setting considered, stochastic BMDPs, seems very specific. It would be great to have more examples of real world settings where this setting would be present.
2. The MiniGrid experiment is a nice example of a setting where existing methods fail in stochastic environments, with a switch that allows AS to remove the stochasticity. Is it the case that the Explore agent can turn the stochasticity back on? How often does it do this?
3. Why are the methods in Fig. 2b) and 2c) different? E.g. AGAC is in one but not the other. More of an aesthetic issue but it is confusing switching the colors for methods in plots that are side by side.
4. The authors say "ViZDoom environment (Kempka et al., 2016b), which was used by AGAC and SMiRL", *but then do not include AGAC in the Doom experiments.* Why?
5. How were the four Atari games chosen? As far as I am aware, the common games used for exploration are Montezuma's Revenge and Pitfall, but these were not included. This makes the reader question the choice, for example if the method works best for these but would do equally poorly on a different set of games. While it isn't the perfect environment by any means, Montezuma's Revenge is a good benchmark because it has been predefined, so if a method does/doesn't work there it can serve as a litmus test.
6. How does AS combine with rewards? All of the other methods (aside from ASP) are designed for settings where an extrinsic reward is available, and they use this to get their best results. I know "unsupervised" or "self-supervised" RL is currently a popular topic, but in many cases we may have a reward function. Indeed - the baselines compared against were not designed to work in the regime they were tested in.
7. How do you choose k? I may have missed it but couldn't find it anywhere. The paper does mention that the ability to tune this per environment is a strength, but as a reviewer it is a concern that this may have led to the performance gains and actually the method could be very sensitive to this hyperparameter. I am thinking if k is less than the size of the room with the switch, Alice and Bob could take turns to turn it on/off and then stay in the same room forever.
8. The authors should cite RIDE, AMIGo and BeBold, three recent works studying exploration in procedurally generated environments. Comparison against them would be a nice to have but not expected, since AGAC is included and it compares against them.  

Minor Comments/Typos:

* p6, reference Equation 5 but I think you mean Equation 4.
* p6, after the AS formula (min max) it says BMPD rather than BMDP. Later in that sentence, "induce"→ "induces".
* Fig 2.c) has the methods twice on the legend.
* P7 Minigrid should have a capital G.
summary_of_the_review: The method is elegant and well motivated, hence a desire to see it accepted despite question marks about the experimental results. In particular, the broader applicability may be limited given the gains are clearest in the setting specifically designed to satisfy the properties which motivated the method. To increase my score I would need clarification around the evaluation protocol, which is already known to be challenging in RL without selecting the top 3 seeds (while saying 5 seeds elsewhere). I would also be happy to increase my score if there are additional baselines (e.g. AGAC for Doom) or benchmark environments (e.g. additional Atari games/MiniGrid environments), clarification around hyperparameter choices or an effective demonstration of combining AS with an extrinsic reward. Overall I could increase multiple times if this is improved.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes Adversarial Surprise (AS), a method for unsupervised training of RL agents based on the competition of two policies dubbed Explore and Control. These two policies control compete to maximize/minimize surprise, respectively, by taking turns to control a shared body. Authors show that under some conditions this objective leads to maximizing state entropy within an episode, and formalize the settings where other approaches may fail. Evaluation is performed on three different domains: procedurally generated MiniGrid tasks, VizDoom and four Atari games. AS explores more rooms within an episode in Minigrid, visits more x positions within an episode in VizDoom, and obtains higher zero-shot scores in 3/4 Atari games.
main_review: **Positives**

+ The paper is well written and generally easy to follow and understand, and the related work properly puts the proposed method in context.
+ Section 4.1 provides an interesting formalization of insights that had been experimentally observed in previous works (e.g. noisy TVs, dark rooms) that had not been mathematically described before as far as I know.
+ The method combines the advantages of surprise maximizing and surprise minimizing strategies in a conceptually simple manner which should be easy to replicate.
+ Multiple baselines are reported for each experiment.


**Concerns**

- The paper uses three metrics to evaluate unsupervised RL methods: coverage (number of rooms in MiniGrid, binned x positions in VizDoom), amount of task reward collected (VizDoom, Atari) and qualitative evaluations based on a few videos available in the project site (at the time of reviewing, videos for MiniGrid and the four Atari games were available). In my opinion, while these metrics can provide some insight on the type of behaviors AS may discover, more thorough quantitative evaluation is required in order to properly assess the usefulness of the method. For instance, a common practice in related works consists in evaluating how the output of the unsupervised pre-training stage helps when solving downstream tasks (i.e. reward functions) in the same environment.
- Some of the considered baselines were proposed or used to improve exploration in the presence of extrinsic reward (RND, AGAC, SMiRL, ASP). The outputs of other unsupervised methods such as DIAYN, VISR or APT can be used for transfer via Hierarchical RL, Generalized Policy Improvement or fine-tuning. After reading the paper, I'm unclear about how one would use AS to either aid with exploration in the presence of extrinsic reward or how the resulting policies could be used for transfer to downstream tasks. Given that the method produces two sets of neural network weights (one per policy), and the fact that the two policies probably need to be interleaved in order to produce meaningful behavior, it is not obvious how to best leverage them which in my opinion reduces the significance of the results.
- I have some concerns (and doubts) about the evaluation of unsupervised agents. Appendix C.4 states that plots report the top-3 seeds (out of 6), whereas Figure 4's caption states that 5 random seeds without any kind of filtering are reported. Which method was used in practice? I am particularly concerned about the former, as it would leak information about the task reward via seed selection.
- The choice of Atari environments is never explained, and I wonder why authors decided to run experiments on this particular subset of games. I believe that it would be much more informative if these methods had been evaluated on some of the 6 hard exploration games identified by Bellemare et al. (NeurIPS, 2016) (cited in the paper): Freeway, Gravitar, Montezuma's Revenge, Pitfall, Private Eye, Solaris and Venture.
- The experimental setting seems to vary across environments and even plots. For instance, Figure 4 shows a different number of train steps across Atari games (ranging from 180k to >400k). Authors report over 120k train steps when showcasing the advantages of AS in terms of zero-shot performance in VizDoom (Figure 5), whereas Figure 3 shows results after only 1k train steps when reporting coverage in this same environment. I would advise authors to unify the evaluation protocol for each domain (i.e. same protocol for all Atari games, same protocol for all VizDoom experiments, etc). Moreover, the term 'train step' is not always clear in RL and I was not able to find its definition in the manuscript.


**Other comments**

I have other suggestions for the authors that did not play an important role in my decision but I believe would improve the overall quality of the paper:

- Many environments feature *irreversible decisions*, i.e. actions that make the agent transition from state $s$ to $s'$ but make it impossible to go back to state $s$. I know that it is difficult to derive theoretical results for these complex environments, but I suggest being more explicit about the limitations of the theory (especially since it seems that even some of the MiniGrid environments have this property, e.g. the ones where the agent can lock a door).
- The paper mentions that $k^E$ and $k^C$ are independent hyperparameters that can be set to different values. Is AS sensitive to this choice? It would be interesting to include an analysis of the role played by these values in the discovered behaviors.
- The structure of Section 5 (questions, description about the experimental setup, answers) makes it somewhat hard to read. I would suggest something like *experimental setup, Q1 (question + answer), Q2 (question + answer), Q3 (question + answer)* instead.
- In Figure 3's caption, I would suggest using $\log p(x)$ instead of $\log p(s)$, as the true state is unknown and will probably include more information than just the agent's x position.
- In page 9, authors mention that the performance of RND decreases over time. Please see Campos et al. in the provided references for an example where using reward normalization enables very long unsupervised pre-training with RND without performance collapse.
- The text in some figures is too small (2b, 2c, 4, 5) or cropped (4a, 4b). 
- The legend in Figure 2c has repeated elements. Figures 2b and 2c do not include the same baselines (e.g. SMiRL is missing in 2c). Please adjust their x limits to be the same, and adjust the y limit to avoid leaving empty half of the figure.

**Additional references**

Empowerment

> Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint arXiv:1611.07507, 2016.

Unsupervised training based on empowerment + fast adaptation via GPI
> Steven Hansen, Will Dabney, Andre Barreto, Tom Van de Wiele, David Warde-Farley, and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. In ICLR, 2020.

Intrinsic motivation based on episodic curiosity
> Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andew Bolt, et al. Never give up: Learning directed exploration strategies. In ICLR, 2020.
>
> Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In ICML, 2020.

Unsupervised pre-training with NGU/RND + transfer to downstream tasks
> Víctor Campos, Pablo Sprechmann, Steven Stenberg Hansen, Andre Barreto, Steven Kapturowski, Alex Vitvitskyi, Adria Puigdomenech Badia, and Charles Blundell. Beyond fine-tuning: Transferring behavior in reinforcement learning. In ICML 2021 Workshop on Unsupervised Reinforcement Learning. 2021.
summary_of_the_review: The paper presents an interesting method, but the evaluation protocol needs to be improved in order to properly assess the advantages of the proposed approach.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a method, called Adversarial Surprise (AS), for unsupervised reinforcement learning. AS employs a two-player, adversarial, sequential procedure in which an Explore player tries to maximize the approximate entropy of the observations, whereas a Control player tries to minimize this same entropy. The method is then compared against other unsupervised RL baselines in visual domains, over both state coverage and zero-shot adaptation.
main_review: AFTER REBUTTAL

After having read the authors response, as well as other reviews and discussions, I am keeping my original, slightly negative, score.

Anyway, I would like to encourage the authors on improving the submitted draft, especially
- considering a critical evaluation of the state density estimation performance, and comparing their results with non-parametric entropy estimation,
- clarifying how subsequent RL tasks can benefit from the pre-trained models (other than zero-shot transfer).
I believe that with these improvements this work will be a nice contribution to the unsupervised RL community.

-------

While the proposed methodology is certainly interesting, my main concerns about the current version of this work regard (i) the applicability of observation density estimation and (ii) the robustness and completeness of the experimental evaluation. I report below some detailed comments on this matter.

DENSITY ESTIMATION

1) From my understanding, the method heavily relies on direct estimation of the observation marginal density to compute the objective function. However, direct density estimation is known to scale badly to the dimensionality of the space (e.g., Beirlant et al., Nonparametric entropy estimation: An overview, 1997). Moreover, density estimation does not seem to be required by the method, which just need an estimate of the observation entropy. The recent works (Mutti et al., 2021; Seo et al., 2021; Liu and Abbeel, 2021) showed that non-parametric entropy estimation can be much better in this setting. On the one hand, I would like to understand if density estimation is really working in the reported experiments (such as comparing with an estimate obtained from a huge number of samples). On the other hand, I am wondering if these results could be improved with non-parametric entropy estimation.

EMPIRICAL EVALUATION

2) In Appendix C.4, the paper reports that all the experiments are obtained with six independent runs. This number is not ideal, but reasonable in the reported settings. However, I do not understand why the plots are just showing the average (and confidence intervals) computed over the top-three seeds. The Appendix motivate this as a comparison of the best-case performance, but worst-case performance arguably matters as well. Moreover, can the authors clarify the strategy behind the hyper-parameters selection, and if they experienced any particular sensitivity to the tried values?

3) The experiments do not include a comparison with maximum state entropy methods, especially APT (Liu and Abbeel, 2021) and RE3 (Seo et al., 2021) that have been experimented in analogous domains. Moreover, an observation coverage metric is only reported for the MiniGrid experiment.

4) The experiments do not include any continuous control domain, which might represent a worst-case setting for AS. Previous works have been extensively analyzed in these kind of domains, such as Mujoco tasks in (Laskin et al., URLB: Unsupervised reinforcement learning benchmark, 2021). Note that the latter is very recent and at most concurrent with this work, but it might provide a useful inspiration.

5) I am not completely convinced about the fairness of the zero-shot transfer comparison. On the one hand, the reported results are somewhat confusing: If the setting is zero-shot, why the plots report training steps? They refer to the training steps of the unsupervised exploration phase? On the other hand, I do not clearly understand why AS should actually work in zero-shot transfer, and the reported baselines are not designed for this setting (especially RND). I think that including a comparison over a (more common) fine-tuning to downstream tasks setting would strengthen the analysis.

6) If my previous hypothesis over the interpretation of the zero-shot setting is correct, I am wondering if this couldn't be seen as a partially negative result on the stability of the method. Indeed, the performance of AS is not monotonically improving, which casts some doubts on whether the method is really converging to something that is useful to downstream tasks, or it is only effective in covering the observation space over the process.

GAME-THEORETIC ANALYSIS

7) This is a lesser concern, but I think that the paper somewhat misses the opportunity to analyze the method from a game-theoretic perspective. The min-max game optimization problem is well-posed and actually feasible? What is the solution concept one should aim to achieve in this formulation?

MINOR
- It is sometimes quite hard to inspect the plots, even when zooming on the pdf;
- Figure 2: changing colors between the two plots does not help tracking the curves, while there is some mess in the legend of Fig. 2c, and it is not clear which one refer to the SMiRL curve;
- It is of course hard to fit everything into a 9-pages paper, but I would suggest the authors to try to squeeze the figures on the "emergence of complexity" into the main text.
summary_of_the_review: This paper introduces some interesting ideas. Especially, it provides a practical and smoother reinterpretation of asynchronous self-play (Sukhbaatar et al., 2017), a method holding compelling premises but with some clear limitations. Moreover, it tries to unify under a unique approach the pros of novelty-seeking exploration and surprise minimization, while mitigating some of their cons (such as noisy-tv and dark-room problems respectively). Overall, the proposed methodology seems valuable, and I believe it can help improving the state of the art in some specific settings (e.g., partially observable visual domains). Those might be sufficient reason for accepting the paper.

However, I think that the paper has some important limitations as it is, which might significantly reduce its potential impact. Thus, I am currently providing a slightly negative evaluation. I detailed in the main review above some of the concerns that the authors might address in their response.
review_title: null

Meta-review: The idea of having two policies with opposing strategies, one aiming to maximize a notion of surprise whereas the other tries to minimize it, is an interesting one. However, even after the author rebuttal, all reviewers have lingering concerns about the evaluation protocol. In addition, there are remaining questions about the bonuses used; there are concerns that these only work for very specific domains. For these reasons, I'm recommending rejection. I encourage the authors to carefully read the concerns of the reviewers about evaluation and consider using a different evaluation protocol for a future version of this work.
Decision: Reject