Resmax: An Alternative Soft-Greedy Operator for Reinforcement Learning
Authors: Erfan Miahi
Revan MacQueen
Alex Ayoub
Abbas Masoumzadeh
Martha White
Venue: ICLR 2022 Submitted (2022)
Keywords: exploration
reinforcement learning
action-value methods
soft-greedy operator
softmax
mellowmax
epsilon-greedy
suboptimality gap

Abstract: Soft-greedy operators, namely $\varepsilon$-greedy and softmax, remain a common choice to induce a basic level of exploration for action-value methods in reinforcement learning. These operators, however, have a few critical limitations. In this work, we investigate a simple soft-greedy operator, which we call resmax, that takes actions proportionally to their suboptimality gap: the residual to the estimated maximal value. It is simple to use and ensures coverage of the state-space like $\varepsilon$-greedy, but focuses exploration more on potentially promising actions like softmax. Further, it does not concentrate probability as quickly as softmax, and so better avoids overemphasizing sub-optimal actions that appear high-valued during learning. Additionally, we prove it is a non-expansion for any fixed exploration hyperparameter, unlike the softmax policy which requires a state-action specific temperature to obtain a non-expansion (called mellowmax). We empirically validate that resmax is comparable to or outperforms $\varepsilon$-greedy and softmax across a variety of environments in tabular and deep RL.

Under review as a conference paper at ICLR 2022
RESMAX: AN ALTERNATIVE SOFT-GREEDY OPERATOR FOR REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Soft-greed, operators, namely e-greedy and softmax, remain a common choice to induce a basic level of exploration for action-value methods in reinforcement learning. These operators, however, have few critical limitations, In this work, we investigate a simple soft-greedy operator, which we call resmax, that takes actions proportionally to their suboptimality gap: the residual to the estimated maximal value. It is simple to use and ensures coverage of the state-space like e-greedy, but focuses exploration more on potentially promising actions like soft- max. Further, it does not concentrate probability as quickly as softmax, and so better avoids overemphasizing sub-optimal actions that appear high-valued during learning. Additionally, we prove it is non-expansion for any fixed exploration hyperparameter, unlike the softmax policy which requires state-action specific temperature to obtain a non-expansion (called mellowmax). We empirically vali- date that resmax comparable or outperforms s-greedy and softmax across a variety of environments in tabular and deep RL.
INTRODUCTION
Every online decision-making problem involves the exploration-exploitaiii dilemma: to choose between taking actions that seem best in the short term and alternatives that can provide potentially valuable information about action selection for the long run. The trade-off between exploration and exploitation has been well studied in reinforcement learning (RL). The literature on exploration is vast, particularly in the field of RI. theory. Many methods with important theoretical insights are not easy to use or are not efficient (Jaksch et al. 2010 Wang et al. 2020). More recent exploration methods developed for deep RL are more practical to use, such as those that use reward bonuses and counts (Bellemare et al. 2016 Taiga et al. 2020 Pathak et al. 2017). These developments, however, yet quite new and several studies have highlighted inconsistent performance and difficulties tuning hyperparameters (Taiga et al. 2020 Yasui et al. 2019).
Due to this, most work continues use basic form of exploration: soft greedy operators, such as softmax (Luce 1959) and E-greedy (Watkins) 1989). These operators actually play two roles: for soft-greedification within the Bellman update when bootstrapping off values in the next state (target policy) and to encourage some amount of exploration (in the behavior policy). Soft-greedification within the Bellman update facilitates learning stochastic soft-optimal policy and can help mitigate the overestimate bias in Q-learning (Song et al. 2019). This changes the target policy being learned. For the second role, regardless of whether Q-learning update is used or a soft-greedy update, the soft-greeds operator can be used to take actions. Such an approach is actually complementary to directed exploration approaches, like those that learn optimistic values, because can provide small amount of additional exploration and so robustness to estimation enror in the optimistic values. And for some environments, where only a small amount of exploration is needed, these soft-greedy operators for the behavior actually provide a sufficient level of exploration.
In this work, we re-examine the utility of these operators for exploration, and propose an operator that is more suitable for both roles. In particular, we overcome a few limitations of e-greedy and softmax. e-greedy explores in a completely undirected way. Regardless of the agent's 's estimates of the value of action, the agent's 's exploration step is uniformly random. Softmax- Boltzmann policy on the action action-values. is more directed, in that it samples corresponding to the value of the actions. However, softmax is notoriously difficult to tune and suffers from concentrating too quickly

---

