Emergence of Exploration in Policy Gradient Reinforcement Learning via Resetting
Authors: Sotetsu Koyamada
Paavo Parmas
Tadashi Kozuno
Shin Ishii
Venue: Submitted to ICLR 2023 (2023)

Abstract: In reinforcement learning (RL), many exploration methods explicitly promote stochastic policies, e.g., by adding an entropy bonus. We argue that exploration only matters in RL because the agent repeatedly encounters the same or similar states, so that it is beneficial to gradually improve the performance over the encounters; otherwise, the greedy policy would be optimal. Based on this intuition, we propose ReMax, an objective for RL whereby stochastic exploration arises as an emergent property, without adding any explicit exploration bonus. In ReMax, an episode is modified so that the agent can reset to previous states in the trajectory, and the agent’s goal is to maximize the best return in the trajectory tree. We show that this ReMax objective can be directly optimized with an unbiased policy gradient method. Experiments confirm that ReMax leads to the emergence of a stochastic exploration policy, and improves the performance compared to RL with no exploration bonus.

EMERGENCE OF EXPLORATION IN POLICY GRADIENT REINFORCEMENT LEARNING VIA RESETTING
Anonymous authors Paper under double-blind review
ABSTRACT
In reinforcement learning (RL), many exploration methods explicitly promote stochastic policies, c.g., by adding an entropy bonus. We argue that exploration only matters in RL because the agent repeatedly encounters the same similar states, so that it is beneficial to gradually improve the performance over the encounters; otherwise, the greedy policy would be optimal. Based this intuition, we propose ReMax, an objective for RL whereby stochastic exploration arises as an emergent property, without adding any explicit exploration bonus. In ReMax, an episode is modified so that the agent can reset to previous states in the trajectory, and the agent's 's goal is to maximize the best return in the trajectory tree. We show that this ReMax objective can be directly optimized with an unbiased policy gradient method. Experiments confirm that ReMax leads to the emergence of a stochastic exploration policy, and improves the performance compared to RL with no exploration bonus.
INTRODUCTION
Exploration widely studied in reinforcement learning (RL) (Sutton & Barto, 2018) (see App. for an extended overview). The most popular method of exploration is to explicitly promote stochastic policy by maximizing the entropy in addition to the rewards (Williams, 1992; Ziehart al., 2008; Mnih et al., 2016; Haarnoja et al., 2018). We note that it is non-obvious why one should add such an entropy bonus-the objective of RL is only to maximize the rewards. Such exploration methods are only retrospectively justified as they improve the performance of the algorithms. In our article, propose a method that, paradoxically, promotes exploration by greedily maximizing the rewards.
The motivation of our method is the following: suppose that exploration is vital in RL because the agent, intentionally or unintentionally, visits the same (or similar) state repeatedly; exploration allows the gain of some valuable information for making better decision the next visit the same state. However, it has no value if the agent would never encounter the same state.
Based on this observation, we propose new objective function for RL called ReMax that encourages exploration in a novel way. Briefly, the ReMax objective is computed as follows: while interacting with the environment, in addition to taking usual actions, the agent may choose reset to a previously visited state in the trajectory up to some limited number of times; then, after the interaction, the value of the ReMax objective computed as the sum of the rewards along the best trajectory.
The crucial difference between our approach and previous ones is that, while most previous approaches explicitly set the goal of obtaining a stochastic exploratory policy via an exploration bonus (e.g.. state-visitation bonus or entropy bonus), in our approach, such an exploratory policy is not the explicit goal, but the optimization of the ReMax objective naturally results in an exploratory policy.
We note that several previous studies successfully utilized resetting. For example, Go-Explore (Fcof- fet et al., 2021), which achieved impressive results on the well-known hard-exploration problem Montezuma's 's Revenge, utilized resetting to rarely visited states, but also AlphaGo (Silver et al., 2016) used Monte-Carlo tree search that can be regarded as a kind of resetting. In practical RL problems, resetting is often possible, such as when have access to the environment simulator (like Go). Also, even if such simulator access is not available, we can use powerful model- RL (MBRL) methods, e.g., DreamerV2 (Hafner et al., 2021), and use resetting in simulations with the learned model.
The main objective of this article is to test our hypothesis that ReMax leads to the emergence of a stochastic exploratory policy. To this end, we perform three phases of experiments:

---

