Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a method for efficient exploration in discrete-action MDP environments. The intuition is to incentivize the agent to take actions that maximize “novelty”, which is measured in terms of the temporal difference (TD) error from the transition. The authors show that under certain assumptions, the expected TD error achieved by the minimum-value action (the actions that minimizes the Q value) is higher than the expected TD error achieved under a uniform action distribution. Based on this motivation, a simple alteration to the $\epsilon$-greedy exploration is proposed where, instead of sampling a uniform action with probability $\epsilon$, the minimum-value action is taken with probability $\epsilon$. Experiments on ALE and ALE 100K benchmarks show that the proposed algorithm compares favorably to the baselines ($\epsilon$-greedy, NoisyNetworks) in terms of sample efficiency due to improved exploration. 
strength_and_weaknesses: **Strengths:**

The paper makes an interesting connection between the expected TD errors under the minimum-value action and the uniform action distribution (proposition 3.1). The proposed exploration strategy is computationally lightweight and, on the evidence of the evaluation section, seems to improve the sample efficiency in several benchmarks, especially in the limited interaction setting. 

**Concerns to address:**

I have concerns about a couple of details mentioned in the paper and the overall presentation. I request the authors to address the following:
1.  As a conclusion to Proposition 3.1, it is mentioned that the expected TD-error achieved by minimum-value action is higher than that achieved by uniform action distribution. Does this require the entity $D(s) – 2\delta - \eta$ to be non-negative, and if yes, does that somehow follow from the definitions? 
2.  Propositions 3.1 and 3.2 are fairly similar in terms of the idea and the proof. I’d recommending moving the Double-Q equations to the appendix to improve the reading experience. 
3.  Algorithm 1 box – could you clearly demarcate (with colors preferably) the difference between standard DQN with $\epsilon$-greedy and MaxMin-Novelty? Are there differences both in the experience-generation and the gradient-calculation aspects? Also, there seems to be some notation errors in the TD definition in the box.
4.  Motivating example (Section 4) – when there are just 2 actions, does the difference between $\epsilon$-greedy and MaxMin-Novelty reduce to just the value of $\epsilon$? Could you add $\epsilon$-greedy with different values of $\epsilon$ to Figure 1?
5.  In Section 6, it’s not clear if the TD values are computed for all transitions, or only for the transitions with the exploratory action (taken with probability $\epsilon$).
6.  It would be good to comment on the limitations of the current method, and/or future work. Any thoughts on extensions to continuous-action environments?
clarity,_quality,_novelty_and_reproducibility: The paper is there or thereabouts in terms of clarity and quality, though I’d like to see resolution on at-least some of the aforementioned issues. Leveraging state-transition novelty or “surprise” for exploration is a well-researched area, but the paper’s approach of using the minimum-value action and the supporting propositions are novel, to the best of my knowledge. In terms of reproducibility, the authors have included the hyperparameters and the architecture details, but I didn't find a link to the anonymized code. 

summary_of_the_review: My initial rating is “5: marginally below the acceptance threshold”. The paper introduces a simple and interesting idea to facilitate exploration and improve the sample efficiency in deep-RL. The results are encouraging. However, I have some concerns about the material presentation and would be happy to reconsider after discussion with the authors.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This method proposed to use minimal action with the lowest Q value to maximize novelty. The experiment demonstrates the effectiveness of the proposed methods. 


strength_and_weaknesses: 

Strength:

It's interesting to see that using the minimum-valued action could lead to better exploration. The proposed method is very simple and requires minor modifications to existing methods. 



Weakness:

Generally, it's hard for me to follow the motivation for using minimum-valued action. The paper seems to claim the minium-valued action should be the one that maximizes the novelty. I didn't see the definition of novelty in Section 3. Although the paper provides several theorems in Sec 3, it's hard to get the main idea of these theorems. 

The improvements in Figure 2 are not very significant. Moreover, on some tasks, the paper demonstrates results with 200 million frame training, while on other tasks, the paper demonstrates result with only 50 million frame training (e.g. Enduro). This is very misleading. Did the proposed method converge on these incomplete-reported tasks?





Several Questions:

Algorithm 1 seems quite unclear to me.