Under review as a conference paper at ICLR 2022
due to the use of an exponential. This concentration overemphasizes actions that appear high- valued under current estimates but are actually suboptimal. This overemphasis can cause softmax to settle reaffirm in our experiments. Further, softmax is not sound when used
on suboptimal policy, within the Bellman update: it does not guarantee that the Bellman update is a non-expansion, and so divergence occur under Sarsa dynamic programming updates.
There have been some works attempting to improve on these soft-greedy operators. Several works have focused on solving the fact that softmax is not guaranteed to be non-expansion (Asadi & Littman 2017 Cesa-Bianchi et al. 2017; Pan et al.). One of these works proposes a soft-greedy operator called mellowmax (Asadi & Littman 2017) that is guaranteed to be non-expansion when is used for soft- seft-greedification. It also effectively tunes the softmax's 's exploration parameter per state and has been shown to improve stability when it is used for exploration (Kim et al., 2019). However, mellowmax is not a simple heuristic to use, as it requires solving a root finding problem to compute the policy for decision making. To solve this problem they used Brent's method, which is computationally complex (Wilkins & Gu 2013). An approach called value-differeece exploration (Tokic) 2010 Tokic
Palm 2011) adapts the exploration parameter e and the temperature for softmax over time, using the difference in the softmax of the values before and after learning. A later empirical study, however, highlighted that this approach does not perform consistently (Gimelfarb et al., 2020).
soft- soft-greedy operator, which call resmax, based on a probability matching scheme originally developed in the contextual bandit setting (Abe & Long 1999. Foster & Rakhlin 2020). This technique is similar softmax in the sense that it assigns distinct probabilities to actions based on the estimated action-values. However, unlike softmax, the probability for taking each action is determined using its suboptimality gap: the difference between the approximated value of the greedy action and the given action. The policy is inversely proportional this suboptimality gap, and avoids the use of the exponential that causes softmax to overemphasize actions. We show that it ensures a minimal probability on each action, regardless of the action-values, ensuring all actions are explored. We show that it is a non-expansion, and so combines well with generalized value iteration algorithms. We conclude with an empirical study, across a variety of hard and easy exploration problems, with tabular and deep function approximation. We find that resmax outperforms softmax and s-greedy, especially when softmax suffers from overestimation.
Instead of improving these existing operators, consider
2 BACKGROUND
We model the environment as a discounted Markov Decision Process (MDP) (S. R, P.7) where the set of states; A the set of actions; the set of possible rewards; 7 E [0. 1] the discount factor; and P S x R x S x A + j0, 1] the dynamics function. In a given state the agent takes action and transitions to state s' and receives reward according to probability p(s', r|s, a).
The agent's goal is to learns policy æ S x A + [0, 1] that maximizes its discounted cumulative reward. To action-value for a state and action, under the policy is
On (x a) = E
Σ k R A.
The agent attempts to estimate fr", the action value function for the optimal policy x². Many RL algorithms compute these estimates iteratively, using either Q-learning or Expected Sarsa. Both methods use and update to the parameter vector of the form
0+11 + 0₂ + ad, Vq(s, a, 0.)
but with different TD errors &, Q-learning uses 6, = + yaax g(s 00) ((s, a, 0,). Expected Sarsa uses 6, + ( a' 0,) - as)
To learn these action-values, the agent needs to explore. Two simple exploration methods based on action-value estimates are Boltzmann softmax policy and e-greedy, defined
Tyoltmax (a () Σ 1
Te-greddy (a ())
8
[A(T]]
if = argmax, a)
otherwise
[A(T
E'EA
2

---

Under review as a conference paper at ICLR 2022
with exploration parameter T >> 0 and [0, 1]. With lower values of т, softmax is greedier; with higher values т, softmax action selection becomes more equiprobable. Resmax and softmax share two essential characteristics: randomness in action selection to guarantee the coverage of the whole state space and a hyperparameter to vary the degree to which the greedy action is chosen.
3 THE RESMAX OPERATOR
Softmax and e-greedy remain two of the most practiced soft-greedy operators for value-based RL algorithms. However, they suffer from several flaws. One of the major problems of E-greedy is that it ignores the estimates of retion-valuess and assigns uniform probability to each non non-greedy action. This undirected exploration results in wasting time taking actions that the agent might already know are suboptimal. Further, to explore specific parts of the environment, might need to chain sequence of random actions, which might be very low probability. For instance, consider the RiverSwim environment (Strchl & Littman 2008) where an agent receives a minor positive reward it takes the left action in the initial state, but a much larger reward at the far right of the environment that is harder to reach. To receive this high reward, the agent might need to take several exploratory actions in row, and so typically gets stuck learning go left.
Softmax is more directed, in that it assigns the probability of each action corresponding to its action-value. However, if the temperature is not set carefully, softmax will assign an excessively disproportionate probability to the greedy action because this probability is based on exponential q- values. Consequently, softmax often overemphasizes actions that currently have high value estimates, at the expense of exploring other actions. Furthermore, when using the Boltzmann softmax operator in the Expected Sarsa update, for the expectation of the value in the next state, this operation is not guaranteed to be non-exxansion (Littman 1996 Littman & Szepesvári 1996). As mentioned earlier, mellowmax operator was designed to fix this son-expansion issue (Asadi Littman 2017). but mellowmax policy is not as straightforward to use as softmax policy because an optimization problem needs to be solved to select the temperature in each state.
Our goal is to gain the best of both worlds: using the information provided by action values without suffering from the two issues with softmax. For this purpose, we propose resmax. For greedy action b = arg max, q(8, a) and non-greedy action the resmax policy probability is
(a 8)
1 A + 11+ (g(s, (s)
T(b | =1 Σ T(a
where the exploration parameter 7) > 0 can be thought of as the exploration pressure. Large values push towards exploration whereas low values result in more exploitation- are greedier. When + 2o the policy is uniformly random and when 1) + 0 the policy is greedy with respect to ((s,b).
This operator efficient to compute and easy to use for exploration or soft-greedification.. To with Q-learning or DQN, the agent simply samples actions from the resmax policy in Equation 2 To use for greedification, we can simply use the corresponding resmax operator
rm(g(s, )).)) = Σ T(a' s)q(s,a')
(3)
a'EA
in Sarsa or Expected Sarsa. Note that as goes to infinity, this operator becomes the max operator (please refer Section A.2 in the appendix for details).
4 RESMAX AVOIDS OVEREMPHASIS AND ENCOURAGES EXPLORATION
In this section, we first confirm that resmax is guaranteed to provide sufficient exploration to get satisfactory convergence properties for certain families of RL algorithms. The resmax policy can either be used off-policy, on top of action-values learned with Q-learning, on-policy. In either case, it is key to ensure we have sufficient exploration. Note that this first role is separate from the second role of the resmax operator, which is to ensure have non-expansion within the Bellman update; we discuss this property in Section Then, we show that resmax avoids overemphasis by conducting experiments in a small environment.
3

---

Under review as a conference paper at ICLR 2022
Exploration strategies should satisfy certain fundamental properties to make that algorithms such as Q-learning and Sarsa converge to the optimal value (Singh et al. 2000; Watkins Dayan (192). A key property is that each state-action pair should be visited infinitely many times during continual learning. To show that resmax satisfies this property, we prove that the probability of taking all of the actions will be higher than zero during learning for any bounded action-values (please refer to Section A. in the appendix for the proof).
10
10
1.0
#2
1e9
0.8
1.75
softmax
1
Return
1.50
resmax
0.6
mellowmax
1.25
0.0
2.5
5.0
7.5
10.0
((a))
-(a2)
1.00
0.125
0.5
2
8
2
2
softmax
resmax
2 x
x 10
T, Q)
(a) Overemphasis
(b) HardSquare MDP
(c) Average return for Q-learning
Figure I: (a) Visualization of overemphasis in softmax and resmax over a range of parameters. As the suboptimality gap increases, softmax is quicker than resmax to place high probability on action a₁. Values of and 17 are given in the legend. Dotted lines are resmax and solid lines softmax. (b) The HardSquare MDP: simple MDP with four states and three actions and 0.95. The edges show deterministic transitions and rewards given an action. The agent starts in states $1 and $2 with equal probability. (c) Performance of resmax, mellowmax and softmax on HardSquare. The x-axis is the hyper-parameter choices for each operator. The y-axis is the average return over the total time steps. Softmax will get stuck in states 81 and 82, whereas resmax can escape from the initial states and successfully explore towards higher value states. Results are shown for T, 17 E (2 20 2- ,..,, 2d) U (1/0.1, 1/0.2..... 1/0.9].
A serious issue with using the softmax for exploration comes from the fact that it uses exponents within its formulation, which can assign an overly disproportionate probability to current estimate of the optimal action. We call this phenomenon overemphasis, which can cause basued exploration using softmax to get stuck in local minima. This effect analogous to the softmux gravity well described by Mei et al. (2020) in the context of policy gradient methods.
To illustrate, consider a bandit problem with two actions, aj and 02- Suppose that a2 is the optimal action, but due to stochasticity in the learning process, the estimate ((a1) > q(az). We visualize the resultant softmax policy Taa)) over a range of for softmax and 1 for resmax in Figure la Here set (aa))) E [-5,3], and (az)) 55 In most choices of the temperature т, if ((aa) is sufficiently larger than (a2). the outputs of softmax π T(a1) will be near 1. Thus, may take a very large number of steps to finally choose action d2 and explore another action. If instead the policy is chosen according to resmax, the probability assigned to the greedy action is proportionate to the suboptimality gap and therefore less extreme. Consequently exploration of ag becomes more likely.
The severity of the softmax overemphasis problem is further demonstrated in the HardSquare MDP (Figure [b). The agent starts in the state 5i and 82 with an equal probability and all actions are deterministic. The agent can stay in the start states for reward of 10a, or move to and 84- which gives a short term reward of -1, but in these states the agent can receive a larger reward of 2 x 10ah We use tabular Q-learning with either resmax or softmax as the exploration heuristic on this problem. We initialize @(s, +- O, v(s,a) S x A. Results are averaged over 30 runs. As shown in Figure Ic the softmax policy gets stuck the initial states s and 82 due to its tendency to overemphasize the approximated optimal action. On the contrary, resmax can escape from the initial states and successfully explore towards the optimal solution. We include mellowmax in our results for hardsquare and note that it performs similarly to resmax. However, due to the optimization procedure inherent mellowmax, its runtime is on average 23x longer than resmax. This prohibitively expensive runtime prevented us from further considering mellowmax in our results.
4

---

Under review as a conference paper at ICLR 2022
5 RESMAX IS NON-EXPANSION
The second key property of resmax is that it is non-expansion. The non-expansion property ensures that Generalized Value Iteration (GVI) algorithms, such as value iteration, will converge unique fixed point (Littman & Szepesvári 1996. Asadi & Littman| 2017). Without the non-expansion property- is the case for the softmax operator- an operator may converge to multiple fixed points, even in the tabular setting, which in turn leads to misbehaviors in both learning and planning.
Figure 2a shows simple two state MDP (taken from Asadi & Littman (017)) where the action values of softmax may not converge, as shown in (2b Resmax, since it is a non non-expansion, converges for all settings of 7). We show Figure 2c that resmax indeed converges under a setting of rj that provides similar exploration to softmax.
2.0
O6sy a)
2.0
((s a) ((s,, b)
Q(s b)
1.5
Action vilonvallle bie
1.5
(a, 0.66, 0.122)
Action
(a, 0.34, 0.122)
1.0
$2
0.5-
0.5-
(6, 0.010, 0.033)
0.0
(b, 0.99. 0.033)
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Iteration
1c7
Iteration
1e7
Simple state MDP
(b) softmax
resmax
Figure 2: The non-expansion property is important for converges under GVI. On the MDP shown in (a) the action-values, if using softmax in the expected sarsa update (with 1/16.55), do not converge (b). We can see that resmax does converge in (c) with 7) = 0.000085. We use a step size time to be 1/(LL/ 100, 000 1). which meets the usual conditions for stochastic approximation to converge (Sutton & Barto 2018). Note that the tuples in (a) are of the form (action, probability of transition given action, reward). Results are smoothed with window size of 10, as Asadi & Littman (017).
We now show that the resmax operator is indeed non-expansion. Property 5.1. The resmax operator is non-expansion, i.e., for any two vectors F. E Rd and exploration pressure we have,
|mm(T, 7) rm n)1 < max [x;
Mi
(4)
sE(d]
Proof. The resmax operator defined as follows
m
Σ
1 -
Σ VEld),i4)
1
d (x. 33)
d
(xr, - xz)
Se (E(d),+1
77
3j Dj
Izj
(5)
d (2; - xz)
iE(d)ii3
where j = arg max, To show that resmax is non-expansion, we need special instance of Theorem of Paulavičius & Zilinskas (006) which states the following. For Lipschitz function f(x). f: Rdd R.
If(x) f(w) < L1 ylloo
(6)
where J, = sup { x E D} is the Lipschitz. constant, D) is a compact set, and Vf(xx)
(0f/Oz1.-) , Of /dra) is the gradient of the function f(x). Therefore, need show that the E
norm of the gradient resmax less than or equal to 1, namely L S 1. To compute the gradient of
mm,, for o j. let 8; Iÿ 24 get
drj
mm L. n)
Ox:
(dn + 6,)²
5