Step 1. We illustrate the main idea and demonstrate that optimizing the ReMax objective causes a stochastic policy in a simple bandit task (Sec. 3). This experiment was non-conclusive as the emergence of the stochastic policy relied on the partial observability of the environment.
Step 2. To overcome the limitation of the previous step, we demonstrate that, by optimizing the ReMax objective, a stochastic policy emerges even in a deterministic maze environment, where optimizing the regular RI. objective causes the policy to become deterministic and the learning to stop (Sec. 5). The limitation here is that the example relied on a simple model parameterization.
Step 3. To make the scenario of the maze experiment more realistic, we modify the maze to represent the observations by images, and use a neural network function approximator (Sec. 6). This experiment indicates that the failure of the regular RL and the emergence of exploration happen in practical deep RL scenario, even in deterministic environment.
Finally, we showed that ReMax can promote exploration in modern policy gradient algorithms, such as A2C (Mnih et al., 2016), and improve the performance in MinAtar (Young & Tian, 2019), simplified version of the Arcade Learning Environment (Bellemare et al., 2013 (SScc. 8.1). We believe ReMax is viable competitor to classical stochastic exploration approaches, such entropy bonuses.
2 PRELIMINARIES
Notation. We consider an episodic Markov decision process (MDP) M, defined a tuple (S,A,P, P.r, Po: T), where the state space S, the action space AA are discrete and T is a finite horizon. The initial state Sp E S follows the distribution Po S [0, 1], and the state transition kernel P:S x A x S - [0, 1] defines the state transition probability from the current state 8 E S to the next state s' S after the action
A is taken. The reward function r S x A [Fiiin Tmax determines the immediate reward given the state, and action, a. At each state, 8, the agent can take legal action a E A(s)) A, where A(s) are the legal actions state s. The agent acts following parameterized policy Ty S x A + [0. 1] with the goal of maximizing the rewards. The trajectory T == (Sg. Go. .... ST) the sequence of state-action pairs from the current episode: 7 ~ (x(() where P = (8)) I π (aaels)) P( (8t, ot). Note that &r is the terminal state. The RL objective to maximize the expected return JRL (x)) == Ey-p= [R()], where R(r) Et= r(st, at).
this study, we focus on the policy gradient (PG) method, which directly optimizes parameterized policy my via gradient ascent. The policy gradient theorem (Sutton et al., 1999) provides an expression of the PG, VoJAL (TT), amenable for estimation. In particular, we use REINFORCE (Williams, 1992) as the simplest PG method, whose gradient estimator is given by 9 = Ei= V log Te ( (R(() - bt). where b, a constant baseline for variance reduction. This estimator is unbiased: VoJnu(TT)) = E, [Ø). One may also average a batch of N gradient estimates from different trajectories, Σn NỘ:- A common baseline is b, = Ei= ,े R(T:). the average of the returns in the batch. Another common method to reduce the variance is using the future return (T) == Σズ= r(sh, an), that only includes the rewards following the action; this maintains the unbiasedness the estimator. An important property of PG methods- and part of the reason we focus on them-is that they remain unbiased even when the system is POMDP (partially observable MDP), i.e., unobservable hidden states characterize the state transitions.
Policy gradient methods.
STEP 1: BANDIT PROBLEM EXAMPLE
In the first step of our 3-stage experiment, we illustrate the core idea behind our ReMax objective. Through simple randomized bandit task, we explain the principle of why stochastic policy is optimal under the ReMax objective; thus, leading to the emergence of exploration.
Problem. There are two arms, indexed by 0 and 1. At the beginning of each episode, one arm is chosen as an unobservable "correct" arm z E {0, 13. The correct arm z E {0, is randomly chosen according to Bernoulli distribution with probability
0.75. In each episode, the agent plays only one arm a E {0. 1). Playing the correct arm (i.e., a = 2) gives the return and otherwise: R(2,a) I==a. where Ie takes 1 if e is true and 0 otherwise. Under the usual RL objective, which maximizes expected return E.,. (2, a)), the optimal policy is deterministic, taking action a = 1 with probability 1, which yields maximum expected return 0.75.
2

---

A
objochive
ReMax objective
probla 10
1.0
1.0
0.5
RL objective
RaMax objeztive
0.0
Optimal RaMax
0.5
0.0
20000
Prob(a 1)
Prob 1)
Episodes
Figure 1: Bandit problem example. (A) A comparison of two objective functions: RL objective (Left) and ReMax objective with K = 2 (Right). The black dotted line indicates the optimal policy. (B) Empirical results of optimizing the policies with the RI. objective and the ReMax objective.
ReMax objective.
We define our ReMax objective on this bandit problem as:
R(z, alt)))) ( |x]]
ReMaax (T) = Es (.ll)....a(k))
max kE(1...K)
(I)
In this objective the agent has K chances to choose an arm, and the best of those returns defined as the value optimize. For the regular RL objective. we saw that deterministic policy was optimal; however, for the ReMax objective, a stochastic policy is optimal instead. To understand this intuitively. consider that pulling the same arm multiple times does not affect the ReMax objective, while pulling both arms guarantees pulling the correct arm, giving the return max(R(= 0), R(z, 1)} = 1. We can analytically compute the expected return in this augmented problem (App. B). The solutions are in Fig. 1 (A) where we compare the ReMax objective (K 2) and the RL objective. We can confirm that (a 1) = 0.75 maximizes the ReMax objective (shown as the black dotted line), and the optimal policy under the ReMax objective is exploratory.
Experiments. We also experimentally confirmed that, when trained maximize the ReMax objective, a direct policy search algorithm converges to the stochastic policy rather than deterministic one. We trained a policy with only one parameter 0 E R. The probability of selecting action is defined as (a 1) (0)), where is the sigmoid function. We initialized 0 so that wo distributes uniformly over [0, 1j. We used K = 2 in this experiment. Given sample (z, (1), a? we updated 0 using A -a [>> k== Ve log Ty (x)) (maxwe((122) [R[22, ()))))) where size parameter. Fig. 1 (B) shows the results of this training procedure. Each line shows an average performance of 10 runs, and the shaded area indicates the standard error. We can see that the policy converges to the deterministic one under the standard RL objective, whereas the policy converges to the optimal stochastic policy under the ReMax objective as expected.
0.01 is the step-
Discussion. The key insight from this bandit problem example is that if the agent can repeat the decision-making, seeking the best result in the same state, the optimal policy may be stochastic. This result relied on the uncertainty due to the hidden state 2. It may be unclear whether the same result will hold up typical fully observable MDPs. However, interestingly, we will show that stochastic policy emerges even in fully observable deterministic MDP (Sec. 5), where argued that there is an implicit uncertainty due to function approximation and distribution shift during learning-
4 REMAX WITH RESETTING IN MDPS
In preparation of stages and 3 of our experiments (Secs. 5, 6), we lay the foundations of using ReMax in MDPs. In the bandit example (Sec. 3), the agent had K chances to play at the given state. However, in RL, it not practical to act K times at each state, especially when the environment is large. To optimize the ReMax objective in practical way, we utilize resetting and define resettable MDP (ReMDP), where the agent has a special action to "jump" back to previously visited states in the episode, and the trajectory free, tree constructed by the state-action pairs in ReMDP episode. Fig. 2 shows the idea of resetting and the trajectory tree. We define our ReMax objective over the ReMDP (Sec. 4.1) and also describe a PG method that optimizes the objective (Sec. 4.2).
4.1 REMAX OBJECTIVE IN MDPS
Resettable MDP. We define ReMDP MRe = (S. PRe, Pu. T) by extending the action space and state transition kernel of the original MDP M = (S.A, Po: T) as follows: the action Are is element of Ane = A AU X, where x E A' indicates reset action to the target state
3

---

(z) S. If a reset action is chosen (u 2), the state immediately transitions to (t))
( (, = [l==en((u) if E X if = a
(((''ss,a)
However, as our motivation was to repeat decisions in the same state, the target states of resetting are limited to previously visited states in the episode: the legal actions at 5, are (Ro( = A(s:) such that for any I E (8:),, (Ra(F) E 8t-11 holds.
Trajectory tree. Now, we can sample T (sc. .I)) a trajectory on the ReMDP, MRe- We call T trajectory tree because we can construct a tree, whose nodes correspond to the states E S, and edges correspond to the actions u = See Fig. 2 for an example trajectory tree, (5o. uo ,0....,,7). The initial state so is the root node, while the states where a reset happened and the terminal states are the leaf nodes.
82 85
Reset
A.
80
Mg E
86
8y
Figure 2: Trajectory tree example.
ReMax return. Given trajectory tree T, we define our ReMax return RReMax (T). Here, we assume that the trajectory tree 7 has leaf nodes. For E (1...., K}. we define the trajectory path (8) as the subsequence of 'T consisting of the states and actions in the path from the root node the
k-th leaf. For example, the trajectory tree Fig. has two trajectory paths 7(1) (So, .o....... 84)
and 7(2) (sg, uo..... 82 $5; Ug....... ;8))..))7)......... We define the ReMax return on the trajectory tree by
RexMax (T) = max (T)
(2)
kE(L.....K)
where, (k) is the return along the path (kk) defined as in conventional RL.
ReMax objective. Our proposed objective is to maximize the expected ReMax return:
JReMax (π) = ReeMa (7)]-
(3)
Note that if no resetting occurs, JReMax reduces to JRL- It is worth mentioning that if the MDP is deterministic, there exists a deterministic policy x² : S - A that maximizes both JRL and JReMax. This obvious as an optimal policy for JRI. also maximizes JReMax because resetting cannot increase the ReMax return if all of the chosen actions were optimal. Interestingly, while there exists a common deterministic optimal policy, optimizing the ReMax objective enhances exploration during training in a deterministic environment. We describe this phenomenon in Sec. 5.
4.2 REMAX POLICY GRADIENT METHOD
We propose to optimize the ReMax objective using policy gradients. As the simplest realization the ReMax PG method, we consider REINFORCE. Given a trajectory tree T, gradient estimator is
T-1 TReMax = Σ
V log (u, (RReMax -be,
where To : :S Are - [0, is the parameterized policy optimize, and b, is a baseline for variance reduction (Sec. 2). This estimator is unbiased: Ey EglrReMax!
/ = -ee-ReMa
Policies in this study. In ReMDPs, agents must select actions from the extended action space Ane AUX. X. In this study, we decompose the policy The :S 5x.An Are - [0. 1] into three independent components: the policy of the original MDP TA :S x A -> [0, 1). the policy of where reset to xx (u)s)) S x X + [0, 1]. and the policy of whether to reset y n(yls), where y E {0, 1} is Boolean variable: means to reset, and 0 means to act in the MDP. Using these components, we have
(5) As our main focus in this study is the emergence of cxploration from our ReMax objective, we only employ simple rule-based policies for π. and y. We show that, even with such deterministic reset policies, the policy for the original MDP тA becomes stochastic. Each realization of л and is described in the corresponding experimental setup section. We parameterize AA as k.. As the reset policy मx is non-parameterizee, we can rewrite Eq.
(uls, y) (1 y) (a(as)) + y (x(x).)).
@ReMax
Σ EAA
Vo To(a, (sc) (RnoMaxx (T) bt),
(6)
4

---

where tlue ae E A is an abbreviation of t {t/u, or A} and To is the parameterized policy for the original MDP. One may use more sophisticated reset policies with search algorithms or trainable models for better performance. We leave such improved reset policies for future work.
Reset Policy Gradient Theorem. Finally, recall that in standard PG methods, one only needs to consider the rewards following an action in the PG, while ignoring the rewards obtained before the current time-step, as the action has no effect on what happened in the past. This is not the case in the reset PG method-the state may be reset to the past, cancelling out previously received rewards. Thus, we may have to consider the full return over the trajectory tree at each time-step. One wonders whether a similar PG theorem could be derived for the case with resets; whether some of the rewards in the return could be deleted while still guaranteeing unbiasedness. A sufficient condition for unbiasedness formalized in the theorem below. Note that we provide this theorem for completeness and for a few justifications, but do not incorporate it in our algorithms.
Theorem 1 (Reset Policy Gradient Theorem). Denote T is the optimal trajectory in the tree, T, so that RReMax (T) = R(T*) = =( r(s, a). Moreover, denote (s) is a subsequence Tixed (st) E r", starting at Sy and ending at St, h < t. s.t. for all possible trajectories with z t, and all s E (St) we have s & (sk). where X(sk) is the set of admissible states to reset to in state Sk- In other words, Tixed (8x) is the set of states in the optimal trajectory to which is impossible to reset to when starting at state St, at any point following time-step, L. Then we have
V& RReMax
(T)-
Σ
Va log To (R)a)ss)(RRMMa)))
RReMax (T) - -R (Tixed be)
(7)
f/u, EA
Proof. See App. D.
5 STEP 2: REMAX ON A DETERMINISTIC TABULAR MDP
In the bandit task (Sec. 3), the emergence of exploration relied on the uncertainty of the environment. To resolve this limitation, in step two of our experiments, we show that exploration also emerges in deterministic MDP. We consider tabular maze environment that we call the biased maze (Fig. 3). Though this maze has no explicit uncertainty or hidden state like the bandit task, we argue that function approximation and generalization leads to an implicit uncertainty, and we show that optimizing the ReMax objective promotes a stochastic exploratory policy even in deterministic MDPs.
Problem. The maze is a deterministic MDP with admissible actions 0 or I in each state. The agent receives a reward of for each step forward. There is only one correct path in the maze (the red line in Fig. 3), and long as the agent chooses the correct action, it can continue to move forward up to maximum of 1000 steps. Once the agent chooses the wrong action, the maze will terminate after one or two steps, depending on whether the following action is also wrong (or not). We designed the maze such that the correct action is 1 in 75% of the states. In this sense, the maze is biased as action 1 tends to lead a higher return.
Figure 3: Biased maze example.
Setup. We train a policy (a 1|st) = a (w; + c). where i indicates the state index, each state i has a corresponding local parameter wi, and e is a global scalar bias term shared by all states. We expect w; to extract the local information at the i-th state and e to learn the global information over the states. We compared training the policy with the standard REINFORCE and with the ReMax version. In this experiment, the resets happen when the agent reaches terminal state (773 1|s) = 1 if s is terminal and () otherwise), and the agent always resets back by optimizer. We estimate the gradient from a batch of trajectory tree samples, and the baseline b, is calculated from the batch mean. For fair comparison of the two algorithms, separate from the training episodes, we include evaluation episodes that are not used for training the policy. In the evaluation episodes, we use greedy action selection, commonly done in previous work (Haarnoja et al., 2018; Hafner et al., 2021). We emphasize that no resetting is used in the evaluation episodes.
2 steps. We used the SGD
Hypothesis. Biased maze is fully observable deterministic MDP. However, claim that, during training, there exists uncertainty when the agent reaches a previously unseen new state. At each new state, the agent does not know whether action 1 or is correct. Moreover, based on the structure of the
5

