text:
\section{Hyperparameter tuning}
\label{app:hparam_tuning}

All bonus based methods are tuned with respect to their final performance on \textsc{Montezuma's Revenge}{} after training on 200 million frames averaged over five runs.
When different hyper parameter settings led to comparable final performance we chose the one that achieve the performance the fastest.
\subsection{Rainbow and Atari preprocessing}

We used the standard  Atari preprocessing from \citet{mnih2015human}. Following \citet{machado2018revisiting} recommendations we enable sticky actions and deactivated the termination on life loss heuristic.
The remaining hyperparameters were chosen to match \citet{hessel2018rainbow} implementation.

\begin{center}
\begin{tabular}{ l|c}
 \multicolumn{1}{c}{Hyperparameter} & Value \\
  \hline
 Discount factor $\gamma$ & 0.99 \\
 Min history to start learning & 80K frames \\
 Target network update period & 32K frames \\
 Adam learning rate & $6.25 \times 10^{-5}$  \\
 Adam $\epsilon$ & $1.5 \times 10^{-4}$ \\
 Multi-step returns $n$ & 3 \\
 Distributional atoms & 51 \\
 Distributional min/max values & [-10, 10] \\
\end{tabular}
\end{center}
Every method except NoisyNets is trained with $\epsilon$-greedy following the scheduled used in Rainbow with $\epsilon$ decaying from $1$ to $0.01$ over 1M frames.

\subsection{Hyperparameter tuning on \textsc{Montezuma's Revenge}{}}
\subsubsection{NoisyNets}
We did not tune NoisyNets. We kept the original hyperparameter $\sigma_0 = 0.5$ as in \citet{fortunato18noisy} and \citet{hessel2018rainbow}.

\subsubsection{Pseudo-counts}
We followed \citeauthor{bellemare2016unifying}'s preprocessing, inputs are $42 \times 42$ greyscale images, with pixel values quantized to 8 bins.

\textbf{CTS}: We tuned the scaling factor $\beta$. We ran a sweep for $\beta \in \{ 0.5, 0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001 \}$ and found that $\beta = 0.0005$ worked best.

\textbf{PixelCNN}: We tuned the scaling factor and the prediction gain decay constant $c$. We ran a sweep with the following values: $\beta \in \{ 5.0, 1.0, 0.5, 0.1, 0.05 \}$, $c \in \{5.0, 1.0, 0.5, 0.1, 0.05 \}$ and found $\beta = 0.1$ and $c = 1.0$ to work best.

\subsection{ICM}
We tuned the scaling factor and the scalar $\alpha$ that weighs the inverse model loss against the forward model. We ran a sweep with $\alpha = \{0.4, 0.2, 0.1, 0.05, 0.01, 0.005 \}$ and $\beta = \{2.0, 1.0, 0.5, 0.1, 0.05, 0.01, 0.005, 0.001, 0.0005 \}$. We found $\alpha = 0.005$ and $\beta = 0.005$ to work best.

\subsection{RND}
Following \citet{burda2018exploration} we did not clip the intrinsic reward while the extrinsic reward was clipped. We tuned the reward scaling factor $\beta$ and learning rate used in Adam \citep{kingma2014adam} by the RND optimizer. We ran a sweep with $\beta = \{0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001, 0.0005, 0.00001, 0.000005 \}$ and $\text{lr} = \{ 0.005, 0.001, 0.0005, 0.0002, 0.0001, 0.00005 \}$.
We found that $\beta = 0.00005$ and $\text{lr} = 0.0001$ worked best.

\subsection{Hyperparameter tuning on second training set (Section \ref{sec:hyp_tuning})}

\subsubsection{Pseudo-counts CTS}
We ran a sweep for $\beta \in \{ 0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001 \}$ and found that $\beta = 0.0001$ worked best.

\subsection{RND}
We did not tune the learning rate and kept $\text{lr} = 0.0001$.
We ran a sweep for $\beta = \{[0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001, 0.00005 \}$ and found that $\beta = 0.00005$ worked best.

\section{Taxonomy of exploration on the ALE}
\label{app:taxonomy}

\citeauthor{bellemare2016unifying}'s taxonomy of exploration propose a classification of Atari 2600 games in terms of difficulty of exploration. It is provided in Table \ref{tab:taxonomy}.

\begin{table}[h!]
\caption{A classification of Atari 2600 games based on their exploration difficulty.}
\begin{center}
\resizebox{\columnwidth}{!}{%
\begin{tabular}{ |c  c | c || c | c | c |  }
 \hline
 \multicolumn{3}{|c}{Easy Exploration} & \multicolumn{2}{c|}{Hard exploration} \\
 \hline \hline
 \multicolumn{2}{|c|}{Human Optimal} & Score Exploit & Dense Reward & Sparse Reward \\
 \hline
 \textsc{Assault} & \textsc{Asterix} & \textsc{Beam Rider} & \textsc{Alien} & \textsc{Freeway} \\
 \textsc{Asteroids} & \textsc{Atlantis} & \textsc{Kangaroo} & \textsc{Amidar} & \textsc{Gravitar} \\
 \textsc{Battle Zone} & \textsc{Berzerk} & \textsc{Krull} & \textsc{Bank Heist} & \textsc{Montezuma's Revenge} \\
 \textsc{Bowling} & \textsc{Boxing} & \textsc{Kung-fu Master} & \textsc{Frostbite} & \textsc{Pitfall!} \\
 \textsc{Breakout} & \textsc{Centipede} & \textsc{Road Runner} & \textsc{H.E.R.O} & \textsc{Private Eye} \\
 \textsc{Chopper Cmd} & \textsc{Crazy Climber} & \textsc{Seaquest} & \textsc{Ms. Pac-Man} & \textsc{Solaris} \\
 \textsc{Defender} & \textsc{Demon Attack} & \textsc{Up N Down} & \textsc{Q*bert} & \textsc{Venture} \\
 \textsc{Double Dunk} & \textsc{Enduro} & \textsc{Tutankham} & \textsc{Surround} & \\
 \textsc{Fishing Derby} & \textsc{Gopher} & & \textsc{Wizard of Wor} & \\
 \textsc{Ice Hockey} & \textsc{James Bond} & & \textsc{Zaxxon} & \\
 \textsc{Name this game} & \textsc{Phoenix} & & & \\
 \textsc{Pong} & \textsc{River Raid} & & & \\
 \textsc{Robotank} & \textsc{Skiing} & & & \\
 \textsc{Space Invaders} & \textsc{Stargunner} & & & \\
 \hline
\end{tabular}
}
\end{center}
\label{tab:taxonomy}
\end{table}

\section{Additional figures}
\label{sec:curves}

The variance of the return on \textsc{Montezuma's Revenge}{} is high because the reward is a step function, for clarity we also provide all the training curves in Figure~\ref{fig:montezuma_training_curves}

\begin{figure*}[!ht]
\centering
\captionsetup{justification=centering}
\begin{subfigure}{0.5\textwidth}
    \centering
  \includegraphics[width=\linewidth]{figures/montezuma_trajectories/CTS_montezuma.pdf}
  \label{fig:cts_montezuma}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
    \centering
  \includegraphics[width=\linewidth]{figures/montezuma_trajectories/PixelCNN_montezuma.pdf}
  \label{fig:pixelcnn_montezuma}
\end{subfigure}%
\vspace{1mm}
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/montezuma_trajectories/ICM_montezuma.pdf}
  \label{fig:icm_montezuma}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/montezuma_trajectories/RND_montezuma.pdf}
  \label{fig:rnd_montezuma}
\end{subfigure}%
\vspace{1mm}
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/montezuma_trajectories/NoisyNets_montezuma.pdf}
  \label{fig:noisy_montezuma}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/montezuma_trajectories/greedy_montezuma.pdf}
  \label{fig:greedy_montezum}
\end{subfigure}%
\caption{Training curves on \textsc{Montezuma's Revenge}}
\label{fig:montezuma_training_curves}
\end{figure*}

We also provide training curves presented in the main paper in larger format.

\begin{figure*}
\centering
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/Gravitar.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
    \centering
  \includegraphics[width=\linewidth]{figures/appendix/PrivateEye.pdf}
\end{subfigure}%
\vspace{2mm}
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/Venture.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/Solaris.pdf}
\end{subfigure}%
\vspace{2mm}
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/Pitfall.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/Freeway.pdf}
\end{subfigure}%
\caption{Evaluation of different bonus-based exploration methods on the set of hard exploration games with sparse rewards. Curves are average over 5 runs and shaded area denotes variance.}
\label{fig:appendix_hard}
\end{figure*}

\begin{figure*}
\begin{subfigure}{0.5\textwidth}
    \centering
  \includegraphics[width=\linewidth]{figures/appendix/Asterix.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/SpaceInvaders.pdf}
\end{subfigure}%
\vspace{2mm}
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/BeamRider.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/Freeway_2.pdf}
\end{subfigure}%
\vspace{2mm}
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/Seaquest.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\hspace*{10mm}
  \includegraphics[width=0.5\linewidth]{figures/all_games/legend.png}
  \label{fig:legend_all_app}
\end{subfigure}%
\caption{Evaluation of different bonus-based exploration methods on the Atari training set. Curves are average over 5 runs and shaded area denotes variance.}
\label{fig:appendix_easy}
\end{figure*}

\begin{figure*}
\centering
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_MontezumaRevenge.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_Gravitar.pdf}
\end{subfigure}%
\vspace{2mm}
\begin{subfigure}{0.5\textwidth}
    \centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_PrivateEye.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_Venture.pdf}
\end{subfigure}%
\vspace{2mm}
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_Solaris.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_Pitfall.pdf}
\end{subfigure}%
\caption{Evaluation of different bonus-based exploration methods on the set of hard exploration games with sparse rewards. Exploration methods are trained for one billion frames. Curves are average over 5 runs and shaded area represents variance.}
\label{fig:app_1b_hard}
\end{figure*}%

\begin{figure*}

\begin{subfigure}{0.5\textwidth}
    \centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_Asterix.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_Freeway.pdf}
\end{subfigure}%
\vspace{2mm}
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_BeamRider.pdf}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
\centering
  \includegraphics[width=\linewidth]{figures/appendix/1b_SpaceInvaders.pdf}
\end{subfigure}%
\vspace{2mm}
\begin{subfigure}{0.5\textwidth}
  \includegraphics[width=\linewidth]{figures/appendix/1b_Seaquest.pdf}
\end{subfigure}%
\label{fig:app_1b_easy}
\begin{subfigure}{0.5\textwidth}
\hspace*{10mm}
  \includegraphics[width=0.5\linewidth]{figures/all_games/legend.png}
  \label{fig:legend_app}
\end{subfigure}%
\caption{Evaluation of different bonus-based exploration methods on the Atari training set. Exploration methods are trained for one billion frames. Curves are average over 5 runs and shaded area represents variance.}
\end{figure*}

\begin{figure*}[!h]
\centering
\begin{subfigure}{0.7\textwidth}
    \centering
  \includegraphics[width=\linewidth]{figures/appendix/legend.png}
\end{subfigure}%
\vspace{2.5mm}
\begin{subfigure}{\textwidth}
    \centering
   \includegraphics[width=\textwidth, height=0.9\textheight]{figures/all_games.pdf}
\end{subfigure}%
\captionsetup{justification=centering}
\caption{Training curves of Rainbow with $\epsilon$-greedy, CTS, PixelCNN, NoisyNets, ICM and RND.}
\label{fig:all_games}
\end{figure*}

\begin{figure*}[h!]
\centering
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth,height=0.18\textheight]{figures/appendix/cts_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth,height=0.18\textheight]{figures/appendix/rnd_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth,height=0.18\textheight]{figures/appendix/pixelcnn_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth,height=0.18\textheight]{figures/appendix/icm_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth,height=0.18\textheight]{figures/appendix/noisy_vs_rainbow.pdf}
    \end{subfigure}%
\caption{Improvements (in percentage of AUC) of Rainbow with various exploration methods over Rainbow with $\epsilon$-greedy exploration in 60 Atari games when hyperparameters are tuned on \textsc{Montezuma's Revenge}{}. The game \textsc{Montezuma's Revenge}{} is represented in purple.}
\label{fig:all_games_appendix}
\end{figure*}

\begin{figure*}[h!]
\centering
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth,height=0.18\textheight]{figures/appendix/cts_vs_rainbow_new_tuning.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth,height=0.18\textheight]{figures/appendix/rnd_vs_rainbow_new_tuning.pdf}
    \end{subfigure}%
