Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a new exploration technique called MADE that computes a bonus that depends on the ratio between the visitation densities of the current policy and policy cover of previous policies. This incentivizes the agent towards it has not been before and leads to more exploration. The authors provide a convergence result for this bonus and evaluate it on grid worlds, Mini Grid and Mujoco environment to show that it leads to better exploration than existing techniques.
main_review: Overall I think that this is a good paper, it builds on previous ideas about using policy covers for exploration but is able to derive a bonus that can be used with any reinforcement learning algorithm, model based or model free and not limited to policy gradient method. I found the paper well written and easy to follow. The empirical evaluation was really thorough, MADE was evaluated on grid worlds, discrete actions and continuous control environments.
MADE showed really good results on MiniGrid, however on DM control while results look promising it is hard to interpret them without knowing the number of seeds used for each.

How was Eq (4) chosen vs other possible solutions? Could we use those insights to derive other exploration bonuses? And could we hope to find an optimal regularizer?
In section 4.1 and Figure 3 MADE is shown to work similarly to Bernstein bonuses which are as good as we can hope. Does it mean that this choice of regularizer is somewhat optimal?

L139: What happened to the term $\sqrt{N_k}$? To match equation 4 it should be included and would lead to different bonuses.
I found the paragraph L148 to be interesting, being able to fit any bonus through the MADE paradigm could be powerful, however little to no insight is actually gained from this. Do you think there is anything we can learn through this point of view?

When looking at Equation (4) it is not clear that the bonus actually goes down to zero. Is that the case? If not that might explain the regularizer instead of exploration bonus. In that case can the bonus impact the reward and change the optimal policy of the problem being solved?

Small typos:
L194 "gradients.= In"
L215 "we as the training"



limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes an new approach for exploration in reinforcement learning (RL). The idea is to give an exploration bonus to visiting with the new policy state-action pairs which have low visitation density compared to previously visited state-action pairs. The paper provides a convergence proof assuming a perfect oracle provides visitation densities for a chosen mixture policy. The proposed approach is compared in experiments to RL baselines in both continuous and discrete control tasks with function approximation and in tabular benchmarks.
main_review: The idea behind the proposed exploration bonus is not surprising by itself. There are other methods that try to explore in parts which have not been explored before. For example, [Hong et al., 2018] adds an exploration bonus for a policy which is different from previous policies. In addition, as mentioned in this paper count based methods also try to visit state-action pairs which have not been visited before. One of the main contributions is to propose an exploration bonus that is efficient and simple and can be implemented in practice.

Authors: how is the proposed approach related to prior work where the new policy is regularized by maximizing the difference to prior policies such as [Hong et al., 2018]? Intuitively, maximizing the difference to prior policies also maximizes the differences to prior state-action distributions indirectly. Is there a benefit to the approach you are using? An experimental comparison to [Hong et al., 2018] would make sense.

The submission appears technically sound. The theoretical proof is nice. It would be good to have a discussion on what the theoretical proof means in practice since there is the assumption on the oracle providing visitation densities. The discussion on how the proposed exploration bonus can be seen as another form of other exploration bonuses is interesting and valuable. The empirical results show the approach outperforming baselines and the results are analyzed in a reasonable way. Having both tabular and continuous tasks is valuable.

The paper should provide timing results. How much computation time does each method use per sample? Is the proposed approach computationally intensive compared to other approaches?

The paper is clear and well written. Emphasizing even more that Algorithm 1 is a theoretical proof but not actually used in the experiments would improve clarity. The practical implementation of the methods is one of the key things for a practitioner in RL and this could be also emphasized (although it is relatively straightforward to find it in the text).

I expect the results of the paper to be used by other researchers. While similar ideas have been proposed before, exploration is an important unsolved problem and the idea proposed in this paper is simple and seems to perform well in the experiments.

[Hong et al., 2018] Hong, Z.W., Shann, T.Y., Su, S.Y., Chang, Y.H., Fu, T.J. and Lee, C.Y., 2018, December. Diversity-driven exploration strategy for deep reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (pp. 10510-10521).