---

Errluatton return
150-
1.00
Evalustion retum
800
100
600
0.75
50
200
0.5
1.0
0.50
80
100
150
10
10
10
Envrooment slops
Evaluation return
Learning rate
K-1 (no reset)
K-2
Kmd
K
Figure 4: Biased maze results. (A) Evaluation return and average probability of selecting action 1 at new (unseen) state with different K. The evaluation return computed without resetting, even if K 1. The shaded area indicates standard error. (B) Evaluation return for different learning rates 10M steps. The bar indicates the standard error.
maze, action is preferable as it has a higher probability of being correct. As our agent can control the "prior" policy at unseen states using the bias parameter c, we hypothesize that ReMax should promote exploration even in such deterministic MDP. We note that such "implicit" uncertainty in fully observable MDPs has been previously studied in relation to generalization (Ghosh et al., 2021).
Results. Fig. 4 (A) shows the results with the learning rate 0.003. The standard REINFORCE
algorithm (K = 1). quickly converged to a suboptimal policy that deterministically chooses action 1 at an unseen state, and the evaluation return stopped increasing. On the other hand, ReMax (K > 1) promoted more exploratory policies. We also see that larger K lead to more exploration and higher evaluation returns. These trends were consistent with other reasonable learning rates. Moreover, the regular REINFORCE cannot be greatly improved even when tuning the learning rate (Fig. 4 B). Finally, also performed ablation studies in Sec. and App. C.2 showing that only the resetting, but also the maximization is important for the emergence of stochasticity, and improved performance.
Discussion. Here, showed that ReMax promotes exploration even in deterministic MDP; however, this phenomenon relied on shared parameter c. One may wonder whether this setup is realistic. In step three of our experiments (Sec. 6), we show that can be replaced with typical param- eterized function approximator policies in RL, and demonstrate the consistency of the phenomenon.
STEP 3: REMAX ON A DETERMINISTIC MDP WITH VISUAL INPUTS
In the previous biased maze experiment, the model too sim- ple and it remained unclear whether exploration would emerge more practical scenario. In the third step of our experiments, we demonstrate that optimizing the ReMax objective promotes exploration even a practical scenario with neural network func- tion approximators, which have been proven successful in visual input environments (Mnih et al., 2015; Silver et al., 2016). For this purpose, we introduce the MNIST maze environment.
Flipped
Figure 5: MNIST maze example.
Problem. Inspired by Elfwing et (2016) we consider an MNIST muze, modified version the biased maze (Fig. 5). This maze is also deterministic MDP but has visual inputs. In the maze, the agent can observe an MNIST image (LeCun et al., 1998) as a hint in addition to the state index. Each MNIST image is zero one, indicating the correct action at the state. Unlike the biased maze there are an equal number of ones and zeros; however, the MNIST image hints are wrong with probability 0.25. Note that this flip does not change between the different episodes. The agent may solve the maze efficiently by generalizing the information in the images. However, if the agent blindly trusts the hints, it will fall into a suboptimal policy that deterministically follows the hints.
Setup. We use the same setup as the biased maze experiment unless stated otherwise. Our neural network is multilayer perceptron (MLP) with one hidden layer with 128 units, followed by sigmoid activation function. We denote this MLP as fo. where ø are the parameters of the MLP. The MLP takes the image, img, at state as an input and produces the output y; = fo (img,) E. The policy is (a = 1[s;) = a (w + dy,), where the d hyperparameter controls the contribution from
Note that without the bias parameter c, the agent cannot control the "prior" at unseen states. See App. C. for the results without the bias term.

---

the MLP. We trained both the state-wise parameter and MLP parameters & simultaneously. We tuned the learning rate and hyperparameters in a different environment setting, where the hint flip probability zero. The chosen learning rate and d are 0.003 and 0.01, respectively. See App. E for the validation experiments regarding the hyperparameters.
Evaluelion Evalluaiie naturn 200
Results and discussion. Fig. 6 shows the results. Like in the biased maze results, when K K= 1, the policy quickly became deter- ministic, trusting the MNIST image hints too much in new states, and the learning stopped. On the other hand, ReMax (K > 1) pro- moted exploration and showed better performance. Thus, we have demonstrated that exploration emerges even in practical scenarios that utilize neural network function approximators. Finally, we will add implementation tricks, and demonstrate the feasibility of using ReMax to promote exploration in modern PG algorithms (Sec. 8).
0.5 Environment steps
Action probabiiity
0.75
(nc meee))
0.59
K-g
Evalustion return
Figure 6: MNIST maze results.
7 SUMMARY OF THE 3-PHASED EXPERIMENTS AND FURTHER ANALYSIS
In the three phases of our experiments, we examined our hypothesis step by step: First, we verified that, by optimizing the ReMax objective, a stochastic policy emerges as the optimal policy in a simple bandit problem (See. 3). Secondly, we confirmed that stochastic exploration emerges even in deterministic MDP (Sec. 5). Finally, we demonstrated that this result is consistent in realistic scenarios with neural network function approximation (Sec. 6). this section, we complement our experiments by showing ablation studies on two components of ReMax: maximization and resetting. Also, we address the overestimation problem in stochastic environments and propose a method to relieve it.
ReMax objective ablation study. To demonstrate that not only the resetting but also the maximization in the ReMax return is important for the emergence of a stochastic policy, we change the maximum operator in the objective to the average operator and compare the performance in the biased maze problem (Fig. 7 A). We see that when we use the average, the policy becomes deterministic faster and results in poor performance. In App. C.2 show extended ablation study, as well as a variant with resetting but while using the standard RL objective.
P(a= S Evaluation
return 100
ReMax
Entropy bonus
Evaluation return
800
800
Tuned rase!
wl entropy bonus ( > 0)
600
Heuristic reset
wlo entropy bonus ( - 0)
0.5
1.0
Random
Environment steps
1e7
400
No reset
400
1.0
200
200
08
Deeael Maa (Tat/so)
08
Evaluetion return
50
100
150
K
B
Figure Ablation study in biased maze. (A) Comparison with the average variant of ReMax (K 2). (B) ReMax performance with different reset policies (Left) and performance of REINFORCE with an entropy bonus (Right). The K and 8 are the hyperparameters for exploration. Black dashed lines indicate the performance of the standard REINFORCE without resetting entropy bonus.
Reset policy ablation study. We also examined the effect of the reset policy on the performance in the biased maze task. As the reset policy used in the previous experiments well-tuned using the information of the maze structure, we prepared two other reset policies that utilize no environment information: random reset and heuristic reset. The random reset simply chooses where to reset randomly from the preceding states in the trajectory. The heuristic reset returns to the state s where (alas)) is the smallest among the previously visited states in the preceding trajectory when the agent reaches the terminal state. Note that these two reset policies have only one hyperparameter K and are not tuned using the information of the maze environment. Fig. 7 (B) shows the performance of ReMax REINFORCE with these reset policies. Also, the results of REINFORCE using an entropy bonus are shown for comparison. The tuned reset is the same reset policy as in the previous experiments (m-step reset with m 2). We found that the choice of reset policy is critical: tuned reset performed the best and heuristic reset achieved significantly better performance than random reset. However, also found that even with poor reset policy like the random reset, it achieves comparable
7

