First return, then explore — part 4/5
Cleaned-text code points [45623, 60941). Bibliography omitted here; source.md includes it.
A fourth major difference is our introduction of increasing entropy when the agent takes too long to reach the next cell (see Methods). This entropy increases the exploration performed by policy-based Go-Explore only when necessary, thus largely avoiding the problem of derailment. Because derailment can severely lower performance, we expect that this innovation contributes substantially to the performance advantage of our implementation of policy-based Go-Explore relative to DTSIL.
A last major difference is with respect to the experiments that were performed. DTSIL was tested on Montezuma’s Revenge and Pitfall without sticky actions. In preliminary experiments with policy-based Go-Explore, we found that removing sticky actions greatly simplified the problem, and testing policy-based Go-Explore without sticky actions would have increased its performance. As a result, and as explained in methods, we did not include DTSIL in our comparison with the state of the art, but we did provide a comparison at the beginning of this section.
Besides these major differences, there are many smaller differences between the two algorithms, including differences in cell selection probabilities, SIL equations, reward clipping, maximum episode length, and hyperparameters. For a full overview of these differences, we recommend comparing the methods explained in this paper directly with the methods described in the DTSIL paper [ 159 ] .
Because the algorithm described in the DTSIL paper is similar to policy-based Go-Explore, in preliminary experiments, we tested whether some of the hyperparameters described in the DTSIL paper would improve the performance of policy-based Go-Explore. In these preliminary experiments, we found that the grid size of their cell representation (determining the granularity for the x and y coordinates of the agent) of 9x9 ∥ ∥ ∥ Note that, while an Atari frame is 160x210 pixels, the top 50 rows of pixels are unreachable in our test games and were ignored, meaning that a discretization of 18x18 pixels does result in a 9x9 grid. and their learning rate of 2.5 ⋅ 10 − 4 2.5\cdot 10^{-4} did indeed perform better than the hyperparameters we were testing at that time, and we adopted these hyperparameters from the DTSIL paper instead.
The training performance of DTSIL on Montezuma’s Revenge and Pitfall was reported by [ 159 ] ( [ 159 ] ) [ 159 ] for experiments that ran for 3.2 billion frames. However, the performance-over-time graph presented in the DTSIL paper is not directly comparable with the performance-over-time graph shown in this paper because they represent results for different selection strategies. For policy-based Go-Explore, we always report the average score achieved when returning to the highest scoring cell in the archive (obtained after training is completed by loading stored checkpoints and testing the policy 100 times). In contrast, the DTSIL graph shows a rolling average score during training, which means that its average includes returning to low-scoring cells as the algorithm attempts to explore the environment. That said, the final performance of DTSIL after 3.2 billion frames is measured over only the highest scoring trajectories, and can thus be reasonably compared with the testing performance of policy-based Go-Explore after that many frames. For Montezuma’s Revenge, we compare policy-based Go-Explore against the results that were reported in the supplementary information of the DTSIL paper for a version of DTSIL that implemented the same cell representation as the one used in the policy-based Go-Explore experiments (note, the Montezuma’s Revenge results reported in the main DTSIL paper were lower). For Pitfall, we compare against the only reported results, which were obtained with a slightly different cell representation than the one used by policy-based Go-Explore. Specifically, the DTSIL cell representation includes the cumulative positive reward achieved; the representations are otherwise the same.
### 0.14 No-ops and sticky actions
The Atari benchmark has been accepted as a common RL benchmark because of the large variety of independent environments it provides [ 146 ] . One downside of the games available in this benchmark is that they are inherently deterministic, making it possible to achieve high scores by simply memorizing state-action mappings or a fixed sequence of actions, rather than learning a policy able to generalize to the much larger number of states that are available in each game. As the community is interested in learning general policies rather than brittle solutions, many have suggested approaches to improve the benchmark, usually by adding some form of stochasticity to the game [ 123 ] .
One of the first of these approaches was to start each game with a random number (up to 30) of no-op (i.e. do nothing) actions [ 134 ] . Executing a random number of no-ops causes the game to start in a slightly different state each episode, as many game entities like enemies and items move in response to time. While no-ops add some stochasticity at the start of an episode, the game dynamics themselves are still deterministic, allowing for frame-perfect strategies that would be impossible for a human player to reproduce reliably. In addition, with only 30 different possible starting states, memorization is more difficult, but still possible.
Because of the downsides of no-ops, an alternative approach called sticky actions was recommended by the community [ 123 ] . Sticky actions mean that, at any time-step greater than 0, there exists a 25 % 25\% chance that the current action of the agent is ignored, and the previous action is executed instead. In a way, sticky actions simulate the fact that it is difficult for a human player to provide the desired input at the exact right frame; often a button is pressed a little bit too early, a little bit too late, or held down for a little too long. Given that Atari games have been designed for human play, this means that human competitive scores should be achievable despite the stochasticity introduced by sticky actions.
While sticky actions have been recommended by the community, no-ops are still widely employed in many recent papers [ 150 , 133 ] . As it is possible that no-ops add some challenges not encountered with just sticky actions, we ensure that Go-Explore is evaluated under conditions that are at least as difficult as those presented in recent papers by evaluating Go-Explore with both sticky actions and no-ops. All Go-Explore scores in this paper come from evaluations with both of these forms of stochasticity combined.
### 0.15 PPO and SIL
Both the robustification “backward” algorithm and the implementation of policy-based Go-Explore are based on the actor-critic-style PPO algorithm from [ 138 ] ( [ 138 ] ) [ 138 ] , wherein N N parallel actors collect data in mini-batches of T T timesteps, and policy updates are performed after each batch. In all PPO-based algorithms presented here, the loss of the policy and value function (both parameterized by θ \theta ) is defined as ℒ ( θ ) = ℒ P G ( θ ) + w V F ℒ V F ( θ ) + w E N T ℒ E N T ( θ ) + w L 2 ℒ L 2 + w S I L ℒ S I L ( θ ) \mathcal{L}(\theta)=\mathcal{L}^{PG}(\theta)+w_{VF}\mathcal{L}^{VF}(\theta)+w_{ENT}\mathcal{L}^{ENT}(\theta)+w_{L2}\mathcal{L}^{L2}+w_{SIL}\mathcal{L}^{SIL}(\theta) (7) ℒ P G ( θ ) \mathcal{L}^{PG}(\theta) is the policy gradient loss with PPO clipping, defined as ℒ P G ( θ ) = 𝔼 s , a ∼ π θ [ max ( − A t r t π ( θ ) , − A t clip ( r t π ( θ ) , 1 − ϵ , 1 + ϵ ) ) ] \mathcal{L}^{PG}(\theta)=\mathbb{E}_{s,a\sim\pi_{\theta}}[\mathrm{max}(-A_{t}r^{\pi}_{t}(\theta),-A_{t}\mathrm{clip}(r^{\pi}_{t}(\theta),1-\epsilon,1+\epsilon))] (8) r t π ( θ ) = π θ ( a t | s t ) π θ o l d ( a t | s t ) r^{\pi}_{t}(\theta)=\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})} (9) where s s izs a state, a a is an action sampled from the policy π θ \pi_{\theta} , r t r_{t} is the reward obtained at time-step t t , and ϵ \epsilon is a hyperparameter limiting how much the policy can be changed at each epoch. A t A_{t} is a truncated version of the generalised advantage estimation: A ^ t = δ t + ( γ λ ) δ t + 1 + … + ( γ λ ) T − t + 1 δ T − 1 \hat{A}_{t}=\delta_{t}+(\gamma\lambda)\delta_{t+1}+...+(\gamma\lambda)^{T-t+1}\delta_{T-1} (10) δ t = r t + γ V θ ( s t + 1 ) − V θ ( s t ) \delta_{t}=r_{t}+\gamma V_{\theta}(s_{t+1})-V_{\theta}(s_{t}) (11) where γ \gamma is the discount factor, λ \lambda interpolates between a 1-step return and a T T -step return, V θ V_{\theta} is the value function parameterised by θ \theta , and s t s_{t} and r t r_{t} are the state and reward at time step t t , respectively. Similar to the policy gradient loss, the value function loss ℒ V F ( θ ) \mathcal{L}^{VF}(\theta) implemented here also includes PPO-based clipping, and is defined as ℒ V F ( θ ) = 𝔼 s , a ∼ π θ [ max ( ( V θ ( s t ) − R ^ t ) 2 , ( clip ( V θ ( s t ) − V θ o l d ( s t ) , − ϵ , ϵ ) − A ^ t ) 2 ) ] \mathcal{L}^{VF}(\theta)=\mathbb{E}_{s,a\sim\pi_{\theta}}[\mathrm{max}((V_{\theta}(s_{t})-\hat{R}_{t})^{2},(\mathrm{clip}(V_{\theta}(s_{t})-V_{\theta_{old}}(s_{t}),-\epsilon,\epsilon)-\hat{A}_{t})^{2})] (12) R ^ t = V θ o l d ( s t , g t ) + A ^ t \hat{R}_{t}=V_{\theta_{old}}(s_{t},g_{t})+\hat{A}_{t} (13) The algorithms further include entropy regularization [ 179 ] ℒ E N T ( θ ) \mathcal{L}^{ENT}(\theta) and an L2 regularization penalty ℒ L 2 ( θ ) \mathcal{L}^{L2}(\theta) .
Finally, both the robustification algorithm and policy-based Go-Explore include a self-imitation learning (SIL) loss [ 158 ] , ℒ S I L ( θ ) \mathcal{L}^{SIL}(\theta) , which is calculated over previously collected data 𝒟 \mathcal{D} . While the source of 𝒟 \mathcal{D} differs between the robustification algorithm and policy-based Go-Explore (see their sub-sections for details), in both cases 𝒟 \mathcal{D} comes from previously collected trajectories τ \tau and consists of tuples ( s , a , R ) (s,a,R) , where s s is a state encountered in one of these rollouts, a a is the action that was taken in that state, and R R is the discounted reward that was collected from that state. With SIL, a small number ( N S I L N_{SIL} ) of PPO’s actors are assigned to be SIL actors. Each of these SIL actors, instead of taking actions in the environment, replays one of these trajectories τ \tau , and at each iteration the data collected by these SIL actors, forms the data set 𝒟 \mathcal{D} . The ℒ S I L ( θ ) \mathcal{L}^{SIL}(\theta) loss is then calculated as ℒ S I L ( θ ) = ℒ S I L _ P G ( θ ) + w S I L _ V F ℒ S I L _ V F ( θ ) + w S I L _ E N T ℒ S I L _ E N T ( θ ) \mathcal{L}^{SIL}(\theta)=\mathcal{L}^{SIL\_PG}(\theta)+w_{SIL\_VF}\mathcal{L}^{SIL\_VF}(\theta)+w_{SIL\_ENT}\mathcal{L}^{SIL\_ENT}(\theta) (14) ℒ S I L _ P G ( θ ) = 𝔼 s , a , R ∈ 𝒟 [ − log π θ ( a | s ) ⋅ max ( 0 , R − V θ o l d ( s ) ) ] \mathcal{L}^{SIL\_PG}(\theta)=\mathbb{E}_{s,a,R\in\mathcal{D}}[-\mathrm{log}\pi_{\theta}(a|s)\cdot\mathrm{max}(0,R-V_{\theta_{old}}(s))] (15) ℒ S I L _ V F ( θ ) = 𝔼 s , a , r ∈ 𝒟 [ 1 2 max ( 0 , R − V θ ( s ) ) 2 ] \mathcal{L}^{SIL\_VF}(\theta)=\mathbb{E}_{s,a,r\in\mathcal{D}}\left[\frac{1}{2}\mathrm{max}(0,R-V_{\theta}(s))^{2}\right] (16)
Here, ℒ S I L _ E N T ( θ ) \mathcal{L}^{SIL\_ENT}(\theta) is the entropy regularization term [ 179 ] calculated by evaluating the current policy over 𝒟 \mathcal{D} .
All architectures that feature recurrent units are updated with a variant of the truncated back-propagation-through-time algorithm called BPTT ( h ; h ′ ) (h;h^{\prime}) [ 180 ] , which is suitable when data is gathered in mini-batches. In BPTT ( h ; h ′ ) (h;h^{\prime}) , the network is updated every h ′ h^{\prime} timesteps (here h ′ = T h^{\prime}=T , the number of timesteps in the mini-batch), but it is unfolded for h ≥ h ′ h\geq h^{\prime} timesteps (here h = 1.5 T h=1.5T ), meaning that gradients can flow beyond the boundaries of the mini-batch. To facilitate BPTT ( h ; h ′ ) (h;h^{\prime}) , the first mini-batch of each run consists of 1.5 T 1.5T timesteps.
### 0.16 The backward algorithm
The “backward algorithm” [ 149 ] operates by placing the agent close to the end of the trajectory and running PPO until the performance of the agent matches or exceeds that of the demonstration. Once that is achieved, the agent’s starting point is moved closer to the trajectory’s beginning and the process is repeated. The algorithm thus learns the demonstration in a backward order.
The original version of the backward algorithm relied on a single demonstration due to the assumption that obtaining human demonstrations was expensive. In our case, however, obtaining multiple demonstrations is easy and cheap by simply re-running the exploration phase, which is why we modified the algorithm to utilise multiple demonstrations: at the start of each episode, a demonstration is chosen at random to provide the starting point for the agent. For Atari, 10 demonstrations from different runs of the exploration phase were used for each robustification. In Atari, the demonstration was extracted by finding all trajectories that reached an end-of-episode state (to prevent selection of length 0 trajectories in games with exclusively negative rewards, see Methods “ 0.5 Evaluation ”), and extracting the shortest one among those with the highest score. For robotics, because it was possible to extract diverse demonstrations from a single run of the exploration phase (this was not possible in Atari because high-scoring trajectories within a given Atari run tended to share most of their actions), 10 demonstrations from the same runs were used for robustification. In robotics, the first demonstration corresponds to the shortest successful trajectory (i.e. the shortest trajectory that puts the object in the shelf), while each subsequent demonstration corresponds to the successful trajectory with the highest mean difference from all previously selected trajectories, where the difference between two trajectories is given by ∑ i = 1 L I ( τ i a ≠ τ i b ) L \frac{\sum_{i=1}^{L}I(\tau^{a}_{i}\neq\tau^{b}_{i})}{L} ( τ a \tau^{a} and τ b \tau^{b} are the list of actions being compared, L = min ( | τ a | , | τ b | ) L=\min(|\tau^{a}|,|\tau^{b}|) , I I is the indicator function). Because actions are continuous, meaning that it is exceedingly unlikely for two independently sampled actions to be the same, τ i a = τ i b \tau^{a}_{i}=\tau^{b}_{i} only for parts where the trajectories are identical because they were branched from the same intermediate trajectory. As such, this metric effectively measures to what degree the two trajectories have a shared history, and prefers trajectories that share as little history as possible. In both cases, SIL was also performed on the set of demonstrations provided to the backward algorithm (see “PPO and SIL” section). Each robustification run used demonstrations from different, non-overlapping exploration phase runs (10 exploration runs for Atari, 1 for robotics).