Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes the so-called Optimistic Value Distribution Explorer (OVD-Explorer) to deal with over-exploration issue in reinforcement learning (RL). It is claimed that the proposed algorithm is tractable for continuous action space and can avoid exploring  the areas with high aleatoric uncertainty. The paper tests the performances of OVD-Explorer and some of its competitors on some common environments.
main_review: This paper studies the over-exploration issue in RL, which is important to designing good exploration algorithms. The paper proposes an information-driven exploration algorithm OVD-Explorer that has potential to deal with the over-exploration issue. Here are some of my questions and comments.
1. The RHS of Equation (7) depends on state $s$, so I think the LHS should also depend on $s$. Equation (7) is the key optimization problem that OVD-Explorer needs to solve, and this maximization is over the policy space which could be much more complicated than the action space. Can the authors comment on the computational complexity of OVD-Explorer? In addition, comparing to information-directed sampling (IDS) that optimizes over the action space, does OVD-Explorer have advantages in terms of computational complexity?
2. Besides the version of IDS proposed [1], [2] also proposes the so-called value-IDS for RL. I think it is necessary to compare OVD-Explorer with other information-theoretic algorithms, especially through comprehensive numerical experiments. Indeed, both OVD-Explorer and value-IDS use Gaussian distributions to to approximate the true distributions of state-action values.
3. Honestly speaking, I had a hard time verifying the properties of OVD-Explorer (e.g., Theorem 1, Lemma 1). In Theorem 1, when $k$ is finite, it is fine, but when $k$ is infinite, things need to be written more carefully and rigorously. Also, please elaborate more the constant $C$ and how it is related to other elements. In Lemma 1, does $\sum_{a\sim\pi(a|s)}$ implies this result only holds for finite-action case? Btw, the notation $a\sim\pi(a|s)$ is a bit weird since both sides has $a$ there. In the proof for two-action case (i.e., $k=2$), there are actions $a$ and $a'$, but why the summation is over $a\sim\pi(s)$? Btw, what is the difference between $\pi(s)$ and $\pi(a|s)$? I am confused with the proof for two-action case and how it could be extended to infinite-action case. I hope these proofs could be more readable and verifiable.
4. I think it is necessary to elaborate more on why OVD-Explorer has potential to deal with the over-exploration issue. I could not get from the paper the intuitions why maximizing the mutual information between policy and the upper bounds of policy's returns can make OVD-Explorer avoid exploring the areas with high aleatoric uncertainty. 
5. It would be great that some theoretical guarantee (e.g. regret bound, sample complexity) can be showed for OVD-Explorer
6. There is no need to introduce the abbreviation OVD several times in the main text.


[1] Nikolay Nikolov, Johannes Kirschner, Felix Berkenkamp, Andreas Krause, Information-Directed Exploration for Deep Reinforcement Learning, ICLR 2019.
[2] Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, Zheng Wen, Reinforcement Learning, Bit by Bit, 2021.
summary_of_the_review: This is an interesting paper, but it seems that some improvements are needed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces OVD-Explorer, an efficient exploration algorithm that is able to detect and avoid areas with high aleatoric uncertainty. Actually, the proposed algorithm explores state-action pairs that have not been visited frequently (high epistemic uncertainty) and at the same time avoids areas with high aleatoric uncertainty. In order to achieve this behavior, OVD-Explorer maximises the mutual information between policy and corresponding upper bounds. Theoretical results show that the over-exploration issue can be tackled through the maximisation of such mutual information. Empirical analysis has been conducted on a toy task and at five MuJoCo environments including their stochastic variants.

main_review: **Pros**

* The proposed OVD-Explorer exploration algorithm is able to force the agent to visit state-action pairs that are not visited frequently, while at the same time avoiding areas with high aleatoric uncertainty. In general the idea of using mutual information is quite novel and interesting. 
* A theoretical analysis is also provided verifying that the over-exploration issue can be tackled through the maximisation of such mutual information.
* The empirical results on the noisy variants of the five MuJoCo environments show the efficiency of the OVD-Explorer compared to the other baselines. 
* In general the paper is well written. The proposed algorithm and the empirical results are presented in a clear way.

**Cons - Comments**