---

performance to that of the entropy bonus. The performance gap between the heuristic reser and the tuned reset may be filled by a sophisticated reset policy, which we leave for future work.
Overestimation in stochastic environments. The maze en- vironments we studied are deterministic. Here we discuss a problem that may arise when optimizing the ReMax objective in stochastic environments. We consider another two-armed bandit problem: Taking
w/o seed beed-fixing w/ seed-fixing
Jaatax
gives reward ro 1 deterministically, and a = gives a random reward rı, which follows the uniform distribution on [-10, 10]. In this bandit problem, the optimal policy in the RL objective is deterministically choosing a =
0.0
0.5
1.0
Prob(a 1)
Figure 8: Overestimation example.
as ro = > 0 = Ir,, [r]] However, the optimal policy in ReMax = The blue line in Fig. shows MRMaax with K = 2. In this example, the ReMax objective overestimates the action with high-variance reward because may randomly achieve a higher reward when playing an arm a second time. To relieve this problem, seed is frozen. Thus, taking the same actions in the same state would always result in the same state transition. This simple trick prevent the agent from repeating the action with high-variance reward as it always gives the same result inside each episode. The orange line in Fig. shows JReMax with this trick. Now the greedy action with the optimal policy in ReMax is O. Note that the bandit example described in Sec. can be regarded as problem to which this trick is applied.
propose a simple seed-fixing trick: inside an episode, the random
8 PRACTICAL ALGORITHM: REMAX A2C
We saw that ReMax promotes exploration in the classical REINFORCE algorithm. Here, we demonstrate the feasibility applying ReMax to promote exploration in modern PG methods. In particular, we apply ReMax to A2C, a synchronous version of the A3C algorithm (Mnih et al., 2016).
Truncated rollouts with resetting. Instead of performing actions for a full episode of T time-steps, then updating the policy, A2C updates the policy many times during an episode, using truncated rollouts of length H < T. A2C estimates the PG on a batch of such fixed-length truncated trajectories. Using truncated rollouts improves the speed of learning by increasing the frequency of updates, and by reducing the PG variance. ReMax A2C analogously uses a batch truncated trajectory trees with fixed tree sizes. We describe the detailed rollout procedure in App. F.
Advantage estimation. Given a truncated rollout trajectory т, A2C uses an advantage estimator AA(T) == Ed 7^-"rA + Vo(SH) (s(s)) composed of the n-step future return and value function baseline, where y discount factor, H is the truncated last time-step in т, and Vo is a parameterized value function. Note that if ,и happens to be terminal state, Vo(HH) is set to zero. As an analogy of Å, given a truncated trajectory tree T by Algorithm 1, define A RRMaax using the best n-step future return and a value function baseline:
A RaMax (T)
max kE(R)
se.r (10 + vo(s!1)) Vo(ss),
(8)
where (8) indicates the i-th node on the k-th trajectory path (from the root node to the leaf node), 4 is the time-step index of the leaf node, and ig,t the time-step index of state s; on the k-th path
satisfying i... 8, for k E (k|se E (A)). Note that this estimator ignores the rewards before the state st, while they should be included if we wish to guarantee unbiasedness. However, based on Thm. we can ignore all rewards received before the truncated rollout, and empirically we found that ignoring the rewards from the start of the truncated rollout performed well. In the next section, empirically verify that ReMax A2C, a PG method with this estimator, also promotes exploration.
(k)
8.1 EVALUATION ON MINATAR ENVIRONMENTS
Finally, we evaluate our ReMax A2C in the MinAtar environments (Young & Tian, 2019), which include five simplified versions of ALE games with image observations (Bellemare et al., 2013): Asterix, Breakout, Freeway, Seaquest, and SpaceInvaders. Ceron & Castro (2021) reported that algorithmic improvements MinAtar transferred to the full Atari, thus allowing for more inclusive
8

---

ReMax A2C
A2C (w/b entropy bonus)
A2C (wl entropy bonus)
MinAlart/Asterssrr
Binklar/rveskouvv1
Minlaa/Freewayw11
SenAaa//esqueetw1
MinAtar Satpaaarpppeeeeeeeeeeee
Evalluation retuu
30
60-
103
83
150
23
50
1.0
0.5
1.2
0.0
1.0
0.5
Action probablity 0.5
1.0
1.0
0.5
0.0
0.0
0.0
0.0
0.5
Environment stepd!e?
Environment stepsle?
Environment stopd
Environment stepgle?
Environment stops
Figure 9: MinAtar results. (A) Average evaluation return for 10 runs. (B) Average probability of the selected action during the evaluation. The shaded area indicates the standard error.
RL research as it becomes possible to test new methods using fewer computational resources. We compared the performance of our ReMax A2C and the standard A2C (without entropy bonus). We also report the performance of standard A2C (with entropy bonus) for comparison. Moreover, in App. G we conducted an ablation study on the maximization in ReMax.
Setup. We employ the same convolutional neural network architecture as Young & Tian (2019). There are 64 parallel rollout workers, and the rollout length 32. We use the Adam optimizer (Kingma & Ba, 2015). The reset policy xx is the heuristic reset (see Sec. 7). Whether to reset is decided by nyy = 1|s} = 1 if s terminal, and constant small hyperparameter Preset otherwise. Hyperparame- ters were grid- grid-searched using five validation runs, which use different random seeds from the test runs. See App. for the details of the network architecture and hyperparameter selection.
Results and discussion. The experiments confirm that ReMax promoted more exploratory policies than A2C (w/o entropy bonus) and lead to better performance in all games (Fig. 9), despite not including any explicit exploration bonus. We note that in the Freeway environment, the episodes always continue for 2500 steps without any early termination by reaching a terminal state, yet our proposal of randomly resetting in non-terminal states with a small probability was sufficient to promote exploration. These results confirm that it is not intractable to construct reset policies that allow taking advantage of ReMax to promote exploration in modern PG algorithms, and even simple heuristics may be sufficient. Comparing A2C (w/ entropy bonus) to ReMax A2C, there was no clear winner. Our main objective in this work is propose ReMax approach to promote stochastic exploration. As entropy bonuses have been researched for a long time, we believe it is promising that our new method, ReMax, shows competitive performance.
competing or complimentary
CONCLUSIONS, LIMITATIONS AND FUTURE WORK
We studied the hypothesis of whether optimizing the ReMax objective results in an exploratory policy by greedily maximizing rewards, without an explict exploration bonus. The results were consistent with our hypothesis in three phases of experiments: randomized bandit (Sec. 3), the deterministic biased maze (Sec. 5), and maze with visual observations (Sec.6). Moreover, our ablation studies showed that not only the resetting, but also the maximization part of ReMax was necessary for the emergence of exploration and the improved performance. Finally, we showed that ReMax can be combined with the A2C algorithm leading to a practical scalable RL algorithm based on our method.
The type of promoted exploration is stochastic action selection similar to exploration from entropy bonus. Thus, it has the same limitations as competing stochastic exploration methods. For example, dense reward signals may be required. Moreover, while the performance antropy-based approach, it did not convincingly improve over this competing method. Lastly, in the present work, have not explored the full potential of the ReMax objective, and only tested simple reset policies, as our focus was on establishing that any exploration would emerge.
competitive with the
There are many avenues of research along which one may build the ReMax objective, e.g., advanced resetting strategies. Resetting hased on search algorithms such as MCTS, may enhance the exploration further. In addition, we may also train the reset policy by optimizing the RL (or probably the ReMax) objective to discover better exploration strategies depending on the task. We believe that many new directions of research on exploration in RL may emerge from the ReMax objective.
9

