Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies exploration bonus in practical deep RL based on Sample Average Uncertainty (SAU) and upper confidence bound (UCB). SAU is a recently studied novel uncertainty quantification that works for rather arbitrary estimators. Previous paper has studied how to use SAU to derive UCB-type bonus in multi-armed bandits and proved that it could achieve optimal regret. 

This paper successfully extends the SAU-UCB-type exploration bonus from bandits settings to RL and most importantly, deep RL settings, and shows how to incorporate SAU-UCB-type bonus in (deep) RL. This paper conducts various experiments for RL and deep RL, demonstrating the advantage of their algorithms over the standard benchmarks. 

The paper is generally well-written.
main_review: 
#### Strengths
1. SAU has good theoretical justification in bandits. This paper contributes to connecting the RL theory and empirical RL, two largely separated areas. I think this should be encouraged. 
2. The algorithm is simple and can potentially be extended to other methods such as policy gradient.

#### Weakness
1. The experiments are mainly compared against vanilla DQN. Since the authors' algorithm is a modified DQN, it would be fairer to compare their algorithm against other modified DQN variants, such as Rainbow, etc. In particular, the authors should compare with DQN with random network distillation (RND), because RND can also be interpreted as adding a UCB-type bonus and thus share similarities with the authors' algorithm.
2. The experimental results seem not improve much upon existing algorithms in RL. 
3. It is strange to use the same counter $n(a)$ across different states, instead of a state-dependent one, e.g. $n(s, a)$. This does not make much sense. May the authors further justify this part? Or provide further ablation studies, e.g. fixing $\delta^2 \equiv 1$, to see if the performance of their algorithm is indeed due to the SAU?
summary_of_the_review: I think the novelty outweighs the weakness, and I would recommend weak accept.

**After Discussion:** I read other reviewers' reviews. Weakness 1 pointed out by Reviewer o8hT mentioned a paper that seems to contradict this paper [Zhu and Rigotti, 2021], and the authors seem not responding to this concern. Also, Reviewer uzFB pointed out several other baselines, including Boltzmann exploration and inverse-gap, that the authors did not compare with. I think the first concern downgrades my evaluation on the theoretical strength of this paper, and the second concern downgrades the empirical strength. Thus, I would like to recommend weak reject.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work introduces $\delta^2$-exploration for reinforcement learning (RL), which aims to incorporate sample average uncertainty (SAU) into RL exploration. The authors discussed the background and formulation of SAU. The authors further propose $\delta^2$-exploration, which incorporates SAU into Q-learning and compare such exploration with value-uncertainty exploration (UCB-type exploration) and $\epsilon$-greedy. The author then proposes to incorporate $\delta^2$-exploration into DQN and conduct experiments to compare $\delta^2$-exploration with SOTA exploration algorithms. Empirical results show that $\delta^2$-explorations attain comparable results to bootstrapped DQN.
main_review: Strength: 

1. This work proposes an exploration strategy that does not hinge on uncertainty estimates, which are typically computationally expensive and require either ensemble of models or specifically designed neural nets.  

2. This work incorporates recent advances in the theoretical study of bandits, which are promising and have been shown to work effectively by various previous studies. e.g. IDS, UCB, Posterior Sampling

Weakness: 

1. The work lacks theoretical support. Though incorporating SAU for exploration is promising (as I claimed in the strength part), the proposed incorporation method in this paper is not grounded by theory. Particularly, in Algorithm 1 of this paper, the author directly incorporates SAU for exploration in Q learning, where the SAU hinges only on the actions. It makes sense to estimate uncertainty based only on the novelty of actions under the multi-arm bandit setting. Nevertheless, in the contextual bandit setting, SAU requires a notion of homogeneous context to yield a reasonable uncertainty estimate [1]. Thus, it is questionable if directly incorporating SAU for the more complicated RL setting is provably efficient.

2. In Algorithm 2, it is reasonable to use deviation between the target and the Q network to compute the TD error. However, it seems that $\Delta_{dqn}$ no longer aggregates the TD errors according to the actions taken as SAU does. Alternatively,$\Delta_{dqn}$ is defined for each of the individual state-action pairs. It would be better if the author could give some discussion on such an adjustment in DQN implementation.

In addition, some exploration strategies based on Q-learning are missing in the literature review. For instance, exploration with IDS ([2], [3]) is also an important SOTA, which incorporates bandit exploration strategy into RL exploration. In addition, from the empirical perspective, previous works also incorporate curiosity-driven methods [4] and mutual information ([5],[6],[7]) to construct the exploration bonus.

[1]  Zhu and Rigotti, Deep Bandits Show-Off: Simple and Efficient Exploration with Deep Networks. (2021)

[2] Russo and van Roy, Learning to Optimize Via Information-Directed Sampling. (2017)

[3] Nikolov et al., INFORMATION-DIRECTED EXPLORATION FOR DEEP REINFORCEMENT LEARNING. (2019)

[4] Pathak et al., Curiosity-driven Exploration by Self-supervised Prediction. (2017)

[5] Houthooft et al., VIME: Variational Information Maximizing Exploration. (2017)

[6] Kim et al., EMI: Exploration with Mutual Information. (2017)

[7] Kim et al., Curiosity-Bottleneck: Exploration by Distilling Task-Specific Novelty. (2019)