* The OVD-Explorer exploration algorithm has been tested only on five domains. The evaluation of  OVD-Explorer in more domains is necessary, e.g., DeepMind control suite.
* The authors should make more clear the problem of aleatoric exploration. When do we encounter this kind of problem in the real world? Some real world use cases should be presented making clear the necessity of this kind of exploration algorithmic schemes. 
* How easy is for OVD-Explorer to be integrated with any other RL algorithm apart from SAC?
* The reasoning behind the usage of mutual information for alleviating the aleatoric uncertainty is not totally clear.


summary_of_the_review: In general the contributions of this work are significant and novel. The proposed OVD-Explorer exploration algorithm seems to be efficient on the noisy variants of the five MuJoCo environments, showing that it is able to avoid areas with high aleatoric uncertainty. Apart from that a theoretical analysis is also provided. The main weakness of this work is the fact that the OVD-Explorer has been tested only on five MuJoCo environments. I would have expected the empirical analysis to have been conducted on more environments, e.g., DeepMind control suite. Last but not least, authors should make more clear the problem of aleatoric exploration by providing some real-world cases where we encounter this type of problem.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper is concerned with the problem of over-exploration in RL. The authors propose to capture the aleatoric uncertainty during exploration and propose a new exploration method called Optimistic Value Distribution Explorer (OVD-Explorer). OVD-Explorer is designed to explore optimistically while avoiding the areas with high aleatoric uncertainty. The authors propose a new measure for policy's exploration ability which aims at maximizing the mutual information between policy and policy return upper bounds. OVD-Explorer achieves good empirical performance, outperforming other methods.
main_review: The paper considers the important problem of over-exploration, which is perhaps one of the main reasons for the inefficiency of existing online RL algorithms. Good empirical performance is the strong point of this paper.

The approach in this paper is based on the following intuition: "avoid areas with high aleatoric uncertainty". However, I am not sure this intuition is correct.

**Example**
Consider an MDP with actions 0 and 1 from the initial state. Upon taking action 0, the agent moves to a terminal state with a reward of 1. Upon taking action 1, the agent moves to any of the terminal states $s_1$, ..., $s_{10}$ all with probability 1/10. State $s_1$ gives a reward of 100 but states $s_2, ..., s_{10}$  all give zero rewards. In this example, the optimal action is 1 which receives a reward of 10 on average. In this example, the agent must explore the area with high aleatoric uncertainty *even more* to figure out that action 1 can lead to a large reward.

In the paper, the authors write

> This issue, to explore overly the state-action pairs visited frequently but with high aleatoric uncertainty, is referred to as the over exploration issue.

