Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new notion of state representation, the first-occupancy representation (FR), inspired by the Successor Representation. It is motivated by situations where the rewards are non-Markovian. Similarly to the SR, the FR can be learnt by TD learning. The usefulness of the FR is demonstrated on exploration, unsupervised RL, planning and escape behaviour tasks. 

main_review: This paper is well-written and well-motivated. The idea is simple but is a nice extension of the concept of the SR. It also seems promising on the different tasks considered by the authors. In particular, the case of non markovian rewards is studied in section 4.2.

How does the FR relate to the dynamic distance function introduced in https://arxiv.org/pdf/1907.08225.pdf ?

In Section 4.2, could you provide a reference for  “a bonus to maintain its effectiveness as time progresses in order to prevent the rate of policy improvement from exponentially decaying“? Unlike the analogy of SR / pseudo-count, it s still a bit unclear what the motivation for the FR is. Testing the benefit of the FR on harder exploration tasks would make the paper stronger I think (e.g., Machado et al 2020 tested their approach on Atari games)

Regarding infinite state spaces, the authors might want to note that recent works has shown that the SR can be extended the continuous state spaces when viewed as a measure without the need to rely on basis functions. See https://arxiv.org/abs/2101.07123 https://arxiv.org/abs/2103.07945

Minor points: Typos: take advantage *of*, theoeretical 
summary_of_the_review: I think this paper provides a nice contribution to the topic of representation learning in RL. The authors provided theoretical results for their FR and demonstrated its benefits on 4 different tasks. Although it would be nice to confirm these findings on harder tasks e.g., in the case of section 4.1, I believe the variety of tasks considered by the authors still shows some promise which is why I recommend an accept for this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents the first-occupancy representation, a sort of non-Markovian analogue of the successor representation that carries information about the time required to reach a state for the first time rather than the full discounted occupancy of a policy.
main_review: This paper proposes a general-purpose modification of the successor representation that has a number of nice properties: in particular, it can be used for shortest path search and can be stitched together to form a multi-step plan in the spirit of options. The paper also shows demonstrations of its usefulness in unsupervised RL and exploration. The evidence for each individual application is somewhat preliminary, which I think is fine for a paper that intends primarily to introduce a new prediction problem and outline potential applications. The most compelling idea to me is the planning (FRP) procedure, which naturally fits into other DP-style methods and multi-step planning frameworks.

The main issue I can find is that the proposed first-occupancy representation might not be as new as the paper describes. As early as [Kaelbling 1993](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3077) there was the so-called "dynamic goal learning" (DG) algorithm, which uses TD to predict the minimum number of timesteps required to reach a goal. The FR is in the space of discounts and DG in the space of timesteps, but at least for deterministic policies and dynamics it seems like there would be a straightforward conversion between the two ($FR = \gamma^{DG}$?).