UPDATE: I am happy with the author's rebuttal and the changes they are planning for the next version of the paper.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes an alternative exploration strategy by MAximizing the DEviation (MADE) of the next policy from explored regions of prior policies by adding an adaptive regularizer (function of state-action visitation counts) to the primary RL objective at each iteration to balance between exploration the new state space and exploit the visited states.  In addition, MADE has been theoretically proven to converge to the global optimum given access to an approximate planning oracle.  The authors show that MADE applies some simple adjustments to the Hoeffding-style count-based bonus. Moreover, experiments in three different RL algorithms (Value iteration, PPO, Q-Learning) show the superiority over the state-of-the-art UCB-bonus methods (Hoeffding and Bernstein bonus). In addition, the authors demonstrate that MADE can practically work both in Model-based (Dreamer) and Model-Free (IMPALA, RAD) RL algorithms, significantly improving sample-efficiency over baselines.
main_review: The paper proposes an interesting method for addressing the problem of exploration in RL, with theoretical results about the global convergence to the optimum and solid empirical performance compared to the SOTA. Overall, I like the paper, but I still have few doubts that I would like the authors to address:

- It is not clear how we can get the total reward at iteration k by taking the gradient of the new objective as shown in equation (5).
- As far as I understand, can $r(s,a)$ be derived from equation (2)?
- But then still, how is that the total reward can be derived from the gradient of the regularized objective function?
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose adding a regularisation term, that encourages a policy to visit states, less visited by previous policies, to the RL problem to address the exploration-exploitation tradeoff. The result is a convex regularised optimisation problem in the state occupancy of the policy. In addition, the authors propose an algorithm to solve this problem that is based on the Frank-Wolfe algorithm, similar to Hazan et al. i.e., they iteratively find a policy that has a state occupancy with maximal correlation with the negative gradient of the objective. Experiments are performed in several domains and include a comparison with various baselines from the reward free literature. 
main_review: The problem of balancing exploration and exploitation with function approximation is perhaps one of the most important problems in current DRL research. The authors propose to tackle the problem by introducing a convex regulariser on the state occupancy that will encourage the policy to visit states that were unvisited by previous policies. 

However, this construction has two fundamental flaws. The first one is that there are no guarantees that adding a convex regulariser indeed balances the exploration-exploitation tradeoff in an efficient manner. This statement is true in general, so far, no paper in the literature of reward free exploration have claimed to balance exploration and exploitation efficiently. Instead, adding a convex regulariser results in a different problem, that perhaps covers the state space better but does not lead, for example, for an efficient regret algorithm for the RL problem unless it is combined with a proper exploration method. The second issue is that in order to solve the convex regularised problem efficiently, in terms of regret, efficient exploration must be used, on top of the intrinsic reward. These two comments stress that the motivation abstract and intro of the paper are misleading. That said, the proposed algorithm and the convex regulariser are interesting contributions by themselves, taking ideas from the reward free literature as regularisers to the RL setup, and I will continue the review addressing them as a separate problem. 

Baselines and related work. The proposed algorithm solves an MDP with an objective that is convex in the state occupancy of the agent, and specifically, a Frank-Wolfe algorithm. That said, I feel that the paper fails to cite relevant papers on the topic. The one paper that is cited (from Hazan et al.) is not compared to empirically, while being the most similar. That said, the baselines that were implemented and compared to are strong baselines and the comparison is done well, I enjoyed reading the experimental section and I feel that if the paper was focused on it, I might have given it a higher score. I believe that further discussion on how to think of these baselines in the lens of convex regularised MDPs would make their introduction better, i.e., do they solve the same problem? I included several papers on Franke Wolfe, FW algorithms in RL and convex regularised MDPs at the end of this review. 

Regarding Theorem 1. I feel that the way the theorem was introduced in the main paper is highly misleading. The Theorem states a linear convergence rate for a FW algorithm with an approximate best response which is not a common result. For that reason I checked the supplementary which adds 4 assumptions on the function f in order for this result to hold, with assumption 4 being non trivial in my opinion. The assumption states that there exists a constant that bounds the iteration error of the FW method and the final sample complexity is given in terms of this constant. On the other hand, the authors state that the constants only depend on the MDP parameters. More broadly, the analysis of FW methods with approximate best response is summarised in "Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimisation", which shows that when an approximate best response is used (the planning oracle that finds the optimal policy in this case) the convergence of FW has a slower rate. The linear convergence in the non approximate case is discussed in "On the Global Linear Convergence of Frank-Wolfe Optimisation Variants" (with MDPs being a special case where d_\pi is in a polytope), but there is not a general result that shows a linear rate with an approximate best response to the best of my knowledge. Furthermore, the linear rate is typically shown for a strongly convex function, which was not assumed by the authors. If the authors can convince me that assumption number 4 is not "stating the linear rate" by construction or will show me some evidence that a similar assumption was used in FW analysis elsewhere, I will consider changing my score. In particular, I would like to see how $\delta_k, \zeta$ and $\tau$ can be expressed as a function of the MDP parameters, without $k$, and without making the strong convexity assumption. 

Question: both the \pi_\mix and \rho_cover are mixed policies that weight the previous policies seen by the agent. Therefore, it is not clear what role does the different weights play. Can you elaborate on this? 
 
[1] "Apprenticeship Learning via Inverse Reinforcement Learning"
The first FW algorithm https://ai.stanford.edu/~ang/papers/icml04-apprentice.pdf (see the supplementary)
[2] "Apprenticeship Learning via Frank-Wolfe" on linear convergence for FW in RL https://arxiv.org/pdf/1911.01679.pdf
[3] "Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization" FW with approximate best response http://proceedings.mlr.press/v28/jaggi13-supp.pdf
[4] "On the Global Linear Convergence of Frank-Wolfe Optimization Variants" https://arxiv.org/pdf/1511.05932.pdf
[5] "Online Apprenticeship Learning" on why exploration is still needed in the convex regularised problem https://arxiv.org/pdf/2102.06924.pdf 
3 papers on solutions to the convex regularised problem: 
[6] "Concave Utility Reinforcement Learning: the Mean-field Game viewpoint "https://arxiv.org/pdf/2106.03787.pdf"
[7] "Reward is enough for convex MDPs" https://arxiv.org/pdf/2106.00661.pdf
[8] "Variational Policy Gradient Method for Reinforcement Learning with General Utilities" https://arxiv.org/pdf/2007.02151.pdf
limitations_and_societal_impact: Not relevant.
review_title: null

Meta-review: The initial reviews were overall positive (and raised concerns well addressed in the rebuttal), except for one review that raised concerns about the proof of the provided theoretical result. This led to an engaged discussion between the authors and the reviewers, that clarified many aspects of the proof and of the approach. Some questions remained about the interpretation of some quantities ($\rho_{cover}$, which is part of the iteration-dependent regularizer, and $d^{\pi_{mix}}$, the iterate computed by the algorithm). Maybe that making a parallel with mirror descent could help clarify this aspect (for the idea of regularizing wrt the last iterates, even though $\rho_{cover}$ is not the last iterate due to different weighting of the involved occupancy measures, and even though the regularizer is not a Bregman divergence).

Overall, I do think that this helpful discussion addressed sufficiently the initial concerns, and that the theoretical result is technically correct. Beside, this is not the sole contribution of this paper, it also provides a strong empirical analysis, where the approach compares favourably to strong baselines. 

To sum up, I think this paper would be a solid addition to the neurips program, and I recommend its acceptance.

I strongly encourage the authors to revise their paper taking into account the discussion with reviewer dMyV as well as other reviews (notably, it is more than Frank-Wolfe, but less general), I think it will widen the audience and increase the impact of this contribution.
Decision: Accept (Poster)