---

REFERENCES
Thomas Anthony, Zheng Tian, and David Barber. Thinking Fast and Slow with Deep Learning and Tree Search. In Advances in Neural Information Processing Systems, 2017. A
Thomas Anthony, Robert Nishihara, Philipp Moritz, Tim Salimans, and John Schulman. Policy Gra- dient Search: Online Planning and Expert Iteration without Search Trees. CoRR, 2019. A
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax Regret Bounds for Reinforce- ment Learning. In International Conference on Machine Learning, 2017. A
Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martin Arjovsky, Alexander Pritzel, Andrew Bolt, and Charles Blundell. Never Give Up: Learning Directed Exploration Strategies. In International Conference on Learning Representations, 2020. A
Nir Baram, Guy Tennenholtz, and Shie Mannor. Action Redundancy in Reinforcement Learning, In Conference on Uncertainty in Artificial Intelligence, 2021. A
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos.
Unifying Count-Based Exploration and Intrinsic Motivation. Advances in Neural Information Processing Systems, 2016. A
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47(1): 253-279, May 2013. 8.1
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. International Conference on Learning Representations, 2019.
Johan Samir Obando Ceron and Pablo Samuel Castro. Revisiting rainbow: Promoting more insightful and inclusive deep reinforcement learning research. In International Conference on Machine Learning, 2021. 8.1
Rémi Coulom, Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. In Interna- tional Conference on Computers and Games, 2006. A
Christoph Dann and Emma Brunskill. Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning. Advances in Neural Information Processing Systems, 2015.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. First return, then explore. Nature, 590 7847:580-586, 2021. 1, A
Stefan Elfwing, Fiji Uchibe, and Kenji Doya. From free energy to expected energy: Improving energy-based value function approximation in reinforcement learning. Neural Networks, 84:17-27, 2016. 6
Stefan Elfwing. Eiji Uchibe, and Kenji Doya. Sigmoid linear units for neural network function approximation in reinforcement learning. Neural Nerworks, 107:3-11, 2018. G
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable Distributed Deep-RL RL with Importance Weighted Actor-Learner Architectures. Interna- tional Conference on Machine Learning, 2018. A
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse Curriculum Generation for Reinforcement Learning. In Conference on Robot Learning, 2017. A
Lior Fox, Leshem Choshen, and Yonatan Loewenstein. DORA The Explorer: Directed Outreaching Reinforcement Action-Selection. In International Conference on Learning Representations, 2018.
Justin Fu, John Co-Reyes, and Sergey Levine. EX2: Exploration with Exemplar Models for Deep
Reinforcement Learning. In Advances in Neural Information Processing Systems, 2017. A
10

---

Dibya Ghosh, Jad Rahme, Aviral Kumar, Amy Zhang, Ryan P Adams, and Sergey Levine. Why generalization in rl is difficult: Epistemic pomdps and implicit partial observability. Advances in Neural Information Processing Systems, 2021. 5
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft Actor-Critic: Off-Policy
Maximum Entropy Deep Reinforcement Learning with Stochastic Actor. In International Conference on Machine Learning, 2018. 1,5, A
Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. 2021. 5,5
lonet-Alexanrru Hosu and Traian Rebedea. Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replay. In Evaluating General-Purposs AI, 2016. A
Rein Houthooft, Xi Chen, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. VIME: Variational Information Maximizing Exploration. In Advances in Neural Information Processing Systems, 2016. A
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-Optimal Regret Bounds for Reinforcement Learning. Journal of Machine Learning Research, 11, 2010.
Chi Jin, Zeyuan Aluen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-Learning Provably Efficient? In Advances Neural Information Processing Systems, 2018.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, 2002. A
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations, 2015. 8.1
Levente Kocsis and Csaba Szepesvári. Bandit Based Monte-Carlo Planning. In European Conference on Machine Learning. 2006. A
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11) 86(11):2278-22 2222-22444 1998. 6
Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's Cube with Approximate Policy Iteration. In International Conference on Learning Representations, 2019. A
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-55 533, February 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous Methods for Deep Reinforcement Learning. International Conference on Machine Learning, 2016. 1, 8,
Rémi Munos. Error Bounds for Approximate Policy Iteration. In International Conference Machine Learning, 2003.
Rémi Munos. Error Bounds for Approximate Value Iteration. In AAAI Conference on Artificial Intelligence, 2005. A
Mirco Mutti, Lorenzo Pratissoli, and Marcello Restelli. Task-Agnostic Exploration via Policy
Gradient of a Non-Parametrie State Entropy Estimate. AAAI Conference on Artificial Intelligence, 2021. A
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity- Driven Exploration by Self- Self-Supervised Prediction. In International Conference Machine Learning, 2017. A
11

---

Xue Bin Peng, Pieter Abbeel, Sergey Levine, and Michiel van de Panne. Deepmimic: Example- guided deep reinforcement learning of physics- based character skills. ACM Trans. Graph., 37(4): 143:1-143:14, July 2018. ISSN 0730-0301. A
Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning. In International Conference on Machine Learning, 2020.
Nikolay Savinov, Anton Raichuk, Damien Vincent, Raphael Marinier, Marc Pollefeys, Timothy Lillicrap, and Sylvain Gelly. Episodic Curiosity through Reachability. In International Conference on Learning Representations, 2019. A
Jürgen Schmidhuber. Curious model-building control systems. In International Joint Conference Neural Networks, 1991a. A
Jürgen Schmidhuber. A Possibility for Implementing Curiosity and Boredom in Model-Building Neural Controllers. In International Conference on Simulation of Adaptive Behavior: From Animals to Animats, 1991b. A
Jürgen Schmidhuber. Formal Theory of Creativity, Fun, and Intrinsic Motivation (1990-2010). IEEE Transactions on Autonomous Mental Development, 2(3):230-24 24772 2010. A
David Silver. Reinforcement Learning and Simulation-Base Based Search in Computer Go. PhD) thesis, CAN, 2009, A
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schritwieserr Ioannis Antonogiou, Veda Pannecrshelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, January 2016. 1, 6
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering Chess and Shogi by Self-Play with General Reinforcement Learning Algorithm. CoRR, abs/1712.01815, 2017. A
Bradly C. Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models. CoRR, abs/ hass/1507.00 000.10014444 14, 2015. A
Alexander L. Strehl and Michael L. Littman. A Theoretical Analysis of Model-Based Interval
Estimation. In International Conference on Machine Learning. 2005.
Alexander L. Strehl and Michael L. Littman. An analysis of model-based Interval Estimation for
Markov Decision Processes. Journal of Computer and System Sciences, 1309 2008.
A
Alexander I.. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael I.. Littman. PAC
Model-Free Reinforcement Learning. In International Conference on Machine Learning, 2006.
Yi Sun, Faustino J. Gomez, and Jürgen Schmidhuber. Planning to Be Surprised: Optimal Bayesian Exploration in Dynamic Environments. In Conference Artificial General Intelligence, 2011, A
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, 2nd edition, 2018. 1
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation. In Advances in Neural Information Processing Systems, 1999.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip TuTurk, and Pieter Abbeel. #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning. In Advances in Neural Information Processing Systems, 2017.
A
12

---

Sebastian B. Thrun and Knut Möller. On Planning And Exploration In Non- Non-Diiseete Environments. Technical report, Gesellschaft fur Mathematik und Datenverarbeitung, D-5205 St, 1991. A
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement
learning, Machine Learning, 8(3):229-256, May 1992. 1,2
Ronald J. Williams and Jing Peng. Function Optimization using Connectionist Reinforcement
Learning Algorithms. Connection Science, 3(3):241-268, 1991. A
Kenny Young and Tian Tian. MinAtar: An Atari Atari-inspired Testbed for More Efficient Reinforcement Learning Experiments. CoRR, abs/ 19903031176 2019. 1, 8.1, G
Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum Entropy Inverse Reinforcement Learning. In AAAI Conference Artificial Intelligence, 2008. 1
13

---