---

Under review as a conference paper at ICLR 2022
We now compute 0rm(ī, ( n)) /0z
drp
nm [ 11)
dzy
(dn + 6.)2
se|d,
Notice now that
drp² (dy + 6.)2
d1j²
drj²
1
d2122 + 2dno; + 8
dnp d'
where the inequality holds because all the terms in the denominator are positive. Therefore, we know that the partial derivative for j is positive. Further,the partial derivatives for * j are also positive, so taking the & norm corresponds to simply summing up those terms
dn (dn + 8,)2
dnj
+
(di + 6:)2
KE id)
Since this is true for any म we know that L1 = 1, and so resmax is a nonexpansion.
This result also lets show that the sequence of policies generated by approximate policy iteration under the resmax operator converges to a unique limiting policy regardless of the choice of the initial policy mo. This follows from Theorem Perkins & Precup 2002), which simply requires that the operator be Lipschitz continuous with an e-solt policy. Policy ा is e-soft if (aass) (s) > As shown in Section A.I the resmax policy is e-soft. By the non-expansion property of resmax, we can also say the resmax operator is Lipschitz continuous (Asadi & Littman 2017).
EXPERIMENTS
In this section, we empirically investigate resmax through series of experiments. We first use tabular hard exploration environment, RiverSwim, show that resmax promotes more exploration than softmax since it does not overemphasize. Next, we show that resmax scales to use with function approximation by benchmarking performance on standard environments. We additionally study the performance of resmax and softmax when varying the replay buffer size of DQN. Details on implementation and computational infrastructure are given in the appendix.
6.1 RESMAX PROMOTES MORE EXPLORATION THAN SOFTMAX
In Section we showed softmax can overemphasize actions that appear high-valued according to its approximate estimates, and so converge to a suboptimal solution. Resmax does not have the same overemphasis issues, and promotes more exploration. environment (Strehl & Littman 2008). RiverSwim consists of 6 states arranged in line, of which the agent starts in the leftmost. This state has a small reward but the rightmost state may give comparatively large reward. In order to reach this state the agent must traverse the MDP from left to right, fighting against a "current" which causes moving right to oftentimes fail. Reaching this rightmost state requires smart exploration. We RiverSwim with fixed horizon, meaning that after 20 actions the agent will be returned to the start state, in effect making the environment more for 800,000 time steps.
illustrate, we use the RiverSwim
difficult. All algorithms

