Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the power of representation learning via auxiliary tasks in deep reinforcement learning. To be concrete, it focuses on find a good representation of the states that is capable of predicting the optimal value functions if followed by a linear predictor. Correspondingly, it proposes a method called the proto-value networks. The proto-value networks take advantage of the success measure over subsets of states to learn a good representation. Empirical studies show that these learned features combined with linear functions capture the optimal value functions in many Atari games. The evaluation rewards are comparable to that of the original version of DQN.
strength_and_weaknesses: The paper has multi-level contributions: 

1. The problem studied is interesting and important in the field of deep RL. Most of the works in RL are based on the representation learning, so it is vital to understand the properties of these representations. 
2. To design such a representation, this work proposes to use the success measure as the learning objective of state representations. Further, they find that it is more effective to learn the success measure over subsets of states, instead of using the original success measure defined on a single state. Finally, they study how to choose such subsets of states as auxiliary tasks. They propose universal hashing functions and random network indicators to effectively help design the state representations.
3. With the learned representations, they conduct systematic experiments on all the Atari games to verify the effectiveness of the representations. The results show that linear functions with regards to the representations are sufficient to learn optimal policies on many tasks, with comparable performance to the DQN algorithm. The experimental results also verify the scaling properties of the number of auxiliary tasks, and the importance of the indicator functions.

On the other hand, I also have several questions regarding to the paper:

1. Could you provide some intuitions on why choosing the uniform random policy as the target policy in the pre-training stage? The performance degradation of the greedy policy (using the max operator instead of averaging) perhaps comes from the correlation of the target policy and current feature estimator. However, is there a more efficient target policy that incorporates the prior knowledge of the tasks?
2. It seems that the learned features of the states at the end of the pre-training stage is the output of the last but one layer of the PVN, since the last layer is a linear prediction layer. How large is the dimension of such features? Is it possible to improve the performance with larger feature dimensions?
3. The empirical results do not provide the comparison with the widely used policy gradient methods such as PPO. Is it possible for PVN to achieve comparable performance to these policy gradient algorithms?

clarity,_quality,_novelty_and_reproducibility: The paper is written in a very clear and organized way. The reproducibility should be good since the descriptions of the algorithms and hyper parameters are clear clear and complete.
summary_of_the_review: Overall, I think this is a good paper, which is suitable for the conference.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces an extension of learning successor feature that ensures that the learned feature could obey the bellman consistency on a set of the states. To empirically define which sets of states that the feature should operates on, the paper introduces two empirical surrogates: using random hash functions or random neural networks. Finally the experiments visualize that the learn feature may indeed show some meaningful semantics over the states.
strength_and_weaknesses: # Strength
- The paper proposes an easy extension of successor features, and the two proposes state aggregation methods seem to provide meaningful results in practice. Also the state aggregation methods are interesting.
- The paper is well-organized and easy to follow.

# Weakness
- One would naturally wonder why when we want to learn the value function $Q$, we should only learn a feature mapping $\phi$ that only operates on states only (specifically, section 3). One example one could think of is where we have finitely many actions, then $\phi(s)$ could be the $Q$ function for each action and $w_a$ is a one-hot encoder. But intuitively this formulation seems have its limitation on the generalizability against, for example, learning the state-action representation.

- The paper does a good job showing that the learned representation are interpretable to human, but there seems to lack of a section that shows that learning representation this way is indeed useful. The paper should consider adding some baselines and try to at least show the performance is comparable, because the method also enjoys the advantage of having the offline data which may provide good coverage.

- Introducing another function to learn a representation that obeys the bellman consistency on that function is actually not new even in representation in RL. For example, in MOFFLE [1] and BRIEE [2], the representation learning objective is to train a feature map that ensures the bellman consistency on the sequence of the most adversarial discriminator function. The idea of using many random network is the same: it ensures that it could cover the whole discriminator class and learn a feature map that works on all of them.

- The usage of random policy still sounds heuristic to me. If you want to do distribution shift to arbitrary policy, you may still need to pay for exponential on $|\mathcal{A}|$.

- There are several confusions in the paper:
1. Right above section 4.1: " These eigenvectors are of special importance because they encode the spatial structure of the MDP in terms of a diffusion process". I am very confused about what this claim, and it would be great if further explanation could be provided and show why this claim is relevant.

2. Second to last paragraph in page 4: " Second, set inclusion allows us to incorporate a notion of closeness to $\psi$, ..." Here the notion of closeness seems ambiguous, especially in the context of set notations. 

3. On the top of page 5: $\xi$ here is a distribution, then the definition of the diagonal matrix seems weird. Is $\xi$ just a $n$-dimensional simplex?

[1] Modi, Aditya, et al. "Model-free representation learning and exploration in low-rank mdps." arXiv preprint arXiv:2102.07035 (2021).

[2] Zhang, Xuezhou, et al. "Efficient reinforcement learning in block mdps: A model-free representation learning approach." International Conference on Machine Learning. PMLR, 2022.

clarity,_quality,_novelty_and_reproducibility: ## Clarity and Quality
The overall writing is good, but several details could need some polishing.

## Novelty
The contribution is quite limited given that previous representation learning methods in RL already consider similar ideas.

## Reproducibility
The paper provides detailed experiments details, but the reproducibility statement and code are missing in the submission.
summary_of_the_review: Overall this is a well-written paper and the paper provides some good insights, some specific aspect of the paper is interesting, but I am not convinced that the paper actually makes enough contribution and seems to overlook some previous methods. I would recommend a borderline reject. 