A ADDITIONAL RELATED WORK
This section describes short survey of exploration in RL.
Optimism in the Face of Uncertainty (OFU), Arguably, the most famous exploration strategy is OFU. Exploration methods based on OFU mainly fall in two categories: confidence-base based (Strehl & Littman, 2005; Jaksch et al., 2010; Dann & Brunskill, 2015) and bonus-basee methods (Strehl et al., 2006; Strehl & Littman, 2008; Azar et al., 2017; Jin al., 2018). While they have strong theoretical guarantees, they do not directly extend to the deep RL setting, since visitation counts need to be stored. Bellemare et (2016) generalize the notion of visitation counts and enable OFU in the deep RL setting.
In contrast OFU, ReMax uses no explicit mechanism to encourage exploration. Instead, exploration emerges through resetting and seeking the best trajectory.
Intrinsic Motivation (LM). An alternative approach that scales well to the deep RL setting is IM-based methods, which are broadly categorized to three types: prediction-error-basdd information- gain-based, and novelty-baser methods.
Prediction-eree eerane-ero--bbeee brree-baaeddddd methods construct state- sateetrrnsition dynamics model and encourage the agent to visit states (or state-action pairs) whose next state is unpredictable by the model (Stadie al., 2015; Pathak et al., 2017). This idea dates back to Schmidhuber (1991b) and Thrun & Möller (1991).
Predictioneerror- based methods may unnecessarily prefer states at which next states are unpredictable (due to e.g., noise) (Schmidhuber, 1991a). Instead, information- iotormationgain-baaae gain-based methods encourage the agent to visit states (or state-action pairs) which the agent can gain information to refine the model (Schmidhuber, 2010; Sun et al., 2011; I; Houthooft et al., 2016).
Novelty- methods literally encourages the agent to visit "novel" states (or state-action pairs). There are different ways measure the novelty, such as pseudo-count (Bellemare et al., 2016), estimated probability of state to be contained in a reply buffer (Fu et al., 2017), reachability (Savinov et al., 2019), and intra-episode diversity of states (Badia et al., 2020). Tang et al. (2017) employ a direct approach for the counts to discretize the state space and use hash.
These methods typically require the estimation of some probability density model, such state- transition dynamics and state visitation frequency. In contrast, our method does not require the estimation of any additional quantity.
RND (Burda et al., 2019) and the E-value (Fox et al., 2018) are interesting exceptions of novelty-based methods that do not require the estimation of probability density model. It would be interesting future direction to combine our method with them to determine state to reset to.
Entropy Maximization. Exploration methods based on entropy maximization are often used with policy gradient and actor-critic methods (Williams & Peng, 1991; Mnih et al., 2016; Espeholt et al., 2018). SAC is example of such methods, and it a popular deep RL algorithm for continuous control (Haarnoja et al., 2018).
While these approaches aim at inereasing the action entropy, increasing the state entropy might be more reasonable from the exploration perspective (Pitis et al., 2020; Mutti et al., 2021) because the action entropy promotes only undirected exploration. Baram al. (2021) propose to maximize a transition entropy, which is the entropy of a next state conditioned on current state, as a proxy for the state entropy.
In contrast to these methods, exploration emerges through resetting and seeking the best trajectory in ReMax, as noted before.
Tree-search. MCTS (Coulom, 2006) and its variant UCT (Kocsis & Szepesvári, 2006) are popular tree-search algorithms. ExIt (Anthony et al., 2017) combines UCT and deep learning. It uses tree search to find an improved policy, and neural networks imitate it and estimate its value. This approach has been shown to work in complex two-player games (Silver et al., 2017) too. Building on ExIt, Anthony al. (2019) propose to express simulation policy by neural network and train it by the policy gradient method, which removes the necessity of state (and state-action pair) counts in UCT. demforal-difference search (Silver, 2009) is based on similar idea, but its simulation policy is the
14

---

e-greedy policy with respect to Q-function, and the Q-function is updated during the search based on
learning.
Our algorithm can be understood as a kind of the tree-search algorithm, wherein it learns a policy maximizing the ReMax objective, and goes back some steps when a leaf node (terminal state) is reached.
Resetting. The closest to our method is probably Go-Explod So-Explore (Ecoffet et al., 2021). It essentially counts the number of visitation to each observed state, resets to less visited state, and then starts an exploration from it. Counting requires the discretization of the state space, and Go-Explore requires some domain knowledge in general for reasonable discretization.
In contrast, our method does not require visitation counts. Instead, exploration automatically emerges through the maximization of the ReMax objective with the policy gradient method. Nonetheless, learning when to reset and to which state in our method is an important and interesting direction. Using counts like Go-Explore is one way, but using RND or E-values explained above may be another.
Change of a Start-state Distribution. An idea different from but related to resetting is the change of start-state distribution. It changes the start-state distribution from MDP's initial-state distribution to one that generates states nearby goal states (Florensa et al., 2017: McAleer et al., 2019), and human-expert data distribution (Hosu & Rebedea, 2016; Peng et al., 2018). As in resetting, restart modifies the data distribution for training, whose importance is backed up by some theoretical work (Kakade & Langford, 2002; Munos, 2003; 2005). However, the start-state distribution must be chosen appropriately and often requires side information like expert data or limited task setting such as goal-condi MDPs. Therefore, did not compare our algorithm against those methods.
B REMAX OBJECTIVE IN BANDIT PROBLEM
We can analytically compute the ReMax objective in the bandit problem:
J J ReMax (T) 0.25 (1 - >) - 0.75 (1 (1 x)*
where p == Taa = 1). The first term represents the probability that the correct arm 0, and the agent plays it at least once. The second term is that of the action = 1. Fig. 1 (A) compares JRL and
ReMax (T) = -2² + 1.5p + 0.25
(10)
We can confirm that p = 0.75 (shown as the black dotted line Fig. 1 A) maximizes the ReMax objective, and the optimal policy under the ReMax objective is exploratory.
C BIASED MAZE ABLATION STUDY
We ran several additional experiments in the biased maze problem (Sec. 5) to analyze the behavior of ReMax REINFORCE in detail.
C.I BIAS TERM EFFECT
In our experiment, the standard REINFORCE got stuck in deterministic suboptimal solution (Fig. 4). This result may be confusing as the policy π (a = 1[st) aww + c) has weight parameter w; for each state. Learning an appropriate we for each state must be enough to solve the maze. It happens because the bias term allows the policy to control the "prior" behavior at unseen states. Note that does not depend on the state index i, and is expected to learn the global maze bias. Fig. 10 shows the results for the standard REINFORCE with and without bias term c. The learning rate was 0.03. Without the algorithm does not get stuck in deterministic suboptimal solution because it cannot control the behavior at unseen states. As w; is initialized to zero, the probability to select action one at state is always 0.5. This initial distribution for unseen states is good enough to keep going on the maze. However, our interest here is the algorithm behavior when the policy can control its exploratory behavior, and thus added the bias term in experiment. In this case, algorithm may fail to solve the maze it has a poor exploration mechanism, as the standard REINFORCE actually did. This is also the case when the policy uses neural network function approximator.
15

---