---

Under review as a conference paper at ICLR 2022
1e6
1e6
resmax
Total Return
resmax
Return
1.5
E E-greedy
Prob. Optimal Action
0.9
softmax
1.0
0.8
resmax
0.5
-greedy
0.5
softmax
0.6
softmax
0.0
2
2
0.0
2.9
0.5
10000
20000 Episode
30000
40000
E, r
E
(a)
(b)
(c)
Figure (a) Hyperparameter sensitivity for RiverSwim. (b) Hyperparameter sensitivity for Stochastic- reward RiverSwim. For both (a) and (b) means and standard errors are shown for 30 runs for each parameter setting. The x-axis is plotted with a log scale, and shows the value of exploration parameters. Note that the horizontal sensitivity curve for (c) The probability of selecting the optimal action (right) from the initial state during the first step in the episode in Stochastic-reward RiverSwim. Results are averaged over 100 runs and are for optimal choices of hyperparameters in Stochastic-reward RiverSwim: 1j = 2-5 2- and e 0.1.
Experiments with Misleading Rewards
Misleading rewards are rewards that, when pursued, lead the agent away from potentially higher reward. Following such a signal can be viewed over-eager exploitation; ignoring the misleading signal and exploring further can lead to much higher long-term reward. HardSquare (Figure [bb] is example of an environment with misleading rewards. RiverSwim is also such an example: the reward on the leftmost state distracts the agent from the much higher reward on the right.
We softmax, resmax and e-greedy coupled with Expected Sarsa RiverSwim across broad range of hyperparameters (7, T and c). The hyperparameter ranges were chosen to match the technique, for example softmax requires relatively larger values of 7 due its exponents. Results are shown in Figure 3a| where we measure algorithm performance by the total online return across these hyperparameters. We find that resmax and softmax perform similarly, however resmax achieves higher total return under optimal hyperparameter settings than softmax, indicating it is more capable of escaping the pull of the left state. s-greedy fails to explore all, and its total return is hardly visible for any values of e.
Interaction with Stochasticity in Rewards
Stochasticity in rewards can help alleviate some of the misleading reward problem. Uncertainty in the rewards can prevent over-exploitation of sub-optimal actions and help drive exploration. We replaced the deterministic positive rewards in RiverSwin with rewards drawn from a Gaussian distribution with the mean being the original reward and variance of Results are shown in [bb All three techniques see reduction in hyperparameter sensitivity, but resmax and e-greedy increase their total return under optimal parameter settings, whereas softmax does not. With stochastic rewards, softmax still assigns too great weight sub-optimal actions, shown in Figure 3cl Softmax learns to take the optimal action in the initial state at a slower rate than resmax, indicating that softmax is concentrating too heavily misleading rewards.
6.2 RESMAX WITH FUNCTION APPROXIMATION
Many RL algorithms with function approximation use e-greedy as default method to add exploration. Resmax, in order to be considered a general-purport method, should also scale to this setting. To show this, we conduct experiments in deep RL setting. We first study the stability of directed exploration techniques, resmax, and softmax, across different replay buffer sizes on two standard OpenAl gym environments (Brockman al., 2016), namely Acrobot-v1 and LunarLander-v2 and Sparse MountainCar (Kumaraswamy et al. 2018). Then, we extend our deep RL experiments to eight large-scale Atari environments.
7

---

Under review as a conference paper at ICLR 2022
6.2.1 STABILITY OF RESMAX ACROSS DIFFERENT REPLAY BUFFER SIZES
Here, we study the effect of varying the replay buffer size on the performance of the resmax and softmax operator to compare the performance of these two soft gofty operators that do more directed exploration. For implementing the Sparse MountainCar environment that is commonly used for benchmarking exploration algorithms, we modified the reward system of OpenAl implementation of MountainCar environment by setting the reward in all of the states to 0, except in the states at the top of the hill. We have also increased the maximum number of steps in Sparse MountainCar to 5, 000. All other environments have been used exactly they are implemented in OpenAl gym. We use Deep Expected Sarsa for running our experiments in this section, which is the same as DQN (Mnih) et al. 2015) except that instead of the maximum uses the expected value. We selected this algorithm because it uses resmax operator presented in Equation 3 to compute the targets. So, in this way, can also see how operator performs in the deep RL setting compared to softmax. Exact hyperparameter settings are given in the appendix.
next state cittinaction pairs to compute targets it
The results for these experiments are presented Figure 4 Resmax achieves a better performance than softmax on LunarLander and Sparse MountainCar environments that require a higher level of exploration and performs similar to softmax on Acrobot environment. In terms of stability, whereas softmax is highly unstable in LunarLander environment and performs poorly with the low replay buffer size, resmax is able to maintain good performance with v = 2- across different sizes of the replay buffer. Both operators gain the same stability on Sparse MountainCar and Acrobot environments. We also ran these experiments on larger set of hyperparameters for each operator and included eesilon-greedy The plots for these larger set of experiments are presented it in the Appendix.
Acrobet-v1
1.50 +17
LunarLander-v2
Arcumulbted Steps per Episade
2.5
MeuntainCar-v0
-0.75
Accumulaned fteuums
1,25
-1.00
1.00
1.5
1.0
1150
0.50
-1.75
0.25
05
214
214
2
2
212
22
2
2
2
Reslay Buffer Size
Replay Buffer Size
Replay Buffer Size
Figure 4: Replay buffer size sensitivity plots describing the effect of different sizes of replay buffer on the performance of the agent for Deep Expected Sarsa. Results shown are averaged over 30 runs for each parameter setting. The step-size value is set to 10-4 for all of the environments. Lower values are better in Sparse MountainCar plot and higher values are better in the other two plots. The value in the legends indicate the value of the exploration parameter of each soft-greedy operator.
6.2.2 EXPERIMENTS ON ATARI ENVIRONMENTS
We use the DQN algorithm (Mii et al. 2015) for our Atari experiments. We investigate the sensitivity of resmax, softmax, and e-greedy to their exploration parameters and compare their perf-perg instances to each other. The results of these experiments are shown in Figure As evident from these graphs, e-greedy fails reach a similar better performance than both resmax and softmax across all three environments. Resmax performs similar to softmax on the Asterix environment. However, it outperforms softmax in Freeway by a large margin and gains a higher return in the Breakout. These graphs also show that resmax is much more stable across a large range of its exploration parameters while this not the case for softmax and g-greedy. Additional results for five other atari environments, three of which are considered hard-cxploration (Taiga et al., 2020), are presented in section E.4 in the appendix. These results provide further evidence that resmax achieves highly better performance over the baselines.
It is good to mention that we chose Freeway because it is cand-exxloration environment TTiga et al. 2020). As our tabular experiments in hard-exploration problems like RiverSwim have shown, resmax outperforms other baselines this set of environments. Freeway is similar to RiverSwim in the sense that chicken should persistently go up reach the top of the screen to get positive reward while
8

---

Under review as a conference paper at ICLR 2022
taking into account the stochasticity in the transition function that is caused by the cars that can crash into the chicken at any moment.
AsterisNooFrmessiip-o
BreakcuttidFFamessip.uu
Preawaytiorammsiio vo
Egreedy rc nux softmax
800-
200
300-
250-
ACc Accummin www.e//eeeee
200
100-
683
200
129
30-
LOW
Medium
High
LOW
Medium Exploration Intensiity
High
LOW
Medium
High
Exploration Intensity
Exploration Intensity
AsterixlooFrameskipoo
Prrkkouttofrrmmsskp--000
Treeviyyoframmeskipps
2.00
sgrodd
1.0
3.0
Iootmaadd
1.50
Feemaac
Auenage Return
2.25
0.6
2.0
Jveragg
1.00
Auerage
2.5
62
(selbmaa)) (resmax)
0.5
(sofmaan)
gresddy
0.25
0.0
(nes max)
30
20
5b
11.6))
Step
Figure 5: Bar charts describing the effect of different level of exploration on the performance of soft-greedy operators DQN setting and learning-cune curves presenting the best performance across different exploration parameters. Results shown are averaged over 10 runs for each parameter setting. The size value set to 10-1 across all the environments. The hyperparameters corresponding low, medium and high exploration used in the x-axis given in the appendix.
CONCLUSION
Soft-greedy operators, including s-greedy, softmax and resmax, continue to play an important role in reinforcement learning. They serve dual purposes: they function as soft-greedification within the Bellman update and induce basic level of exploration; and hence, are valuable for both on- on-policy and off- off-policy learning. While simple, these operators are complementary and more focused exploration techniques. We propose a new soft- soft-greedy operator, called resmax. Its properties are both theoretically desirable and perform well empirically. Unlike softmax, resmax non-expansion, regardless of the hyperparameter settings and thus converges under generalized approximate policy iteration. Moreover, resmax ensures state-action space coverage and it avoids softmax's 's fundamental issue of overemphasis. Our empirical results show that resmax encourages more exploration than softmax in RiverSwim, since it does not overemphasize and also explores more efficiently than e-greedy.
function approximation
This paper proposes resmax in its simplest form, so there are many avenues for future research. As resmax is new operator reinforcement learning, it deserves further benchmarking and experimentation in both simple and complex environments in order to shed more light on when this operator is useful. Another natural direction for future work is explore adaptation and normalization techniques which are suitable for resmax. Just like decay schedules for s, schedules or adaption schemes for resmax could allow more exploration in early layer, and allow greedier policies later.
8 REPRODUCIBILITY STATEMENT
All the experiments in this paper reproducible and can be reproduced by the code made available in the submitted supplementary materials. The instructions for reproducing these experiments are given in the Readme files in the provided source code. Also, all the major proofs of this paper along with their assumptions are presented in the main text of the paper. Finally, no datasets are used for this paper and all the environments that are used are freely available.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In International Conference Machine Learning, 1999.
Kavosh Asadi and Michael Littman. An alternative softmax operator for reinforcement learning. In International Conference on Machine Learning, 2017.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos.
Unifying count-based exploration and intrinsic motivation. International Conference on Neural Information Processing Systems, 2016.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint urXiv:1606.01544 2016.
Nicolò DesaaBBinchhi, Claudio Gentile, Gabor Lugosi, and Gergely Neu. Boltzmann exploration done right. In International Conference Neural Information Processing Systems, 2017.
Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, 2020.
Michael Gimelfarb, Scott Sanner, and Chi-Guhn Lee. Epsilon-BMC: BMM:: A Bayesian ensemble approach to epsilon-greedy exploration in model-free reinforcement learning. In Uncertainty in Artificial Intelligence, 2020.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11651):1533-160, 2010.
Seungchan Kim, Kavosh Asadi, Michael L. Littman, and George Konidaris. Deepmellow: removing the need for target network in deep Q-learning. In International Joint Conference Artificial Intelligence, 2019.
Raksha Kumaraswamy, Matthew Schlegel, Adam White, and Martha White. Context-dependent upper-confidence bounds for directed exploration. arXiv preprint arXiv:1811 1..6669, 2018
Michael L. Littman. Algorithms for sequential decision making. Brown University, 1996.
Michael L. Littman and Csaba Szepesvári. generalized reinforcement-leaming model: Convergence and applications. In International Conference on Machine Learning, 1996.
R Duncan Luce. Individual choice behavior: A theoretical analysis. 1959.
Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Escaping the gravitational pull of softmax. International Conference on Neural Information Processing Systems, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 51 518(7540):529-533 2015.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In International Conference on Neural Information Processing Systems, 2013.
Ling Pan, Qingpeng Cai, Qi Meng, Wei Chen, and Longbo Huang. Reinforcement learning with dynamic boltzmann softmax updates. In International Joint Conference on Artificial Intelligence.
D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell. Curiosity-driven exploration by self-supervised prediction. In IEEE Conference on Computer Vision and Pattern Recognition Workshops, 2017.
Remigijus Paulavičius and Julius Žilinskas. Analysis different norms and corresponding lipschitz constants for global optimization. Technological and Economic Development of Economy, 12: 301-306, 12 2006. doi: 10.3846/1392866 99.069999999099677773
Theodore J. Perkins and Doina Precup. A convergent form of approximate policy iteration. In International Conference Neural Information Processing Systems, 2002.
10