\caption{Improvements (in percentage of AUC) of Rainbow with CTS and RND over Rainbow with $\epsilon$-greedy exploration in 60 Atari games when hyperparameters have been tuned on \textsc{Seaquest}, \textsc{Qbert}, \textsc{Pong}, \textsc{Breakout} and \textsc{Asterix}. The game \textsc{Montezuma's Revenge}{} is represented in purple. Games in the training set have stars on top of their bar.}
\end{figure*}

\newpage
\begin{table}[h!]
\caption{Raw scores for all games after 10M training frames}
\begin{center}
\resizebox{!}{0.38\paperheight}{%
\begin{tabular}{l|rrrrrr}
\toprule
Games &          $\epsilon$-greedy &               RND &              CTS &          PixelCNN &              ICM &        NoisyNets \\
\midrule
AirRaid          &           5393.2 &            5374.7 &           4084.7 &   \textbf{5425.8} &           5374.7 &           4361.4 \\
Alien            &           1289.6 &   \textbf{1352.1} &           1250.6 &            1228.0 &           1310.6 &           1222.0 \\
Amidar           &            335.0 &             286.8 &            345.1 &    \textbf{428.0} &            364.9 &            324.7 \\
Assault          &           1459.5 &            1453.4 &           1303.6 &   \textbf{1641.9} &           1431.7 &           1080.4 \\
Asterix          &           2777.5 &            2793.9 &  \textbf{2841.0} &            2748.0 &           2736.7 &           2698.6 \\
Asteroids        &            759.6 &             848.4 &            722.7 &             800.5 &            789.5 &  \textbf{1117.0} \\
Atlantis         &         117166.5 &          172134.9 &          99510.6 & \textbf{184420.5} &         148927.5 &         109464.9 \\
BankHeist        &            901.5 &             896.5 &            426.7 &             756.8 &            904.4 &  \textbf{1039.9} \\
BattleZone       & \textbf{23909.5} &           22374.9 &           9734.0 &           22822.1 &          22575.3 &          11581.6 \\
BeamRider        &           5475.7 &            5135.5 &           4066.8 &            3415.4 &  \textbf{5796.6} &           3845.6 \\
Berzerk          &            419.1 &             442.5 &            446.8 &             435.5 &            430.8 &   \textbf{476.0} \\
Bowling          &             40.8 &              39.0 &    \textbf{92.6} &              47.6 &             35.5 &             27.1 \\
Boxing           &             75.7 &              74.8 &             45.2 &     \textbf{76.0} &             74.7 &             57.5 \\
Breakout         &             49.2 &     \textbf{49.5} &             45.6 &              46.4 &             48.8 &             44.7 \\
Carnival         &  \textbf{4644.9} &            4375.3 &           3658.4 &            4138.8 &           4317.0 &           2291.5 \\
Centipede        &           4845.3 &            5009.4 &           4731.0 &            4963.4 &  \textbf{5110.2} &           4912.0 \\
ChopperCommand   &  \textbf{2494.5} &             913.6 &           2293.9 &            2420.5 &           2376.6 &           1899.1 \\
CrazyClimber     &         107706.9 &          105940.9 &          90549.0 & \textbf{107724.2} &         104783.2 &          96063.8 \\
DemonAttack      &           2932.2 &            3135.8 &           1442.0 &            2564.6 &  \textbf{3153.3} &           1864.6 \\
DoubleDunk       &            -18.4 &             -18.1 &            -19.4 &             -18.2 &            -19.0 &    \textbf{-8.2} \\
ElevatorAction   &             29.1 &             114.7 &              0.0 &    \textbf{141.8} &             22.9 &              0.0 \\
Enduro           &           1657.1 &            1719.1 &           1230.0 &   \textbf{1767.0} &           1727.4 &           1272.9 \\
FishingDerby     &    \textbf{15.5} &               9.7 &             13.8 &              15.0 &             14.5 &             10.8 \\
Freeway          &    \textbf{32.3} &              32.2 &             32.2 &              32.3 &             32.2 &             31.7 \\
Frostbite        &           3035.7 &   \textbf{3286.5} &           3078.9 &            2787.7 &           2854.7 &           2913.0 \\
Gopher           &           4047.6 &            4224.1 &           4295.8 &   \textbf{4349.7} &           4266.1 &           3760.1 \\
Gravitar         &            229.4 &    \textbf{236.8} &            130.0 &             235.1 &            225.8 &            211.3 \\
Hero             &          10730.5 &           10858.1 &          12753.7 &  \textbf{12999.9} &          11808.4 &           9441.1 \\
IceHockey        &             -5.0 &     \textbf{-4.9} &            -11.9 &              -5.9 &             -5.1 &             -7.7 \\
Jamesbond        &            520.3 &             508.0 &            473.2 &    \textbf{536.0} &            517.0 &            484.6 \\
JourneyEscape    &          -2376.4 &           -2299.0 &          -9208.8 &           -2463.4 &          -2414.1 & \textbf{-1784.3} \\
Kangaroo         &           5233.1 &            5537.0 &           1747.0 &            5266.2 &  \textbf{5823.1} &           5147.0 \\
Krull            &           5941.1 &            5997.8 &           5620.4 &            5999.8 &           5935.5 &  \textbf{6195.1} \\
KungFuMaster     &          19824.1 &           17676.9 & \textbf{22668.2} &           21673.9 &          19199.3 &          19150.5 \\
MontezumaRevenge &              0.5 &               1.5 &   \textbf{231.8} &              17.8 &              0.0 &             13.2 \\
MsPacman         &           2371.0 &            2271.4 &  \textbf{2452.5} &            2443.6 &           2424.6 &           2436.4 \\
NameThisGame     &           9086.7 &            8561.7 &           7402.8 &   \textbf{9089.4} &           8820.6 &           7590.1 \\
Phoenix          &           4758.3 &            4790.7 &           4498.7 &            4840.8 &           4788.1 &  \textbf{4868.0} \\
Pitfall          &            -13.3 &             -10.4 &    \textbf{-2.4} &             -11.1 &             -5.6 &             -3.0 \\
Pong             &             14.6 &              14.0 &              9.8 &              14.3 &    \textbf{15.5} &             12.4 \\
Pooyan           &           3917.3 &            3867.7 &           3885.9 &   \textbf{3996.4} &           3722.1 &           3623.4 \\
PrivateEye       &             77.4 &    \textbf{180.3} &           -903.9 &              89.1 &            116.5 &             78.9 \\
Qbert            &           7025.6 &            7442.4 &           5466.8 &            5885.5 &  \textbf{8090.2} &           4363.0 \\
Riverraid        &           4578.2 &            4904.3 &  \textbf{6830.2} &            5002.2 &           4739.3 &           3820.5 \\
RoadRunner       &          33743.4 &           34944.0 & \textbf{39145.9} &           35081.6 &          34109.7 &          33649.4 \\
Robotank         &             22.5 &     \textbf{22.7} &              1.8 &              17.9 &             22.6 &             18.5 \\
Seaquest         &           1711.6 &   \textbf{1744.0} &           1476.0 &            1631.9 &           1647.4 &           1155.9 \\
Skiing           &         -22580.5 & \textbf{-21378.9} &         -27888.8 &          -23652.6 &         -23040.9 &         -22729.0 \\
Solaris          &           1164.7 &            1103.4 &           1108.2 &             966.8 &           1254.2 &  \textbf{1495.9} \\
SpaceInvaders    &            793.6 &             764.5 &            641.6 &    \textbf{800.6} &            780.6 &            687.0 \\
StarGunner       &           1533.2 &            1523.3 &           1579.6 &            1530.3 &           1500.3 &  \textbf{1587.5} \\
Tennis           &             -2.8 &     \textbf{-0.4} &            -21.2 &              -7.5 &             -1.0 &             -1.0 \\
TimePilot        &           2969.7 &            3001.6 &  \textbf{4516.1} &            2810.5 &           3049.9 &           2710.6 \\
Tutankham        &            187.0 &             207.2 &             54.3 &    \textbf{232.3} &            169.2 &            162.2 \\
UpNDown          &          14237.9 &           11060.1 &           4373.8 &           12494.2 &          13220.7 & \textbf{16120.4} \\
Venture          &             25.0 &              16.4 &             13.3 &              17.8 &             19.0 &    \textbf{34.9} \\
VideoPinball     & \textbf{33347.6} &           30284.0 &          31173.0 &           33294.5 &          30661.6 &          22802.8 \\
WizardOfWor      &           2432.5 &   \textbf{2865.3} &           1451.5 &            2376.6 &           2191.3 &           1568.7 \\
YarsRevenge      &          10349.2 &           11161.2 &           9926.9 &           11002.0 & \textbf{11415.6} &          10930.2 \\
Zaxxon           &           4282.7 &   \textbf{4707.7} &           3603.9 &            3766.4 &           4266.8 &           3016.6 \\
\bottomrule
\end{tabular}
}
\end{center}
\end{table}

\newpage
\begin{table}[h!]
\caption{Raw scores for all games after 50M training frames}
\begin{center}
\resizebox{!}{0.385\paperheight}{%
\begin{tabular}{l|rrrrrr}
\toprule
Games &           $\epsilon$-greedy &              RND &              CTS &         PixelCNN &               ICM &         NoisyNets \\
\midrule
AirRaid          &           12081.8 & \textbf{13005.2} &          11016.9 &          12399.0 &           11392.8 &           10433.7 \\
Alien            &            2114.1 &           2004.9 &           1969.4 &           2200.6 &            1979.4 &   \textbf{2308.3} \\
Amidar           &            1535.6 &           1140.6 &           1469.5 &  \textbf{1791.9} &            1504.0 &            1337.2 \\
Assault          &            2384.1 &           2423.8 &           2265.6 &           2465.2 &            2555.6 &   \textbf{3050.1} \\
Asterix          &            5722.4 &           6488.7 &           4959.4 &           5439.3 &            5931.7 &  \textbf{13981.5} \\
Asteroids        &            1363.7 &           1409.2 &           1095.8 &           1315.3 &            1247.5 &   \textbf{1901.6} \\
Atlantis         & \textbf{831286.0} &         807958.0 &         805574.0 &         816578.0 &          763538.0 &          827702.0 \\
BankHeist        &            1113.8 &           1070.0 &  \textbf{1154.6} &           1005.5 &            1028.9 &            1104.3 \\
BattleZone       &           30959.7 &          31271.5 &          16167.4 &          31011.8 &  \textbf{32357.5} &           30606.6 \\
BeamRider        &            5550.9 &  \textbf{5782.2} &           4726.8 &           5504.9 &            5633.0 &            5636.4 \\
Berzerk          &             697.9 &            643.8 &            700.4 &            662.8 &             667.5 &    \textbf{731.7} \\
Bowling          &              41.4 &             42.6 &             45.5 &    \textbf{56.5} &              36.1 &              30.0 \\
Boxing           &              95.7 &             95.8 &             91.2 &             95.8 &              96.0 &     \textbf{98.0} \\
Breakout         &              48.3 &             48.3 &             48.6 &             49.7 &              51.2 &     \textbf{82.3} \\
Carnival         &            4936.0 &           4554.8 &  \textbf{5199.7} &           4600.6 &            4644.4 &            4110.6 \\
Centipede        &            4312.1 &           4568.4 &           4235.0 &           4544.2 &            4652.0 &   \textbf{4986.9} \\
ChopperCommand   &            6438.2 &           2087.1 &  \textbf{6504.8} &           6010.3 &            5840.4 &            5589.4 \\
CrazyClimber     &          131002.1 &         132982.7 &         126655.8 &         133039.8 &          130491.3 & \textbf{133873.7} \\
DemonAttack      &            6021.3 &           5590.7 &           4499.4 &           4985.7 &            6052.2 &  \textbf{13754.6} \\
DoubleDunk       &              17.9 &             15.4 &            -11.0 &    \textbf{20.0} &              18.0 &              -0.6 \\
ElevatorAction   &           55982.0 & \textbf{66996.0} &              0.0 &          52254.0 &           58349.4 &           17514.5 \\
Enduro           &            2173.9 &           2076.4 &           2105.2 &           2119.4 &            1683.3 &   \textbf{2180.9} \\
FishingDerby     &              35.1 &             32.7 &             23.9 &             37.2 &     \textbf{37.5} &              33.6 \\
Freeway          &              33.4 &             33.3 &             33.3 &             33.3 &              33.4 &     \textbf{33.7} \\
Frostbite        &            5773.9 &           6162.9 &  \textbf{6334.9} &           5759.3 &            5551.6 &            6010.9 \\
Gopher           &            6564.7 &           6445.1 &           6111.8 &           6688.1 &            6761.3 &  \textbf{10255.0} \\
Gravitar         &   \textbf{1148.3} &            990.6 &            635.6 &            953.9 &             950.7 &             903.5 \\
Hero             &           29014.5 &          30679.0 &          29273.5 & \textbf{31150.1} &           30756.5 &           27165.2 \\
IceHockey        &               1.3 &              1.0 &             -3.8 &              1.8 &      \textbf{1.8} &               0.9 \\
Jamesbond        &             600.8 &            633.0 &            669.5 &   \textbf{712.6} &             622.9 &             707.7 \\
JourneyEscape    &           -1448.3 &          -1422.1 &          -3424.2 &          -1437.9 &           -1541.1 &  \textbf{-1304.6} \\
Kangaroo         &           12426.5 & \textbf{12731.0} &          12333.7 &          11771.7 &           12606.5 &           12428.5 \\
Krull            &   \textbf{4522.9} &           4065.4 &           4041.7 &           4051.8 &            4319.1 &            4341.5 \\
KungFuMaster     &           26929.2 &          22972.3 &          25573.2 &          26135.5 &           25883.8 &  \textbf{30161.7} \\
MontezumaRevenge &             553.3 &  \textbf{2789.6} &           2550.4 &           2528.5 &            1160.7 &            2492.9 \\
MsPacman         &            3185.3 &           3218.8 &           3272.4 &           3400.7 &            3310.0 &   \textbf{3768.5} \\
NameThisGame     &            8304.9 &           8106.9 &           6978.1 &           8467.3 &            8222.7 &  \textbf{10883.2} \\
Phoenix          &            5862.1 &           7434.0 &           4781.2 &           7664.7 &            7369.7 &  \textbf{11873.4} \\
Pitfall          &              -4.0 &    \textbf{-3.6} &            -13.9 &            -10.1 &             -13.1 &              -4.5 \\
Pong             &              19.5 &             19.0 &    \textbf{19.9} &             19.2 &              19.1 &              19.2 \\
Pooyan           &            3703.3 &           3884.6 &           3724.3 &           3727.1 &            3775.3 &   \textbf{4561.7} \\
PrivateEye       &             127.6 &            319.6 &            948.6 &            679.7 &  \textbf{12156.0} &              96.2 \\
Qbert            &           15498.0 & \textbf{17014.5} &          14804.3 &          16463.1 &           16786.7 &           16780.0 \\
Riverraid        &           14935.6 &          15797.5 &          15747.2 & \textbf{16137.5} &           15590.9 &           10469.4 \\
RoadRunner       &           50559.5 &          50349.6 & \textbf{50915.7} &          49905.1 &           50042.5 &           46314.5 \\
Robotank         &              62.2 &             62.0 &              4.6 &             59.4 &              60.5 &     \textbf{63.9} \\
Seaquest         &            4915.9 &           5036.7 & \textbf{19227.6} &           3708.0 &            3331.5 &            4433.2 \\
Skiing           & \textbf{-21899.7} &         -24633.1 &         -23028.8 &         -25674.1 &          -24216.7 &          -25306.5 \\
Solaris          &            2272.7 &  \textbf{2347.2} &           1921.1 &           1444.2 &            2076.0 &            2063.7 \\
SpaceInvaders    &            1904.4 &           1881.2 &           1275.9 &  \textbf{2007.6} &            1827.3 &            1888.8 \\
StarGunner       &           35867.0 &          38744.5 &          33868.7 &          39416.2 &           41771.6 &  \textbf{42542.3} \\
Tennis           &              -0.1 &              0.0 &    \textbf{22.1} &            -14.3 &              -0.7 &              -1.2 \\
TimePilot        &            8901.6 &  \textbf{9295.9} &           4785.5 &           8927.9 &            9220.9 &            8956.7 \\
Tutankham        &             227.9 &   \textbf{235.1} &             96.6 &            234.6 &             220.8 &             201.8 \\
UpNDown          &           15097.4 &          13116.4 &           9151.3 &          14436.6 &           14621.5 &  \textbf{39546.4} \\
Venture          &   \textbf{1460.4} &           1435.4 &           1117.7 &           1426.2 &            1443.2 &            1220.3 \\
VideoPinball     &          398511.1 &         419047.9 &         414727.1 &         386829.1 & \textbf{452874.2} &          154968.4 \\
WizardOfWor      &            6941.0 &           5932.6 &           4108.2 &           6226.2 &   \textbf{7027.8} &            6906.1 \\
YarsRevenge      &           30769.2 &          36086.1 &          30596.5 &          32049.2 &           30721.4 &  \textbf{36136.7} \\
Zaxxon           &           13161.2 &          13341.5 &           7223.7 &          11332.8 &           13177.1 &  \textbf{13936.2} \\
\bottomrule
\end{tabular}
}
\end{center}
\end{table}

\newpage
\begin{table}[h!]
\caption{Raw scores for all games after 100M training frames}
\begin{center}
\resizebox{!}{0.385\paperheight}{%
\begin{tabular}{l|rrrrrr}
\toprule
Games &           $\epsilon$-greedy &              RND &              CTS &          PixelCNN &      ICM &         NoisyNets \\
\midrule
AirRaid          &           11744.3 &          12081.2 &          11819.6 &  \textbf{13292.9} &  12744.2 &           10096.6 \\
Alien            &            2696.7 &           2531.9 &           2519.4 &            2761.6 &   2593.9 &   \textbf{3237.0} \\
Amidar           &            2033.1 &           1527.9 &           1797.0 &   \textbf{2295.1} &   2167.2 &            1872.9 \\
Assault          &            2946.8 &           2832.5 &           2535.3 &            2839.1 &   2574.8 &   \textbf{3718.9} \\
Asterix          &            9279.4 &          10785.7 &           6083.1 &            8540.0 &  10661.5 &  \textbf{26367.6} \\
Asteroids        &            1374.3 &           1423.3 &           1156.8 &            1391.8 &   1266.7 &   \textbf{2169.9} \\
Atlantis         & \textbf{859040.0} &         799144.2 &         747436.0 &          852382.0 & 754256.0 &          857076.0 \\
BankHeist        &            1106.0 &           1090.6 &           1131.7 &             932.2 &   1013.4 &   \textbf{1156.8} \\
BattleZone       &           32850.4 &          30523.1 &          19369.3 &           35162.6 &  32625.4 &  \textbf{35483.1} \\
BeamRider        &            6044.1 &           5977.9 &           5197.7 &            5644.8 &   6070.2 &   \textbf{6117.3} \\
Berzerk          &             746.4 &            709.1 &            788.6 &             728.7 &    715.5 &    \textbf{894.2} \\
Bowling          &              36.0 &             32.5 &             45.5 &     \textbf{61.9} &     31.5 &              29.9 \\
Boxing           &              97.5 &             97.6 &             96.6 &              96.9 &     97.7 &     \textbf{98.7} \\
Breakout         &              56.9 &             59.8 &             57.7 &              58.1 &     63.2 &     \textbf{75.8} \\
Carnival         &            4805.4 &           4743.3 &  \textbf{5040.4} &            4427.9 &   4623.5 &            4480.7 \\
Centipede        &            4460.7 &           4909.7 &           4701.9 &            4613.3 &   4700.2 &   \textbf{5154.6} \\
ChopperCommand   &   \textbf{9812.9} &           2306.4 &           9742.8 &            8967.3 &   9238.2 &            7611.4 \\
CrazyClimber     &          135531.2 &         139641.8 &         133805.3 &          139011.0 & 138967.9 & \textbf{145380.2} \\
DemonAttack      &            7570.5 &           6883.6 &           6268.4 &            5736.4 &   7298.5 &  \textbf{26478.1} \\
DoubleDunk       &              21.6 &             20.1 &             -1.4 &     \textbf{21.8} &     21.6 &              -1.3 \\
ElevatorAction   &           74358.0 & \textbf{74846.0} &              0.0 &           71432.9 &  73506.0 &           64614.0 \\
Enduro           &            2155.8 &           2159.9 &           2132.2 &            2112.2 &    237.6 &   \textbf{2271.2} \\
FishingDerby     &     \textbf{44.3} &             40.1 &             34.2 &              42.4 &     42.9 &              44.0 \\
Freeway          &              33.6 &             33.5 &             33.5 &              33.6 &     33.6 &     \textbf{33.8} \\
Frostbite        &            7139.6 &           6980.3 &  \textbf{7758.2} &            6777.8 &   5901.5 &            7391.7 \\
Gopher           &            7815.1 &           7421.3 &           7295.3 &            7578.1 &   7581.9 &  \textbf{12069.6} \\
Gravitar         &   \textbf{1763.4} &           1171.2 &           1050.4 &            1132.8 &   1165.9 &            1149.1 \\
Hero             &           38102.2 & \textbf{38727.3} &          35444.2 &           37496.3 &  38217.7 &           35595.3 \\
IceHockey        &               0.4 &              0.7 &             -0.5 &              -0.2 &     -0.3 &      \textbf{5.2} \\
Jamesbond        &             586.0 &            650.6 &            747.1 &    \textbf{896.6} &    663.7 &             733.9 \\
JourneyEscape    &           -1224.9 &          -1261.3 &          -3441.8 &           -1241.1 &  -1250.5 &   \textbf{-992.9} \\
Kangaroo         &           12676.2 &          12404.3 & \textbf{13028.7} &           12691.8 &  12834.1 &           12617.5 \\
Krull            &            4250.4 &           4016.2 &           4171.0 &            4242.7 &   4046.5 &   \textbf{4290.8} \\
KungFuMaster     &           26459.1 &          23429.2 &          25450.0 &           27472.8 &  26899.8 &  \textbf{34510.8} \\
MontezumaRevenge &             780.0 &  \textbf{5188.8} &           5118.8 &            4364.6 &   2449.8 &            2486.2 \\
MsPacman         &            3774.2 &           3749.3 &           3577.0 &            3694.1 &   3694.0 &   \textbf{4376.9} \\
NameThisGame     &            8309.9 &           8086.0 &           7598.0 &            7947.5 &   7810.1 &  \textbf{11602.0} \\
Phoenix          &            6340.5 &           7073.2 &           4779.7 &            7576.2 &   6902.3 &  \textbf{14687.3} \\
Pitfall          &              -9.8 &    \textbf{-1.6} &             -5.4 &             -15.1 &    -18.8 &              -2.0 \\
Pong             &     \textbf{20.1} &             19.4 &             20.1 &              19.6 &     19.6 &              19.7 \\
Pooyan           &            3920.6 &           4125.0 &           3946.0 &            4103.6 &   3871.5 &   \textbf{4731.5} \\
PrivateEye       &           12284.7 &           3371.9 &          10081.2 &  \textbf{26765.1} &  13566.5 &             216.6 \\
Qbert            &           17261.8 & \textbf{19027.1} &          17926.5 &           17453.1 &  17072.6 &           18169.5 \\
Riverraid        &           18317.0 & \textbf{19032.5} &          18281.6 &           18392.1 &  17705.1 &           13969.1 \\
RoadRunner       &           52548.1 &          52626.6 &          52641.4 &  \textbf{52853.6} &  52164.1 &           52048.7 \\
Robotank         &              62.4 &             62.1 &             13.8 &              59.3 &     61.4 &     \textbf{67.0} \\
Seaquest         &            9605.5 &           7083.1 & \textbf{23277.5} &            6833.4 &   6403.1 &            9315.5 \\
Skiing           &          -25020.7 &         -24296.5 &         -23602.8 & \textbf{-23077.5} & -24954.3 &          -25814.9 \\
Solaris          &   \textbf{2187.8} &           1877.9 &           1951.8 &            1375.9 &   1939.5 &            2032.2 \\
SpaceInvaders    &            2621.1 &           2417.1 &           1682.1 &            2955.8 &   2604.4 &   \textbf{5527.1} \\
StarGunner       &           45718.0 &          46682.3 &          46281.6 &           48348.0 &  51118.0 &  \textbf{55886.7} \\
Tennis           &              -0.8 &             -0.1 &    \textbf{22.8} &              22.7 &     -1.1 &              -0.0 \\
TimePilot        &           10484.4 &          10637.3 &           5421.0 &           10474.8 &  10281.4 &  \textbf{11161.8} \\
Tutankham        &    \textbf{240.8} &            232.4 &            147.8 &             240.2 &    223.3 &             212.0 \\
UpNDown          &           21518.4 &          15871.6 &          11277.8 &           16540.0 &  17411.3 &  \textbf{36217.2} \\
Venture          &   \textbf{1541.0} &           1515.0 &           1303.8 &            1470.2 &   1529.8 &            1528.2 \\
VideoPinball     & \textbf{453118.7} &         431034.8 &         410651.4 &          431198.8 & 414069.2 &          327080.8 \\
WizardOfWor      &            7172.8 &           6163.0 &           4719.3 &            6580.8 &   7323.6 &   \textbf{8578.7} \\
YarsRevenge      &           36432.8 &          42317.0 &          35471.4 &           37539.3 &  36775.4 &  \textbf{44978.0} \\
Zaxxon           &           14106.7 &          13750.8 &           8881.5 &           11179.1 &  14333.5 &  \textbf{18290.2} \\
\bottomrule
\end{tabular}
}
\end{center}
\end{table}

\newpage
\begin{table}[h!]
\caption{Raw scores for all games after 200M training frames}
\begin{center}
\resizebox{!}{0.385\paperheight}{%
\begin{tabular}{l|rrrrrr}
\toprule
Games &           $\epsilon$-greedy &              RND &              CTS &          PixelCNN &              ICM &         NoisyNets \\
\midrule
AirRaid          &           12719.7 &          12035.0 &          12296.9 &           12849.5 & \textbf{12923.5} &           10097.4 \\
Alien            &            3461.2 &           3393.2 &           3177.4 &            3622.7 &           3455.5 &   \textbf{4562.1} \\
Amidar           &            2411.3 &           2263.8 &           2311.2 &            2499.6 &           2601.6 &   \textbf{2837.4} \\
Assault          &            3215.9 &           3247.1 &           2970.2 &            3026.7 &           1829.1 &   \textbf{4929.5} \\
Asterix          &           17337.1 &          18772.5 &          14855.6 &           19092.0 &          17287.0 &  \textbf{42993.4} \\
Asteroids        &            1609.5 &           1456.2 &           1350.5 &            1474.3 &           1442.0 &   \textbf{3392.9} \\
Atlantis         &          843635.3 &         796360.0 &         752722.0 & \textbf{874296.2} &         742868.0 &          860326.0 \\
BankHeist        &            1041.1 &           1132.0 &           1086.1 &             621.9 &           1137.3 &   \textbf{1255.0} \\
BattleZone       &  \textbf{38978.1} &          32521.0 &          29587.0 &           38601.4 &          37003.4 &           37314.9 \\
BeamRider        &            5791.0 &           6416.3 &           5433.5 &            4604.3 &  \textbf{6499.4} &            6016.1 \\
Berzerk          &             772.9 &            772.1 &            845.5 &             779.3 &            740.5 &    \textbf{938.4} \\
Bowling          &              39.7 &             34.4 &             41.3 &     \textbf{49.1} &             42.2 &              33.2 \\
Boxing           &              98.2 &             98.4 &             97.8 &              98.2 &             98.5 &     \textbf{98.9} \\
Breakout         &             102.3 &            118.8 &            112.8 &             104.6 &            113.7 &    \textbf{129.2} \\
Carnival         &            4792.3 &           4726.3 &  \textbf{5058.3} &            4385.5 &           4585.1 &            4464.1 \\
Centipede        &            6470.3 &  \textbf{6933.9} &           6572.6 &            6434.8 &           6600.6 &            6466.8 \\
ChopperCommand   &  \textbf{12578.4} &           2674.9 &          12133.2 &           12396.4 &          11595.2 &            9556.3 \\
CrazyClimber     &          145511.7 &         146489.0 &         145465.8 &          147683.8 &         145570.3 & \textbf{153267.5} \\
DemonAttack      &           19737.1 &          14349.2 &          11689.9 &            9350.5 &          18477.4 &  \textbf{48634.6} \\
DoubleDunk       &              22.3 &             21.9 &             10.3 &              22.1 &    \textbf{22.3} &              -0.2 \\
ElevatorAction   &           75946.0 &          76118.0 &              0.0 &           67752.0 &          75606.0 &  \textbf{81142.0} \\
Enduro           &            2153.0 &           2175.9 &           2184.7 &            2170.9 &             31.6 &   \textbf{2263.7} \\
FishingDerby     &              46.4 &             41.4 &             44.3 &              44.7 &    \textbf{47.5} &              45.6 \\
Freeway          &              33.6 &             33.7 &             33.6 &              33.6 &             33.6 &     \textbf{33.9} \\
Frostbite        &            8048.7 &           8133.9 &           8343.3 &            7859.6 &           6909.5 &   \textbf{9012.5} \\
Gopher           &           10709.6 &           9630.3 &           9844.3 &           10547.0 &          10551.9 &  \textbf{13382.3} \\
Gravitar         &   \textbf{1999.3} &           1245.6 &           1442.2 &            1338.2 &           1332.6 &            1337.8 \\
Hero             &           43671.9 & \textbf{47802.0} &          41244.6 &           44286.2 &          45974.3 &           40075.3 \\
IceHockey        &              -1.0 &             -1.0 &              2.7 &              -0.9 &             -1.4 &     \textbf{13.6} \\
Jamesbond        &             721.6 &            839.5 &           1094.4 &   \textbf{1168.6} &            935.1 &             828.4 \\
JourneyEscape    &           -1185.4 &          -1215.0 &          -1992.6 &           -1112.0 &          -1199.6 &   \textbf{-986.2} \\
Kangaroo         &           12917.7 &          12606.1 &          12521.5 &           12611.1 &          12593.4 &  \textbf{13981.5} \\
Krull            &            4249.5 &           4202.2 &           4153.0 &            4075.4 &           4276.6 &   \textbf{4371.8} \\
KungFuMaster     &           28741.8 &          24087.6 &          26439.4 &           27234.6 &          28168.3 &  \textbf{39382.1} \\
MontezumaRevenge &             780.0 &  \textbf{5199.2} &           5028.2 &            4652.3 &           2795.9 &            2435.4 \\
MsPacman         &            4063.2 &           4008.6 &           3964.5 &            3993.7 &           3861.0 &   \textbf{5051.5} \\
NameThisGame     &            9496.4 &           9202.3 &           8779.3 &            9147.4 &           9247.3 &  \textbf{11499.7} \\
Phoenix          &            6672.1 &           7318.6 &           4762.9 &            7671.8 &           8306.2 &  \textbf{17579.5} \\
Pitfall          &              -5.3 &    \textbf{-1.8} &             -6.5 &             -11.4 &            -35.9 &             -15.7 \\
Pong             &     \textbf{20.3} &             20.1 &             20.2 &              20.3 &             19.9 &              19.9 \\
Pooyan           &            4324.6 &           4353.1 &           4416.6 &            4382.3 &           4128.3 &   \textbf{4974.4} \\
PrivateEye       &           26038.5 &          19421.7 &           5276.8 &           12211.4 & \textbf{26363.8} &            4339.9 \\
Qbert            &           17606.8 &          18369.7 &          17247.3 &           17293.6 &          18603.9 &  \textbf{18785.1} \\
Riverraid        &           20607.1 & \textbf{20941.0} &          20694.7 &           20699.5 &          20290.8 &           16250.6 \\
RoadRunner       &           54381.9 &          53829.7 &          56352.5 &           54773.0 &          53630.3 &  \textbf{62423.5} \\
Robotank         &              64.7 &             66.1 &             34.3 &              60.3 &             61.0 &     \textbf{70.0} \\
Seaquest         &           16044.8 &          11821.2 & \textbf{27027.8} &           11185.7 &          15469.9 &           20898.3 \\
Skiing           & \textbf{-24988.0} &         -28678.5 &         -27801.4 &          -29094.5 &         -28781.4 &          -29613.9 \\
Solaris          &            1792.5 &           1684.3 &           1622.6 &            1252.0 &           1470.1 &   \textbf{3024.6} \\
SpaceInvaders    &            4172.0 &           3232.1 &           2229.4 &            4217.7 &           4936.0 &   \textbf{9719.3} \\
StarGunner       &           55112.9 &          57334.7 &          58005.6 &           56811.3 &          59500.1 &  \textbf{63232.9} \\
Tennis           &              -0.1 &             -0.6 &             23.0 &     \textbf{23.2} &              2.6 &              -0.0 \\
TimePilot        &           11640.6 &          12010.6 &           7430.4 &           11564.4 &           9210.8 &  \textbf{13593.5} \\
Tutankham        &    \textbf{239.4} &            237.9 &            193.0 &             234.7 &            233.6 &             238.1 \\
UpNDown          &           38975.8 &          22559.4 &          14958.5 &           21799.9 &          24751.1 &  \textbf{43345.9} \\
Venture          &            1591.7 &           1554.7 &           1356.3 &            1536.6 &           1555.8 &   \textbf{1646.4} \\
VideoPinball     &          382581.4 &         447711.5 &         463181.6 &          454007.7 &         432640.6 & \textbf{478029.4} \\
WizardOfWor      &            7939.4 &           6365.5 &           5807.5 &            7330.5 &           7041.1 &  \textbf{10980.4} \\
YarsRevenge      &           44142.9 & \textbf{56794.0} &          43173.2 &           47749.1 &          45821.0 &           52570.1 \\
Zaxxon           &           15101.4 &          14532.9 &          10559.9 &           12248.3 &           8451.7 &  \textbf{19211.5} \\
\bottomrule
\end{tabular}
}
\end{center}
\end{table}\textbf{}
\section{Evaluation protocol}
We evaluate previously introduced exploration methods along two main axes, the first one being sample efficiency i.e. how quickly can they get to closer to the optimal for a particular environment.
While it is a key objective for exploration methods, published agents are often trained under different regimes making it hard to an apples to apples comparison.
They often employ different reinforcement learning algorithms, varying quantity of training frames or inconsistent hyperparameter tuning.
As a remedy, we fixed our training protocol and trained bonus-based methods with a common agent, the Rainbow implementation provided by the Dopamine framework \citep{castro2018dopamine} which includes Rainbow's three most important component: $n$-step updates \citep{mnih2016asynchronous}, prioritized experience replay \citep{schaul2015prioritized} and distributional reinforcement
learning \citep{bellemare2017distributional}.

The second axis is generality, the initial goal of the ALE was to promote the design agents with a general competency in a variety of different domains.
The current practice followed by the community has been to tune agents in \textsc{Montezuma's Revenge}{}. We evaluate if \textsc{Montezuma's Revenge}{} is indeed predictive of performance in other settings. Moreover we evaluate how well these algorithms across all Atari games to understand the impact these bonuses have in other domains
\section{Exploration methods}
\label{sec:exploration_methods}
We focus on bonus-based methods, that is, methods that promote exploration through a reward signal.
An agent is trained with the reward $r = r^{\text{ext}} + \beta \cdot r^{\text{int}}$ where $r^{\text{ext}}$ is the extrinsic reward provided by the environment, $r^{\text{int}}$ the intrinsic reward computed by agent, and $\beta > 0$ is a scaling parameter.
We now summarize the methods we evaluate to compute the intrinsic reward $r^{\text{int}}$.

\subsection{Pseudo-counts}
Pseudo-counts \citep{bellemare2016unifying,count-based} were proposed as way to estimate counts in high dimension states spaces using a density model. The agent is then encouraged to visit states with a low visit count.
Let $\rho$ be a density model over the state space $\mathcal{S}$, we write $\rho_t (s)$ the density assigned to a state $s$ after training on a sequence of states $s_1, ..., s_t$.
We write $\rho'_t (s)$ the density assigned to $s$ if $\rho$ were to be trained on $s$ an additional time.
The \textit{pseudo-count} $\hat N$ is then defined such that updating $\rho$ on a state $s$ leads to a one unit increase of its pseudo-count
\begin{equation}
\label{eq:pseudo}
    \rho_t (s) = \frac{\hat N (s)}{\hat{n}}, \quad \rho^{'}_t (s) = \frac{\hat N (s) + 1 }{\hat{n} +1},
\end{equation}
where $\hat{n}$, the pseudo-count total is a normalization constant.
This formulation of pseudo-counts match empirical counts when the density model corresponds to the empirical distribution.
\Eqref{eq:pseudo} can be rewritten as
\begin{equation}
    \hat N (s) = \frac{\rho_t (s) (1 - \rho^{'}_t (s))}{\rho^{'}_t (s) - \rho_t (s)}.
\end{equation}
The intrinsic reward is then given by
\begin{equation}
\label{eq:psc}
    r^{\text{int}} (s_t) \coloneqq ( \hat N_t (s_t) )^{-1/2}.
\end{equation}
CTS \citep{bellemare2014skip} and PixelCNN \citep{oord2016pixel} have been both used as density models.
We will disambiguate these agent by the name of their density model.

\subsection{Intrinsic Curiosity Module}
Intrinsic Curiosity Module \citep[ICM,][]{pathak17curiositydriven} promotes exploration via curiosity. \citeauthor{pathak17curiositydriven} formulates curiosity as the error in the agent's ability to predict the consequence of its own actions in a learned feature space. ICM includes three submodules: a learned embedding, a forward and an inverse model.
At the each timestep the module receives a transition $(s_t, a_t, s_{t+1})$ -- where $s_t$ and $a_t$ are the current state and action and $s_{t+1}$ is the next state. States $s_t$ and $s_{t+1}$ are encoded into the features $\phi (s_t)$ and $\phi (s_{t+1})$ then passed to the inverse model which is trained to predict $a_t$. The embedding is updated at the same time, encouraging it to only model environment features that are influenced by the agent's action. The forward model has to predict the next state embedding $\phi(s_{t+1})$ using $\phi (s_t)$ and $a_t$.
The intrinsic reward is then given by the error of the forward model in the embedding space between $\phi (s_{t+1})$, and the predicted estimate $\hat{\phi} (s_{t+1})$:
\begin{equation}
\label{eq:icm}
    r^{\text{int}} (s_t) = \| \hat{\phi} (s_{t+1}) - \phi (s_{t+1}) \|_2^2 .
\end{equation}

\subsection{Random Network Distillation}
Random Network Distillation \citep[RND,][]{burda2018exploration} derives a bonus from the prediction error of a random network.
The intuition being that the prediction error will be low on states that are similar to those previously visited and high on newly visited states.
A neural network $\hat f$ with parameters $\theta$ is trained to predict the output of a fixed, randomly initialized neural network $f$. The intrinsic reward is given by
\begin{equation}
\label{eq:rnd}
    r^{\text{int}} (s_t) = \| \hat{f} (s_t; \theta) - f(s_t) \|_2^2
\end{equation}
where $\theta$ represents the parameters of the network $\hat{f}$.

\subsection{Noisy Networks}
We also evaluate Noisy Networks \citep[NoisyNets;][]{fortunato18noisy}, which is part of the original Rainbow implementation.
NoisyNets does not explore using a bonus. Instead NoisyNets add noise in parameter space and replace the standard fully-connected layers, $y = Ws + b$, by a noisy version that combines a deterministic and a noisy stream:
\begin{equation}
    y = (W + W_{noisy} \odot \epsilon^W) s + (b + b_{noisy} \odot \epsilon^b),
\end{equation}
where $\epsilon^W$ and $\epsilon^b$ are random variables and $\odot$ denotes elementwise multiplication.

\section{Introduction}
In reinforcement learning, the exploration-exploitation trade-off describes an agent's need to balance maximizing its cumulative rewards and improving its knowledge of the environment.
While many practitioners still rely on simple exploration strategies such as the $\epsilon$-greedy scheme, in recent years a rich body of work has emerged for efficient exploration in deep reinforcement learning.
One of the most successful approaches to exploration in deep reinforcement learning is to provide an exploration bonus based on the relative novelty of the state.
This bonus may be computed, for example, from approximate counts \citep{bellemare2016unifying,count-based,tang2017exploration,machado18_SR}, from the prediction error of a dynamics model \citep[ICM, ][]{pathak17curiositydriven} or by measuring the discrepancy to a random network \citep[RND,][]{burda2018exploration}.

\citet{bellemare2016unifying} argued for the importance of the Atari 2600 game \textsc{Montezuma's Revenge}{} as a challenging domain for exploration.
\textsc{Montezuma's Revenge}{} offers a sparse reinforcement signal and relatively open domain that distinguish it from other Atari 2600 games supported by the Arcade Learning Environment \citep[ALE;][]{bellemare2013arcade}. As a consequence,
recent exploration research (bonus-based or not) has aspired to improve performance on this particular game, ranging from a much deeper exploration (6600 points; Bellemare et al., 2016), to completing the first level \citep[14000 points;][]{pohlen18observe,burda2018exploration}, to super-human performance \citep[400,000 points;][]{ecoffet19goexplore}.

Yet the literature on exploration in reinforcement learning still lacks a systematic comparison between existing methods, despite recent entreaties for better practices to yield reproducible research \citep{henderson2018deep,machado2018revisiting}.
One of the original tenets of the ALE is that agent evaluation should take on the entire suite of 60 available Atari 2600 games. Even within the context of bonus-based exploration, \textsc{Montezuma's Revenge}{} is but one of seven hard exploration, sparse rewards games \citep{bellemare2016unifying}.
Comparisons have been made between agents trained under different regimes: using different learning algorithms and varying numbers of training frames, with or without reset, and with and without controller noise \citep[e.g. \emph{sticky actions}][]{machado2018revisiting}.
As a result, it is often unclear if the claimed performance improvements are due to the exploration method or other architectural choices, and whether these improvements carry over to other domains.
The main conclusion of our research is that an over-emphasis on one Atari 2600 game, combined with different training conditions, may have obfuscated the real pace of progress in exploration research.

To come to this conclusion, we revisit popular bonus-based exploration methods (CTS-counts, PixelCNN-counts, RND, and ICM) in the context of a common evaluation framework. We apply the Rainbow \citep{hessel2018rainbow} agent in turn to \textsc{Montezuma's Revenge}{}, Bellemare et al.'s seven hardest Atari 2600 games for exploration, and the full suite from the ALE.

\textbf{Source of exploration bonus.} We find that all agents perform better than an $\epsilon$-greedy baseline, confirming that exploration bonuses do provide meaningful gains. However, we also find that more recent exploration bonuses do not, by themselves, lead to higher performance than the older pseudo-counts method. Across the remainder of hard exploration games, we find that all bonuses lead to performance that is comparable, and in one case worse, than $\epsilon$-greedy.

\textbf{Performance across full Atari 2600 suite.} One may expect a good exploration algorithm to handle the exploration/exploitation trade-off efficiently: exploring in difficult games, without losing too much in games where exploration is unnecessary. We find that performance on \textsc{Montezuma's Revenge}{} is in fact \emph{anticorrelated} with performance across the larger suite. Of the methods surveyed, the only one to demonstrate better performance across the ALE is the non-bonus-based Noisy Networks \citep{fortunato18noisy}, which provide as an additional point of comparison. Noisy Networks perform worse on \textsc{Montezuma's Revenge}{}.

\textbf{Hyperparameter tuning procedure.}
The standard practice in exploration research has been to tune hyperparameters on \textsc{Montezuma's Revenge}{} then evaluate on other Atari 2600 games. By virtue of this game's particular characteristics, this approach to hyperparameter tuning may unnecessarily increase the behaviour of exploration strategies towards a more exploratory behavior, and explain our observation that these strategies perform poorly in easier games. However, we find that tuning hyperparameters on the original ALE training set does not improve performance across Atari 2600 games beyond that of $\epsilon$-greedy .

\textbf{Amount of training data.} By design, exploration methods should be sample-efficient. However, some of the most impressive gains in exploration on \textsc{Montezuma's Revenge}{} have made use of significantly more data (1.97 billion Atari 2600 frames for RND, versus 100 million frames for the pseudo-count method). We find that, within our common evaluation framework, additional data does not play an important role on exploration performance.

Altogether, our results suggests that more research is needed to make bonus-based exploration robust and reliable, and serve as a reminder of the pitfalls of developing and evaluating methods primarily on a single domain.

\subsection{Related Work}

Closest to our work, \citet{burda2018large} benchmark various exploration bonuses based on prediction error \citep{schmidhuber1991curious,pathak17curiositydriven} within a set of simulated environment including many Atari 2600 games.
Their study differs from ours as their setting ignores the environment reward and instead learns exclusively from the intrinsic reward signal.
Outside of the ALE, \citet{osband2019behaviour} recently provide a collection of experiments that investigate core capabilities of exploration methods.

\input{exploration_methods}

\section{Empirical Results}
In this section we present our experimental study of bonus-based exploration methods.

\subsection{Experimental protocol}
We evaluate the three bonus-based methods introduced in Section \ref{sec:exploration_methods} as well as NoisyNets and $\epsilon$-greedy exploration.
To do so, we keep our training protocol fixed throughout our experiments.
All methods are trained with a common agent architecture, the Rainbow implementation provided by the Dopamine framework \citep{castro2018dopamine}. It includes Rainbow's three most important component: $n$-step updates \citep{mnih2016asynchronous}, prioritized experience replay \citep{schaul2015prioritized} and distributional reinforcement learning \citep{bellemare2017distributional}. Rainbow was designed combining several improvements to value-based agents that were developed independently. Pairing Rainbow with recent exploration bonuses should lead to further benefits. We also keep the original hyperparameters of the learning algorithm fixed to avoid introducing bias in favor of a specific bonus.

Unless specified, our agents are trained for 200 million frames.
Following \citet{machado2018revisiting} recommendations we run the ALE in the stochastic setting using sticky actions ($\varsigma = 0.25$) for all agents during training and evaluation.
We also do not use the mixed Monte-Carlo return \citep{bellemare2016unifying,count-based} or other algorithmic improvements that are combined with bonus-based methods \citep[e.g.][]{burda2018exploration}.

\begin{figure}
\hspace*{0.2\linewidth}
    \includegraphics[width=0.75\linewidth]{figures/all_games/MontezumaRevenge.pdf}
    \caption{A comparison of different exploration methods on \textsc{Montezuma's Revenge}{}.
    }
    \label{fig:montezuma}
\end{figure}

\subsection{Common Evaluation Framework}
\label{sec:montezuma}
Our first set of results compare exploration methods introduced in Section \ref{sec:exploration_methods} on \textsc{Montezuma's Revenge}{}. We follow the standard procedure to use this game to tune the hyperparameters of each exploration bonus.
Details regarding implementation and hyperparameter tuning may be found in Appendix \ref{app:hparam_tuning}.
Figure~\ref{fig:montezuma} shows training curves (averaged over 5 random seeds) for Rainbow augmented with the different exploration bonuses.

As anticipated, $\epsilon$-greedy exploration performs poorly here and struggles in such a hard exploration game. On the other hand, exploration bonuses have a huge impact and all eventually beat the baselines $\epsilon$-greedy  and NoisyNets. Only ICM is unable to surpass the baselines by a large margin. RND, CTS and PixelCNN all average close to 5000 points.
Interestingly, we observe that a more recent bonus like RND does not lead to higher performance over the older pseudo-count method.
Of note, the performance we report at 200 millions frames improves on the performance reported in the original paper for each method. As expected, Rainbow leads to increased performance over older DQN variants previously used in the literature.

\begin{figure*}
\centering
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Gravitar.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=\linewidth]{figures/all_games/PrivateEye.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Venture.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Solaris.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Pitfall.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Freeway.pdf}
    \end{subfigure}%
\caption{Hard exploration games.}
\label{fig:hard}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=\linewidth]{figures/all_games/Asterix.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Freeway_2.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/BeamRider.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/SpaceInvaders.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=1.1\linewidth]{figures/all_games/Seaquest.pdf}
      \label{fig:seaquest}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \hspace*{10mm}
      \includegraphics[width=0.7\linewidth]{figures/all_games/legend.png}
      \label{fig:legend}
    \end{subfigure}%
\caption{Atari training set.}
\label{fig:easy}
\end{subfigure}
\caption{Evaluation of different bonus-based exploration methods on several Atari games, curves are averaged over 5 runs, shaded area denotes variance.}
\label{fig:evaluation}
\end{figure*}

\subsection{Exploration methods evaluation}
It is standard in the exploration community to, first tune hyperparameters on \textsc{Montezuma's Revenge}{}, and then, evaluate these hyperparameters on the remaining hard exploration games with sparse rewards. This is not in line with the original ALE guidelines which recommend to evaluate on the entire suite of Atari 2600 games. In this section we provide empirical evidence that, failing to follow the ALE guidelines may interfere with the conclusions of the evaluation.

\textbf{Hard exploration games.}
\label{sec:hard}
We now turn our attention to the set of games categorized as hard exploration games with sparse rewards in \citeauthor{bellemare2016unifying}'s taxonomy (the taxonomy is available in Appendix~\ref{app:taxonomy}). It includes ALE's most difficult games for exploration, this is where good exploration strategies should shine and provide the biggest improvements. These games are: \textsc{Gravitar}, \textsc{Private Eye}, \textsc{Venture}, \textsc{Solaris}, \textsc{Pitfall! } and \textsc{Freeway}.

We evaluate agents whose hyperparameters were tuned on \textsc{Montezuma's Revenge}{} on this set of games.
Training curves averaged over 5 runs are shown in Figure~\ref{fig:hard}.
We find that performance of each method on \textsc{Montezuma's Revenge}{} does not correlate with performance on other hard exploration domains.
All methods seem to behave similarly contrary to our previous observations on \textsc{Montezuma's Revenge}{}.
In particular, there is no visible difference between $\epsilon$-greedy and more sophisticated exploration bonuses.
$\epsilon$-greedy exploration is on par with every other method and even outperforms them by a significant margin on \textsc{Gravitar}.
These games were initially classified to be hard exploration problems because a DQN agent using $\epsilon$-greedy exploration was unable to achieve a high scoring policy; it is no longer the case with stronger learning agents available today.

\begin{figure}
\centering
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/cts_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/rnd_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/noisy_vs_rainbow.pdf}
    \end{subfigure}%
\caption{Improvements (in percentage of AUC) of Rainbow with various exploration methods over Rainbow with $\epsilon$-greedy exploration in 60 Atari games. The game \textsc{Montezuma's Revenge}{} is represented in purple.}
\label{fig:all_games_bar}
\end{figure}

\begin{wrapfigure}{R}{0.43\textwidth}
\centering
\includegraphics[width=\linewidth]{figures/normalized_score.pdf}
\caption{Normalized score of bonus-based methods compared to $\epsilon$-greedy}
\label{fig:normalized}
\end{wrapfigure}

\textbf{Full Atari suite.}
\label{sec:full_atari}
The set of hard exploration games was chosen to highlight the benefits of exploration methods, and, as a consequence, performance on this set may not be representative of an algorithm capabilities on the whole Atari suite. Indeed, exploration bonuses can negatively impact performance by skewing the reward landscape.
To demonstrate how the choice of particular evaluation set can lead to different conclusions we also evaluate our agents on the original Atari training set which includes the games \textsc{Asterix}, \textsc{Freeway}, \textsc{Beam Rider}, \textsc{Space Invaders} and \textsc{Seaquest}. Except for \textsc{Freeway} all these games are easy exploration problems \citep{bellemare2016unifying}.

Figure~\ref{fig:easy} shows training curves for these games.
Pseudo-counts with a CTS model appears to struggle when the environment is an easy exploration problem and end up performing worse on every game except \textsc{Seaquest}.
RND and ICM are able to consistently match $\epsilon$-greedy exploration but never beat it.
It appears that bonus-based methods have limited benefits in the context of easy exploration problems.
Finally, despite its limited performance on \textsc{Montezuma's Revenge}{}, we found that NoisyNets presented the most consistent improvements.

\begin{figure}
\centering
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/cts_vs_rainbow_new_tuning.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/rnd_vs_rainbow_new_tuning.pdf}
    \end{subfigure}%
\caption{Improvements (in percentage of AUC) of Rainbow with CTS and RND over Rainbow with $\epsilon$-greedy exploration in 60 Atari games when hyperparameters have been tuned on \textsc{Seaquest}, \textsc{Qbert}, \textsc{Pong}, \textsc{Breakout} and \textsc{Asterix}. The game \textsc{Montezuma's Revenge}{} is represented in purple. Games in the training set have stars on top of their bar.}
\label{fig:overfit_auc}
\end{figure}

Overall, while the Atari training set and the set of the hard exploration games both show that bonus-based method only provide marginal improvements they lead us to different conclusions regarding the best performing exploration scheme.
It appears that to fully quantify the behavior of exploration methods one cannot avoid evaluating on the whole Atari suite.
We do so and add the remaining Atari games to our study. See Figure~\ref{fig:all_games_bar} and \ref{fig:normalized} and  for a high level comparison.  Altogether, it appears that the benefit of exploration bonuses is mainly allocated towards \textsc{Montezuma's Revenge}{}. None of them, except NoisyNets, seems to improve over $\epsilon$-greedy by significant margin.
Bonus-based methods may lead to increased performance on a few games but seem to deteriorate performance by a roughly equal amount on other games.

We could have hoped that these methods focus their attention on hard exploration games at the expense of easier ones, meaning they trade exploitation for exploration. Unfortunately, it does not seem to be the case as they do not exhibit a preference for hard exploration games (red and orange bars). We may wonder if these methods are overfitting on \textsc{Montezuma's Revenge}{}.

\subsection{Hyperparameter tuning procedure}
\label{sec:hyp_tuning}

Previous experiments have so far depicted  a somewhat dismal picture of bonus-based methods, in particular their penchant to overfit on \textsc{Montezuma's Revenge}{}.
Though it is unfortunate to see they do not generalize to the full Atari gamut, one may wonder if their tendency to overfit to \textsc{Montezuma's Revenge}{} specifically is caused by the hyperparameter tuning procedure or their inherent design. The experiments in this section aim at addressing this issue. We ran a new hyperparameter sweep on CTS and RND using a new training set. We chose these algorithms as we found them to be particularly sensitive to their hyperparameters. The new training set includes the games \textsc{Pong}, \textsc{Asterix}, \textsc{Seaquest}, \textsc{Q*bert} and \textsc{Breakout}. This set as been previously used by others as a training set to tune reinforcement learning agents \citep{bellemare2017distributional,dabney2018distributional}.

Results are depicted in Figure~\ref{fig:overfit_auc}. Both algorithm still perform much better than $\epsilon$-greedy  exploration on \textsc{Montezuma's Revenge}{}. As it is to be expected, performance also increased for games within the training set. A notable example is CTS on \textsc{Seaquest} which now improves over the $\epsilon$-greedy  baseline by $140\%$ instead of $120\%$ previously. Nevertheless, the conclusions from Section \ref{sec:full_atari} remain valid. Bonus-based exploration strategies still provide only limited value except for a few games. In addition, neither algorithm seems to achieve better results on easy exploration problems outside of the training set.

\subsection{Amount of training data}

Current results so far showed that exploration bonuses provide little benefits in the context of exploration in the ALE. Nonetheless, our experiments have been limited to 200 millions environment frames, it is possible that with additional data exploration bonuses would perform better. This would be in line with an emerging trend of training agents an order of magnitude longer in order to produce a high-scoring policy, irrespective of the sample cost \citep{Espeholt2018IMPALASD,burda2018exploration,kapturowski2018recurrent}. In this section we present results that contradict this hypothesis. We reuse agents trained in Section 4.2.2 and lengthen the amount training data they process to 1 billion environment frames. We use Atari 2600 games from the set hard exploration with sparse rewards and the Atari training set. See Figure \ref{fig:1b} for training curves.
All exploration strategies see their score gracefully scale with additional data on easier exploration problems.
In hard exploration games, none of the exploration strategies seem to benefit from receiving more data.
Score on most games seem to plateau and may even decrease. This is particularly apparent in \textsc{Montezuma's Revenge}{} where only RND actually benefits from longer training. After a while, agents are unable to make further progress and their bonus may collapse. When that happens, bonus-based methods cannot even rely on $\epsilon$-greedy  exploration to explore and may therefore see their performance decrease.
This behavior may be attributed to our evaluation setting, tuning hyperparameters to perform best after one billion training frames will likely improve results.
It is however unsatisfactory to see that exploration methods do not scale effortlessly as they receive more data.
In practice, recent exploration bonuses have required a particular attention to handle large amount of training data \citep[e.g.][]{burda2018exploration}.
Moreover, it is interesting to see that the performance at 200 millions frames leads to conclusions similar to those obtained with one billion frames.

\begin{figure*}
\centering
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_MontezumaRevenge.pdf}
      \label{fig:1b_montezuma}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Gravitar.pdf}
      \label{fig:1b_gravitar}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_PrivateEye.pdf}
      \label{fig:1b_privateeye}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Venture.pdf}
      \label{fig:1b_venture}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Solaris.pdf}
      \label{fig:1b_solaris}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Pitfall.pdf}
      \label{fig:1b_pitfall}
    \end{subfigure}%
\caption{Hard exploration games.}
\label{fig:1b_hard}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Asterix.pdf}
      \label{fig:1b_asterix}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Freeway.pdf}
      \label{fig:1b_freeway}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_BeamRider.pdf}
      \label{fig:1b_beamrider}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_SpaceInvaders.pdf}
      \label{fig:1b_spaceinvaders}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Seaquest.pdf}
      \label{fig:1b_seaquest}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \hspace*{7mm}
      \includegraphics[width=.7\linewidth]{figures/all_games/legend.png}
      \label{fig:1b_legend}
    \end{subfigure}%
\caption{Atari training set.}
\label{fig:1b_easy}
\end{subfigure}
\caption{Evaluation of bonus-based methods when training is extended to one billion frames}
\label{fig:1b}
\end{figure*}

\section{Conclusion}

Recently, many exploration methods have been introduced with confounding factors within their evaluation -- longer training duration, different model architecture and other ad-hoc techniques.
This practice obscures the true value of these methods and makes it difficult to prioritize more promising directions of investigation.
Therefore, following a growing trend in the reinforcement learning community, we advocate for better practices on empirical evaluation for exploration to fairly assess the contribution of newly proposed methods.
In a standardized training environment and context, we found that current bonus-based methods are unable to surpass $\epsilon$-greedy exploration.
As a whole this suggest progress in bonus-based exploration may have been driven by confounding factors rather than improvement in the bonuses.
This shows that more work is still needed to address the exploration problem in complex environments.

We may wonder why do we not see a positive impact of bonus-based exploration. One possible explanation is our use of the relatively sophisticated Rainbow learning algorithm. The benefits that others have observed using exploration bonuses might be made redundant through other mechanisms already in Rainbow, such as a prioritized replay buffer.
An important transition may only be observed with low frequency but it can be sampled at a much higher rate by the replay buffer. As a result, the agent can learn from it effectively without the need for encouragement from the exploration bonus to visit that transition more frequently.
Though the merits of bonus-based methods have been displayed with less efficient learning agents, these benefits did not carry on to improved learning agents.
This is disappointing given that the simple NoisyNets baseline showed efficient exploration can still achieve noticeable gains on the ALE.
As of now, the exploration and credit assignment communities have mostly been operating independently. Our work suggests that they may have to start working hand in hand to design new agents to make reinforcement learning truly sample efficient.

\subsubsection*{Acknowledgements}
The authors would like to thank Hugo Larochelle, Benjamin Eysenbach, Danijar Hafner, Valentin Thomas and Ahmed Touati for insightful discussions as well as Sylvain Gelly for careful reading and comments on an earlier draft of this paper. This work was supported by the CIFAR Canadian AI Chair.

\section{Introduction}

Deep reinforcement learning algorithms, starting with DQN \citep{mnih2015human}, have shown that learning control policies from high dimensional inputs such as images is possible.
These approaches often achieve super human-level control in standard benchmarks such as the Atari 2600 games supported by the Arcade Learning Environment~\citep[ALE;][]{bellemare2013arcade}.
However, in this same benchmark there are some games in which most deep reinforcement learning approaches are not able to outperform a purely random agent.
A prominent example is the game \textsc{Montezuma's Revenge}{}.
This game requires the agent to navigate an environment with different rooms filled with life threatening traps and explicit progress feedback in the form of a score increase is rare.
In fact, the games with sparse rewards are often the games in which deep reinforcement learning methods that rely on $\epsilon$-greedy  exploration do not perform well at.
This highlights one of the central challenges in reinforcement learning (RL), the exploration-exploitation trade-off: acting optimally given the current knowledge about the world or aiming to acquire more knowledge.

Motivated by these results, a rich body of work has emerged for efficient exploration in deep reinforcement learning.
Often these approaches aspire to improve performance on \textsc{Montezuma's Revenge}{} \citep[e.g.,][]{bellemare2016unifying,burda2018exploration,ecoffet19goexplore,pathak17curiositydriven,tang2017exploration}.
One of the most successful approaches to drive agents towards exploratory behaviour is to provide an intrinsic reward or bonus based on the relative novelty of the state.
\citet{bellemare2016unifying}, for example, proposed the first agent capable of reliably advance through the game.
Their agent scores, on average, 3700 points and explores 15 of 24 rooms of the first level.
Other exploration bonuses have since been able to reach similar level of performance \citep{count-based,martin2017count,machado18_SR}.
Recently, Random Network Distillation \citep{burda2018exploration} exceeded those results.
Their agent is able to score, on average, 8150 points, visiting 22 rooms and occasionally clearing the first level.
However, despite a seemingly well-defined metric such as game score, these methods are often not directly comparable.
Agents are often trained under different regimes: using different learning algorithms and varying numbers of training frames, with or without reset, and with and without controller noise \citep[e.g. \emph{sticky actions;}][]{machado2018revisiting}.

In this context, the literature on exploration in reinforcement learning still lacks a systematic comparison between existing methods, despite recent entreaties for better practices to yield reproducible research \citep{henderson2018deep,machado2018revisiting}.
One of the original tenets of the ALE is that agent evaluation should take on the entire suite of 60 available Atari 2600 games.
Even within the context of bonus-based exploration, \textsc{Montezuma's Revenge}{} is but one of seven hard exploration, sparse rewards games \citep{bellemare2016unifying}.
As a result, it is not clear whether progress in \textsc{Montezuma's Revenge}{} carries over to other domains.
Moreover, the lack of a systematic comparison between existing methods make it unclear if the claimed performance improvements are due to the exploration method or other architectural choices.
The main conclusion of our research is that an over-emphasis on one Atari 2600 game, combined with different training conditions, may have obfuscated the real pace of progress in exploration research.

To come to this conclusion, we revisit popular bonus-based exploration methods (pseudo-counts, PixelCNN-counts, Random Network Distillation, and Intrinsic Curiosity Module) in the context of a common evaluation framework.
We apply the Rainbow \citep{hessel2018rainbow} agent in turn to \textsc{Montezuma's Revenge}{}, Bellemare et al.'s seven hardest Atari 2600 games for exploration, and the full suite from the ALE.
Our main contributions are listed below.

\textbf{Source of exploration bonus.} We find that all agents perform better than an $\epsilon$-greedy baseline, confirming that exploration bonuses do provide meaningful gains. However, we also find that more recent exploration bonuses do not, by themselves, lead to higher performance than the older pseudo-counts method on \textsc{Montezuma's Revenge}{}. Across the remainder of hard exploration games, we find that all bonuses lead to performance that is comparable, and in one case worse, than $\epsilon$-greedy.

\textbf{Performance across full Atari 2600 suite.} One may expect a good exploration algorithm to handle the exploration/exploitation trade-off efficiently: exploring in difficult games such as \textsc{Montezuma's Revenge}{}, without losing too much in games where exploration is unnecessary. We find that performance on \textsc{Montezuma's Revenge}{} is in fact \emph{anticorrelated} with performance across the larger suite. Of the methods surveyed, the only one to demonstrate better performance across the ALE is the non-bonus-based Noisy Networks \citep{fortunato18noisy}, which serves as an additional baseline but performs worse on \textsc{Montezuma's Revenge}{}.

\textbf{Hyperparameter tuning procedure.}
The standard practice in exploration research has been to tune hyperparameters on \textsc{Montezuma's Revenge}{} then evaluate on other Atari 2600 games. Doing so may however bias exploration strategies towards a more exploratory behavior and hurt on games where exploration is not an issue. This would help explaining why exploration bonuses do so well on \textsc{Montezuma's Revenge}{} and why these gains to not translate to easier games. Yet, we find that when hyperparameter are tuned on a set of easy exploration games exploration bonuses are still unable to improve over $\epsilon$-greedy  across the ALE suite.

\textbf{Amount of training data.} By design, exploration methods should be sample-efficient. However, some of the most impressive gains in exploration on \textsc{Montezuma's Revenge}{} have made use of significantly more data (1.97 billion Atari 2600 frames for RND, versus 100 million frames for the pseudo-count method). We find that, within our common evaluation framework, additional data does not play an important role on exploration performance.

Altogether, our results suggests that more research is needed to make bonus-based exploration robust and reliable, and serve as a reminder of the pitfalls of developing and evaluating methods primarily on a single domain.
Our paper is the first to provide such a thorough comparison between existing exploration methods on the ALE.
The large-scale study of \citet{burda2018large} is most similar to our work. \citet{burda2018large} benchmark various exploration bonuses based on prediction error \citep{schmidhuber1991curious,pathak17curiositydriven} within a set of simulated environment including many Atari 2600 games.
Their study differs from ours as their setting ignores the environment reward and instead learns exclusively from the intrinsic reward signal.
Outside of the ALE, \citet{osband2019behaviour} provide a collection of experiments that investigate core capabilities of RL agents including exploration.

\input{exploration_methods}

\section{Empirical Results}
In this section we present our experimental study of bonus-based exploration methods.

\subsection{Experimental protocol}
We evaluate the three bonus-based methods introduced in Section \ref{sec:exploration_methods} as well as NoisyNets and $\epsilon$-greedy exploration.
To do so, we keep our training protocol fixed throughout our experiments.
All methods are trained with a common agent architecture, the Rainbow implementation provided by the Dopamine framework \citep{castro2018dopamine} which includes Rainbow's three most important component: $n$-step updates \citep{mnih2016asynchronous}, prioritized experience replay \citep{schaul2015prioritized} and distributional reinforcement learning \citep{bellemare2017distributional}. Rainbow was designed combining several improvements to value-based agents that were developed independently. Pairing Rainbow with recent exploration bonuses should lead to further benefits. We also keep the original hyperparameters of the learning algorithm fixed to avoid introducing bias in favor of a specific bonus.

Unless specified our agents are trained for 200 million frames.
Following \citet{machado2018revisiting} recommendations we run the ALE in the stochastic setting using sticky actions ($\varsigma = 0.25$) for all agents during training and evaluation.
We also do not use the mixed Monte-Carlo return \citep{bellemare2016unifying,count-based} or other techniques that may positively impact bonus based methods such as in \citet{burda2018exploration}.

\begin{figure}
    \centering

    \includegraphics[width=0.5\linewidth]{figures/MontezumaRevenge_master.pdf}
    \caption{A comparison of different exploration methods on \textsc{Montezuma's Revenge}{}.
    }
    \label{fig:montezuma}
\end{figure}

\subsection{\textsc{Montezuma's Revenge}{} Without Confounders}
\label{sec:montezuma}
Our first set of results compare exploration methods introduced in section \ref{sec:exploration_methods} on the infamous Atari 2600 game \textsc{Montezuma's Revenge}{}. We follow the standard procedure to use this game to tune the hyperparameters of each exploration bonus.
Details regarding implementation and hyperparameter tuning may be found in Appendix \ref{app:hparam_tuning}.
Figure~\ref{fig:montezuma} shows training curves (averaged over 5 random seeds) for Rainbow augmented with different exploration bonuses.

As anticipated, $\epsilon$-greedy exploration performs poorly here and struggle in such a hard exploration game. On the other hand, exploration bonuses have a huge impact and all eventually beat the baselnes. Only ICM is unable to surpass the baselines $\epsilon$-greedy  and NoisyNets by a large margin, RND, CTS and PixelCNN all average close to 5000 points.
Interestingly we observe that more recent bonus like RND does not lead to higher performance over the older pseudo-count method.
Of note, the performance we report at 200 millions frames improves on the performance reported in their original paper for each method. As expected Rainbow leads to increased performance over older DQN variants previously used in the litterature.

\begin{figure*}
\centering
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Gravitar.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=\linewidth]{figures/all_games/PrivateEye.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Venture.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Solaris.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Pitfall.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Freeway.pdf}
    \end{subfigure}%
\caption{Hard exploration games.}
\label{fig:hard}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=\linewidth]{figures/all_games/Asterix.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Freeway.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/BeamRider.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/SpaceInvaders.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Seaquest.pdf}
      \label{fig:seaquest}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.7\linewidth]{figures/all_games/legend.png}
      \label{fig:seaquest}
    \end{subfigure}%
\caption{Atari training set.}
\label{fig:easy}
\end{subfigure}
\caption{Evaluation of different bonus-based exploration methods on several Atari games, curves are averaged over 5 runs, shaded area denotes variance.}
\label{fig:evaluation}
\end{figure*}

\subsection{Exploration methods evaluation}
It is standard in the exploration community to, first tune hyperparameters on \textsc{Montezuma's Revenge}{}, then, evaluate these hyperparameters on the remaining hard exploration games with sparse rewards. This is not in line with the original ALE guidelines which recommend to evaluate on the entire suite of Atari 2600 games. In this section we provide empirical evidence that, failing to follow the ALE guidelines may interfere with the conclusions of the evaluation.

\subsubsection{Hard exploration games}
\label{sec:hard}

We now turn our attention to the set of games categorized as hard exploration games with sparse rewards in \citeauthor{bellemare2016unifying}'s taxonomy (the taxonomy is available in Appendix~\ref{app:taxonomy}). It includes ALE's most difficult games for exploration, this is where good exploration strategies should shine and provide the biggest improvements. These games are: \textsc{Gravitar}, \textsc{Private Eye}, \textsc{Venture}, \textsc{Solaris}, \textsc{Pitfall! } and \textsc{Freeway}.

We evaluate agents whose hyperparameters were tuned on \textsc{Montezuma's Revenge}{} on this set of games.
Training curves averaged over 5 runs are shown in Figure~\ref{fig:hard}.
We find that performance of each method on \textsc{Montezuma's Revenge}{} does not correlate with performance on other hard exploration domains.
All methods seem to behave similarly contrary to our observations on \textsc{Montezuma's Revenge}{}, .
In particular, there is no visible difference between $\epsilon$-greedy and more sophisticated exploration bonuses.
$\epsilon$-greedy exploration is on par with every other method and even outperforms them by a significant margin on \textsc{Gravitar}.
These games were initially classified to be hard exploration problems because a DQN agent using $\epsilon$-greedy exploration was unable to achieve a high scoring policy; it is no longer the case with stronger learning agents available today.

\subsubsection{Full Atari suite}
\label{sec:full_atari}

The set of hard exploration games was chosen to highlight the benefits of exploration methods, and, as a consequence, performance on this set may not be representative of an algorithm capabilities on the whole Atari suite. Indeed, exploration bonuses can negatively impact performance by skewing the reward landscape.
To demonstrate how the choice of particular evaluation set can lead to different conclusions we also evaluate our agents on the original Atari training set which includes the games \textsc{Asterix}, \textsc{Freeway}, \textsc{Beam Rider}, \textsc{Space Invaders} and \textsc{Seaquest}. Except for \textsc{Freeway} all these games are easy exploration problems \citep{bellemare2016unifying}.

Figure~\ref{fig:easy} shows training curves for these games.
Pseudo-counts with a CTS model appears to struggle when the environment is an easy exploration problem and end up performing worse on every game except \textsc{Seaquest}.
RND and ICM are able to consistently match $\epsilon$-greedy exploration but never beat it.
It appears that bonus-based methods have limited benefits in the context of easy exploration problems.
Finally, despite its limited performance on \textsc{Montezuma's Revenge}{} we found that NoisyNets gave the most consistent improvements.

\begin{figure*}
\centering
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/cts_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/rnd_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}

    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/noisy_vs_rainbow.pdf}
    \end{subfigure}%
\caption{Improvements (in percentage of AUC) of Rainbow with various exploration methods over Rainbow with $\epsilon$-greedy exploration in 60 Atari games. The game \textsc{Montezuma's Revenge}{} is represented in purple.}
\label{fig:all_games}
\end{figure*}

Overall, while the Atari training set and the set of the hard exploration games both show that bonus-based method only provide marginal improvements they lead us to different conclusions regarding the best performing exploration scheme.
It appears that to fully quantify the behavior of exploration methods one cannot avoid evaluating on the whole Atari suite.
We do so and add the remaining Atari games to our study. See Figure~\ref{fig:evaluation} for a high level comparison for CTS, RND and NoisyNets (PixelCNN and ICM are available in Figure~\ref{fig:all_games_appendix} in the appendix). Altogether, it appears that the benefit of exploration bonuses is mainly allocated towards \textsc{Montezuma's Revenge}{}. None of them except NoisyNets seems to improve over $\epsilon$-greedy by significant margin.
Bonus-based methods may lead to increased performance on a few games but seem to deteriorate performance by a roughly equal amount on other games.
We report improvement over $\epsilon$-greedy
We could have hoped that these methods focus their attention on hard exploration games at the expense of easier ones, meaning they trade exploitation for exploration. Unfortunately it does not seem to be the case as they do not exhibit a preference for hard exploration games. We may wonder if these methods are overfitting on \textsc{Montezuma's Revenge}{}.

\begin{figure*}
\centering
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/cts_vs_rainbow_new_tuning.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/rnd_vs_rainbow_new_tuning.pdf}
    \end{subfigure}%
\caption{Improvements (in percentage of AUC) of Rainbow with CTS and RND over Rainbow with $\epsilon$-greedy exploration in 60 Atari games when hyperparameters have been tuned on \textsc{Seaquest}, \textsc{Qbert}, \textsc{Pong}, \textsc{Breakout} and \textsc{Asterix}. The game \textsc{Montezuma's Revenge}{} is represented in purple. Games in the training set have stars on top of their bar.}
\label{fig:overfit_auc}
\end{figure*}

\subsection{Hyperparameter tuning procedure}
\label{sec:hyp_tuning}

Previous experiments have so far depicted  a somewhat dismal picture of bonus-based methods, in particular their penchant to overfit on \textsc{Montezuma's Revenge}{}.
Though it is unfortunate to see they do not generalize to the full Atari gamut, one may wonder if their tendency to overfit to \textsc{Montezuma's Revenge}{} specifically is caused by the hyperparameter tuning procedure or their inherent design. The experiments in this section aim at addressing this issue. We ran a new hyperparameter sweep on CTS and RND using a new training set. We chose these algorithms as we found them to be particularly sensitive to their hyperparameters. The new training set includes the games \textsc{Pong}, \textsc{Asterix}, \textsc{Seaquest}, \textsc{Q*bert} and \textsc{Breakout}. This set as been previously used as a training set to tune reinforcement learning agents in the literature \citep{bellemare2017distributional,dabney2018distributional}.

Results are depicted in Figure~\ref{fig:overfit_auc}. Both algorithm still perform much better than $\epsilon$-greedy  exploration on \textsc{Montezuma's Revenge}{}. After 200 millions frames, CTS reaches 4200 points while RND reaches 2700 points. As it is to be expected, performance also increased for games within the training set. A notable example is CTS on \textsc{Seaquest} which now improves over the $\epsilon$-greedy  baseline by $140\%$ instead of $120\%$ previously. Nevertheless the conclusions from Section \ref{sec:full_atari} remain valid. Bonus-based exploration strategies still provide only limited value except for a few games. In addition, neither algorithm seems to achieve better results on easy exploration problems outside of the training set.

\subsection{Amount of training data}

Current results so far showed that exploration bonuses provide little benefits in the context of exploration in the ALE. Nonetheless, our experiments have been limited to 200 millions environment, it is possible that with additional data. This would be in line with an emerging trend of training agents an order of magnitude longer in order to produce a high-scoring policy, irrespective of the sample cost \citep{Espeholt2018IMPALASD,burda2018exploration,kapturowski2018recurrent}. In this section we provide experiments to contradict this hypothesis. We reuse agents trained in Section 4.2.2 and lengthen the amount training data they can process to 1 billion environment frames. We use Atari 2600 games from the set hard exploration with sparse rewards and the Atari training set. See Figure \ref{fig:1b} for training curves.
On easier exploration problem all exploration strategies see their score gracefully scale with additional data.
In hard exploration games, none of the exploration strategies seem to benefit from the additional training data.
Score on most games seem to plateau and may even decrease. This is particularly stricking in \textsc{Montezuma's Revenge}{}. After a while, agents are unable to make further progress and their bonus collapse. When that happens, bonus-based methods cannot even rely on $\epsilon$-greedy  exploration to explore and may therefore see their performance decrease.
This behavior may be attributed to our evaluation setting, tuning hyperparameters to perform best after one billion training frames will likely improve results. It is however unsatisfactory to see that exploration methods do not scale effortlessly as they receive more data.

\begin{figure*}
\centering
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_MontezumaRevenge.pdf}
      \label{fig:1b_montezuma}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_Gravitar.pdf}
      \label{fig:1b_gravitar}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_PrivateEye.pdf}
      \label{fig:1b_privateeye}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_Venture.pdf}
      \label{fig:1b_venture}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_Solaris.pdf}
      \label{fig:1b_solaris}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_Pitfall.pdf}
      \label{fig:1b_pitfall}
    \end{subfigure}%
\caption{Hard exploration games.}
\label{fig:1b_hard}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_Asterix.pdf}
      \label{fig:1b_asterix}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_Freeway.pdf}
      \label{fig:1b_freeway}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_BeamRider.pdf}
      \label{fig:1b_beamrider}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_SpaceInvaders.pdf}
      \label{fig:1b_spaceinvaders}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/1b_frames/1b_Seaquest.pdf}
      \label{fig:1b_seaquest}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.7\linewidth]{figures/all_games/legend.png}
      \label{fig:seaquest}
    \end{subfigure}%
\caption{Atari training set.}
\label{fig:1b_easy}
\end{subfigure}
\caption{Evaluation of bonus-based methods when training is extended to one bilion frames}
\label{fig:1b}
\end{figure*}

\section{Conclusion}

Recently, many exploration methods have been introduced with confounding factors within their evaluation -- longer training duration, different model architecture and new hyper parameters.
This practice obscures the true value of these methods and makes it difficult to prioritize more promising directions of investigation.
Therefore, following a growing trend in the reinforcement learning community, we advocate for better practices on empirical evaluation for exploration to fairly assess the contribution of newly proposed methods.
In a standardized training environment and context, we found that current bonus-based methods are unable to surpass $\epsilon$-greedy exploration.
This shows that more work is still needed to address the exploration problem in complex environments.

We may wonder why do we not see a positive impact of bonus-based exploration?  One possible explanation is our use of the relatively sophisticated Rainbow learning algorithm. The benefits that others have observed using exploration bonuses might be made redundant through other mechanisms already in Rainbow, such as a prioritized replay buffer.
An important transition may only be observed with low frequency but it can be sampled at a much higher rate by the replay buffer. As a result, the agent can learn from it effectively without the need for encouragement from the exploration bonus to visit that transition more frequently.
Though the merits of bonus-based methods have been displayed with less efficient learning agents, these benefits did not carry on to improved learning agents.
This is disappointing given that the simple NoisyNets baseline showed efficient exploration can still achieve noticeable gains on the ALE.
As of now, the exploration and credit assignment communities have mostly been operating independently, our work suggests that they may have to start working hand in hand to design new agents to make reinforcement learning truly sample efficient.

\clearpage

\section{Introduction}
In reinforcement learning, the exploration-exploitation trade-off describes an agent's need to balance maximizing its cumulative rewards and improving its knowledge of the environment.
While many practitioners still rely on simple exploration strategies such as the $\epsilon$-greedy scheme, in recent years a rich body of work has emerged for efficient exploration in deep reinforcement learning.
One of the most successful approaches to exploration in deep reinforcement learning is to provide an exploration bonus based on the relative novelty of the state.
This bonus may be computed, for example, from approximate counts \citep{bellemare2016unifying,count-based,tang2017exploration,machado18_SR}, from the prediction error of a dynamics model \citep[ICM, ][]{pathak17curiositydriven} or by measuring the discrepancy to a random network \citep[RND, ][]{burda2018exploration}.

\citet{bellemare2016unifying} argued for the importance of the Atari 2600 game \textsc{Montezuma's Revenge}{} as a challenging domain for exploration.
\textsc{Montezuma's Revenge}{} offers a sparse reinforcement signal and relatively open domain that distinguish it from other Atari 2600 games supported by the Arcade Learning Environment \citep[ALE;][]{bellemare2013arcade}. As a consequence,
recent exploration research (bonus-based or not) has aspired to improve performance on this particular game, ranging from a much deeper exploration (6600 points; Bellemare et al., 2016), to completing the first level \citep[14000 points;][]{pohlen18observe,burda2018exploration}, to super-human performance \citep[400,000 points;][]{ecoffet19goexplore}.

Yet the literature on exploration in reinforcement learning still lacks a systematic comparison between existing methods, despite recent entreaties for better practices to yield reproducible research \citep{henderson2018deep,machado2018revisiting}.
One of the original tenets of the ALE is that agent evaluation should take on the entire suite of 60 available Atari 2600 games. Even within the context of bonus-based exploration, \textsc{Montezuma's Revenge}{} is but one of seven hard exploration, sparse rewards games \citep{bellemare2016unifying}.
Comparisons have been made between agents trained under different regimes: using different learning algorithms and varying numbers of training frames, with or without reset, and with and without controller noise \citep[e.g. \emph{sticky actions}][]{machado2018revisiting}.
As a result, it is often unclear if the claimed performance improvements are due to the exploration method or other architectural choices, and whether these improvements carry over to other domains.
The main conclusion of our research is that an over-emphasis on one Atari 2600 game, combined with different training conditions, may have obfuscated the real pace of progress in exploration research.

To come to this conclusion, we revisit popular bonus-based exploration methods (pseudo-counts, PixelCNN-counts, RND, and ICM) in the context of a common evaluation framework. We apply the Rainbow \citep{hessel2018rainbow} agent in turn to \textsc{Montezuma's Revenge}{}, Bellemare et al.'s seven hardest Atari 2600 games for exploration, and the full suite from the ALE.

\textbf{Source of exploration bonus.} We find that all agents perform better than an $\epsilon$-greedy baseline, confirming that exploration bonuses do provide meaningful gains. However, we also find that more recent exploration bonuses do not, by themselves, lead to higher performance than the older pseudo-counts method. Across the remainder of hard exploration games, we find that all bonuses lead to performance that is comparable, and in one case worse, than $\epsilon$-greedy.

\textbf{Performance across full Atari 2600 suite.} One may expect a good exploration algorithm to handle the exploration/exploitation trade-off efficiently: exploring in difficult games, without losing too much in games where exploration is unnecessary. We find that performance on \textsc{Montezuma's Revenge}{} is in fact \emph{anticorrelated} with performance across the larger suite. Of the methods surveyed, the only one to demonstrate better performance across the ALE is the non-bonus-based Noisy Networks \citep{fortunato18noisy}, which provide as an additional point of comparison. Noisy Networks perform worse on \textsc{Montezuma's Revenge}{}.

\textbf{Hyperparameter tuning procedure.}
The standard practice in exploration research has been to tune hyperparameters on \textsc{Montezuma's Revenge}{} then evaluate on other Atari 2600 games. By virtue of this game's particular characteristics, this approach to hyperparameter tuning may unnecessarily increase the exploratory behaviour of exploration strategies towards a more exploratory behavior, and explain our observation that these strategies perform poorly in easier games. However, we find that tuning hyperparameters on the original ALE training set does not improve performance across Atari 2600 games beyond that of $$\epsilon$-greedy $.

\textbf{Amount of training data.} By design, exploration methods should be sample-efficient. However, some of the most impressive gains in exploration on \textsc{Montezuma's Revenge}{} have made use of significantly more data (1.97 billion Atari 2600 frames for RND, versus 100 million frames for the pseudo-count method). We find that, within our common evaluation framework, additional data does not play an important role on exploration performance.

Altogether, our results suggests that more research is needed to make bonus-based exploration robust and reliable, and serve as a reminder of the pitfalls of developing and evaluating methods primarily on a single domain.

\input{exploration_methods}

\section{Related Work}

Deep Q-Networks \citep[DQN;][]{mnih2015human} has shown that learning control policies from high dimensional inputs such as images is possible and that such an approach achieves above human-level performance on many games supported by the ALE.
However, in the set of Atari games supported by the ALE, there are some games in which DQN, and the approaches that succeed it, are not able to outperform a purely random agent.
A prominent example is the game \textsc{Montezuma's Revenge}{}.
In this game the agent must learn to navigate an environment with different rooms filled with life threatening traps.
As an additional difficulty, the reward function in this environment is sparse and random exploration is unlikely to lead the agent towards positive rewards.
This is one of the main reasons algorithms that rely on $\epsilon$-greedy  exploration, such as DQN and many of its successors, were unable to make meaningful progress in this problem.
Recent work has addressed this issue through the use smarter exploration mechanisms.
\citet{bellemare2016unifying} proposed the first agent capable of reliably advance through the game.
Their agent scores, on average, 3700 points and explores 15 of 24 rooms of the first level.
Other exploration bonuses have since been able to reach similar level of performance \citep{count-based,martin2017count,machado18_SR}.
Recently, Random Network Distillation \citep{burda2018exploration} exceeded those results.
Their agent is able to score, on average, 8150 points, visiting 22 rooms and occasionally clearing the first level.

In parallel, improvements in credit assignment for reinforcement learning lead to more sample efficient learning algorithm \citep{hessel2018rainbow,horgan2018distributed,Espeholt2018IMPALASD,kapturowski2018recurrent}.
Though they still rely on $\epsilon$-greedy  exploration to explore, better credit assignment also positively impacted exploration.
On \textsc{Montezuma's Revenge}{}, many of them are able to pass the first few rooms of the game, however they are usually unable to overcome the barrier of 2500 points.

Remarkably, there is little to no comparison between existing exploration methods on the ALE.
The large-scale study of \citet{burda2018large} is most similar to our work. \citet{burda2018large} benchmark various exploration bonuses based on prediction error \citep{schmidhuber1991curious,pathak17curiositydriven} within a set of simulated environment including many Atari 2600 games.
Their study differs from ours as their setting ignores the environment reward and instead learns exclusively from the intrinsic reward signal. Outside of the ALE, \citet{osband2019behaviour} provide a collection of experiments that investigate core capabilities of reinforcement learning agents including exploration.

\section{Empirical Results}
In this section we present our experimental study of bonus-based exploration methods.

\subsection{Experimental protocol}
We evaluate the three bonus-based methods introduced in Section \ref{sec:exploration_methods} as well as NoisyNets and $\epsilon$-greedy exploration.
To do so, we keep our training protocol fixed throughout our experiments.
All methods are trained with a common agent architecture, the Rainbow implementation provided by the Dopamine framework \citep{castro2018dopamine} which includes Rainbow's three most important component: $n$-step updates \citep{mnih2016asynchronous}, prioritized experience replay \citep{schaul2015prioritized} and distributional reinforcement learning \citep{bellemare2017distributional}. Rainbow was designed combining several improvements to value-based agents that were developed independently. Pairing Rainbow with recent exploration bonuses should lead to further benefits. We also keep the original hyperparameters of the learning algorithm fixed to avoid introducing bias in favor of a specific bonus.

Unless specified our agents are trained for 200 million frames.
Following \citet{machado2018revisiting} recommendations we run the ALE in the stochastic setting using sticky actions ($\varsigma = 0.25$) for all agents during training and evaluation.
We also do not use the mixed Monte-Carlo return \citep{bellemare2016unifying,count-based} or other techniques that may positively impact bonus based methods such as in \citet{burda2018exploration}.

\begin{figure}
    \centering
    \includegraphics[width=0.5\linewidth]{figures/all_games/MontezumaRevenge.pdf}

    \caption{A comparison of different exploration methods on \textsc{Montezuma's Revenge}{}.
    }
    \label{fig:montezuma}
\end{figure}

\subsection{\textsc{Montezuma's Revenge}{} Without Confounders}
\label{sec:montezuma}
Our first set of results compare exploration methods introduced in section \ref{sec:exploration_methods} on the infamous Atari 2600 game \textsc{Montezuma's Revenge}{}. We follow the standard procedure to use this game to tune the hyperparameters of each exploration bonus.
Details regarding implementation and hyperparameter tuning may be found in Appendix \ref{app:hparam_tuning}.
Figure~\ref{fig:montezuma} shows training curves (averaged over 5 random seeds) for Rainbow augmented with different exploration bonuses.

As anticipated, $\epsilon$-greedy exploration performs poorly here and struggle in such a hard exploration game. On the other hand, exploration bonuses have a huge impact and all eventually beat the baselnes. Only ICM is unable to surpass the baselines $\epsilon$-greedy  and NoisyNets by a large margin, RND, CTS and PixelCNN all average close to 5000 points.
Interestingly we observe that more recent bonus like RND does not lead to higher performance over the older pseudo-count method.
Of note, the performance we report at 200 millions frames improves on the performance reported in their original paper for each method. As expected Rainbow leads to increased performance over older DQN variants previously used in the litterature.

\begin{figure*}
\centering
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Gravitar.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=\linewidth]{figures/all_games/PrivateEye.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Venture.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Solaris.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Pitfall.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Freeway.pdf}
    \end{subfigure}%
\caption{Hard exploration games.}
\label{fig:hard}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=\linewidth]{figures/all_games/Asterix.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Freeway.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/BeamRider.pdf}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/SpaceInvaders.pdf}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/all_games/Seaquest.pdf}
      \label{fig:seaquest}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.7\linewidth]{figures/all_games/legend.png}
      \label{fig:seaquest}
    \end{subfigure}%
\caption{Atari training set.}
\label{fig:easy}
\end{subfigure}
\caption{Evaluation of different bonus-based exploration methods on several Atari games, curves are averaged over 5 runs, shaded area denotes variance.}
\label{fig:evaluation}
\end{figure*}

\subsection{Exploration methods evaluation}
It is standard in the exploration community to, first tune hyperparameters on \textsc{Montezuma's Revenge}{}, then, evaluate these hyperparameters on the remaining hard exploration games with sparse rewards. This is not in line with the original ALE guidelines which recommend to evaluate on the entire suite of Atari 2600 games. In this section we provide empirical evidence that, failing to follow the ALE guidelines may interfere with the conclusions of the evaluation.

\subsubsection{Hard exploration games}
\label{sec:hard}

We now turn our attention to the set of games categorized as hard exploration games with sparse rewards in \citeauthor{bellemare2016unifying}'s taxonomy (the taxonomy is available in Appendix~\ref{app:taxonomy}). It includes ALE's most difficult games for exploration, this is where good exploration strategies should shine and provide the biggest improvements. These games are: \textsc{Gravitar}, \textsc{Private Eye}, \textsc{Venture}, \textsc{Solaris}, \textsc{Pitfall! } and \textsc{Freeway}.

We evaluate agents whose hyperparameters were tuned on \textsc{Montezuma's Revenge}{} on this set of games.
Training curves averaged over 5 runs are shown in Figure~\ref{fig:hard}.
We find that performance of each method on \textsc{Montezuma's Revenge}{} does not correlate with performance on other hard exploration domains.
All methods seem to behave similarly contrary to our observations on \textsc{Montezuma's Revenge}{}, .
In particular, there is no visible difference between $\epsilon$-greedy and more sophisticated exploration bonuses.
$\epsilon$-greedy exploration is on par with every other method and even outperforms them by a significant margin on \textsc{Gravitar}.
These games were initially classified to be hard exploration problems because a DQN agent using $\epsilon$-greedy exploration was unable to achieve a high scoring policy; it is no longer the case with stronger learning agents available today.

\subsubsection{Full Atari suite}
\label{sec:full_atari}

The set of hard exploration games was chosen to highlight the benefits of exploration methods, and, as a consequence, performance on this set may not be representative of an algorithm capabilities on the whole Atari suite. Indeed, exploration bonuses can negatively impact performance by skewing the reward landscape.
To demonstrate how the choice of particular evaluation set can lead to different conclusions we also evaluate our agents on the original Atari training set which includes the games \textsc{Asterix}, \textsc{Freeway}, \textsc{Beam Rider}, \textsc{Space Invaders} and \textsc{Seaquest}. Except for \textsc{Freeway} all these games are easy exploration problems \citep{bellemare2016unifying}.

Figure~\ref{fig:easy} shows training curves for these games.
Pseudo-counts with a CTS model appears to struggle when the environment is an easy exploration problem and end up performing worse on every game except \textsc{Seaquest}.
RND and ICM are able to consistently match $\epsilon$-greedy exploration but never beat it.
It appears that bonus-based methods have limited benefits in the context of easy exploration problems.
Finally, despite its limited performance on \textsc{Montezuma's Revenge}{} we found that NoisyNets gave the most consistent improvements.

\begin{figure*}
\centering
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/cts_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/rnd_vs_rainbow.pdf}
    \end{subfigure}%
    \vspace{1mm}

    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/noisy_vs_rainbow.pdf}
    \end{subfigure}%
\caption{Improvements (in percentage of AUC) of Rainbow with various exploration methods over Rainbow with $\epsilon$-greedy exploration in 60 Atari games. The game \textsc{Montezuma's Revenge}{} is represented in purple.}
\label{fig:all_games}
\end{figure*}

Overall, while the Atari training set and the set of the hard exploration games both show that bonus-based method only provide marginal improvements they lead us to different conclusions regarding the best performing exploration scheme.
It appears that to fully quantify the behavior of exploration methods one cannot avoid evaluating on the whole Atari suite.
We do so and add the remaining Atari games to our study. See Figure~\ref{fig:evaluation} for a high level comparison for CTS, RND and NoisyNets (PixelCNN and ICM are available in Figure~\ref{fig:all_games_appendix} in the appendix). Altogether, it appears that the benefit of exploration bonuses is mainly allocated towards \textsc{Montezuma's Revenge}{}. None of them except NoisyNets seems to improve over $\epsilon$-greedy by significant margin.
Bonus-based methods may lead to increased performance on a few games but seem to deteriorate performance by a roughly equal amount on other games.
We report improvement over $\epsilon$-greedy
We could have hoped that these methods focus their attention on hard exploration games at the expense of easier ones, meaning they trade exploitation for exploration. Unfortunately it does not seem to be the case as they do not exhibit a preference for hard exploration games. We may wonder if these methods are overfitting on \textsc{Montezuma's Revenge}{}.

\begin{figure*}
\centering
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/cts_vs_rainbow_new_tuning.pdf}
    \end{subfigure}%
    \vspace{1mm}
    \begin{subfigure}{\textwidth}
    \centering
      \includegraphics[width=\linewidth]{figures/agent_comparison/rnd_vs_rainbow_new_tuning.pdf}
    \end{subfigure}%
\caption{Improvements (in percentage of AUC) of Rainbow with CTS and RND over Rainbow with $\epsilon$-greedy exploration in 60 Atari games when hyperparameters have been tuned on \textsc{Seaquest}, \textsc{Qbert}, \textsc{Pong}, \textsc{Breakout} and \textsc{Asterix}. The game \textsc{Montezuma's Revenge}{} is represented in purple. Games in the training set have stars on top of their bar.}
\label{fig:overfit_auc}
\end{figure*}

\subsection{Hyperparameter tuning procedure}
\label{sec:hyp_tuning}

Previous experiments have so far depicted  a somewhat dismal picture of bonus-based methods, in particular their penchant to overfit on \textsc{Montezuma's Revenge}{}.
Though it is unfortunate to see they do not generalize to the full Atari gamut, one may wonder if their tendency to overfit to \textsc{Montezuma's Revenge}{} specifically is caused by the hyperparameter tuning procedure or their inherent design. The experiments in this section aim at addressing this issue. We ran a new hyperparameter sweep on CTS and RND using a new training set. We chose these algorithms as we found them to be particularly sensitive to their hyperparameters. The new training set includes the games \textsc{Pong}, \textsc{Asterix}, \textsc{Seaquest}, \textsc{Q*bert} and \textsc{Breakout}. This set as been previously used as a training set to tune reinforcement learning agents in the literature \citep{bellemare2017distributional,dabney2018distributional}.

Results are depicted in Figure~\ref{fig:overfit_auc}. Both algorithm still perform much better than $\epsilon$-greedy  exploration on \textsc{Montezuma's Revenge}{}. After 200 millions frames, CTS reaches 4200 points while RND reaches 2700 points. As it is to be expected, performance also increased for games within the training set. A notable example is CTS on \textsc{Seaquest} which now improves over the $\epsilon$-greedy  baseline by $140\%$ instead of $120\%$ previously. Nevertheless the conclusions from Section \ref{sec:full_atari} remain valid. Bonus-based exploration strategies still provide only limited value except for a few games. In addition, neither algorithm seems to achieve better results on easy exploration problems outside of the training set.

\subsection{Amount of training data}

Current results so far showed that exploration bonuses provide little benefits in the context of exploration in the ALE. Nonetheless, our experiments have been limited to 200 millions environment, it is possible that with additional data exploration bonuses would perform better. This would be in line with an emerging trend of training agents an order of magnitude longer in order to produce a high-scoring policy, irrespective of the sample cost \citep{Espeholt2018IMPALASD,burda2018exploration,kapturowski2018recurrent}. In this section we provide experiments to contradict this hypothesis. We reuse agents trained in Section 4.2.2 and lengthen the amount training data they can process 1 billion environment frames. We use Atari 2600 games from the set hard exploration with sparse rewards and the Atari training set. See Figure \ref{fig:1b} for training curves.
On easier exploration problem all exploration strategies see their score gracefully scale with additional data.
In hard exploration games, none of the exploration strategies seem to benefit from receiving more data.
Score on most games seem to plateau and may even decrease. This is particularly apparent in \textsc{Montezuma's Revenge}{} where only RND actually benefits from longer training. After a while, agents are unable to make further progress and their bonus may collapse. When that happens, bonus-based methods cannot even rely on $\epsilon$-greedy  exploration to explore and may therefore see their performance decrease.
This behavior may be attributed to our evaluation setting, tuning hyperparameters to perform best after one billion training frames will likely improve results. It is however unsatisfactory to see that exploration methods do not scale effortlessly as they receive more data.
In practice, recent exploration bonuses have required a particular attention to handle large amount of training data \citep[e.g.][]{burda2018exploration}.

\begin{figure*}
\centering
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_MontezumaRevenge.pdf}
      \label{fig:1b_montezuma}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Gravitar.pdf}
      \label{fig:1b_gravitar}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_PrivateEye.pdf}
      \label{fig:1b_privateeye}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Venture.pdf}
      \label{fig:1b_venture}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Solaris.pdf}
      \label{fig:1b_solaris}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Pitfall.pdf}
      \label{fig:1b_pitfall}
    \end{subfigure}%
\caption{Hard exploration games.}
\label{fig:1b_hard}
\end{subfigure}%
\begin{subfigure}{0.5\textwidth}
    \begin{subfigure}{0.5\textwidth}
        \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Asterix.pdf}
      \label{fig:1b_asterix}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Freeway.pdf}
      \label{fig:1b_freeway}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_BeamRider.pdf}
      \label{fig:1b_beamrider}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_SpaceInvaders.pdf}
      \label{fig:1b_spaceinvaders}
    \end{subfigure}%
    \vspace{2mm}
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.9\linewidth]{figures/all_games/1b_Seaquest.pdf}
      \label{fig:1b_seaquest}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
    \centering
      \includegraphics[width=.7\linewidth]{figures/all_games/legend.png}
      \label{fig:seaquest}
    \end{subfigure}%
\caption{Atari training set.}
\label{fig:1b_easy}
\end{subfigure}
\caption{Evaluation of bonus-based methods when training is extended to one billion frames.}
\label{fig:1b}
\end{figure*}

\section{Conclusion}

Recently, many exploration bonuses have been introduced with confounding factors within their evaluation -- longer training duration, different model architecture and other ad-hoc techniques
This practice obscures the true value of these methods and makes it difficult to prioritize more promising directions of investigation.
Therefore, following a growing trend in the reinforcement learning community, we advocate for better practices on empirical evaluation for exploration to fairly assess the contribution of newly proposed methods.
In a standardized training environment and context, we found that current bonus-based methods are unable to surpass $\epsilon$-greedy exploration.
As a whole it
This shows that more work is still needed to address the exploration problem in complex environments.

We may wonder why do we not see a positive impact of bonus-based exploration?  One possible explanation is our use of the relatively sophisticated Rainbow learning algorithm. The benefits that others have observed using exploration bonuses might be made redundant through other mechanisms already in Rainbow, such as a prioritized replay buffer.
An important transition may only be observed with low frequency but it can be sampled at a much higher rate by the replay buffer. As a result, the agent can learn from it effectively without the need for encouragement from the exploration bonus to visit that transition more frequently.
Though the merits of bonus-based methods have been displayed with less efficient learning agents, these benefits did not carry on to improved learning agents.
This is disappointing given that the simple NoisyNets baseline showed efficient exploration can still achieve noticeable gains on the ALE.
As of now, the exploration and credit assignment communities have mostly been operating independently, our work suggests that they may have to start working hand in hand to design new agents to make reinforcement learning truly sample efficient.

\clearpage