For a more modern take on the same problem, [dynamical distance learning (DDL)](https://arxiv.org/abs/1907.08225) also estimates the expected number of timesteps required to reach a goal state, and [temporal difference models (TDMs)](https://arxiv.org/abs/1802.09081) estimate how close a policy will come to a goal state in a fixed number of timesteps. 

It is not necessarily an issue that there are papers from the last few years investigating a similar line of inquiry; the paper is still a thorough description of this idea and has enough in it that it is not subsumed by these prior works. But since the space has already been scoped out a bit, the framing of this paper as a first introduction of the idea might not be the right one, and raises the bar slightly in terms of experimental evaluation. It would be valuable to compare it to the related approaches that have already been scaled to higher dimensions (like DDL and TDMs).

**Minor**
1. "to take advantage this shared" --> "advantage of"
2. In Equation 8, should the condition read $s_t = s$?

summary_of_the_review: The paper gives a thorough description of a variant of the successor representation and its potential application in a few different settings. Its main issue is that it frames itself as a sort of preliminary description of an idea, with a somewhat limited evaluation in any one setting, but very similar ideas have already been shown to scale to the types of problems commonly studied in contemporary deep RL. Including a comparison to these ideas (both experimentally and also in the framing) would improve the paper and situate it better in context.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a novel representation of the dynamics of an environment that is independent of the reward structure encoding a particular sequential decision task in it, and thus can be reused to speed up the computation of policies for multiple tasks in this environment. Unlike successor representations, which compute the likelihood of occupying a particular state at any time in the future, when starting from a given initial state, the proposed first-occupancy representation encodes the likelihood of reaching a particular state for the first time. Because of this, the novel representation effectively represents the expected path length between all pairs of states when following a particular policy. The benefits of the proposed representation are illustrated in several decision problems with non-Markovian reward structure. It is also argued that animals might use similar representations of their environment to effectively find escape routes in a short amount of time.
main_review: The proposed representation (FR) seems to have clear advantages in comparison to approaches that convert MDPs with non-Markovian reward structure to such with Markovian one. The use of the first-occupancy values as an exploration bonus results in much more efficient exploration. The authors also demonstrate that FR can be used effectively for unsupervised pre-training RL with non-Markovian rewards, where the successor representations tends to produce incorrect estimates of the value function. The use of FR for planning is also demonstrated on a high-dimensional continuous control problem involving a robotic arm. All of these illustrate well the advantages of the proposed representation, and overall, I find this representation highly original.

One limitation of this general approach is probably the assumption that a fixed, and relatively small number of policies will be provided in advance, and the solution of the sequential decision problem can be expressed by switching between these policies. It is not clear if and under what conditions this assumption is justified. Could the (sub-)optimality of this approach be analyzed theoretically or empirically, by computing the true optimal policy and comparing with its performance? Section 3 talks about "Policy evaluation and improvement with the FR", and although the use of FR for fast policy evaluation is explained very well, I do not see any discussion about policy improvement there.

A minor typo, on page 4, last paragraph: "automoton" -> "automaton".
 
 
summary_of_the_review: I find the proposed novel representation highly original, and ICLR is the right venue for its publication. It is a clear advance of the state of the art in computing intermediate representations that cache the system dynamics in a format that is more suitable for policy evaluation than the basic transfer function of the MDP. Its advantages over successor representations for the case of non-Markovian rewards are clearly explained and supported by empirical evaluations. For these reasons, I recommend acceptance. It is also apparent that the proposed approach has some limitations, and the authors readily acknowledge this.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an alternative to the successor representation (SR) -- the first-occupancy representation (FR) -- which represents the expected time to first visitation of a state. The paper motivates the representation to be applicable in environments with non-Markovian rewards and show that the proposed FR can handle such cases. The authors present a well-executed comparison to SR and demonstrate improved exploration in MF settings and the ability to plan in a model-based setting. The authors also provide some theoretical analysis of the representation, most notably a convergence result on the Bellman operator for the FR, and planning optimality in a model-based setting.
main_review: ## Short Version
Overall, I think this is a very nice paper that presents a neat little idea with a lot of potential impact in the community. Successor features have resurfaced in the RL community in the past few years, and the proposed "FF" features improve upon them in a very specific, but evident way. My biggest concern is the somewhat limited empirical evaluations and broader comparisons that bring out the strengths of the method.  
[Full Disclosure: I have not checked the accuracy of the theoretical claims thoroughly; they seem appropriate on a quick glance.]

---
## Strengths
1. The writing is very succinct and the authors make a great case of comparing against the SR in every way possible (and do so fairly).
2. The paper is well-written in terms of reproducibility and the authors make plenty of information available about the experiments and algorithm to reproduce the results. The theoretical results are also discussed elaborately in the appendix.
3. The suite of capabilities considered, and demonstrated, is very complete and makes a good case for "FR > SR" -- exploration bonus, unsupervised pretraining and planning. Particularly, the section on planning with FR makes a good case for their strengths and could be made more prominent in the contributions/introduction, in my opinion. The paper makes a great case for the _completeness_ of a first-occupancy representation.
4. The parallels to animal behavior, although a bit far-fetched to me, are very nice inclusions in the article. I appreciate the candor of the authors in presenting the facts ("We do not claim that this is the exact process by which mice are able to efficiently learn escape behavior. Rather, we demonstrate that the FR facilitates behavior that is consistent with our under- standing of animal learning") and not overfitting their findings to tall claims about understanding the animal brain. The findings are interesting in their own right and add value to the paper.


---
## Weaknesses
1. While the paper does a great job at comparing against the vanilla successor representation and shows (quite clearly) that FR > SR in tabular domains, my biggest concern is that the results don't go too far beyond that. In most realistic domains, the infinite state-space version (FF) would be more relevant and there is almost no empirical analysis of how the method performs in more complex domains/tasks, beyond Section 4.2. The authors also do not compare against a broader suite of methods in the recent years that use successor features to do more interesting control and planning problems; a more thorough empirical evaluation will greatly increase the impact of the work and serve as a strong baseline for future works to present results against. As a suggestion, I would recommend [a recent paper by Janner et al.](https://arxiv.org/abs/2010.14496) which conducts thorough empirical evaluation of a model similar to the SR, and can provide some pointers towards more tasks to consider for empirical analysis.
2. While motivating the need for a _better_ representation, the authors frequently make claims about how the problem of non-Markovian rewards is widespread and _natural_, e.g. "Such natural problems emphasize the importance of FR...". However, the text fails to provide a concrete example for the reader to conceptualize the claims and contributions of the paper. As a suggestion on the presentation, I would urge the authors to present a concrete example that motivates the need for the first-occupancy early on, or a toy problem that can isolate the issue, for clarity.
summary_of_the_review: The paper presents a simple idea which is supported by ample theoretical analysis and (some) experiments. Comparison to prior work, while not exhaustive, is convincing. I vote to accept the paper but strongly urge the authors to improve the empirical analysis for the overall impact of the paper.
review_title: null

Meta-review: This paper introduces a first-occupancy representation for reinforcement learning problems, with potential benefits on problems with non-stationary rewards.  The representation is defined analogously to the successor representations, but captures the expected discounted time to first arrive at a state instead of measuring discounted visitations.  The paper develops the idea and illustrates some uses for exploration, unsupervised RL, and non-stationary reward functions (for example when food rewards are consumed).

The reviews brought forward a number of related older ideas in the literature, where several aspects of the method have been previously developed.  These include dynamic goal learning, option conditional predictions, general value functions, dynamical distance learning, and temporal difference models.  However, from the author response and ensuing discussion, the exact form of the proposed representation has not been studied for the purposes presented in this paper.  The reviewers appreciated the utility of this representation for problems with non-Markovian rewards, in particular that “the use of the first-occupancy values as an exploration bonus results in much more efficient exploration”.  Multiple reviewers commented on the desire for a stronger empirical evaluation, but they were satisfied with the contribution of the paper.

The reviewers arrived at a consensus that the paper contributes a new representation for RL problems with non-stationary rewards, with two reviewers strongly convinced and none opposed.  The paper is therefore accepted.
Decision: Accept (Poster)