---

Under review as a conference paper at ICLR 2022
Satinder Singh, Tommi Jaakkola, Michael L. Littman, and Csaba Szepesvári. Convergence results for single-step on- on-policy reinforcement-leaming algorithms. Machine learning, 38(3):287-308, 2000.
Zhao Song, Ron Parr, and Lawrence Carin. Revisiting the softmax bellman operator: New benefits and new perspective. In International Conference Machine Learning, 2019.
Alexander Strehl and Michael L.. Littman. analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309-133) 2008.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Adrien Ali Taiga, William Fedus, Marlos C. Machado, Aaron Courville, and Marc G. Bellemare. On bonus based exploration methods in the arcade learning environment. In International Conference Learning Representations, 2020.
Michel Tokic. Adaptive e-greedy exploration in reinforcement learning based on value differences. In Annual Conference on Artificial Intelligence, 2010.
Michel Tokic and Günther Palm. Value-difference based exploration: Adaptive control between epsilon-greedy and softmax. In German Conference on Advances Artificial Intelligence, 201 1.
Ruosong Wang, Ruslan Salakhutdinov, and Lin F. Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. arXiv preprint arXiv:2005. 10804, 2020.
Christopher J. C. H. Watkins. Learning from delayed rewards. King's College, Cambridge, 1989.
Christopher J. C. H. Watkins and Peter Dayan. Technical note Q-learning. Machine Learning. 8: 279-292, 1992.
Gautam Wilkins and Ming Gu. A modified brent's method for finding zeros of functions. Numerische Mathematik, 123(1):177-188, 2013.
Niko Yasui, Sungsu Lim, Cam Linke, Adam White, and Martha White. An empirical and concep- tual categorization of value-based exploration methods. Exploration in Reinforcement Learning Workshop at the International Conference on Machine Learning, 2019.

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL PROPERTIES OF RESMAX
A.1 STATE-ACTION SPACE COVERAGE
Exploration strategies should satisfy certain fundamental properties to make sure that algorithms such as Q-learning and Sarsa converge to the optimal value (Singh et al.) 20000; Watkins & Dayan (192). key property that each state-action pair should be visited infintelly many times during continual learning. To show that resmax satisfies this property, we prove that the probability of taking all of the actions will be higher than zero during learning for any bounded action-values.
Property A.1. Assume that there exists qmax such that Vss a, Iq(s, a) S 9max. The probability of taking any non- con-greedy action and a greedy action b is bounded as follows:
1
< [A| + 2 9maz
S n (a
S
S
( 8) <1
A
Proof. First determine the upper-hound and lower-bound for non-greedy actions a and then proceed to show this for the greedy action 6. By analyzing Equation 2 it is clear that its lowest-value will be obtained only when the difference between q(s, 6) and g(s, a) its highest. We therefore get the following lower bound on (a |s)
(a 5) = |A| 1 ( ((s a))
IV
1)+
11 (Amas (-4max)) |A] + 2 Amar
Furthermore, the highest possible value for π ()) for a non-greedy action a is 1/|_A,, which occurs when g(s, a) (s, b). Based Equation 2 when the probability of non-greed, actions reaches its highest value, the probability of greedy action b will be at its lowest, which is similarly 1/|.A|. Therefore, have π (s a) 1/1A (b s) 1, completing the proof.
A.2 RESMAX DOES MAXIMIZATION
It can be easily shown that the Expected Sarsa update of resmax, represented in Equation 3 can do maximization (i.e., give the highest probability to the greedy action) when 1 goes to 0. We first show how T(a s) for non-greedy actions will change when this happens:
lim (a 8) = lim 7
7-0 A + (g(s, ((8,a)) =
This equality will hold as long as g(s, b) o ((s a).
Considering this, we can derive Equation 3 when v goes to infinity follow:
lim rm( (), ))
lim n-
xaa
a))
adt
(1
Σ r(a s))g(s,)) b
0 (1 (s, b) = ((s,b)
Since q(s,b) b) is the action-value of the greedy action, resmax can do maximization. is also interesting to note that when 1) goes to xo, the generated policy will be equiprobable thus Expected Sarsa update of resmax will average all the action-values. So, this operator can make balance between q- g-learning update and update with equiprobable policy by tuning the value of n like softmax and mellowmax.
B COMPUTATIONAL INFRASTRUCTURE
We ran our experiments on a compute cluster. Each job used a single CPU core, except for atari experiments that we used GPUs. The compute cluster allocated CPUs based availability. The possible options were 2. Ghz Intel CPUs with model numbers E5-2683 V4 Broadwell, E7-4809 V4 Broadwell, Platinum 81 S16 Skylake, well 2.4Ghz Intel Platinum 8260 Cascade Lake. For
2

---