What do you mean by Populating the Experience Replay Buffer? 

Do you mean you need the MDP model (including the transition and reward function)?

How to obtain $s_{t+1}^{min}$ based on $a^{min}$ (and how to obtain $s_{t+1}$)?  

What do you mean by $e$?
clarity,_quality,_novelty_and_reproducibility: 

The main idea of the paper is hard to follow. And there is some confusing part in the theorems, experiments, and algorithms.

The code of this paper is not open-sourced. Supplying code could help the readers understand the details of the paper.


summary_of_the_review: 

This paper tried to propose a new novelty maximization method with minor computation costs. However, the main motivation for using minimal-valued action is hard to follow. There are some confusing parts in the theorems, experiments, and algorithms that make it hard to assess the idea.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: As an alternative to the usual $\epsilon$-greedy exploration used in DQN and similar approaches, the authors propose taking the action with the minimum Q value with probability $\epsilon$.
strength_and_weaknesses: Strengths
- I found the chain MDP experiment to be quite interesting to transmit the issue the authors want to tackle. That is, the fixed noise that comes from initialization of parametric Q functions.

Unfortunately, I have some major worries with this paper.

Weaknesses
- After some thought, I realized that the proposed method isn't guaranteed to converge to an optimal policy even in very simple examples. Take for example a 3-armed bandit problem with rewards 0, 1 and 2 per arm. An agent that learnt the Q-values 0, 1 and 0.5 for the arms (in the same order as before), will take the second arm (maximum Q value), except for when it's exploring that it will take the first arm (minimum Q value). Thus, it will never be able to explore the third arm, which is the most rewarding one. This is already a big red flag about this algorithm.
- On top of the main issue with the theory of the paper, I don't find the experimental results convincing. In order to make a fair comparison HP-searches must be ran for each individual algorithm. At the very least, the value of $\epsilon$ should be tuned differently, as it has a very different role in each algorithm. In fact, model-free approaches have been shown to achieve much higher scores in [1]. I suspect the 0.03 of $\epsilon$-greedy from this paper comes mainly from a lack of proper hyper-parameters.

[1] https://arxiv.org/pdf/1906.05243.pdf
clarity,_quality,_novelty_and_reproducibility: The paper was easy to follow. The theory felt unnecessary in my opinion.
summary_of_the_review: The proposed approach isn't guaranteed to converge to an optimal policy, even in the tabular case. While this could be acceptable if the experimental part of the paper was very solid, that is not the case either. I expect the authors to clearly state that the approach doesn't converge to the optimal policy if they plan to submit this paper to any conference/journal.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper claims in the abstract that they develop a method for exploration that is "theoretically well motivated, and comes with zero computational cost while leading to significant sample efficiency gains in deep reinforcement learning training". The claim about their experiments is that the "technique improves the human normalized median scores of Arcade Learning Environment by 248% in the low-data regime".
strength_and_weaknesses: Strengths:
The claims of the paper are ambitious.

Weaknesses:
The paper is not sound.
clarity,_quality,_novelty_and_reproducibility: CLARITY
The paper has several elements that should be written differently. In the abstract only, here are three elements:
- It is written that deep RL "achieved high acceleration in its progress". A constant progress would already mean that things improve steadily. An accelerating progress is even more specific and I think that using such terms is debatable and should be avoided in a technical abstract.
- It is written that efficient exploration is "a well-understudied and ongoing open problem". Beyond the choice of the word "well-understudied", it feels a bit odd to say that exploration is "understudied" because exploration is known as being one of the top challenges in RL.
- The algorithm is described as coming "with zero computational cost". It should be made clear that it is compared to another algorithm. In addition, the term "zero" is quite precise and I'm unsure you can actually claim this.

Additional elements lack clarity, for instance in the Algorithm 1: What is $e$? It seems that the replay buffer is not used in the learning phase?