1,0
bias term
175
w/o
0.9
Evaluation retur
150
125
Prob a 1
100
677
0.6-
Steps
Evallaaion retum
Figure 10: REINFORCE performance with/without bias term Average evaluation return of ten runs (Left) and average probability to choose action new state (Right).
C.2 COMPARISON TO OTHER OBJECTIVES
In Sec. 7, we compared the ReMax objective and its average variant (instead of maximization). Here, we show the results of another variant and the results with different K. We consider two variants:
average: replaced the maximizing operation in ReMax objective by averaging operation. separated: we regard a trajectory tree as separated trajectories, and apply the standard RL objective and REINFORCE algorithm them.
See Fig. 11 for the results with the average variant and Fig. 12 for the separated variant. The learning rate was 0.03. Although both variants benefit from sampling with well-tuned resetting, they are not as exploratory as the ReMax objective, and we see that their performance are worse than the ReMax objective.
1.0
Evaluation return
303
250
K=1
1
K-2 (ReMax)
200
Prob =
0.7
K=4 (ReMax)
150
K=8 (ReMax)
100
K=2 (avg)
K*4 (avg)
K=8 (avg)
Sleps
Evaluation return
Figure 11: Results of average variant. Evaluation return (Left) and probability select action state (Right). Dotted lines indicate results average variant.
D PROOF OF THE RESET POLICY GRADIENT THEOREM
Theorem 1 (Reset Policy Gradient Theorem). Denote T" is the optimal trajectory in the tree, T. so that RReMax (T) = R(r") = -((s,)er- r(s, a). Moreover, denote T8xea(s:) is a subsequence Tixed(s;) T", starting at and ending at Sh. h < t. s.t. for all possible trajectories with k 2 t, and all 8 E Tixxa (8t) we have s & (ss), where x(xx) the set of admissible states to reset to in state Sy- In other words, Fixea($:) is the set of states in the optimal trajectory to which it is impossible to reset to when starting at state St, at any point following time-step, Then we have
V VelE [RReMax [
Σ
(alogms(as/ss)) (R))MMe (T) R (Tixed (8t)) be) (11)
16

---

1.0
Evaluation return
500
250
Prob( a 1
K*2 (ReMax)
200
K=4 (ReMax)
100
K=8 (ReMax)
100
K-2 (separated)
0.6-
(separated)
K=8 (separated)
Steps
Evaluation retum
Figure 12: Results of separated variant. Evaluation return (Left) and probability to select action one at new state (Right). Dotted lines indicate the results of separated variant.
Proof. Starting from the unbiasedness of Eq. have
VgE ReeMax (T) =
Σ
Ve log (RRMax - bi)
N===EEA
Σ
Vologmolalio Tologta(asss)(R(T (Thxaa))))))))))) + ( (Tixod bt)
M4 Ea
Vo lolog (ologoo(asss)(R (Txed(s))))))))) be)
u==aEEA
E
Vo log (o( (Tixxad
(12)
remains be shown that Enju, ma.e. Ve log (a(aess)) (Txxed(s:))) O. It is well known
that E V log (a) 0, for random variable Y statistically independent to because Ena [o log Th (a) Ex, (Vo log To)a)] Ex, [Y]. and E,, V log To(a) = VoE,, [1] = 0. Fi- nally, note that R (Tixed (s.)) will not change, irrespective of the choice of a, based on the definition of Thxed (s:); hence, it is statistically independent to a,, and the expectation is O.
E HYPERPARAMETEL SELECTION IN MNIST MAZE PROBLEM
the MNIST maze experiments (Sec. 6), we aimed to examine the behavior of ReMax REINFORCE when the policy appropriately utilizes the information from the image input solve the maze. Therefore, we searched the hyperparameters, the learning rate and the image input scale so that the policy solve the maze well when the image flip probability is temporarily set to 0, i.c. when the agent can solve the maze perfectly it blindly believes the MNIST image hint. We performed ten validation runs with different seeds than the test runs and grid-searched the hyperparameters. The search space was {0.0003, 0.001, 0.003, 0.01, 0.03] for the learning rate and {1.0, 0.1, 0.01} } for d. Fig. 13 shows the learning curve of top five hyperparameter experiment, we used 0.003 for the learning rate and 0.01 for d. Note that, with those hyperparameters, the policy quickly learned to reach the maximum length of maze (1000).
in validation runs. Based on this
F TRUNCATED ROLLOUTS WITH RESETTING
The rollout procedure of each rollout worker is described in Algorithm Each rollout function call receives the state Sstart: from which the rollout starts and returns a fixed-size trajectory tree and the start state Sstart for the next rollout. Note that the initial Sstart is sampled from Po- Instead of setting
17

---