Under review as a conference paper at ICLR 2022
GPU experiments, used V100 Volta GPU. We also requested 400MB for the tabular setting. In the case of deep RL, we requested 4GB for low-scale environments and 16GB memory for Atari environments. Different algorithms and exploration heuristics within one environment used the same configurations of resources.
C LOGGING PROCEDURE
To save returns and steps per episode, we average returns or the number of steps per episode for all of the episodes that have been finished in specific number of steps that call log-interval. To elaborate, returns and the number of steps per episode for all the episodes that are finished in the log interval will be accumulated and averaged. We only store this final averaged value. For instance, we set the total number of steps to 100, 000 and define ong-interval of 1, 0000, 100 values will be stored. This way of storing the results same time, the stored results are proportional to the performance of each of the employed algorithms.
experiments can save both memory and space. At the
We use log-interval of 1, 000 for all our tabular experiments and log-interval of 10, 000 for all the DQN experiments, except in Atari experiments that we use log-interval of 100, 000.
D HYPERPARAMETER STUDY
In this section, we present the hyperparameters that are used in our experiments and the reason for selecting them. One of the hyperparameters we needed to set fairly across different soft-greedy operators were their respective exploration parameters, such 7 and т. To do this, swept over large set of hyperparameters for each soft-greedy operator to make sure that the exploration parameter with the near-best performance resides in this set.
Our tabular experiments used E {2 12 12-12,2-11, ...,,, 2",, T E 12-8,2-7 2*} and E e (0, 001, 1}. Softmax and resmax required different ranges of hyperparamters since softmax uses exponents, and would therefore need larger values than resmax does for 1).
We plotted the hyperparameter sensitivity in the function apprimation settings across large set of hyperparameter in the range of 2-21 to 2 for different environments. Our experiments showed that all the best exploration parameters for these operators except for softmax in CartPole-vO) environment that works best with values lower than 1. For s-greedy on the other hand, we noticed that æ 0.1 always results in near-best performance, so we only tried several values around it to see how increasing exploration changes its performance. Based on this, we have chosen the exploration parameters for each operator and presented its hyperparameter sensitivity plots in the appendix.
located somewhere between 2-21 and
In the deep RL setting, we use the DQN algorithm. We chose fixed parameters that work well across all three benchmark environments. These parameters are presented in Appendix Table [ We swept over three different step sizes across all our experiments: 0.0005, 0.0001, 0.00005. Our experiments with these step sizes show that step size of 0.0001 works best across all the low-scale and large-scale environments. We present the results this paper based on these step sizes. Furthermore, ran first set of DQN experiments with 17, E (2 2,,,...,,2 2163 and E {0.1, 0.3, 0.5, 0.7). Then, based on these results, we have cho
"e.,....,,,
When were choosing low, medium, and high exploration values, selected lower set of values for softmax compared to resmax because softmax exponentially reduces the degree of exploration when increase but this is not the case for resmax. In our DQN experiments, 216 for softmax and 28, 216 221 for resmax and mellowmax as high, medium, and low exploration values. For e-greedy, we used 0.1, 0.3, and 0.5. It is good to mention that these set of values were chosen based on several experiments that we ran on Atari environments showing that these operators work best with these of values when Atari environments need low, medium, and high level of exploration.
used 2 2..
3

---

Under review as a conference paper at ICLR 2022
Parameter Name
Fixed Value Adam
Optimizer
B1
0.9
B
0.999
for Adam
10
Batch size
64
Buffer size
50,000 000
Number of training steps per iteration
Target network update frequency
1. 0000
Number of steps before learning starts
5, 000
Number hidden layers
2
Number of Neurons in each layer
64
0.99
Table The fixed parameters used to run DQN experiments
E ADDITIONAL RESULTS
In this section, we present additional results for our experiments in the tabular and Deep RL settings.
E.I
TABULAR
0.4
0.6
0.6
0.6
0.6
0.6
0.35
0.35
0.35
0.35
1,r 0.005
0.6,
0.05
0.05
0.05
0.05
0.4
(a) RiverSwim
0.4
0.6
0.6
0.6
0.6
0.6
0.35
0.35
0.35
0.35
1, N/0.005
82
84
86
0.6,
((1,1)
0.05
0.05
0.05
7
0.05
0.4
(b) Stochastic-reward wiverSwim
Figure Diagram of RiverSwim and Stochastic-rewart RiverSwim. Dotted lines and solid lines show the transitions and probabilities for the left and right actions, respectively. Diagram adapted from Osband et al. 2013).
4

---

Under review as a conference paper at ICLR 2022
E.2 DEEP RL
In this section, we first present learning curves of best hyperparameters for each soft-greedy operator along with hyperparameter sensitivity plots of each operator and its sensivitiy plots for different replay buffer sizes. Then, we discuss our results on five atari environments.
E.3 REPLAY BUFFER STUDY
Here first we go through the performance these operators based on different exploration parameters. Then, we present the plots for their stability across different replay buffer sizes.
The results for our first of experiments are presented in Appendix Figures softmax and resmax are similar in terms of hyperparameter sensitivity and best performance, except in the Sparse MountainCar environment that resmax is much less sensitive compared to softmax and its best performing instance outperforms softmax. s-greedy, comparative performance with 0.1 in comparison to the best instance of resmax. In the case of LunarLander--ve whereas the best instance of e-greedy surpasses resmax in the beginning of learning, the final performance of resmax is slightly better than e-greedy.
Overall,
the other hand, achieves
MourilainCariv0
+39
Acrobot-vl
1.5
2.0
Accumstnnd Returns Ratums
Accumulats uattuddddd Rubums
1.0-
2.5
-125
2.0
-1.50
0.5
eggeady
-2.00
-225
sttma
2
2
2
5.0.T
6.0.7
(b)
(c)
Figure 2: Hyperparameter sensitivity for DQN. Results shown are averaged over 30 runs for each parameter setting. The x-axis is plotted with a symmetrical log scale.
MountainCar-v0
LunarLander-42
Acrobot-v1
greedy
Steps Epicode
wilma
Average Avtrage/Rtuum Return
Awe aago Aatum
-1
V.
greody merma sertmax
egeedy
1.
-4
nemes
softmaes
20
80
100
20
40
(10.)
Stop 110f)
(a)
(b)
(c)
Learning curves for best performing hyperparameter settings for DQN. Best settings (based on average return) are shown the top left each subplot. Results are averaged over 30 e-greedy consistently reaches its best performance with 0.1 across all three environments. Resmax achieves its best performance with r) values of 216 25, and 210 in Sparse MountainCar, LunarLander-v2, and Acrobot-vl respectively. Softmax performs best with 7 values of 28, 214 and 26 in Sparse MountainCar, LuderLander--2, and Acrobot-vl respectively.
Figure 3:
The results describing the effect of different sizes of replay buffer on the performance the agent for Deep Expected Sarsa algorithm is presented in Figure
5

---

