Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: **Summary:**

This paper offers a critique of current exploration techniques as being overly complex and engineered to only work on specific tasks. As an alternative, the paper proposes temporally extended $ \epsilon$-greedy exploration which maintains the simplicity and generality of $ \epsilon$-greedy while offering better . More specifically, the proposed algorithm simply repeats the randomly chosen action for a random number of steps (where the number of steps comes from a specific distribution), this is a specific instantiation of the more general algorithm presented in the paper where any set of semi-markov options can be used.

--------------------------------------------------------------------

**Strengths:**

1. Clarity. This paper is very well-written and clear, making it enjoyable to read. It sets up the shortcomings of prior methods and offers a simple solution. I also especially appreciated the clear discussion of the limitations of the proposed method.

2. Strong critique of prior methods to provide motivation. It is an important observation that while many exploration methods are developed in the theory and deep RL communities, they are often inferior in practice to simple strategies like $ \epsilon$-greedy. While this is not a novel contribution, this paper really drives home the point by providing a slightly smarter variant of dithering that competes favoriable with much more complicated algorithms. This is an especially important contribution of this paper since it makes the point to the RL community that simple exploration strategies may be more effective in practice, but there is still room to innovate while maintaining simplicity and generality.

3. Strong empirical results. The experiments clearly show an improvement over $ \epsilon$-greedy in small benchmark problems. Then, they demonstrate how $ \epsilon z$-greedy even improves over more complocated exploration strategies for deep RL algorithms applies to atari relative to more complicated exploration algorithms like RND (at least in the "average" case, but not on "hard exploration" games like Montezuma's revenge).

   

--------------------------------------------------------------------

**Weaknesses:**

1. The theory could be tightened. The paper would be stronger if the theorem were stated more formally (defining polynomial sample complexity) and the proof provided the specific results being used from the cited papers (maybe as lemmas in the appendix). At a more substantive level, it is not clear how exhaustive the list of desired properties of an exploration algorithm is. The paper lists three desiderata for an exploration strategy: (1) that it is simple, (2) that it is stationary, and (3) that it promotes full coverage of the state-action space. Each of these goals makes sense, but the paper does not provide any framework to explain why these are a necessary or sufficient set of properties to yield the desired behavior. Moreover, it is not clear what the tension or tradeoffs are between the properties. A more clear discussion of these issues or formal framework could go a long way toward clarifying the landscape of exploration algorithms. 

--------------------------------------------------------------------

**Recommendation:**

I reccomend accepting this paper and gave it a score of 8. I think the paper provides a clear argument for simple and general exploration strategies and that $ \epsilon z$-greedy seems to be an algorithm that achieves these goals. Moreover, I think that the paper makes an important point to the community working on exploration algorithms that the complicated algorithms being developed can often be beaten by simple strategies when considering a broad range of problems.

--------------------------------------------------------------------

**Additional feedback:**

- One reference that I think should be included when discussing learning temporally extended representations of actions is [1].

- Typo: line 2 of the last paragraph on page 1 should be "such a compromise".
- The discussion of the choice of distribution over durations was somewhat abrupt. This is an interesting part of the algorithm and it would be nice if it was fleshed out a bit more. 



[1] Whitney, W., Agarwal, R., Cho, K., & Gupta, A. (2019). Dynamics-aware Embeddings. *arXiv preprint arXiv:1908.09357*.
review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper presents a generalized overview of temporally extended e-greedy exploration. Basic principle of temporally extended e-greedy exploration is to apply the e-greedy exploration policy for an extended period of time. Specifically, authors use a heavy-tailed zeta distribution. 

Strong points
- This paper analyze theoretical properties of temporally extended e-greedy exploration in Theorem 1. 
- ez-Greedy policy outperforms e-Greedy policy in some experiments environments qualitative and quantitatively.

Weak points
- The theoretical analysis is too general under too strong assumptions. Thus, the presented results are not unexpectedly novel.
- The presented methods based on the zeta distribution are not concrete enough. 
- Algorithm is not clearly specified. Thus, it is hard to evaluate the algorithmic contributions of this paper.

Although this paper presents a general analysis on temporally extended e-greedy exploration, the presented ideas are too general. Thus, it is very hard to verify the technical contributions (in terms of models and algorithms) of this paper.
review_title: An important problem which is weakly supported by a concrete model

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ##########################################################################
Summary:

This paper proposes a simple yet general approach for exploration in discrete-action problems. The proposed approach, called ez-greedy, combines randomly selected options with the well-adopted e-greedy exploration policy to achieve temporally-extended e-greedy exploration. The paper overviews the publicized exploration methods from the perspective of their inductive biases, and clearly states where the inductive bias of ez-greedy would be better suited over e-greedy. The paper reports results in tabular, linear, and deep RL settings, on numerous domains ranging from classic toy problems to Atari-57. The results are interesting, and the analysis aligns and supports nicely the narrative of the paper.    

##########################################################################
Reasons for Score:

Overall, I vote for accepting this paper. The idea is simple (a generalization of e-greedy) and the discussions nicely illustrate the main properties of an ideal generally-applicable exploration method. The experiments clearly show where ez-greedy exploration would be useful. Also, they show that the inductive bias of ez-greedy does not hurt much the performance in simpler dense-reward domains while more specialized algorithms suffer significantly.  

##########################################################################
Pros:

See "Reasons for Score" above.

##########################################################################
Cons:

1) The results in Atari are based on a deterministic version of Atari (i.e. not using "sticky actions"). Also, in DeepSea the deterministic version of the task is used. Ideally, I would've liked to see empirical results in stochastic domains as well. More importantly, I'm not sure why only deterministic domains are used?