QUALITY, NOVELTY
- Conceptually, my main concern is that the strategy of the algorithm does not sound reasonable. Imagine that you have initialized all Q-values at 0 for a given state. Imagine now that from that state, one of the actions gets a negative Q-value (e.g. negative reward followed by terminal state) and another one a postive Q-value (e.g. small positive reward followed by terminal state). In that case, it seems that the algorithm would never explore the other actions in that state.
- The paper claims that it demonstrates "theoretically that our method MaxMin Novelty based on minimization of the state-action value results in higher temporal difference loss, and thus creates novel transitions in exploration with more unique experience collection". This claim is very strong (as it seems to be always true, including with deep learning as a function approximator). That is not what is see in terms of theoretical results in the paper.
- From Table 3 in the appendix, the results are much less convincing as compared to what they are presented in the paper.

REPRODUCIBILITY
The source code does not seem to be provided.
summary_of_the_review: The paper studies a potentially interesting setting but the claims are not well substantiated.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a simple exploration strategy in which the action with the minimum action-value function is occasionally selected. Some theoretical results are provided as well as empirical ones.

The reviewers have raised several concerns about this paper, including the followings:
- The clarity and presentation of the paper need improvement. Some reviewers had problem understanding the motivation for using minimum-valued action.
- Correctness of the method is questionable. Reviewers 7Z6y and 3c9Y constructed simple finite armed bandit examples that show the method does perform correctly as an exploration strategy.
- There were concerns regarding the experimental results.


Regarding the correctness, the authors argued that as Deep RL is more complicated than bandits, a strategy that works for deep RL does not need to work with bandits.

I do not agree with this direction of argument. I agree that it is likely that a strategy that works for bandit may not work for deep RL, but a method that is supposed to be able to solve a harder problem, yet cannot solve a simpler problem, is questionable.

Even though we had some discussions between one of the reviewers and the authors, the rest of the reviewers unfortunately did not participate in the discussions. Therefore, I read the paper myself before closely looking at the reviews.

I agree with the issue of clarity, especially in Section 3. The algorithm's motivation is a bit hand wavy. The theoretical results, even though they seem to show some specific and concrete statements, do not really clarify why choosing the action with the minimum action-value is good for exploration-exploitation tradeoff.
The justification that it leads to a larger TD loss, and that maximizes the novelty, which is supposedly good for exploration, is questionable to me. One reason is that what the authors call the TD loss is actually TD error, so it can be both positive and negative. There is no absolute value or squared error of TD error. What is the significance of a very large negative TD error, which makes it a good criteria? Why not choosing an action with a very large positive TD error? It is more intuitive to consider the absolute (or squared) value of TD error as an indicator of surprise and novelty. Even in that case, why is it a good criterion to optimize for exploration-exploitation? This link is not made clearly in the paper.

Perhaps more importantly, I believe the proof of Proposition 3.1 has an error. To see why, let us first consider Definition 3.2. That definition says that for a fixed $\hat{a}$, how different the $\max_a Q_\theta(s,a)$ is from $\max_a Q_\theta(s',a)$, when $s'$ is sampled from the transition kernel $T(s,\hat{a}, \cdot)$. The important point here to notice is that $\hat{a}$ is fixed and does not depend on theta.

Now consider the first inequality in the proof of Proposition 3.1. Let us pay attention to how random variables in the expectation of the first line and the second line are sampled. 
First, theta is sampled. This defines $Q_\theta$. As a result, $a^\min$ is selected. As $a^\min$ depends on $Q_\theta$, it is a function of theta, i.e., we have $a^\min(\theta)$. Afterwards, $s^\min_{t+1}$ is selected according to $T(s_t, a^\min(\theta), \cdot)$. This depends on theta because of the dependence of $a^\min$ on $\theta$. So, for each sample of theta, we have a different action $a^\min$ that defines the transition.

Comparing this with Definition 3.2 shows the error in the proof. The definition is based on a fixed $\hat{a}$ across all samples of $\theta$, but we have a theta-dependent action in this proof. 
That definition, as is stated, cannot be used to upper bound the difference between two quantities on the first and second line, with an addition of a delta term.

How can this be fixed?
Perhaps the definition should be changed to hold for any $\theta$ in the $\Theta$ space, as opposed to in expectation. I let the authors figure this out and discuss whether that is a reasonable assumption or not.

Overall, because of all these issues, unfortunately I do not think the paper in its current form should be accepted.
justification_for_why_not_higher_score: Unclear writing and motivation. The algorithm is not sound. The proof has an error.
Decision: Reject