### Post-rebuttal
The authors make the paper more ready for publishing after the rebuttal thus I raised my score. See the discussion thread for more details.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the question of representation learning in deep RL by means of learning successor features for auxiliary tasks. It presents an approach to learn successor features with reward agnostic tasks which will learn features that can then be used to learn a linear action-value function for downstream tasks.
The features learned via this approach have connections to a previous approach for representation learning, proto-value functions.

These reward agnostic tasks are based on a set inclusion reward, where the paper proposes to generate sets using universal hash functions or random network indicators (RNIs) to ensure that the sets will cover the entire state space. The main technique used in the paper then utilizes this idea of learning successor features with sets generated using RNIs and tuned with quantile regression to learn a representation from offline Atari datasets. The representation is tested with some online interaction.
strength_and_weaknesses: ### Strengths:
* This paper presents a method to approximate proto-value functions using the idea of auxiliary tasks.
* It presents an interesting workaround to the state equality problem by instead formulating it as a set inclusion reward

### Shortcomings:
* The paper states that the set inclusion reward is a relaxation of the state equality, and this relaxation allows the learning of features that relate to the proto-value functions. A toy experiment on a grid world to show how the set inclusion reward compares to the state equality reward would have been illuminating.
* Some questions are raised (See below) that are not entirely answered by the paper.

### Questions:
* Is there an assumption that the dataset used to learn these representations have coverage? Since the learned representations be dependent on the transition structure of the environment, if the MDP has bottleneck states that a random policy that starts from a restricted set of start states might find hard to get through, will the learned representations be suboptimal?
* How does the scaling of the Impala network's penultimate layer affect the number of parameters in the network? If the scaling does not change the number of parameters substantially, it might be a possible explanation of the saturation of the number of tasks that can be learned.
* Can these features be used for purely offline RL? Or would that introduce some bias which required online learning to learn the task specific policy?
* In the ablations, PVN is compared to a version that learns the successor features for the optimal policy for the auxiliary tasks. The reduced performance of this approach is attributed to the max operator needed for the Q-learning update. This conclusion seems preliminary. Is the reason that the greedy policy fails because of the max? Or because the representations no longer capture the environment dynamics alone (and also represent the policy)? What if the policy being evaluated here was the Boltzmann softmax policy with respect to the task, where the expected sarsa-type update for the successor features could still be performed, but the policy is not random?

### Minor issues and typos:
* In Section 3, it is unclear which policy the successor representation is being learned for. If it is implicitly the random policy, clarify.
* In Section 3, for the indicator function formulation, is previous work that lays out this formulation different from the Dayan paper? If so, cite it.
* Section 4.1 starts off by discussing $\psi^\pi$ but then proceeds to discuss $\psi$. It is unclear why $\psi$ has become policy agnostic.
clarity,_quality,_novelty_and_reproducibility: * Clarity and quality: The paper is clear and straightforward to follow, with high quality and readability.
* Novelty: The paper bridges several ideas through some novel and interesting techniques.
* Reproducibility: The results seem reproducible given the details in the paper. The authors are planning to release learned representations as well.
summary_of_the_review: The paper presents an analysis of a particular class of auxiliary tasks to learn successor features which can be connected to the proto-value functions and thus encode the spatial structure of the MDP. They present practical methods to generate these auxiliary tasks and show effectively that features learned via this method are useful for the downstream task.
The idea is straightforward, the proposed technique is interesting, and the results bear out the approach.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies representations obtained due to using auxiliary tasks and larger networks. The main claim is that tasks derived from randomly initialized networks are sufficient to train strong representations.

strength_and_weaknesses: The major strength of the work is the fact that it addresses an important problem of augmenting the RL training with unsupervised data. Moreover, the execution and clarity of the paper are very good.

The weakness, in my opinion, is that the presented evaluation protocol is unsatisfactory. 

clarity,_quality,_novelty_and_reproducibility: The paper is clear and nicely executed. The quality of the experiments is high; ablations are satisfactory. In some cases, the number of seeds is low, I would, however treat this as a minor issue as the overall number of experiments seems to be enough to get tangible claims.

summary_of_the_review: The paper studies relevant research questions: how the quality of representations depends on the number of auxiliary tasks and the size of the network. It suggests that it is beneficial to substantially increase the model size (e.g. 8x), while the number of auxiliary tasks needed is around $\approx 10$ (depending on the model size).

Importantly, the auxiliary tasks used in the paper are defined by a randomly initialised neural network, meaning that they are very cheap to obtain. The main finding is that these are enough to induce useful representations even when using random trajectories. 

My main concern is about the evaluation protocol. The authors measure the quality of the representations by the performance of $3.75$M samples training. This seems quite arbitrary for at least two reasons. The first one, very down-to-earth, is why $3.75$M. Are the conclusions stable for other number of samples? Secondly, more philosophically, why to measure the quality of representation by online RL training? Clearly, I can see the practical motivation; however, I can also see some problems due to the fact that RL setup is complex. I can imagine, for example, that representations are good for performance but poor for exploration or vice versa. I do not know a canonical answer to these problems, and I am ready to be convinced in the discussion period.

I would also appreciate some discussion about the games, for which random trajectories do not explore well the state space. 

Questions:
- Could you provide results for other number of samples?
- Does it make sense to measure the quality of representation using some other metric. Simple and perhaps too crude would be if (how fast) the reward can be learned using the representation.
- What would be the benefits for $16x$, i.e. when the improvements are saturated.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a new approach for representation learning in reinforcement learning by designing a new family of auxiliary tasks based on the successor measure. All reviewers found this idea interesting. The AC agrees and recommends acceptance. 
justification_for_why_not_higher_score: While the ideas and results are interesting, the (perceivable) impact is not high enough to reach the bar of the spotlight.
justification_for_why_not_lower_score: The new idea in this paper is interesting and novel.
Decision: Accept: poster