2) The literature on action-repeats are discussed briefly. But it's hard to know how the former related works were different in their formulation and use of action-repeats. Also, could you clarify how sticky-actions are positioned w.r.t. ez-greedy (beyond that the purpose behind sticky-actions was to induce stochasticity in the environment as opposed to being used explicitly for exploration)? For instance, do sticky-actions actually improve learning performance in the same domains were ez-greedy improves performance?

3) The rainbow + e-greedy vs. Rainbow + ez-greedy Median and Mean plots do not show significant findings. I think a bar-plot should be added to show per-game relative human-normalized improvements for these versions. The same should be done for R2D2 (e-greedy) vs. R2D2 + ez-greedy as well. I think what this could reveal is symmetric bars over the 57-Atari games (i.e. number of games in which ez-greedy outperforms and underperforms e-greedy are the same). Also, the extent of improvements on average is the same as shown in the Mean plot of Figure 8. 
To clarify, I don't see an issue with this outcome (i.e. if the bars are symmetric; meaning overall there are as many games in Atari-57 that would benefit from ez-greedy over e-greedy as there are games in which the opposite is the case). This does not go against the narrative of the paper which makes it clear that they each have an inductive bias that suits some tasks over others. But I think this should be made super clear in the results section, through such bar plots. For the same reason, I think the Mean plots should also be brought to the main text and shown next to the Median curves.   

4) Why only 5 random seeds in DeepSea? I suggest showing results for 30 randoms seeds like in the other toy problems.
  
##########################################################################
Questions during the rebuttal period:

Please address and clarify the "Cons" above.

##########################################################################
Minor comments:

- It would be useful to replace "Rainbow" with "Rainbow (NoisyNet)" in Figure 3 so as to emphasize the difference between "Rainbow" and "Rainbow + e-greedy". Similarly, for "R2D2" it'd make it easier for the reader if the Figures show "R2D2 (e-greedy)". 

- Table 1: "Algorithm (@200M)": M doesn't need to be italicized (to be consistent with "Algorithm (@30B)").

- It'd make it easier if "(100%)" is added to the y-axis of Median/Mean plots.

review_title: Official Review for Temporally-Extended e-Greedy Exploration

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper presents an extension of \eps-greedy strategy in order to increase the coverage of exploration in RL problems. The main idea is to take an exploratory option instead of a single action e.g., by repeating an action for n steps, where the duration of repeat is sampled from some distribution. The authors demonstrate that given certain conditions, the algorithm will converge in polynomial time for Q-learning method.