summary_of_the_review: The idea of incorporating SAU into RL exploration is promising. Nevertheless, the presence of context and transition dynamics makes it unclear from the theoretical perspective whether SAU can be directly adopted into the exploration of RL. Hence, the work would be stronger if the authors could provide additional quantitative arguments supporting the validity of SAU for RL. In addition, the comparison with other baselines can be made more straightforward if the authors could provide charts of evaluation scores.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper extends a recently-proposed exploration method called SAU in bandits to the RL problem. They combine this exploration approach with the standard Q-learning algorithm. Their experiments show that this approach can obtain better performance compared with the Q-learning algorithm with eps-greedy exploration.
main_review: The paper are well-written and easy-to-understand. However, there are following concerns from my point of view.

The algorithm looks like a trivial extension of SAU method developed by Rigotti & Zhu. There should be more discussion about the difference between $\delta^2$-exploration method and SAU method. To me, it seems the technical novelty of the algorithm design is rather weak.

The authors fail to explain why this simple exploration strategy can work (or at least better than $\epsilon$-greedy). As far as I am concerned, collecting enough samples for an action on certain states cannot indicate well-exploration of such an action on any other states. There are many simple hard instances that this strategy may fail. For example, we can construct an MDP in which the agent will always enters state $s_1$ with high probability, and occasionally enters $s_2$. The expected reward of $a_1$ is higher than $a_2$ in $s_1$, while the expected reward of $a_2$ is higher than $a_1$ in $s_2$. Using $\delta^2$-exploration strategy, the agent may never take action $a_2$ in $s_2$ if the expected reward of $(s_2,a_1)$ is higher than $(s_2,a_2)$ in the first several attempts. Therefore, I believe the exploration strategy is not theoretically-convinced enough to obtain good performance on all possible RL tasks.

The experiments in the paper seems not enough to indicate the benefits of $\delta^2$ exploration mechanism. The authors evaluate their algorithm on the Cliff-Walking task and the Atari games. For the former, the reason why the $\epsilon$-greedy algorithm achieves slightly worse performance may be that the agent may occasionally choose the bad action due to the $\epsilon$-greedy mechanism. This case may not always happen in the general RL tasks. For the latter, the authors only conduct experiments on 8 games. I believe that more experiments are necessary (on other games or even other benchmarks such as Mujoco tasks) if the authors want to argue that $\delta^2$-exploration could serve as a competitive baseline or even replace the role of $\epsilon$-greedy in RL. Also, I doubt whether these games are particularly selected or randomly chosen. 
summary_of_the_review: Based on the above issues, I am inclined to given a negative score. I will increase the score if the above problems are well-tackled in the rebuttal:
1. Discussions on the comparison with SAU method by Rigotti & Zhu.
2. Explanation of the insight behind the exploration strategy.
3. More experiments to support their conclusion.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper extends the recently introduced SAU measure from bandits to RL. The idea is to enhance the exploration of action based on an approximation of the estimation error. More precisely, the bonus is proportional to the average squared temporal difference error. This uncertainty measure is easy to compute and can be integrated into both tabular and continuous methods (e.g., Q-learning and DQN).
main_review: The method is simple and intuitive, and I think it's an interesting idea. However, I have various concerns about the paper. 

The paper does not try to claim any connection with theory, but I'm wondering what is the intuition behind this approach. In particular, the idea of averaging over states seems very suboptimal in RL. In particular, it is easy to imagine problems where you have only a few actions available (in the extreme case one) in certain states that are visited often. By using your method you are decreasing the uncertainty of these actions (by dividing by the total counter $n(a)$) also in states that are maybe hard to reach, potentially leading to under-exploration. I understand that the numerator is a squared error, but it still seems potentially critical. It would be good to test your method in other tabular domains where this situation may happen.

This leads me to the second issue: experiments are not enough to support your claims. First, I disagree with the argument that you need only to compare with the $\epsilon$-greedy strategy. Second, there is not enough diversity in terms of domains and baselines to support your claims.
There are plenty of easy methods that could be tested. First of all, you could have tested multiple annealing schedules for $\epsilon$-greedy and not only $1/\sqrt{n(s)}$, e.g., $n(s)^{\alpha}$ with $\alpha>0.5$ or even action-dependent values $n(s,a)^{\alpha}$. There are also other techniques, like optimistic initialization of the Q-function, that often help with exploration. I would have also tested softmax exploration, this is another standard technique for randomized exploration with Q-learning. There are also inverse gap techniques, originally introduced in [1]. This is just a short list of easy techniques you could compare with. Clearly, in tabular RL, you could even try to compare with exploration strategies based on upper-confidence bounds or Thompson sampling.

I found also limited the set of experiments in deepRL. Several heuristics have been proposed over time and I believe it is necessary to compare with a few of them even if they are more complicated. It is important for understanding the potential sub-optimality of the proposed strategy.

Moreover, I would add more ablation studies either in tabular and continuos MDPs. For example, you can play with the level of stochasticity in the MDP, the structure of the MDP itself (as mentioned in a previous point) and add other classical control environments.

Finally, you refer to the appendix that seems not to be available. Maybe we could have obtained more details about the setting used in the experiment (or other experiments) from there.

[1] Abe and Long, Associative reinforcement learning using linear probabilistic concepts. ICML 1999

Minor comments:
- I would suggest adding a dependence on the current time $t$ in the definition of $\Delta^2(a)$ and providing an explicit definition of $\mathbb{T}_a$
summary_of_the_review: Overall, while I think the idea is interesting, it is necessary to provide a more detailed experimental evaluation of the method to support the claims. I think the paper is not currently ready for publication.
review_title: null

Meta-review: Although the reviewers found the idea of the work interesting, they all think it is not ready for publication. The experiments do not properly support the claims. Discussion on the connection to some related work is missing. And also the proposed method is not well motivated. I suggest the authors to take the reviewers' comments into account, revise their work and prepare it for future venues.
Decision: Reject