Under review as a conference paper at ICLR 2022
Acrobot
LunarLander
MountainCar-vo
-1.0
Stege
Acomu
0.5
0.0
25
2
2
2
211
2 2
2
2 211
2
2
24
2
2
Replay Buffer Sic
Replay Buffer Size
Raglay Suller 3ice
Figure 4: Replay buffer size sensitivity plots describing the effect of different sizes of replay buffer on the performance of the agent for DQN. Results shown are averaged over 30 runs for each parameter setting. The step-size value is set to 10 for all of the environments. Lower values better in Sparse MountainCar plot and higher values are better in the other two plots.
E,4 ADDITIONAL ATARI RESULTS
Here present the results of our experiment on five atari environments, including Pong. SpaceIn- vaders, Gravitar, Pitfall, and Venture. First, we go through our results on three of these environments that are considered hard-exploration: Gravitar, Pitfall, and Venture. Then, we discuss our results on Pong and SpaceInvaders environments.
The results for hard-exploration atari environments are presented in Figure 5 As evident from this graph, resmax surpasses the performance of softmax and s-greedy policies on Gravitar and Venture. Especially Venture, there is huge performance gap between resmax and other baselines. However, the best performing instance of all the soft-greedy policies reaches similar performance with E-greedy performing slightly better than softmax. These results show that resmax promising technique to be used even for hard-exploration problems.
Graviarrooramessiio000
VentureNofrraeskipn meskiipp-
RttallNooiraessipvvo
egreedy
egreedy
resmax
resmax
22-
50ft mox
moft
Accumatieed
Accumalated
careedy softrac
LOW
Medium
Hiigh
LoW
Mediam
High
LDW
Medium
Hiigh
Exploration Intensity
Exploration intensity
Exploration Intensity
Gravitartiorrameskkpp..
PrrallNoFramessip-00
VenturetooFraeesiip.o
3.50
0.0
cageedy
(sofmaak
3.25
0.8
(resmax)
Avarage Roturn Ruturn
Average Reium
-0.4-
0.6
2.75
2.50
-0.8
0.4
-0.8
0.2
2.00
(sstmme)
Instimacd tneerac
(reimax)
0.0
10
40
50
10
2.
20
50
(1.07)
Figure 5: Bar charts for hard exploration atari environments describing the effect of different level of exploration the performance of soft-greedy operators in DQN setting and learning-curves presenting the best performance across different exploration parameters. Results shown are averaged over 10 runs for each parameter setting. The step-size value is set 10- across all the environments. The hyperparameters corresponding low, medium and high exploration used in the x-axis are given in the appendix.
Finally, the results on Pong and SpaceInvaders environments shown in Figure 6 These results follow a similar trend to the results that we have for hard exploration environments. with resmax being highly competitive the provided baselines.

---

Under review as a conference paper at ICLR 2022
SpacelvaadesNNorraesskivvvv
PongNoFrameskip-v0
E-greedy
2000
resmax
Accumulated Returns
Accumulated Retums
7000
softmax
0
6000
-2000
5200
-4000
3009
-6000
egreedy
2000
saftmax
Low
Medium Exploration Intensity
High
Medium Exploration Intensity
High
Framss-rr
SpacelnadeesNorrameeiiooo
2.0
Average Return
1.5
Average
1.0
-1
e-gredy
0.5
greedy
(softmax] (resmax)
(softmax)
-2
(resmax)
0.0
200 300
400
500
100
200
300
400
500
Step (10*)
Step (10*)
Figure 6: Bar charts describing the effect of different level of exploration on the performance of soft-greedy operators in DQN setting and learning-curee presenting the best performance across different exploration parameters. Results shown are averaged over 10 runs for each parameter setting. The step-size value is set 10-1 across all the environments. The hyperparameters corresponding low, medium and high exploration used in the x- x-axis are given in the appendix.


Reviews:
[{"review_id": "t4Mr4jx9T0", "reviewer": "Reviewer_sPif", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths : \n\t- 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. \n\t- 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. \n\t- The experiments in the paper demonstrates the usefulness of the proposed operator.\u000b\n\n\n\nWeakness : \n\t- 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. \n\t- 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?\n\t- 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. \n\t- 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?\n\t- 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\n\n\n\n\n\nOther comments : \n\t- The paper claims that the proposed resmax operator has better properties unlike softmax \u000bor epsilon greedy operators.  There are few lines of work similar in motivation, addressing issues of the softmax \u000boperator,  \"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. \n\t-  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?\n\t- 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?\n", "summary_of_the_paper": "This paper proposes an alternative greedy operator for RL which selects actions proportional \u000bto the optimality gap of value functions.  The claim is that it can explore better compared to an epsilon greedy approach\u000band has similar benefits to a softmax operator. The main advantage of the proposed operator is that the probabiliteis\u000bof the actions do not converge too quickly, as in softmax operators. \n", "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. \n\n\nThe 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. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_qijYKDYLY_", "reviewer": "Reviewer_ypnG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The article is clear and easy to follow.\n- The proposed policy is simple and fast to compute. Much simpler and faster than mellowmax.\n- It may improve some RL algorithms.\n- The proofs of (Property 4.1) and (Property 5.1) are simple and correct.\n- The results are reproducible. I managed to run (partially) the experiment code provided as supplementary material.\n\nWeaknesses:\n- 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.\n- Another solution is to learn the softmax temperature as in [Kim Konidaris 2019]. Did you try this as well ?\n- For these reasons I am still wondering if the proposed method is a clear improvement against mellowmax and its tuned-softmax variants.\n\n\nDoubts/Questions:\n- 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.\n- 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 ?\n\nMinor remarks:\np2l-1 more greedy -> greedier\np3l26 b = \\arg\\max -> b \\in \\arg\\max (or the uniqueness assumption should be set on the table)\np3l-7 \"with results in a small environment\" : ?? unclear to me\np5 Prop 4.1 give the softmax lower bound as well\np5 Prop 5.1 \"temperature\" or \"pressure\" as on page 3 ?\np6 proof : getting rid of the p and q on equation (7) and follow-up could save a few precious lines for your reproducibility statement\np6l-5 \"show resmax\" -> \"show that resmax\"\np7 Figure 3 \"Stochastic RiverSwim\" -> \"Stochastic-reward RiverSwim\" (it's only clarified in appendix)\n", "summary_of_the_paper": "The most commonly used exploration policies for SARSA/Q-learning are epsilon-greedy and softmax sampling.\nThe 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.\nThis 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).\nSome experiments are then provided both with tabular and fitted Q function estimates. These experiments show empirically that ResMax is \noutperforming both epsilon-greedy and softmax on small (but misleading) MDPs and Atari environments.\nThe 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.\nAccording 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.\n", "summary_of_the_review": "A novel non-expansive and simple exploration policy called ResMax.\nI 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.\nOn 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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DUULLKFPvCQ", "reviewer": "Reviewer_Y4xX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n* 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.\n* The proposed operator has nice mathematical properties and seems well-behaved (unlike softmax).\n* The paper brings its theory all the way through to deep learning experiments.\n* The writing is mostly very clear.\n\n**Weaknesses**\n* 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.\n* 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.\n* 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.\n* The work could use more analysis (theory or experiment) of convergence properties, along the lines of the \"softmax gravity well\" paper.\n", "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.", "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.\n\n\n### After responses\n\nAfter 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5aaNBoTdEa4", "reviewer": "Reviewer_NLrw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI 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.\n\nOn 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. \n\nIn 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*. \n\nGoing 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. \n\nThe 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.\n\nProperty 4.1 seems too trivial to me to warrant being in the main text.\n\nI 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. \n\nThe 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.\n\nFinally, 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.\n\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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