Overall, the paper provides a simple yet effective exploration technique for RL methods. However, there are some unclear points regrading the impact of the approach on the filed, I thus vote for a weak reject. 

Pros:
- A simple and universal approach to promote full coverage in reinforcement learning
- Scalable and easy to implement
- Interesting inspiration from animal foraging behavior
- Demonstrates effective performance in conducted experiments


Comments:

- The key concern about the paper is whether gaining the full coverage in exploration is beneficial at any cost. In my view, RL favors smarter exploration over the total coverage. For instance , the exemplary scenario in figure 1 shows how the proposed approach increases the coverage of the state space.  But why we would need to search the whole space if we are on the right path to the goal. Unnecessary coverage will lead to higher regret and delayed convergence that is the result of naive exploration.

- Another problem with \eps-greedy is that it explores forever. Hence, it would be an improvement to stop/reduce exploration at some point rather than intensify it. Assume in the steps close to the goal, the worst action has the same probability to be chosen as the second-best action and it repeats for n times which moves the agent farther from the goal. I would suggest to add evaluation in terms of regret and/or convergence time in such scenarios.

- The limitations both enumerated in the paper and the dependency of the approach on some strong conditions on the options seem to be more than the benefits of the proposed method. Besides, it is not general in terms of class of applications; e.g., in complex tasks we can not simply repeat an action in different states.

- How does the approach behave in very simple settings, e.g., bandits? I would recommend to add such analysis for online exploration into the paper.

Minor:
Table 1 is not referenced in the text
review_title: Insufficient impact

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes an easy-to-implement algorithm for the efficient exploration, which is a temporally-extended version of \eps-greedy. Instead of uniformly selecting primitive actions with probability \eps for exploration, the algorithm explores using options. In theory, it has been shown that if the option set is well-designed with a sublinear expected reaching time, the algorithm achieves a polynomial sample complexity. Empirically, the authors tested a simple instantiation, ez-greedy, in multiple environments and claimed that ez-greedy improves exploration and performance in sparse-reward environments with minimal loss in performance on easier, dense-reward environments.

I appreciate this work for its motivation and the algorithm is simple-to-implement and not computationally expensive, which points to an interesting direction for future study. 

But there are several concerns I have: 
1. The conditions in Thm. 1, i.e. a sublinear upper bound on visiting time and 1/p(w), is not straightforward for me to realize. How should one construct such an option set if no prior knowledge is given? Do the option-learning methods in [Jinnai et al. 2019, 2020] and [Machado et al. 2017 2018] satisfy these conditions? Does ez-greedy satisfy these conditions? If not, what approximately are the upper bounds for these heuristics? There should be more discussion about this.
2. In the tabular RL, it would be more complete if the authors can compare with UCB-based exploration strategies as well, e.g. the UCB-Q as in http://papers.nips.cc/paper/7735-is-q-learning-provably-efficient.
3. As mentioned by the authors, the performance of ez-greedy depends on whether the effects of actions differ significantly across states. There should be more adversarial cases to show the possible outcomes of ez-greedy compared with other exploration strategies.
4. As mentioned by the authors, action-repeats are not new in deep RL. The novelty of this work lies in using it for exploration with sampled duration. However, the selection of zeta-distribution for duration sampling is only partially empirically demonstrated as well as the choice of \mu. It would be better if the authors can support it with a theoretical justification or some quantitive analysis in terms of e.g., how the value of \mu affects the final performance.

I am open to adjusting the score if the rebuttal can address my concerns.

review_title: A simple algorithm. 

Meta-review: This paper proposes a simple generalization to epsilon-greedy exploration that induces temporally extended probes and can leverage options.  The idea and analysis are trivial.  Computational results demonstrate when this sort of exploration is helpful.  The paper is well written and the authors offer a fair assessment of when these ideas do or do not address challenging exploration tasks.  A range of computational results support and offer insight into the concepts.

Decision: Accept (Poster)