1000
0.003 0.01
Ir: 0.01, 6: 0.0.01
0.03, d: 0.001
Evaluation return
800
0.003,
0.01,
200
0.0
0.2
0.4
0.6
0.8
1.0
Environment steps
1e5
Figure 13: Top five hyperparameters validation runs.
fixed number of resets K previously, the resetting will continue for many times necessary until the fixed tree size is reached. Moreover, as there is the possibility of no resets occurring if the agent does encounter terminal state, introduced a hyperparameter Preset that determines the probability of resetting at non-terminal states: 77 = 1ss) if is terminal state and Preset otherwise.
Algorithm 1 Rollout function with reset
Input: 8start
Initialize 1 = 0, Satart, X' = {s). and T = {s}
while H do
Determine whether reset or not y 77-16)
if y == then
Add to Icaf nodes
Determine where to resef i T
Update (R)
Reset SR (z)
continue
else
Sample ~ No (-() and s' ~ P(-ss,
Update T - {a, s'} and X X (s')
Update & t f and
end while
Add to leaf nodes
Sample Satart randomly from leaf node states Satart is terminal then Satart ~ po(:)
return T, Sstart
G MINATAR EXPERIMENT DETAILS
Neural network architecture. We employed the same neural network architecture in the original MinAtar study (Young & Tian, 2019) to ensure reasonable baseline algorithm performance. The architecture consists of one convolutional layer, one linear hidden layer, and one fully connected output player. The convolutional layer has 16 output channels from 3 x 3 kernel with stride size 1. Both hidden layer and output layer have 128 units. The SiLU and dSiLU activation functions (Elfwing et al., 2018) are used after the convolutional layer and hidden layer, respectively. The policy and value function share the network.
Ablation study. To confirm that the ReMax objective enhances the exploration, compared the ReMax A2C with a variant that uses resetting but not the ReMax objective as we did in the biased maze experiments (Sec. C.2). We found that the separated variant, which regards trajectory tree
18

---

reset ReMax (RaMax A2C)
reset (separated)
MinAtar/Astorrevv1
MinAmnSrraakutvi
MinAtarFFrowwayyv11
MinAtan/Soqussiivl
MrAtanSpacalnvaddssww
250
20
100
100
0.5
1.0
0.0
0.5
14
0.0
0.5
1.5
0.0
0.5
10
0.
0.5
Action probabitty
1.0
1.0
1.0
1.0
1.0
0.0
0.
0.0
6.5
Envronment stopsle?
Environment
Environment stapdle7
Environment stepste?
Figure 14: MinAtar ablation. (A) Average evaluation return for 10 runs. (B) Average probability of the selected action during the evaluation. The shaded area indicates the standard error.
a set of separated trajectories and uses RL objective, becomes more deterministic in all games and performs poorly 4/5 MinAtar games compared to the ReMax A2C.
Hyperparameter selection with validation runs. In the MinAtar experiments, we used learning rate 0.003 for all experiments, which performed best with all algorithms in the preliminary experiments. We determined the other hyperparameters using the results of validation runs. The hyperparameter for A2C (w/ entropy bonus) is 3 for controlling the scale of entropy bonus term. In ReMax A2C, the hyperparameter is Preset. probability that reset happens at non-terminal state. The separated variant of ReMax A2C also has Preset as the hyperparameter. In each of the MinAtar games, we selected the hyperparameters which maximized the average evaluation return of five validation runs. The results of validation runs are shown Table Table and Table 3.
Table I: Validation return of A2C (w/ entropy bonus)
8
Asterix
Breakout
Freeway
Seaquest
SpaceInvaders
0.01
23.634
18.609
61.859
99.253
197.897
0.03
26.744
20.997
62.766
54.888
185.309
0.1
17.291
24.331
46.463
4.044
183.844
0.3
6.194
11.813
19.375
1,209
41.784
Table 2: Validation return of ReMax A2C
Preset
Asterix
Breakout
Freeway
Seaquest
SpaceInvaders
0.0
36.353
25.544
43.081
94.934
238.434
0.02
35,659
25.947
62.284
103.978
257.588
0.05
32.403
24.744
62.409
93.475
187.694
19

---

Table 3: Validation return of separated variant
Preset
Asterix
Breakout
Freeway
Seaquest
SpaceInvaders
0.0
35.675
21.65
46.722
70.553
234.091
0.02
34.616
23.788
57.188
28.05
202.994
0.05
39.041
26.809
58.472
74.928
210.713
20


Reviews:
[{"review_id": "hcWk10caJF", "reviewer": "Reviewer_6LaJ", "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": "", "summary_of_the_paper": "The paper proposes an alternative objective for Reinforcement Learning called ReMax. The authors claim that an agent optimizing this objective naturally develops an exploratory behavior, differently from standard RL, where exploration typically should be enforced, for instance adding an entropy bonus. The main idea consists in allowing the agent to reset its trajectory to a specific state, instead of explicitly adding exploration.\nThe authors provide a policy gradient theorem to optimize such objective, and analysed the obtained policies in three worked examples where the algorithm was applied. Finally, the provided strategy is tested the MinAtar benchmark, in terms of performance w.r.t. the standard RL objective.", "summary_of_the_review": "While the idea is interesting, the provided results look still preliminary, and do not seem to be still strong enough to support the authors hypothesis. It appears that the presented method does not offer a better or equivalent way of inducing exploratory behavior w.r.t. to state-of-the-art techniques, which do not suffer from the limitation of requiring a simulator.", "strength_and_weaknesses": "## Strengths\nThe paper deals with the interesting topic of exploration, which is of paramount interest in the RL community, since it is deeply connected with the challenging topic of generalization in RL. The main goal of the article is to re-phrase the exploration problem as the necessity for the agent of visiting the same states multiple times. The author claim that this can be achieved by allowing the agent to properly reset the trajectory. \n\n## Weaknesses\nHowever, the evidence the authors provide to prove their thesis does appear completely convincing. First, it is not clear, from a theoretical point of view, how the ReMax objective optimal solutions relate to the standard objective ones. Does the optimal ReMax solution have some bias w.r.t. to the standard one? Second, it is difficult to state whether the authors claim, that the policy obtained with their strategy promote exploration, is true or not. While the strategy seems to be effective in the worked examples, in the MinAtar benchmark the entropy bonus seems to be more or equally effective w.r.t. the expected return obtained, in all the environment a part from Seaquest. \nW.r.t. this aspect, it is not clear to me why the authors affirm \"Comparing A2C (w/ entropy bonus) to ReMax A2C, there was no clear winner.\".\nIn order to better understand the effectiveness of the approach in promoting exploration, it would be interesting to compare the two strategy also w.r.t. exploration metrics.\n\nMoreover, the paper lacks a in-depth study of the impact of employing different strategy for resetting and selecting the reset state, and heuristics are used instead. In practice, these strategies could have a fundamental role in the development of the desired exploratory behavior, thus, more should be done to investigate how to properly build them.\nFinally, the proposed approach has the strong limitation of requiring the availability of a simulator, differently from entropy based approaches which don't have such requirement.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "M5YrAwAbOWy", "reviewer": "Reviewer_KQHn", "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": "", "summary_of_the_paper": "This paper introduces a new setting which utilizes resetting to previously visited states in the trajectory and continuing on from there. The objective is then defined as the max return over the resulting trajectory tree. The paper shows that directly optimizing for this objective results in stochastic, exploratory policies. ", "summary_of_the_review": "I think this is an interesting idea, and should eventually be published, but I think it is not ready in its current state. Its contributions need to be reframed, certain baselines need to be added, and the way the experimental results are presented need to be changed.  ", "strength_and_weaknesses": "Strengths\n- The paper shows the emergence of stochastic policies when resetting the agent to previous states in the trajectory and using the ReMax return. This is an interesting contribution, and could lead to future research directions in how to develop exploration policies.\n\n\nWeaknesses\n- The motivation of this paper is that directly optimizing for this objective results in a stochastic exploration policy. It would be helpful to see how this policy actually works as an exploration policy used to train another policy that is trying to optimize the original RL objective. \n- The paper compares against other methods that don't reset the simulator during training. The comparison is done based on the number of steps taken in the environment. I am not sure this is a valid comparison. Resetting the environment involves hacking the environment. Other work that hack the environment in such a fashion do so to study a phenomenon that emerges (Go-explore) which is fine. If you're comparing to other methods that don't hack the environment, you need to make allowances to account for that, since doing so is not really possible for most problems of interest. For example, if the agent resets to state A, it automatically skips the steps that another agent would need to take to get to state A. A non resetting agent would almost necessarily be at a disadvantage in terms of sample complexity if thats how the environment steps were counted.\n- Another useful baseline to compare against could be where the agent is reset, but the return is calculated as normal. This could also show whether the max operator is needed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KHqTz6fOJAQ", "reviewer": "Reviewer_Z1SD", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "", "summary_of_the_paper": "The paper proposes an approach for training exploratory policies, without adding any explicit exploration bonus. They formulate a new objective (ReMax) which allows resetting to an arbitrary prior state (hence generating new sequences), and then maximizing the best return over the set of sequences, and argue that this leads to the emergence of a stochastic policy. The paper is presented with analysis in 3 phases - random bandit arm (simple partially observable env), biased maze (deterministic fully observed env, uses simple model) and maze with image inputs (deterministic env, uses network model) .\n", "summary_of_the_review": "I am in favor of rejecting this paper because there is no comparison or discussion of the exploration performance to that of previous methods (except on the minAtar envs where the proposed method performs better on only 1/5 envs). Further, the proposed idea is very similar to that of go-explore (which obtained state of the art results on montezuma's revenge), again without any comparison or analysis of why/when this method should be used instead.", "strength_and_weaknesses": "Weaknesses\n\n1. No analysis/comparison of relation to prior exploration approaches, Quality of experimental environments\n\nThe main focus of the paper seems to be to establish that optimizing the reMax objective leads to learning a stochastic policy, and that this is desirable because it leads to better exploration performance. However, it is unclear how well the learned stochastic policy stacks up compared to prior exploration approaches, in any of the 3 phases considered (bandits, biased maze and  maze with image inputs). The only comparison to a different exploration approach was for A2C with entropy bonus on the minAtar envs, where the proposed approach gets higher return on only 1 out of 5 environments (Fig 9). There have been numerous exploration algorithms studied in tabular settings, specifically for bandits, with detailed analysis and none of them have been discussed in relation to the experiments done in phase 1. Regarding the maze environment, exploration algorithms have been shown to solve much more complex visual mazes like VizDoom [1]. Again the authors do not compare against or discuss how the proposed approach's exploration strategies would differ. This is further worrying because prior work has used exactly the settings used here (bandits and visual mazes).\n\n2. Significance of the idea\n\nThe idea of resetting to a past state to enhance exploration has been studied in Go-explore [2], as the the authors point out themselves. In go-explore, the environment is reset to states that are rarely encountered, either directly or via a goal-reaching policy. This is very similar to the idea in the proposed paper of maximizing return after resetting to an arbitrary past encountered state in the trajectory. The authors don't include any analysis or comparison against go-explore, or any discussion of which settings would the proposed resetting scheme be better. From an algorithmic perspective, it seems Go-explore should be more exploratory since it resets to arbitrary states, while this paper only considers rests to past states in the same trajectory. Furthermore, Go-explore is evaluated on very challenging exploration environments (Montezuma's revenge) as well as challenging simulated robotic manipulation environments.  \n\n[1] Pathak, Deepak, et al. \"Curiosity-driven exploration by self-supervised prediction.\" International conference on machine learning.\n[2] Ecoffet, Adrien, et al. \"Go-explore: a new approach for hard-exploration problems.\"\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "4nsiTLGnzJG", "reviewer": "Reviewer_AvuR", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "", "summary_of_the_paper": "It proposes a novel objective function (ReMax) and a novel algorithm of resetting to previous states for encouraging implicit 'stochastic exploration' policies.", "summary_of_the_review": "Based on the major weaknesses listed above, I recommend to reject this paper.", "strength_and_weaknesses": "Major Weaknesses:\n1. The paper fails to motivate the need for their proposed objective function when there are several existing exploration based objectives and algorithms that achieve state-of-the-art results on many environments.\n2. The performance of the policy obtained with ReMax objective is not shown against the actual reward of the environment we wanted to optimize. One could also define their objective as maximizing the entropy of actions and show that taking random actions at every time step maximizes their defined objective. It misses the whole point of optimizing for the actual objective and I fail to see the utility of these objectives and corresponding algorithms.\n3. There aren't any experiments comparing ReMax with other exploration based methods\n4. \"As our main focus in this study is the emergence of exploration from our ReMax objective, we only employ simple deterministic rule-based policies for πX and η\". This seems like exploration did not 'emerge' but is being imposed by the epsilon value which determines whether to explore or not given a particular state.\n5. A stochastic policy is the one where each action output has a probability associated with it. One could define a policy network in such a manner. I do not understand how an objective function can encourage stochasticity. Relatedly, what is a \"stochastic exploration\"? \n6. The proposed algorithm isn't novel. As mentioned in the paper, this idea has been explored in Go-Explore. Moreover, it seems like a very inferior version of MCTS (which has a more principled way of exploring different future states without arbitrarily resetting to previous states) \n\nMinor weaknesses:\n1. It mentions entropy bonus based objectives but fails to mention several other algorithms like count-based exploration (Tang, 2016) or intrinsic rewards (Zheng, 2018) \n2. Insufficient detail about the maze environment and results. How long is the maze? What is 'maximum sufficient fixed length'? Why does it need 10M training steps for such a seemingly simple environment? \n3. Figure-4b is unclear. Why does it cause such a huge variance with changing learning rate? Is the experiment performed with the learning rates 1e-3, 1e-2, 1e-1 or other intermediate learning rates too? Why is this comparison relevant? Aren't we just interested in the performance with best learning rate? Are other hyper parameters tuned too? \n\nQuestions:\n1. When the agent resets to a previous state, does the time_steps also reset to their old value? What prevents it from going in an infinite-loop or never-ending episodes? \n2. What is the rationale for choosing policy gradient methods and not value-based methods? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject