Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a new operator for exploration in reinforcement learning. The new operator, named resmax, is shown to be a non-expansion, therefore ensuring convergence in learning and planning. Resmax is also competitive in practice on a set of benchmarks tested.
main_review: There is always a trade-off in reinforcement learning between taking actions that are estimated to be high-rewarding, and trying the less rewarding actions to learn if better options are available. A standard technique to addressing this trade-off in large-scale reinforcement learning is to use operators/functions that assign high probability to the best action, but also put some non-zero probability behind the less rewarding ones. While this approach is generally not provably sample efficient, it is often easy to apply and very competitive. Examples include epsilon-greedy, Boltzmann, and mellowmax.

I find it useful to make a distinction between the operator used in value-function optimization (such as softmax), and the policy used for decision making (such as soft argmax). The current draft sometimes recognizes the distinction, but sometimes conflates the two by generically referring to both as operators.

On this very note, it is not that mellowmax "requires" solving for a root finding algorithm. If the objective is to have an on-policy algorithm, i.e one that uses the same form in value-function optimization and decision making, the way to obtain that is by solving the root-finding algorithms. In fact, previous work has shown the impact of using Boltzmann/mellowmax just for value function optimization and not in decision making (See Song and others "Revisiting the softmax bellman operator: New benefits and new perspective"). So parts of the paper need revision to clearly state this point. 

In the background section, stating that q* is the value for "the" soft optimal policy is incorrect. There may generally be multiple optimal policies, though they all yield "the" same q*. 

Going to the main contribution, namely resmax, it is interesting to note that the behavior of resmax can be qualitatively different than epsilon greedy when more than one greedy actions co-exist. In particular, epsilon greedy will deterministically chose an action (assuming we are breaking ties non-randomly) but resmax would yield equiprobable policy. On this note, I was wondering if authors have any thoughts about generalizing this to the continuous control setting where the notion of action gap may be difficult/impossible to compute. 

The paper alleges that softmax overemphasizes good actions, and it is desirable to reduce this overemphasis. While this is intuitively plausible, overemphasis does not sound like an objective thing to me. Why is the amount of emphasis put by resmax the right one? why not to emphasize the gap even less than resmax does? Is the least emphasizing operator, namely uniformly at random, the best choice? well clearly not, so what’s the right strategy if one exists at all? More about this on my note about the proof of the non-expansion.

Property 4.1 seems too trivial to me to warrant being in the main text.

I checked the proof of Property 5.1 and it is correct. That said, i feel like the proof could have been generalized with some moderate work. In particular, right now probabilities are proportional to 1/delta where delta could be the gap. But in general this could have been 1/f(delta) where f is any positive and non-decreasing function. In that sense one does not have to commit to the current (identity) f but in general can have square root, quadratic, or even exponential f. I believe it is possible to generalize the proof to arbitrary f, which in turn also addresses my concern about the arbitrary amount of emphasis obtained by using f=identity. 

The paper provides experimental results on 3 toy domains as well as 3 Atari domains. On the toy domains, I see two odd choices: 1- the mountain car task has been altered. I generally prefer not to see any modification to standard benchmarks as this makes it impossible to cross-check performance with other existing results 2- there is a strange focus on the size of the replay buffer and the robustness of different algorithms with respect to it. I can't see why this is interesting to study/relevant to the thesis of the paper.

Finally, for Atari tasks, it is unclear to me why these three domains are chosen. It would have been meaningful to only choose domains that are hard for exploration. To be fair, Freeway is one such domain, but it also lends itself to the shockingly simple policy of always moving up.


summary_of_the_review: Overall, it is useful to have an additional operator/policy that is somewhat similar to softmax but with its own strengths and weaknesses. The form of the operator is a little ad hoc and too specific, but all things considered I lean towards acceptance here.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a new soft operator, resmax, for mapping Q-values to action probabilities. This operator is designed to replace softmax in Boltzmann-style policies while having the non-expansion property which enables the convergence of Q learning.  The paper provides theory demonstrating the coverage and non-expansion properties of resmax, as well as somewhat more heuristic evidence that resmax enables more exploration than softmax.
main_review: **Strengths**
* The proposed method is simple and widely applicable. Boltzmann policies are commonly used and improvements to their learning would affect many  This method has only one hyperparameter and requires no extra compute.
* The proposed operator has nice mathematical properties and seems well-behaved (unlike softmax).
* The paper brings its theory all the way through to deep learning experiments.
* The writing is mostly very clear.

**Weaknesses**
* The various hyperparameter comparisons between different methods are somewhat confusing, and I worry that they could be misleading. For example, in Figure 3 the hyperparameters for softmax, resmax, and $\varepsilon$-greedy are put on the same axis. It's hard to draw conclusions from this, given that e.g. $\varepsilon$ lives on a different scale than $\tau$, and $\tau$ and $\eta$ are not obviously comparable either. The results in the bar charts in Figure 5 will also depend strongly on the authors' choices for hyperparameters corresponding to varying amounts of exploration for each method.
* The title of Section 6.1 claims that resmax leads to more exploration than softmax, but I don't see any direct evidence for this. On some environments resmax leads to better performance, and it seems potentially less sensitive to its hyperparameter (although maybe the hyperparameters just live on different scales), but there is no clear empirical analysis of the amount of exploration, e.g. state coverage.
* The crucial question for a method like this is whether or not it makes a difference overall when used more widely. It would make the case a lot stronger to have a broader set of experiments with deep learning, though I understand computational resources might be a limiting factor.
* The work could use more analysis (theory or experiment) of convergence properties, along the lines of the "softmax gravity well" paper.

summary_of_the_review: The new resmax operator proposed in this work seems interesting and could be a more robust choice for Boltzmann-type policies. The paper contains straightforward reasoning supporting its candidacy, but falls short in really proving the claims that resmax outperforms softmax in terms of (1) exploration, (2) convergence to the optimal policy, and (3) deep learning practice. Nonetheless the method seems interesting and worth trying more widely.


### After responses

After reading the other reviews and considering the authors' responses I am leaning towards rejecting this paper. The results are potentially interesting but not compelling, and I do not find that the analysis in this work significantly illuminates the problem otherwise.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes an alternative greedy operator for RL which selects actions proportional to the optimality gap of value functions.  The claim is that it can explore better compared to an epsilon greedy approachand has similar benefits to a softmax operator. The main advantage of the proposed operator is that the probabiliteisof the actions do not converge too quickly, as in softmax operators. 

main_review: Strengths : 
	- The resmax operator achieves best of both worlds - an epislon greedy like operator and the softmax operator, which takes into account the optimality gap of value functions. 
	- Figure 1 demonstrates the usefulness of the resmax operator on a simple MDP. It clearly shows how the resmax and mellowmax operator are considerably better than the softmax operator. 
	- The experiments in the paper demonstrates the usefulness of the proposed operator.



Weakness : 
	- The paper does not address very recent works that addresses convergence and optimization issues of the softmax operator. The usual drawbacks of the softmax operator, as discussed in the paper, are known but does not provide new insights to existing literature. 
	- It is not clear to me how this operator influences or addresses the optimization issues (as mentioned in the related works below). During the early training stages, the optimality gap is rather poor (and in practice we do not have a good approximation to the optimality gap either). How does the approach take account of this? Considering the optimality gap between poor estimates of the value function can lead to sub-optimal convergence?
	- The paper claims "that the resmax operator is guaranteed to provide sufficient exploration" - I think simply justifying this based on visitation counts on simple problems is not enough. It is not clear to me how this operator balances trade-off between the exploration and optimization issues, even in simple RL problems. 
	- The proposed operator is not theoretically justified. Proposition 5.1, even though is a good example - it is not clear to me why one should use the resmax operator in practice - since it seems that the claim is to propose an alternative to the softmax operator? It would have been helpful if the authors could at least comment on the convergence and optimality issues with the resmax operator, in a simple policy gradient setting? The softmax operator is often popular for PG learning - and recent works have established convergence rates to the global optima for softmax policies too. How does the resmax operator compare in contrast to the existing works supporting benefits and drawbacks of the softmax operator?
	- Experiments do not well justify why the proposed resmax operator may be helpful. It seems that there are several tasks where the beneftis are presented, but given existing works discussing issues with softmax, I am not surprised by the experimental results





Other comments : 
	- The paper claims that the proposed resmax operator has better properties unlike softmax or epsilon greedy operators.  There are few lines of work similar in motivation, addressing issues of the softmax operator,  "Escaping the Gravitational Pull of Softmax" (Mei et al) and "Softmax Deep Double Deterministic PGs" (Pan et al) which addresses issues based on early sub-optimal convergence of the softmax operator. 
	-  Can the authors discuss about the optimization issues, similar to Mei et al., for the proposed resmax operator? On those simple counter-examples, how does the resmax operator perform, and does it avoid the local optimas?
	- Perhaps not entire related : The RL literature often uses entropy regularization with softmax policies - and we know several benefits of the entropy regularizer (in terms of optimization landscapes, faster convergence rate etc). It seems to me that with the proposed resmax operator, which depends on value functions - the entropy regularization would not have the same effect? Can the authors comment on the use of entropy regularizers with resmax operator based action selection?

summary_of_the_review: I do not think this paper has enough novelty for acceptance. The proposed operator is indeed novel, but I can see several drawbacks of the operator, mainly since it can depend on very poorly estiamted value functions. Morever, the paper claims to provide an alternative to the softmax operator - there are quite some related works discusisng issues with softmax, and proposes alternative operators which can help with faster convergence, or solving the counter-examples of PG divergence with softmax policies. The softmax operator is well used in the policy gradient literature - and it is surprising that the paper completely ignores any issues or discusses anything about the effectiveness of the resmax operator in PG learning context. 


The lack of discussions to related works (both theoretical and empirical) is a major red flag for me, since I do not know how reliable this resmax operator can be. Empirical experiments are not enough - and by that I do not mean large empirical studies showing effectinvess of resmax; but there are several counter-examples that exists in the literature (e.g from Mei et al) that discusses issues of the softmax operator. It would have been helpful to see why the resmax operator can be considered as an alternative to softmax (e.g like the Escort Transform proposed by Mei et al) in the context of those experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The most commonly used exploration policies for SARSA/Q-learning are epsilon-greedy and softmax sampling.
The problem with epsilon-greedy is that it explores obliviously the action space which may slow-down convergence of the Q function estimate, especially when the environment requires long sequences of actions to reach high rewards. On the other hand softmax provides a more informed exploration strategy, but as pointed out in [Assadi & Littman 2017] it is not a non-expansive operator and it is hence not guaranteed to converge toward a unique Bellman fixed-point.
This article propose a novel exploration policy called ResMax. The authors first show that ResMax is sufficiently exploring by exhibiting a simple lower bound on action selection probability (Property 4.1). They then show that the corresponding soft-greedy operator is non-expansive by bounding its gradient (Property 5.1).
Some experiments are then provided both with tabular and fitted Q function estimates. These experiments show empirically that ResMax is 
outperforming both epsilon-greedy and softmax on small (but misleading) MDPs and Atari environments.
The most direct concurrent exploration policy: mellowmax proposed by [Assadi Littman 2017] is a variant of softmax where the temperature is adapted at each step. It is non-expensive but it requires to solve a linear root-finding problem a each step.
According to the authors this overhead was too costly to integrate mellowmax to their benchmarks. On the contrary, the ResMax policy is simple and quick to compute.

main_review: Strengths:
- The article is clear and easy to follow.
- The proposed policy is simple and fast to compute. Much simpler and faster than mellowmax.
- It may improve some RL algorithms.
- The proofs of (Property 4.1) and (Property 5.1) are simple and correct.
- The results are reproducible. I managed to run (partially) the experiment code provided as supplementary material.

Weaknesses:
- To my opinion the authors should integrate mellowmax policy, at least in a degraded form, to their tabular benchmarks (not only on HardSquare). The scipy implementation of the brentq algorithm could be accelerated by relaxing the default bounds and the  "xtol" and "rtol" parameters.
- Another solution is to learn the softmax temperature as in [Kim Konidaris 2019]. Did you try this as well ?
- For these reasons I am still wondering if the proposed method is a clear improvement against mellowmax and its tuned-softmax variants.


Doubts/Questions:
- I did not really catch the overemphasis argument on Figure 1a. According to the curves, a high-temperature softmax can place lower probability on a1 than a low-pressure/temperature resmax.
- The presented results and the lower-bound/gradient-bound proof machinery is straightforward and generic. It seems possible to generalize your results on a wider family of soft-greedy operators. What about a softmax where another convex function is used instead of exponential ? What about an ordinal "mean-of-top-k" operator ?

Minor remarks:
p2l-1 more greedy -> greedier
p3l26 b = \arg\max -> b \in \arg\max (or the uniqueness assumption should be set on the table)
p3l-7 "with results in a small environment" : ?? unclear to me
p5 Prop 4.1 give the softmax lower bound as well
p5 Prop 5.1 "temperature" or "pressure" as on page 3 ?
p6 proof : getting rid of the p and q on equation (7) and follow-up could save a few precious lines for your reproducibility statement
p6l-5 "show resmax" -> "show that resmax"
p7 Figure 3 "Stochastic RiverSwim" -> "Stochastic-reward RiverSwim" (it's only clarified in appendix)

summary_of_the_review: A novel non-expansive and simple exploration policy called ResMax.
I read this simple and direct paper with pleasure and it wakened a few questions in my head. This is a reason for me to support the paper.
On the other hand, due to the lack of experiments comparisons, I am still wondering if the proposed method is a clear improvement against mellowmax and the host of tuned-softmax variants that come to mind.
review_title: null

Meta-review: This paper proposes a new softmax like operator, to be used instead of eps-greedy or softmax in Q learning algorithms. There has been some previous work in this direction, most notably Mellowmax, but the proposed operator is more computationally efficient, and there is some experimental evidence that it improves DQN performance.
The reviews were mixed, with two mildly positive reviewers (6), who found the work interesting, and two negative reviewers (3,5), who raised issues about the impact of the work when taken as a part of a larger RL algorithm, and about the generality of the work w.r.t. to other RL algorithms like policy gradients. During the discussion, the reviewers did not reach an agreement.
My decision to reject the paper is based on the following: while the idea is novel, and the contraction analysis is appropriate, the main interest to the community in such an idea is either experimental - can it be used to push the state of the art RL algorithms? or theoretical - can we glean new theoretical insights using this method? In its current presentation, there is not enough evidence in the paper to support either of these. 
I encourage the authors to either dig deeper into the experimental evaluation and produce more convincing results, or dig deeper into the theory and show some theoretical benefit of Resmax.
Decision: Reject