OFU principle constructs confidence bounds based on the samples and high aleatoric uncertainty does not misguide the confidence bounds and result in over exploration. For example, in tabular MDPs, Hoeffding-based exploration, adds a bonus of $\frac{c}{\sqrt{N(s,a)}}$ to the rewards, and the exploration bonus only depends on the number of times $(s,a)$ is visited and it does not depend on aleatoric uncertainty (which is e.g. related to the entropy of $P(s'|s,a)$).

Furthermore, Bernstein-based exploration, adds a bonus of $c \sqrt{\frac{\mathbb{V}_{s'|s,a}(V(s'))}{N(s,a)}}$, which is proved to be information-theoretically optimal up to log factors (see [1]). Notice from this bonus that when the variance of $V(s')$ is larger (which can be attributed to large aleatoric uncertainty), *more exploration is proved to be required*. [2] relates exploration to environmental attributes such as degree of stochasticity.

In OFU, overexploration happens when the constructed upper confidence bound is *loose*, which results in revisiting regions of the MDP that are already explored. This can happen e.g. when coefficient $c$ in the above bonuses is too large.

**Questions/Comments**
- Why is maximizing the multi-variable mutual information in (8) a good idea? 
- The exploration strategy has many components such as optimistic estimation of $\mu_{\bar{Z}}$ in (11), pessimistic estimation of $Z^\pi$ in (13), etc. It is unclear which of these components are helping the empirical results.

**References**

[1] Zhang, Zihan, Yuan Zhou, and Xiangyang Ji. "Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition." Advances in Neural Information Processing Systems 33 (2020).

[2] Zanette, Andrea, and Emma Brunskill. "Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds." International Conference on Machine Learning. PMLR, 2019.
summary_of_the_review: The paper presents a new exploration method and shows improved performance compared to state-of-the-art methods. However, the intuition behind the exploration strategy does not seem to be correct.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new information-theoretic exploration approach, called OVD-Explorer, for deep reinforcement learning with continuous action space. The OVD-Explorer is capable of exploring epistemic uncertainty while avoiding aleatoric uncertainty. The paper also contains extensive experiments to evaluate the performance of OVD-Explorer.
main_review: ### Strengths
Overall, I appreciate the idea of maximizing mutual information between policy and values and the framework it builds to distinguish epistemic and aleatoric uncertainty, which I consider to be novel. The extensive experiments also show that OVD-Explorer can avoid aleatoric uncertainty while exploring epistemic uncertainty, and has good performance on exploration-demanding environments.

### Weaknesses
I apologize if I made any mistakes here. My major concern is about the technical soundness in paper's theoretical deriviation. In particular, in proof of Lemma 1, it is not clear whether $a$ and $a'$ are fixed or random. In the derivation of $\mathbf{F}^\pi$, it seems $a$ is randomly sampled from $\pi(s)$ while $a'$ is another fixed action, which looks quite wired to me. From my pespective, $a$ and $a'$ should be in a symmetric situation. That is, they should be either both fixed or both random.

Meanwhile, since $p(a\mid \bar{z}(s, a), s)$ is approximated instead of exactly evaluated, it doesn't look appropriate to claim that $p(a\mid \bar{z}(s, a), s)=\frac{1}{C}\pi(a\mid s)\mathbb{E}\_{z^\pi(s, a)\sim Z^\pi(s, a)}\left[\mathbf{1}_{z^\pi(s, a)\leq\bar{z}(s, a)}\right]$.

Furthermore, the writing of this paper may also need some improvements. The detailed suggestions are put in later section.

### Questions
- Connection between law of total variance and two kinds of variances?
- Do $a_0, \dots, a_k$ defined in Eq. (8) enumerate all possible actions in $\mathbf{A}$ or just some subset of $\mathbf{A}$?
- Can OVD-Explorer be applied to value-based algorithm or the case when the action set is discrete and finite? It is not very clear to me how $\frac{\partial \bar{z}(s, a)}{\partial a}$ should be computed under these two scenarios.

### Suggestions on Writing
- Based on the standard notation in information theory, it's probably better to use semicolon ";" to separate $\bar{Z}^\pi(s, a_k)$ and $\pi(s)$ when talking about mutual information.
- Since $\mu_{Z^\pi}$ depends on $\sigma_{\mathrm{epistemic}}$, in Fig. 2(a), assuming means of $Z^\pi$ at $a_1$ and $a_2$ are the same violates Eq. (13). That is, although the conclusion is not affected, PDF curves cannot overlap in Fig. 2(a). It's better to move the curve of $Z^\pi(s, a_1)$ to the left a little bit.
- The statement of Proposition 1 is confusing. Maybe you can simply state that "the gradient of $\hat{\mathbf{F}}^\pi$ with respect to action $a$ at $a=\mu_T$ is ..." in Proposition 1 and then give the formula for $\mu_E$ outside the proposition, which clarifies how you obtain $\mu_E$ by one-step gradient ascent.
- "Target policy" in Algorithm 1 may be confused with target policy network $\bar{\phi}$. Furthermore, it may be better to put Algorithm 2 also into the main context if extra space is allowed later, which can help understand Algorithm 1 a lot.
- It may be better to mention OVDE_G and OVDE_Q in Section 4 and explain that they differ mainly in using Eq. 13 or 14 in line 3 of Algorithm 1.
summary_of_the_review: This paper proposes a novel explorer that can distinguish epistemic and aleatoric uncertainty. Although technically the theoretical motivation does not look very sound to me, the experiment results seem to be quite promising.
review_title: null

Meta-review: The reviewers found the work interesting but have concerns about the correctness of some of the claims in the paper. Also some reviewers would like to see more experiments and some have concerns about the theoretical results. Overall, I see the work promising but it requires a major revision and some improvements to pass the bar. I would recommend the authors to use the reviewers' comments and prepare the paper for future venues.
Decision: Reject