Noisy Networks for Exploration
Meire Fortunato\thanks{Equal contribution.
We introduce \algoinit{, a deep reinforcement learning agent with parametric noise added to its weights, and show that the induced stochasticity of the agent's policy can be used to aid efficient exploration. The parameters of the noise are learned with gradient descent along with the remaining network weights. \algoinit{ is straightforward to implement and adds little computational overhead. We find that replacing the conventional exploration heuristics for A3C, DQN and Dueling agents (entropy reward and $\epsilon$-greedy respectively) with NoisyNet yields substantially higher scores for a wide range of Atari games, in some cases advancing the agent from sub to super-human performance.
iclr2018_conference.tex
\documentclass{article} % For LaTeX2e
\usepackage{iclr2018_conference,times}
%\usepackage[table]{xcolor}
\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{subfigure}
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{mathtools}
%\usepackage{xcolor}
\usepackage{enumerate}
%\mathtoolsset{showonlyrefs=true}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
%\usepackage{letltxmacro}
\newcommand{\argmax}{\operatorname*{argmax}}
\newcommand{\argmin}{\operatorname*{argmin}}
\newcommand{\var}{\operatorname*{Var}}
\newcommand{\lstd}{\operatorname*{LSTD}}
\newcommand{\diag}{\operatorname*{diag}}
\newcommand{\sgn}{\operatorname*{sgn}}
\newcommand{\lin}{\operatorname*{lin}}
\newcommand{\supp}{\operatorname*{Supp}}
\newcommand{\todo}[2]{{\color{yellow}{#1 TODO: #2}}}
\newcommand{\algoinit}{NoisyNet}
\newcommand{\algofull}{Noisy Networks for Reinforcement Learning}
\newcommand*\samethanks[1][\value{footnote}]{\footnotemark[#1]}
\title{Noisy Networks for Exploration}
\newcommand\blfootnote[1]{%
  \begingroup
  \renewcommand\thefootnote{}\footnote{#1}%
  \addtocounter{footnote}{-1}%
  \endgroup
}

\author{
 Meire Fortunato\thanks{Equal contribution.}
\quad Mohammad Gheshlaghi Azar\footnotemark[1]
\quad Bilal Piot \footnotemark[1] \And
\textbf{Jacob Menick
\quad  Matteo Hessel
\quad Ian Osband
\quad Alex Graves
\quad Vlad Mnih} \And
\textbf{Remi Munos
\quad Demis Hassabis 
\quad Olivier Pietquin
\quad Charles Blundell 
\quad Shane Legg}  \\ \\
DeepMind
  \texttt{\{meirefortunato,mazar,piot,} \\
  \texttt{jmenick,mtthss,iosband,gravesa,vmnih,}\\
  \texttt{munos,dhcontact,pietquin,cblundell,legg\}@google.com} \\
}

\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}

\iclrfinalcopy % Uncomment for camera-ready version, but NOT for submission.

\begin{document}

\maketitle

\input{symbolsdef.tex}

\begin{abstract}
We introduce \algoinit{}, a deep reinforcement learning agent with  parametric noise added to its weights, and show that the induced stochasticity of the agent's policy can be used to aid efficient exploration.
The parameters of the noise are learned with gradient descent along with the remaining network weights. \algoinit{} is straightforward to implement and adds little computational overhead.
We find that replacing the conventional exploration heuristics for A3C, DQN and Dueling  agents (entropy reward and $\epsilon$-greedy respectively) with NoisyNet yields substantially higher scores for a wide range of Atari games, in some cases advancing the agent from sub to super-human performance.
\end{abstract}
%
\section{Introduction}
\label{sec:introduction}
Despite the wealth of research into efficient methods for exploration in Reinforcement Learning (RL) \citep{kearns2002near,jaksch2010near}, most exploration heuristics rely on random perturbations of the agent's policy, such as $\epsilon$-greedy \citep{sutton1998reinforcement} or entropy regularisation \citep{williams1992simple}, to induce novel behaviours. 
However such local `dithering' perturbations are unlikely to lead to the large-scale behavioural patterns needed for efficient exploration in many environments \citep{osband2017deep}.

\textit{Optimism in the face of uncertainty} is a common exploration heuristic in reinforcement learning.
Various forms of this heuristic often come with theoretical guarantees on agent performance \citep{azar2017minimax,lattimore2013sample,jaksch2010near,auer2007logarithmic,kearns2002near}.
However, these methods are often limited to small state-action spaces or to linear function approximations and are not easily applied with more complicated function approximators such as neural networks (except from work by \citep{geist2010kalman,geist2010managing} but it doesn't come with convergence guarantees). A more structured approach to exploration is to augment the environment's reward signal with an additional \textit{intrinsic motivation} term \citep{singh2004intrinsically} that explicitly rewards novel discoveries.
Many such terms have been proposed, including learning progress \citep{oudeyer07intrinsic}, compression progress \citep{schmidhuber2010formal}, variational information maximisation \citep{houthooft2016vime} and prediction gain \citep{bellemare2016unifying}.
One problem is that these methods separate the mechanism of generalisation from that of exploration; the metric for intrinsic reward, and--importantly--its weighting relative to the environment reward, must be chosen by the experimenter, rather than learned from interaction with the environment.
Without due care, the optimal policy can be altered or even completely obscured by the intrinsic rewards; furthermore, dithering perturbations are usually needed as well as intrinsic reward to ensure robust exploration \citep{ostrovski2017count}. 
Exploration in the policy space itself, for example, with evolutionary or black box  algorithms~\citep{moriarty1999evolutionary,fix2012monte,2017arXiv170303864S}, usually requires many prolonged interactions with the environment. Although these algorithms are quite generic and can apply to any type of parametric policies (including neural networks), they are usually not data efficient and require a simulator to allow many policy evaluations.

We propose a simple alternative approach, called \algoinit{}, where learned perturbations of the network weights are used to drive exploration.
The key insight is that a single change to the weight vector can induce a consistent, and potentially very complex, state-dependent change in policy over multiple time steps -- unlike dithering approaches where decorrelated (and, in the case of  $\epsilon$-greedy, state-independent) noise is added to the policy at every step.
The perturbations are sampled from a noise distribution.
The variance of the perturbation is a parameter that can be considered as the energy of the injected noise.
These variance parameters are learned using gradients from the reinforcement learning loss function, along side the other parameters of the agent.
The approach differs from parameter compression schemes such as variational inference \citep{hinton1993keeping,bishop1995training,graves2011practical,blundell2015weight,gal16} and flat minima search \citep{hochreiter1997flat} since we do not maintain an explicit distribution over weights during training but simply inject noise in the parameters and tune its intensity automatically. Consequently, it also differs from Thompson sampling \citep{thompson1933likelihood,lipton2016efficient} as the distribution on the parameters of our agents does not necessarily converge to an approximation of a posterior distribution.


At a high level our algorithm is a randomised value function, where the functional form is a neural network. Randomised value functions provide a provably efficient means of exploration \citep{osband2014generalization}. Previous attempts to extend this approach to deep neural networks required many duplicates of sections of the network \citep{osband2016deep}.
By contrast in our \algoinit{} approach while the number of parameters in the linear layers of the network is doubled, as the weights are a simple affine transform of the noise, the computational complexity is typically still dominated by the weight by activation multiplications, rather than the cost of generating the weights. Additionally, it also applies to policy gradient methods such as A3C out of the box \citep{mnih2016asynchronous}.
Most recently (and independently of our work) \citet{plappert2017parameter} presented a similar technique where constant Gaussian noise is added to the parameters of the network. Our method thus differs by the ability of the network to adapt the noise injection with time and it is not restricted to Gaussian noise distributions. We need to emphasise that the idea of injecting noise to improve the optimisation process has been thoroughly studied in the literature of supervised learning and optimisation under different names (e.g., Neural diffusion process ~\citep{mobahi2016training} and graduated optimisation  ~\citep{hazan2016graduated}). These methods often rely on a noise of vanishing size that is non-trainable, as opposed to NoisyNet which tunes the amount of noise by gradient descent. 


NoisyNet can also be adapted to any deep RL algorithm and we demonstrate this versatility by providing \algoinit{} versions of DQN~\citep{mnih2015human}, Dueling~\citep{wang2016Dueling} and A3C~\citep{mnih2016asynchronous} algorithms. Experiments on 57 Atari games show that NoisyNet-DQN and NoisyNetDueling achieve striking gains when compared to the baseline algorithms without significant extra computational cost, and with less hyper parameters to tune. Also the noisy version of A3C provides some improvement over the baseline.
%
\section{Background}
\label{sec:background}
This section provides mathematical background for Markov Decision Processes (MDPs) and deep RL with Q-learning, dueling and actor-critic methods.
\subsection{Markov Decision Processes and Reinforcement Learning}
MDPs model stochastic, discrete-time and finite action space control problems~\citep{bellman1965dynamic,bertsekas1995dynamic,puterman1994markov}.
An MDP is a tuple $M=(\X,\A,R,P,\gamma)$ where $\X$ is the state space, $\A$ the action space, $R$ the reward function, $\gamma\in ]0,1[$ the discount factor and $P$ a stochastic kernel modelling the one-step Markovian dynamics ($P(y|x,a)$ is the probability of transitioning to state $y$ by choosing action $a$ in state $x$). A stochastic policy $\pi$ maps each state to a distribution over actions $\pi(\cdot|x)$ and gives the probability $\pi(a|x)$ of choosing action $a$ in state $x$. The quality of a policy $\pi$ is assessed by the action-value function $Q^\pi$ defined as:
\begin{align}
Q^\pi(x,a)&=\mathbb{E}^\pi\left[\sum_{t=0}^{+\infty}\gamma^t R(x_t,a_t)\right],
\end{align}
where $\mathbb{E}^\pi$ is the expectation over the distribution of the admissible trajectories $(x_0,a_0,x_1, a_1,\dots)$ obtained by executing the policy $\pi$ starting from $x_0=x$ and $a_0=a$. Therefore, the quantity $Q^\pi(x,a)$ represents the expected $\gamma$-discounted cumulative reward collected by executing the policy $\pi$ starting from $x$ and $a$.
A policy is optimal if no other policy yields a higher return.
The action-value function of the optimal policy is $Q^\star(x, a) = \arg\max_\pi Q^\pi(x,a)$.

The value function $V^\pi$ for a policy is defined as $V^\pi(x)=\mathbb{E}_{a~\sim\pi(\cdot|x)}[Q^\pi(x,a)]$, and represents the expected $\gamma$-discounted return collected by executing the policy $\pi$ starting from state $x$.
\subsection{Deep Reinforcement Learning}

Deep Reinforcement Learning uses deep neural networks as function approximators for RL methods. Deep Q-Networks (DQN)~\citep{mnih2015human}, Dueling architecture \citep{wang2016Dueling}, Asynchronous Advantage Actor-Critic (A3C)~\citep{mnih2016asynchronous}, Trust Region Policy Optimisation~\citep{schulman2015trust}, Deep Deterministic Policy Gradient~\citep{lillicrap2015continuous} and distributional RL (C51)~\citep{bellemare2017distributional} are examples of such algorithms. They frame the RL problem as the minimisation of a loss function $L(\theta)$, where $\theta$ represents the parameters of the network. In our experiments we shall consider the DQN, Dueling and A3C algorithms. 

DQN~\citep{mnih2015human} uses a neural network as an approximator for the action-value function of the optimal policy $Q^\star(x, a)$.
DQN's estimate of the optimal action-value function, $Q(x,a)$, is found by minimising the following loss with respect to the neural network parameters $\theta$:
\begin{align}
L(\theta)&=\mathbb{E}_{(x,a,r,y)\sim D}\left[\left(r+ \gamma \max_{b \in A}Q(y,b;\theta^-)-Q(x,a;\theta)\right)^2\right],
\end{align} 
where $D$ is a distribution over transitions $e=(x,a,r=R(x,a),y\sim P(\cdot|x,a))$ drawn from a replay buffer of previously observed transitions. 
Here $\theta^-$ represents the parameters of a fixed and separate target network which is updated ($\theta^-\leftarrow\theta$) regularly to stabilise the learning.
An $\epsilon$-greedy policy is used to pick actions greedily according to
the action-value function $Q$ or, with probability $\epsilon$, a random action is taken.

The Dueling DQN  \citep{wang2016Dueling} is an extension of the DQN  architecture. The main difference is in using Dueling network architecture as opposed to the Q network in DQN. Dueling network estimates the action-value function using two parallel sub-networks, the value and advantage sub-network, sharing a convolutional layer. Let $\theta_{\text{conv}}$, $\theta_V$, and $\theta_A$ be, respectively, the parameters of the convolutional encoder $f$, of the value network $V$, and of the advantage network $A$; and $\theta =\{\theta_{\text{conv}},\theta_V,\theta_A\}$ is their concatenation. The output of these two networks are combined  as follows for every  $(x,a)\in \X\times\A$:
%
\begin{equation} 
\label{Dueling}
Q(x,a;\theta) = V(f(x;\theta_{\text{conv}}),\theta_V) + A(f(x;\theta_{\text{conv}}),a;\theta_A) - \frac{\sum_{b}A(f(x;\theta_{\text{conv}}),b;\theta_A)}{N_\text{actions}}.
\end{equation}
%

The Dueling algorithm then makes use of the double-DQN update rule \citep{van2016deep} to optimise $\theta$:

\begin{align}
L(\theta)&=\mathbb{E}_{(x,a,r,y)\sim D}\left[\left(r+ \gamma Q(y,b^*(y);\theta^-)-Q(x,a;\theta)\right)^2\right],
\\
\text{s.t.}\qquad b^*(y)&=\arg\max_{b\in\A}Q(y,b;\theta),
\end{align} 

where the definition distribution $D$ and the target network parameter set $\theta^-$ is identical to DQN. 

In contrast to DQN and Dueling, A3C~\citep{mnih2016asynchronous} is a policy gradient algorithm.
A3C's network directly learns a policy $\pi$  and a value function $V$ of its policy.
The gradient of the loss on the A3C policy at step $t$ for the roll-out $(x_{t+i},a_{t+i}\sim\pi(\cdot|x_{t+i};\theta),r_{t+i})_{i=0}^{k}$ is:
\begin{equation}
\nabla_{\theta}L^\pi(\theta)=-\mathbb{E}^\pi\left[\sum_{i=0}^k\nabla_{\theta}\log(\pi(a_{t+i}|x_{t+i};\theta))A(x_{t+i}, a_{t+i};\theta)+\beta\sum_{i=0}^k\nabla_{\theta} H(\pi(\cdot|x_{t+i};\theta))\right].
\end{equation}
$H[\pi(\cdot|x_t; \theta)]$ denotes the entropy of the policy $\pi$ and $\beta$ is a hyper parameter that trades off between optimising the advantage function and the entropy of the policy.
The advantage function $A(x_{t+i}, a_{t+i};\theta)$ is the difference between observed returns and estimates of the return produced by A3C's value network: $A(x_{t+i}, a_{t+i};\theta) = \sum_{j=i}^{k-1}\gamma^{j-i}r_{t+j}+\gamma^{k-i}V(x_{t+k};\theta) - V(x_{t+i};\theta)$, $r_{t+j}$ being the reward at step $t+j$ and $V(x;\theta)$ being the agent's estimate of value function of state $x$.

The parameters of the value function are found to match on-policy returns; namely we have 
\begin{equation}L^V(\theta) = \sum_{i=0}^k \mathbb{E}^\pi\left[(Q_i-V(x_{t+i};\theta))^2 \left|\right. x_{t+i} \right]\end{equation}
\noindent where $\Q_i$ is the return obtained by executing policy $\pi$ starting in state $x_{t+i}$.
In practice, and as in \cite{mnih2016asynchronous}, we estimate $Q_i$ as $\hat{Q}_i=\sum_{j=i}^{k-1}\gamma^{j-i}r_{t+j}+\gamma^{k-i}V(x_{t+k};\theta)$ where $\{r_{t+j}\}_{j=i}^{k-1}$ are rewards observed by the agent, and $x_{t+k}$ is the $k$th state observed when starting from observed state $x_t$.
The overall A3C loss is then $L(\theta) = L^\pi(\theta) + \lambda L^V(\theta)$ where $\lambda$ balances optimising the policy loss relative to the baseline value function loss.


\section{NoisyNets for Reinforcement Learning}
\label{sec:noisynets}

NoisyNets are neural networks whose weights and biases are perturbed by a parametric function of the noise. These parameters are adapted with gradient descent. More precisely, let $y=f_\theta(x)$ be a neural network parameterised by the vector of \emph{noisy} parameters $\theta$ which takes the input $x$ and outputs $y$.  We represent the noisy parameters $\theta$ as $\theta \eqdef \mu +\Sigma\odot\eps$, where  $\zeta\eqdef(\mu,\Sigma)$ is a set of vectors of learnable parameters, $\eps$ is a vector of zero-mean noise with fixed statistics and  $\odot$ represents element-wise multiplication. The usual loss of the neural network is wrapped by expectation over the noise $\eps$: $\bar L(\zeta) \eqdef \mathbb{E}\left[L(\theta)\right]$. Optimisation now occurs with respect to the set of parameters $\zeta$.

Consider a linear layer of a neural network with $p$ inputs and $q$ outputs, represented by 
%
\beq
\label{eq:lin.layer}
y = wx + b,
\eeq
%
where $x\in \mathbb{R}^{p}$ is the layer input, $w\in\mathbb{R}^{q\times p}$ the weight matrix, and $b\in\mathbb{R}^q$ the bias.
The corresponding noisy linear layer is defined as:
\beqa
\label{eq:param}
y&\eqdef&(\mu^w+\sigma^w\odot\eps^w) x+ \mu^b  +\sigma^b\odot\eps^b ,
\eeqa
 where  $\mu^w+\sigma^w\odot\eps^w$ and $\mu^b  +\sigma^b\odot\eps^b$ replace $w$ and $b$ in Eq.~\eqref{eq:lin.layer}, respectively.  The parameters $\mu^w\in \mathbb{R}^{q\times p}$, $\mu^b\in \mathbb{R}^{q}$, $\sigma^w\in \mathbb{R}^{q\times p}$ and $\sigma^b\in \mathbb{R}^{q}$ are learnable whereas $\eps^w\in \mathbb{R}^{q\times p}$  and $\eps^b\in \mathbb{R}^{q}$ are noise random variables (the specific choices of this distribution are described below). We provide a graphical representation of a noisy linear layer in Fig.~\ref{fig:noisy linear layer} (see Appendix~\ref{sec:noisy linear layer}). 

We now turn to explicit instances of the noise distributions for linear layers in a noisy network. We explore two options: Independent Gaussian noise, which uses an independent Gaussian noise entry per weight and Factorised Gaussian noise, which uses an independent noise per each output and another independent noise per each input. The main reason to use factorised Gaussian noise is to reduce the compute time of random number generation in our algorithms. This computational overhead is especially prohibitive in the case of single-thread agents such as DQN and Duelling. For this reason we use factorised noise for DQN and Duelling and independent noise for the distributed A3C, for which the compute time is not a major concern.

\begin{enumerate}[(a)]
    \item Independent Gaussian noise: the noise applied to each weight and bias is independent, where each entry $\eps^w_{i,j}$ (respectively each entry $\eps^b_j$) of the random matrix $\eps^w$ (respectively of the random vector $\eps^b$) is drawn from a unit Gaussian distribution.
    This means that for each noisy linear layer, there are $pq+q$ noise variables (for $p$ inputs to the layer and $q$ outputs).
    \item Factorised Gaussian noise: by factorising $\eps^w_{i,j}$, we can use $p$ unit Gaussian variables $\eps_i$ for noise of the inputs and
and $q$ unit Gaussian variables $\eps_j$ for noise of the outputs (thus $p+q$ unit Gaussian variables in total). 
Each $\eps^w_{i,j}$ and $\eps^b_j$ can then be written as:
\begin{align}
\eps^w_{i,j}& = f(\eps_i)f(\eps_j), \\
\eps^b_j& = f(\eps_j), \label{eq:bias}
\end{align}
where $f$ is a real-valued  function.
In our experiments we used $f(x) = \sgn(x)\sqrt{|x|}$. Note that for the bias Eq.~\eqref{eq:bias} we could have set $f(x)=x$, but we decided to keep the same output noise for weights and biases.
\end{enumerate}
%
Since the loss of a noisy network, $\bar L(\zeta) = \mathbb{E}\left[L(\theta)\right]$, is an expectation over the noise, the gradients are straightforward to obtain:
\begin{align}
\nabla \bar L(\zeta)= \nabla \mathbb{E}\left[L(\theta)\right]= \mathbb{E}\left[\nabla_{\mu,\Sigma} L(\mu + \Sigma\odot \eps)\right].
\end{align}
We use a Monte Carlo approximation to the above gradients, taking a single sample $\xi$ at each step of optimisation:
\begin{align}
\nabla \bar L(\zeta) &\approx \nabla_{\mu,\Sigma} L(\mu + \Sigma\odot \xi).
\end{align}
%
%
\subsection{Deep Reinforcement Learning with NoisyNets}
\label{sec:Reinforcement Learning using Randomised Networks}
%
We now turn to our application of noisy networks to exploration in deep reinforcement learning.
Noise drives exploration in many methods for reinforcement learning, providing a source of stochasticity external to the agent and the RL task at hand.
Either the scale of this noise is manually tuned across a wide range of tasks (as is the practice in general purpose agents such as DQN or A3C) or it can be manually scaled per task.
Here we propose automatically tuning the level of noise added to an agent for exploration, using the noisy networks training to drive down (or up) the level of noise injected into the parameters of a neural network, as needed.

A noisy network agent samples a new set of parameters after every step of optimisation.
Between optimisation steps, the agent acts according to a fixed set of parameters (weights and biases).
This ensures that the agent always acts according to parameters that are drawn from the current noise distribution.


\paragraph{Deep Q-Networks (DQN) and Dueling.}
We apply the following modifications to both  DQN and Dueling: first, $\eps$-greedy is no longer used, but instead the policy greedily optimises the (randomised) action-value function.
Secondly, the fully connected layers of the value network are parameterised as a noisy network, where the parameters are drawn from the noisy network parameter distribution after every replay step. We used factorised Gaussian noise as explained in (b) from Sec.~\ref{sec:noisynets}.
For replay, the current noisy network parameter sample is held fixed across the batch.
Since DQN and Dueling take one step of optimisation for every action step, the noisy network parameters are re-sampled before every action.
We call the new adaptations  of DQN and Dueling, \algoinit{}-DQN and \algoinit{}-Dueling, respectively.

We now provide the details of the loss function that our variant of DQN is minimising.  When replacing the linear layers by noisy layers in the network (respectively in the target network), the parameterised action-value function $Q(x,a,\eps;\zeta)$ (respectively $Q(x,a,\eps';\zeta^-)$) can be seen as a random variable and the DQN loss becomes the \algoinit{}-DQN loss:
 \begin{equation}
 \bar L(\zeta)=\mathbb{E}\left[\mathbb{E}_{(x,a,r,y)\sim D}[r+ \gamma \max_{b\in A}Q(y,b,\eps';\zeta^-)-Q(x,a,\eps;\zeta)]^2\right],
 \label{eq:Noisy.DQN.loss}
 \end{equation}
\noindent where the outer expectation is with respect to distribution of the noise variables $\eps$ for the noisy value function $Q(x,a,\eps;\zeta)$ and the noise variable $\eps'$ for the noisy target value function $Q(y,b,\eps';\zeta^-)$.
 Computing an unbiased estimate of the loss is straightforward as we only need to compute, for each transition in the replay buffer, one instance of the target network and one instance of the online network. We generate these independent noises to avoid bias due to the correlation between the noise in the target network and the online network. Concerning the action choice, we generate another independent sample  $\eps''$ for the online network and we act greedily with respect to the corresponding  output action-value function. 


Similarly the loss function for \algoinit{}-Dueling is defined as:
 \begin{align}
 \bar L(\zeta)&=\mathbb{E}\left[\mathbb{E}_{(x,a,r,y)\sim D}[r+ \gamma Q(y,b^*(y),\eps';\zeta^-)-Q(x,a,\eps;\zeta)]^2\right]
 \\
 \text{s.t.}\qquad b^*(y)&=\arg\max_{b\in\A}Q(y,b(y),\eps'';\zeta).
 \end{align}
 
 Both algorithms are provided in Appendix~\ref{sec: algo DQN}.


\paragraph{Asynchronous Advantage Actor Critic (A3C).}
A3C is modified in a similar fashion to DQN: firstly, the entropy bonus of the policy loss is removed.
Secondly, the fully connected layers of the policy network are parameterised as a noisy network. We used independent Gaussian noise as explained in (a) from Sec.~\ref{sec:noisynets}.
In A3C, there is no explicit exploratory action selection scheme (such as $\epsilon$-greedy); and the chosen action is always drawn from the current policy. For this reason, an entropy bonus of the policy loss is often added to discourage updates leading to deterministic policies. However, when adding noisy weights to the network, sampling these parameters corresponds to choosing a different current policy which naturally favours exploration.
As a consequence of direct exploration in the policy space, the artificial entropy loss on the policy can thus be omitted. New parameters of the policy network are sampled after each step of optimisation, and since A3C uses $n$ step returns, optimisation occurs every $n$ steps. We call this modification of A3C, \algoinit{}-A3C.


Indeed, when replacing the linear layers by noisy linear layers (the parameters of the noisy network are now noted $\zeta$), we obtain the following estimation of the return via a roll-out of size $k$:
\begin{equation}
\hat{Q}_i=\sum_{j=i}^{k-1}\gamma^{j-i}r_{t+j}+\gamma^{k-i}V(x_{t+k};\zeta,\eps_i).
\end{equation}
As A3C is an on-policy algorithm the gradients are unbiased when noise of the network is consistent for the whole roll-out.
Consistency among action value functions $\hat{Q}_i$ is ensured by letting letting the noise be the \emph{same} throughout each rollout, i.e., $\forall i, \eps_i=\eps$.
Additional details are provided in the Appendix~\ref{sec:A3Cimplementation} and the algorithm is given in Appendix~\ref{sec: algo A3C}.

\subsection{Initialisation of Noisy Networks}

In the case of an unfactorised noisy networks, the parameters $\mu$ and $\sigma$ are initialised as follows.
Each element $\mu_{i,j}$ is sampled from independent uniform distributions $\mathcal{U}[-\sqrt{\frac{3}{p}},+\sqrt{\frac{3}{p}}]$, where $p$ is the number of inputs to the corresponding linear layer, and each element $\sigma_{i,j}$ is simply set to $0.017$ for all parameters. This particular initialisation was chosen because similar values worked well for the supervised learning tasks described in \cite{fortunato2017bayesian}, where the initialisation of the variances of the posteriors and the variances of the prior are related. We have not tuned for this parameter, but we believe different values on the same scale should provide similar results.

For factorised noisy networks, each element $\mu_{i,j}$ was initialised by a sample from an independent uniform distributions $\mathcal{U}[-\frac{1}{\sqrt{p}},+\frac{1}{\sqrt{p}}]$ and each element $\sigma_{i,j}$ was initialised to a constant $\frac{\sigma_0}{\sqrt{p}}$. The hyperparameter $\sigma_0$ is set to $0.5$. 
%
\section{Results}
%
\begin{centering}
\begin{figure}[ht!]
    \subfigure[Improvement in percentage of \algoinit{}-DQN over DQN~\citep{mnih2015human} ]{\includegraphics[width=1.0\textwidth]{plotbar_DQN}}
    \subfigure[Improvement in percentage of \algoinit{}-Dueling over Dueling~\citep{wang2016Dueling} ]{\includegraphics[width=1.0\textwidth]{plotbar_Dueling}}
    \subfigure[Improvement in percentage of \algoinit{}-A3C over A3C~\citep{mnih2016asynchronous} ]{\includegraphics[width=1.0\textwidth]{ICLR_barplot_a3c}}
    \caption{Comparison of \algoinit{} agent versus the baseline according to Eq.~\eqref{eq:relative.human.norm}. The maximum score is truncated at 250\%.}
    \label{fig:normalised.bar} 
\end{figure}
\end{centering} 
%
We evaluated the performance of noisy network agents on 57 Atari games \citep{bellemare2015arcade} and compared to baselines that, without noisy networks, rely upon the original exploration methods ($\eps$-greedy and entropy bonus).

\subsection{Training details and performance}
We used the random start no-ops scheme for training and evaluation as described the original DQN paper \citep{mnih2015human}. 
The mode of evaluation is identical to those of~\cite{mnih2016asynchronous} where randomised restarts of the games are used for evaluation after training has happened. The raw average scores of the agents are evaluated during training, every 1M frames in the environment, by suspending learning and evaluating the latest agent for 500K frames. Episodes are truncated at 108K frames (or 30 minutes of simulated play)~\citep{van2016deep}.

We consider three baseline agents: DQN \citep{mnih2015human}, duel clip variant of Dueling algorithm~\citep{wang2016Dueling} and A3C \citep{mnih2016asynchronous}. The DQN and A3C agents were training for 200M and 320M frames, respectively.
In each case, we used the neural network architecture from the corresponding original papers for both the baseline and \algoinit{} variant. For the \algoinit{} variants we used the same hyper parameters as in the respective original paper for the baseline.

We compared absolute performance of agents using the human normalised score:
\begin{equation}
\label{eq:absolute.human.norm}
100 \times \frac{\text{Score}_{\text{agent}}-\text{Score}_{\text{Random}}}{\text{Score}_{\text{Human}}-\text{Score}_{\text{Random}}},
\end{equation}
where human and random scores are the same as those in \cite{wang2016Dueling}.
Note that the human normalised score is zero for a random agent and $100$ for human level performance. Per-game maximum scores are computed by taking the maximum raw scores of the agent and then averaging over three seeds. However, for computing the human normalised scores in Figure~\ref{fig:learning curves median}, the raw scores are evaluated every 1M frames and averaged over three seeds. The overall agent performance is measured by both mean and median of the human normalised score across all 57 Atari games.

The aggregated results across all 57 Atari games are reported in Table~\ref{tab:totalhuman}, while the individual scores for each game are in Table~\ref{tl:raw.score} from the Appendix~ \ref{sec:learning_curves}.
The median human normalised score is improved in all agents by using \algoinit{}, adding at least $18$ (in the case of A3C) and at most $48$ (in the case of DQN)  percentage points to the median human normalised score.
The mean human normalised score is also significantly improved for all agents.
Interestingly the Dueling case, which relies on multiple modifications of DQN, demonstrates that \algoinit{} is orthogonal to several other improvements made to DQN.
\begin{table}[ht!]
\centering
\begin{tabular}{rccccc}
\toprule
 & \multicolumn{2}{c}{Baseline} & \multicolumn{2}{c}{\algoinit{}}&Improvement \\
 & Mean & Median & Mean & Median& (On median) \\
 \hline
 \\
DQN & 319 & 83 & \textbf{379} & \textbf{123} & 48\%\\ 
Dueling & 524 & 132 & \textbf{633} & \textbf{172} & 30\% \\
A3C & 293 & 80 & \textbf{347} & \textbf{94} &  18\%\\
\bottomrule
\end{tabular}
\vspace{1em}
 \caption{Comparison between the baseline DQN, Dueling and A3C  and their \algoinit{} version in terms of median and mean human-normalised scores defined in Eq.~\eqref{eq:absolute.human.norm}. We report on the last column the percentage  improvement on the baseline in terms of median human-normalised score.}\label{tab:totalhuman} 
\end{table}
%
We also compared relative performance of \algoinit{} agents to the respective baseline agent without noisy networks:
\begin{equation}
\label{eq:relative.human.norm}
100 \times \frac{\text{Score}_{\text{\algoinit{}}}-\text{Score}_{\text{Baseline}}}{\max(\text{Score}_{\text{Human}},\text{Score}_{\text{Baseline}})-\text{Score}_{\text{Random}}}.
\end{equation}
As before, the per-game score is computed by taking the maximum performance for each game and then averaging over three seeds. 
The relative human normalised scores are shown in Figure~\ref{fig:normalised.bar}.
As can be seen, the performance of \algoinit{} agents (DQN, Dueling and A3C) is better for the majority of games relative to the corresponding baseline, and in some cases by a considerable margin. Also as it is evident from the learning curves of Fig.~\ref{fig:learning curves median}  NoisyNet agents produce superior performance compared to their corresponding baselines throughout the learning process. This improvement is especially significant in the case of NoisyNet-DQN and NoisyNet-Dueling. Also in some games, \algoinit{} agents provide an order of magnitude improvement on the performance of the vanilla agent; as can be seen in Table \ref{tl:raw.score} in the Appendix~\ref{sec:learning_curves} with detailed breakdown of individual game scores and the learning curves plots from Figs \ref{fig:all_games_dqn}, \ref{fig:all_games_Dueling} and ~\ref{fig:all_games_a3c}, for DQN, Dueling and A3C,  respectively.
We also ran some experiments evaluating the performance of NoisyNet-A3C with factorised noise. We report the corresponding learning curves and the scores  in Fig.~\ref{fig:learning curves median facotrised} and Table \ref{table:factorised}, respectively (see Appendix \ref{sec:appx.factor.A3C}). This result shows that using factorised noise does not lead to any significant decrease in the performance of A3C. On the contrary it seems that it has positive effects in terms of improving the median score as well as speeding up the learning process. 
\begin{centering}
\begin{figure}[htp!]
    \includegraphics[width=0.33\textwidth]{DQN_median_scores}
    \includegraphics[width=0.33\textwidth]{Dueling_median_scores}
    \includegraphics[width=0.33\textwidth]{A3C_median_scores}
    \caption{Comparison of the learning curves of \algoinit{} agent versus the baseline according to the median human normalised score.}
    \label{fig:learning curves median} 
\end{figure}
\end{centering} 
%
\subsection{Analysis of Learning in Noisy Layers}
In this subsection, we try to provide some insight on how noisy networks affect the learning process and the exploratory behaviour of the agent. In particular, we  focus on analysing the evolution of the noise weights  $\sigma^w$ and $\sigma^b$ throughout the learning process. We first note that, as $L(\zeta)$ is a positive and continuous function of $\zeta$, there always exists a \emph{deterministic} optimiser for the loss $L(\zeta)$ (defined in Eq.~\eqref{eq:Noisy.DQN.loss}). Therefore, one may expect that, to obtain the deterministic optimal solution, the neural network may learn to discard the noise entries by eventually pushing $\sigma^w$s and $\sigma^b$ towards $0$. 

To test this hypothesis we track the changes in $\sigma^w$s throughout the learning process. Let  $\sigma^w_i$ denote the $i^{\text{th}}$ weight of a noisy layer. We then define $\bar \Sigma$, the mean-absolute of the $\sigma^w_i$s of a noisy layer, as
%
\begin{equation}
\bar \Sigma = \frac{1}{\mathrm{N_{weights}}}\sum_i|\sigma^w_i|.
\end{equation}
%
 Intuitively speaking $\bar \Sigma$ provides some measure of the stochasticity of the Noisy layers. We report the learning curves of the average of $\bar \Sigma$ across $3$ seeds in Fig.~\ref{fig:sigma_curves} for a selection of Atari games in NoisyNet-DQN agent. We observe that $\bar \Sigma$ of the last layer of the network decreases as the learning proceeds in all cases, whereas in the case of the penultimate layer this only happens for 2 games out of 5 (Pong and Beam rider) and in the remaining 3 games $\bar \Sigma$ in fact increases. This shows that in the case of NoisyNet-DQN the agent does not necessarily evolve towards a deterministic solution as one might have expected. Another interesting observation is that the way $\bar \Sigma$ evolves significantly differs from one game to another and in some cases from one seed to another seed, as it is evident from the error bars. This suggests that NoisyNet produces a problem-specific exploration strategy as opposed to fixed exploration strategy used in standard DQN.      
 %
\begin{centering}
\begin{figure}[ht!]
    \includegraphics[width=0.5\textwidth]{penultimate_layer_error_bar}
    \includegraphics[width=0.5\textwidth]{last_layer_error_bars}
    \caption{Comparison of the learning curves of the average noise parameter $\bar\Sigma$ across five Atari games in NoisyNet-DQN. The results are averaged across 3 seeds and error bars (+/- standard deviation) are plotted.}
    \label{fig:sigma_curves} 
\end{figure}
\end{centering} 
%
\section{Conclusion}
\label{sec:conclusion}
We have presented a general method for exploration in deep reinforcement learning that shows significant performance improvements across many Atari games in three different agent architectures. In particular, we observe that in games such as Beam rider, Asteroids and Freeway that the standard DQN, Dueling and A3C perform poorly compared with the human player, \algoinit{}-DQN, \algoinit{}-Dueling  and \algoinit{}-A3C achieve super human performance, respectively. Although the improvements in performance might also come from the optimisation aspect since the cost functions are modified, the uncertainty in the parameters of the networks introduced by NoisyNet is the \textit{only} exploration mechanism of the method. Having weights with greater uncertainty introduces more variability into the decisions made by the policy, which has potential for exploratory actions, but further analysis needs to be done in order to disentangle the exploration and optimisation effects. 
 


Another advantage of NoisyNet is that the amount of noise injected in the network is tuned automatically by the RL algorithm. This alleviates the need for any hyper parameter tuning (required with standard entropy bonus and $\epsilon$-greedy types of exploration). 
This is also in contrast to many other methods that add intrinsic motivation signals that may destabilise learning or change the optimal policy. 
Another interesting feature of the \algoinit{} approach is that the degree of exploration is contextual and varies from state to state based upon per-weight variances.
While more gradients are needed, the gradients on the mean and variance parameters are related to one another by a computationally efficient affine function, thus the computational overhead is marginal.
Automatic differentiation makes implementation of our method a straightforward adaptation of many existing methods.
A similar randomisation technique can also be applied to LSTM units~\citep{fortunato2017bayesian} and is easily extended to reinforcement learning, we leave this as future work.

Note \algoinit{} exploration strategy is not restricted to the baselines considered in this paper. In fact, this idea can be applied to any deep RL algorithms that can be trained with gradient descent, including DDPG~\citep{lillicrap2015continuous}, TRPO~\citep{schulman2015trust} or distributional RL (C51) \citep{bellemare2017distributional}. As such we believe this work is a step towards the goal of developing a universal exploration strategy. 

\paragraph{Acknowledgements}
We would like to thank Koray Kavukcuoglu, Oriol Vinyals,  Daan Wierstra, Georg Ostrovski, Joseph Modayil, Simon Osindero, Chris Apps, Stephen Gaffney and many others at DeepMind for insightful discussions, comments and feedback on this work.

\bibliography{iclr2018_conference}
\bibliographystyle{iclr2018_conference}
\newpage
\appendix

\section{\algoinit{}-A3C implementation details}

 \label{sec:A3Cimplementation}
 In contrast with value-based algorithms, policy-based methods such as A3C~\citep{mnih2016asynchronous} parameterise the policy $\pi(a|x;\theta_\pi)$ directly and update the parameters $\theta_\pi$ by performing a gradient ascent on the mean value-function $\mathbb{E}_{x\sim D}[V^{\pi(\cdot|\cdot;\theta_\pi)}(x)]$ (also called the expected return)~\citep{sutton1999policy}. A3C uses a deep neural network  with weights $\theta=\theta_\pi\cup\theta_V$ to parameterise the policy $\pi$ and the value $V$. The network has one softmax output for the policy-head $\pi(\cdot|\cdot;\theta_\pi)$ and one linear output for the value-head $V(\cdot;\theta_V)$, with all non-output layers shared. The parameters $\theta_\pi$ (resp. $\theta_V$) are relative to the shared layers and the policy head (resp. the value head). A3C is an asynchronous and online algorithm that uses roll-outs of size $k+1$ of the current policy to perform a policy improvement step. 

For simplicity, here we present the A3C version with only one thread. For a  multi-thread implementation, refer to the pseudo-code \ref{sec: algo A3C} or to the original A3C paper~\citep{mnih2016asynchronous}. In order to train the policy-head, an approximation of the policy-gradient is computed for each state of the roll-out $(x_{t+i},a_{t+i}\sim\pi(\cdot|x_{t+i};\theta_\pi),r_{t+i})_{i=0}^{k}$:
 \begin{equation}
 \nabla_{\theta_\pi}\log(\pi(a_{t+i}|x_{t+i};\theta_\pi))[\hat{Q}_i-V(x_{t+i};\theta_V)],  
 \end{equation}
 where $\hat{Q}_i$ is an estimation of the return $\hat{Q}_i=\sum_{j=i}^{k-1}\gamma^{j-i}r_{t+j}+\gamma^{k-i}V(x_{t+k};\theta_V).$ The gradients are then added to obtain the cumulative gradient of the roll-out:
 \begin{equation}
 \sum_{i=0}^k\nabla_{\theta_\pi}\log(\pi(a_{t+i}|x_{t+i};\theta_\pi))[\hat{Q}_i-V(x_{t+i};\theta_V)].
 \end{equation}
 A3C trains the value-head by minimising the error between the estimated return and the value $\sum_{i=0}^k(\hat{Q}_i-V(x_{t+i};\theta_V))^2$. Therefore, the network parameters $(\theta_\pi,\theta_V)$ are updated after each roll-out as follows:
 \begin{align}
 &\theta_\pi \leftarrow \theta_\pi + \alpha_\pi\sum_{i=0}^k\nabla_{\theta_\pi}\log(\pi(a_{t+i}|x_{t+i};\theta_\pi))[\hat{Q}_i-V(x_{t+i};\theta_V)],
 \\
 &\theta_V \leftarrow \theta_V -\alpha_V\sum_{i=0}^k\nabla_{\theta_V}[\hat{Q}_i-V(x_{t+i};\theta_V)]^2,
 \end{align}
 where $(\alpha_\pi,\alpha_V)$ are hyper-parameters. As mentioned previously, in the original A3C algorithm, it is recommended to add an entropy term $\beta\sum_{i=0}^k\nabla_{\theta_\pi} H(\pi(\cdot|x_{t+i};\theta_\pi))$ to the policy update, where $H(\pi(\cdot|x_{t+i};\theta_\pi))=-\beta\sum_{a\in A}\pi(a|x_{t+i};\theta_\pi)\log(\pi(a|x_{t+i};\theta_\pi))$. Indeed, this term encourages exploration as it favours policies which are uniform over actions. 
 When replacing the linear layers in the value and policy heads by noisy layers (the parameters of the noisy network are now $\zeta_\pi$ and $\zeta_V$), we obtain the following estimation of the return via a roll-out of size $k$:
 \begin{equation}
 \hat{Q}_i=\sum_{j=i}^{k-1}\gamma^{j-i}r_{t+j}+\gamma^{k-i}V(x_{t+k};\zeta_V,\eps_i).
 \end{equation}
 We would like $\hat{Q}_i$ to be a consistent estimate of the return of the current policy. To do so, we should force $\forall i, \eps_i=\eps$. As A3C is an on-policy algorithm, this involves fixing the noise of the network for the whole roll-out so that the policy produced by the network is also fixed. Hence, each update of the parameters $(\zeta_\pi,\zeta_V)$ is done after each roll-out with the noise of the whole network held fixed for the duration of the roll-out:
 \begin{align}
 &\zeta_\pi \leftarrow \zeta_\pi + \alpha_\pi\sum_{i=0}^k\nabla_{\zeta_\pi}\log(\pi(a_{t+i}|x_{t+i};\zeta_\pi,\eps))[\hat{Q}_i-V(x_{t+i};\zeta_V,\eps)],
 \\
 &\zeta_V \leftarrow \zeta_V -\alpha_V\sum_{i=0}^k\nabla_{\zeta_V}[\hat{Q}_i-V(x_{t+i};\zeta_V,\eps)]^2.
 \end{align}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage

\section{Noisy linear layer}
 \label{sec:noisy linear layer}
 
 In this Appendix we provide a graphical representation of noisy layer.
 
\begin{figure}[!htp]
\begin{centering}
    \includegraphics[width=0.6\textwidth]{noisy_linear_layer.png}
    \caption{Graphical representation of a noisy linear layer. The parameters $\mu^w$, $\mu^b$, $\sigma^w$ and $\sigma^b$ are the learnables of the network whereas $\eps^w$  and $\eps^b$ are noise  variables which can be chosen in factorised or non-factorised fashion. The noisy layer functions similarly to the standard fully connected linear layer. The main difference is that in the noisy layer both the weights vector and the bias is perturbed by some parametric zero-mean noise, that is, the noisy weights and the noisy bias can be expressed as $w=\mu^w+\sigma^w\odot\eps^w$ and $b=\mu^b+\sigma^b\odot\eps^b$, respectively. The output of the noisy layer is then simply obtained as $y=wx+b$.}
    \label{fig:noisy linear layer} 
    \end{centering}
\end{figure}

\newpage


\section{Algorithms}
\subsection{\algoinit{}-DQN and \algoinit{}-Dueling}
\label{sec: algo DQN}
\begin{algorithm}[!ht]
\DontPrintSemicolon
\SetAlgoLined
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{$Env$ Environment; $\eps$ set of random variables of the network}
\Input{DUELING Boolean; "true" for \algoinit{}-Dueling and "false" for \algoinit{}-DQN}
\Input{$B$ empty replay buffer; $\zeta$ initial network parameters; $\zeta^-$ initial target network parameters}
\Input{$N_B$ replay buffer size; $N_T$ training batch size; $N^-$ target network replacement frequency}
\Output{$Q(\cdot,\eps;\zeta)$ action-value function}
\BlankLine
\For{ episode $e\in \{1,\dots,M\}$}{    
    \BlankLine
    Initialise state sequence $x_0\sim Env$\;
    \For{$t\in\{1,\dots\}$}{
    \tcc{$l[-1]$ is the last element of the list $l$}
        Set $x\leftarrow x_0$\;    
        Sample a noisy network $\xi\sim\eps$\;
        Select an action $a\leftarrow\argmax_{b\in A}Q(x,b,\xi;\zeta)$\;
        Sample next state $y\sim P(\cdot|x,a)$, receive reward $r\leftarrow R(x,a)$\ and set $x_0 \leftarrow y$\;
        Add transition $(x,a,r,y)$ to the replay buffer $B[-1]\leftarrow (x,a,r,y)$\;
        \If{$|B|> N_B$}{
        Delete oldest transition from $B$\;
        }
        \tcc{$D$ is a distribution over the replay, it can be uniform or implementing prioritised replay}
        Sample a minibatch of $N_T$ transitions $\left((x_j,a_j,r_j,y_j)\sim D\right)_{j=1}^{N_T}$\;
        \tcc{Construction of the target values.}
        Sample the noisy variable for the online network  $\xi\sim\eps$\;
        Sample the noisy variables for the target network $\xi'\sim\eps$\;
        \uIf{DUELING}{
        Sample the noisy variables for the action selection network $\xi''\sim\eps$\;
        }
        \For{$j\in\{1,\dots,N_T\}$}{

            \uIf{$y_j$ is a terminal state}{
                $\wh Q\leftarrow r_j$\;
            }
            \uIf{DUELING}{
                $b^*(y_j)= \arg\max_{b\in\A} Q(y_j,b,\xi'';\zeta)$\;
                $\widehat Q\leftarrow r_j+\gamma Q(y_j,b^*(y_j),\xi';\zeta^-)$\;
            }  
            \uElse{
                $\wh Q\leftarrow r_j+\gamma\max_{b\in A}Q(y_j,b,\xi';\zeta^-)$\;
            }  
            
            Do a gradient step with loss $(\wh Q-Q(x_j,a_j,\xi;\zeta))^2$\;
        }
        
        \If{$t \equiv 0 \pmod{N^-}$}{
        Update the target network: $\zeta^-\leftarrow \zeta$\;
        }
        
            
    }    
}
\caption{\algoinit{}-DQN / \algoinit{}-Dueling}
\end{algorithm}



\newpage
\subsection{\algoinit{}-A3C}
\label{sec: algo A3C}
\begin{algorithm}[!ht]
\DontPrintSemicolon
\SetAlgoLined
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Environment $Env$, Global shared parameters $(\zeta_\pi,\zeta_V)$, global shared counter $T$ and maximal time $T_{max}$.}
\Input{Thread-specific parameters $(\zeta'_\pi,\zeta'_V)$, Set of random variables $\eps$, thread-specific counter $t$ and roll-out size $t_{max}$.}
\Output{$\pi(\cdot;\zeta_\pi,\eps)$ the policy and $V(\cdot;\zeta_V,\eps)$ the value.}
\BlankLine
Initial thread counter $t\leftarrow 1$\;
\Repeat{$T>T_{max}$}{
    Reset cumulative gradients: $d\zeta_\pi\leftarrow 0$ and $d\zeta_V\leftarrow 0$.\;
    Synchronise thread-specific parameters: $\zeta'_\pi\leftarrow\zeta_\pi$ and $\zeta'_V\leftarrow\zeta_V$. \;
    $counter\leftarrow 0$.\;
    Get state $x_t$ from $Env$\;
    Choice of the noise: $\xi\sim\eps$\;
    \tcc{$r$ is a list of rewards}
    $r\leftarrow[\text{ }]$\;
    \tcc{$a$ is a list of actions}
    $a\leftarrow[\text{ }]$\;
    \tcc{$x$ is a list of states}
    $x\leftarrow[\text{ }]$ and $x[0]\leftarrow x_t$\;
    \Repeat{$x_t$ terminal or $counter==t_{max}+1$}{
        Policy choice: $a_t\sim\pi(\cdot|x_t;\zeta'_\pi;\xi)$\;
        $a[-1]\leftarrow a_t$\; 
        Receive reward $r_t$ and new state $x_{t+1}$\;
        $r[-1]\leftarrow r_t$ and $x[-1]\leftarrow x_{t+1}$\;
        $t\leftarrow t+1$ and $T\leftarrow T+1$\;
        $counter=counter + 1$
        }
    \uIf{$x_t$ is a terminal state}{
        $Q=0$\;
    }
    \uElse{
      $Q=V(x_t;\zeta'_V,\xi)$\;
    }   
    \For{$i\in\{counter-1,\dots,0\}$}{
        Update $Q$: $Q\leftarrow r[i]+\gamma Q$.\;
        Accumulate policy-gradient: $d\zeta_\pi\leftarrow d\zeta_\pi+\nabla_{\zeta'_\pi}\log(\pi(a[i]|x[i];\zeta'_\pi,\xi))[Q-V(x[i];\zeta'_V,\xi)]$.\;
        Accumulate value-gradient: $d\zeta_V\leftarrow d\zeta_V+\nabla_{\zeta'_V}[Q-V(x[i];\zeta'_V,\xi)]^2$.\;
    }
    Perform asynchronous update of $\zeta_{\pi}$: $\zeta_\pi\leftarrow\zeta_\pi+\alpha_\pi d\zeta_\pi $\;
    Perform asynchronous update of $\zeta_V$: $\zeta_V\leftarrow\zeta_V-\alpha_V d\zeta_V $\;
      
}
\caption{\algoinit{}-A3C for each actor-learner thread}
\end{algorithm}


\newpage
\section{Comparison between NoisyNet-A3C (factorised and non-factorised noise) and A3C}

\label{sec:appx.factor.A3C}





\begin{figure}[!htp]
\begin{centering}
    \includegraphics[width=0.8\textwidth]{A3C_factorised_median_scores_all.png}
    \caption{Comparison of the learning curves of factorised and non-factorised NoisyNet-A3C versus the baseline according to the median human normalised score.}
    \label{fig:learning curves median facotrised} 
    \end{centering}
\end{figure}


\begin{table}[ht!]
\centering
\begin{tabular}{rccccc}
\toprule
 & \multicolumn{2}{c}{Baseline} & \multicolumn{2}{c}{\algoinit{}}&Improvement \\
 & Mean & Median & Mean & Median& (On median) \\
 \hline
 \\
DQN & 319 & 83 & \textbf{379} & \textbf{123} & 48\%\\ 
Dueling & 524 & 132 & \textbf{633} & \textbf{172} & 30\% \\
A3C & 293 & 80 & \textbf{347} & \textbf{94} &  18\%\\
A3C (factorised) & \textbf{293} & 80 & 276 & \textbf{99} & 24  \%\\
\bottomrule
\end{tabular}
\caption{Comparison between the baseline DQN, Dueling and A3C   and their \algoinit{} version in terms of median and mean human-normalised scores defined in Eq.~\eqref{eq:absolute.human.norm}. In the case of A3C we inculde both factorised and non-factorised variant of the algorithm. We report on the last column the percentage  improvement on the baseline in terms of median human-normalised score.}
\label{table:factorised}
\end{table}



\newpage
\section{Learning curves and raw scores}
\label{sec:learning_curves}

Here we directly compare the performance of DQN, Dueling DQN and A3C and their NoisyNet counterpart by presenting the maximal score in each of the 57 Atari games (Table \ref{tl:raw.score}), averaged over three seeds. In Figures~\ref{fig:all_games_dqn}-\ref{fig:all_games_a3c} we show the respective learning curves. 

\begin{table}[!ht]
\centering
\tiny
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
 Games & Human & Random & DQN & NoisyNet-DQN & A3C & NoisyNet-A3C & Dueling & NoisyNet-Dueling \\
\hline
 alien & \bf{7128} & 228 & 2404 $\pm$ 242 & 2403 $\pm$ 78 & 2027 $\pm$ 92 & 1899 $\pm$ 111 & 6163 $\pm$ 1077 & 5778 $\pm$ 2189 \\
 amidar & 1720 & 6 & 924 $\pm$ 159 & 1610 $\pm$ 228 & 904 $\pm$ 125 & 491 $\pm$ 485 & 2296 $\pm$ 154 & \bf{3537 $\pm$ 521} \\
 assault & 742 & 222 & 3595 $\pm$ 169 & 5510 $\pm$ 483 & 2879 $\pm$ 293 & 3060 $\pm$ 101 & 8010 $\pm$ 381 & \bf{11231 $\pm$ 503} \\
 asterix & 8503 & 210 & 6253 $\pm$ 154 & 14328 $\pm$ 2859 & 6822 $\pm$ 181 & \bf{32478 $\pm$ 2567} & 11170 $\pm$ 5355 & 28350 $\pm$ 607 \\
 asteroids & 47389 & 719 & 1824 $\pm$ 83 & 3455 $\pm$ 1054 & 2544 $\pm$ 523 & 4541 $\pm$ 311 & 2220 $\pm$ 91 & \bf{86700 $\pm$ 80459} \\
 atlantis & 29028 & 12580 & 876000 $\pm$ 15013 & 923733 $\pm$ 25798 & 422700 $\pm$ 4759 & 465700 $\pm$ 4224 & 902742 $\pm$ 17087 & \bf{972175 $\pm$ 31961} \\
 bank heist & 753 & 14 & 455 $\pm$ 25 & 1068 $\pm$ 277 & 1296 $\pm$ 20 & 1033 $\pm$ 463 & \bf{1428 $\pm$ 37} & 1318 $\pm$ 37 \\
 battle zone & 37188 & 2360 & 28981 $\pm$ 1497 & 36786 $\pm$ 2892 & 16411 $\pm$ 1283 & 17871 $\pm$ 5007 & 40481 $\pm$ 2161 & \bf{52262 $\pm$ 1480} \\
 beam rider & 16926 & 364 & 10564 $\pm$ 613 & \bf{20793 $\pm$ 284} & 9214 $\pm$ 608 & 11237 $\pm$ 1582 & 16298 $\pm$ 1101 & 18501 $\pm$ 662 \\
 berzerk & \bf{2630} & 124 & 634 $\pm$ 16 & 905 $\pm$ 21 & 1022 $\pm$ 151 & 1235 $\pm$ 259 & 1122 $\pm$ 35 & 1896 $\pm$ 604 \\
 bowling & \bf{161} & 23 & 62 $\pm$ 4 & 71 $\pm$ 26 & 37 $\pm$ 2 & 42 $\pm$ 11 & 72 $\pm$ 6 & 68 $\pm$ 6 \\
 boxing & 12 & 0 & 87 $\pm$ 1 & 89 $\pm$ 4 & 91 $\pm$ 1 & \bf{100 $\pm$ 0} & 99 $\pm$ 0 & 100 $\pm$ 0 \\
 breakout & 30 & 2 & 396 $\pm$ 13 & \bf{516 $\pm$ 26} & 496 $\pm$ 56 & 374 $\pm$ 27 & 200 $\pm$ 21 & 263 $\pm$ 20 \\
 centipede & \bf{12017} & 2091 & 6440 $\pm$ 1194 & 4269 $\pm$ 261 & 5350 $\pm$ 432 & 8282 $\pm$ 685 & 4166 $\pm$ 23 & 7596 $\pm$ 1134 \\
 chopper command & 7388 & 811 & 7271 $\pm$ 473 & 8893 $\pm$ 871 & 5285 $\pm$ 159 & 7561 $\pm$ 1190 & 7388 $\pm$ 1024 & \bf{11477 $\pm$ 1299} \\
 crazy climber & 35829 & 10780 & 116480 $\pm$ 896 & 118305 $\pm$ 7796 & 134783 $\pm$ 5495 & 139950 $\pm$ 18190 & 163335 $\pm$ 2460 & \bf{171171 $\pm$ 2095} \\
 defender & 18689 & 2874 & 18303 $\pm$ 2611 & 20525 $\pm$ 3114 & 52917 $\pm$ 3355 & \bf{55492 $\pm$ 3844} & 37275 $\pm$ 1572 & 42253 $\pm$ 2142 \\
 demon attack & 1971 & 152 & 12696 $\pm$ 214 & 36150 $\pm$ 4646 & 37085 $\pm$ 803 & 37880 $\pm$ 2093 & 61033 $\pm$ 9707 & \bf{69311 $\pm$ 26289} \\
 double dunk & -16 & -19 & -6 $\pm$ 1 & 1 $\pm$ 0 & 3 $\pm$ 1 & 3 $\pm$ 1 & \bf{17 $\pm$ 7} & 1 $\pm$ 0 \\
 enduro & 860 & 0 & 835 $\pm$ 56 & 1240 $\pm$ 83 & 0 $\pm$ 0 & 300 $\pm$ 424 & \bf{2064 $\pm$ 81} & 2013 $\pm$ 219 \\
 fishing derby & -39 & -92 & 4 $\pm$ 4 & 11 $\pm$ 2 & -7 $\pm$ 30 & -38 $\pm$ 39 & 35 $\pm$ 5 & \bf{57 $\pm$ 2} \\
 freeway & 30 & 0 & 31 $\pm$ 0 & 32 $\pm$ 0 & 0 $\pm$ 0 & 18 $\pm$ 13 & \bf{34 $\pm$ 0} & 34 $\pm$ 0 \\
 frostbite & \bf{4335} & 65 & 1000 $\pm$ 258 & 753 $\pm$ 101 & 288 $\pm$ 20 & 261 $\pm$ 0 & 2807 $\pm$ 1457 & 2923 $\pm$ 1519 \\
 gopher & 2412 & 258 & 11825 $\pm$ 1444 & 14574 $\pm$ 1837 & 7992 $\pm$ 672 & 12439 $\pm$ 16229 & 27313 $\pm$ 2629 & \bf{38909 $\pm$ 2229} \\
 gravitar & \bf{3351} & 173 & 366 $\pm$ 26 & 447 $\pm$ 94 & 379 $\pm$ 31 & 314 $\pm$ 25 & 1682 $\pm$ 170 & 2209 $\pm$ 99 \\
 hero & 30826 & 1027 & 15176 $\pm$ 3870 & 6246 $\pm$ 2092 & 30791 $\pm$ 246 & 8471 $\pm$ 4332 & \bf{35895 $\pm$ 1035} & 31533 $\pm$ 4970 \\
 ice hockey & 1 & -11 & -2 $\pm$ 0 & -3 $\pm$ 0 & -2 $\pm$ 0 & -3 $\pm$ 1 & -0 $\pm$ 0 & \bf{3 $\pm$ 1} \\
 jamesbond & 303 & 29 & 909 $\pm$ 223 & 1235 $\pm$ 421 & 509 $\pm$ 34 & 188 $\pm$ 103 & 1667 $\pm$ 134 & \bf{4682 $\pm$ 2281} \\
 kangaroo & 3035 & 52 & 8166 $\pm$ 1512 & 10944 $\pm$ 4149 & 1166 $\pm$ 76 & 1604 $\pm$ 278 & 14847 $\pm$ 29 & \bf{15227 $\pm$ 243} \\
 krull & 2666 & 1598 & 8343 $\pm$ 79 & 8805 $\pm$ 313 & 9422 $\pm$ 980 & \bf{22849 $\pm$ 12175} & 10733 $\pm$ 65 & 10754 $\pm$ 181 \\
 kung fu master & 22736 & 258 & 30444 $\pm$ 1673 & 36310 $\pm$ 5093 & 37422 $\pm$ 2202 & \bf{55790 $\pm$ 23886} & 30316 $\pm$ 2397 & 41672 $\pm$ 1668 \\
 montezuma revenge & \bf{4753} & 0 & 2 $\pm$ 3 & 3 $\pm$ 4 & 14 $\pm$ 12 & 4 $\pm$ 3 & 0 $\pm$ 0 & 57 $\pm$ 15 \\
 ms pacman & \bf{6952} & 307 & 2674 $\pm$ 43 & 2722 $\pm$ 148 & 2436 $\pm$ 249 & 3401 $\pm$ 761 & 3650 $\pm$ 445 & 5546 $\pm$ 367 \\
 name this game & 8049 & 2292 & 8179 $\pm$ 551 & 8181 $\pm$ 742 & 7168 $\pm$ 224 & 8798 $\pm$ 1847 & 9919 $\pm$ 38 & \bf{12211 $\pm$ 251} \\
 phoenix & 7243 & 761 & 9704 $\pm$ 2907 & 16028 $\pm$ 3317 & 9476 $\pm$ 569 & \bf{50338 $\pm$ 30396} & 8215 $\pm$ 403 & 10379 $\pm$ 547 \\
 pitfall & \bf{6464} & -229 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 \\
 pong & 15 & -21 & 20 $\pm$ 0 & \bf{21 $\pm$ 0} & 7 $\pm$ 19 & 12 $\pm$ 11 & 21 $\pm$ 0 & 21 $\pm$ 0 \\
 private eye & \bf{69571} & 25 & 2361 $\pm$ 781 & 3712 $\pm$ 161 & 3781 $\pm$ 2994 & 100 $\pm$ 0 & 227 $\pm$ 138 & 279 $\pm$ 109 \\
 qbert & 13455 & 164 & 11241 $\pm$ 1579 & 15545 $\pm$ 462 & 18586 $\pm$ 574 & 17896 $\pm$ 1522 & 19819 $\pm$ 2640 & \bf{27121 $\pm$ 422} \\
 riverraid & 17118 & 1338 & 7241 $\pm$ 140 & 9425 $\pm$ 705 & 8135 $\pm$ 483 & 7878 $\pm$ 162 & 18405 $\pm$ 93 & \bf{23134 $\pm$ 1434} \\
 road runner & 7845 & 12 & 37910 $\pm$ 1778 & 45993 $\pm$ 2709 & 45315 $\pm$ 1837 & 30454 $\pm$ 13309 & 64051 $\pm$ 1106 & \bf{234352 $\pm$ 132671} \\
 robotank & 12 & 2 & 55 $\pm$ 1 & 51 $\pm$ 5 & 6 $\pm$ 0 & 36 $\pm$ 3 & 63 $\pm$ 1 & \bf{64 $\pm$ 1} \\
 seaquest & \bf{42055} & 68 & 4163 $\pm$ 425 & 2282 $\pm$ 361 & 1744 $\pm$ 0 & 943 $\pm$ 41 & 19595 $\pm$ 1493 & 16754 $\pm$ 6619 \\
 skiing & \bf{-4337} & -17098 & -12630 $\pm$ 202 & -14763 $\pm$ 706 & -12972 $\pm$ 2846 & -15970 $\pm$ 9887 & -7989 $\pm$ 1349 & -7550 $\pm$ 451 \\
 solaris & 12327 & 1263 & 4055 $\pm$ 842 & 6088 $\pm$ 1791 & \bf{12380 $\pm$ 519} & 10427 $\pm$ 3878 & 3423 $\pm$ 152 & 6522 $\pm$ 750 \\
 space invaders & 1669 & 148 & 1283 $\pm$ 39 & 2186 $\pm$ 92 & 1034 $\pm$ 49 & 1126 $\pm$ 154 & 1158 $\pm$ 74 & \bf{5909 $\pm$ 1318} \\
 star gunner & 10250 & 664 & 40934 $\pm$ 3598 & 47133 $\pm$ 7016 & 49156 $\pm$ 3882 & 45008 $\pm$ 11570 & 70264 $\pm$ 2147 & \bf{75867 $\pm$ 8623} \\
 surround & 6 & -10 & -6 $\pm$ 0 & -1 $\pm$ 2 & -8 $\pm$ 1 & 1 $\pm$ 1 & 1 $\pm$ 3 & \bf{10 $\pm$ 0} \\
 tennis & -8 & -24 & \bf{8 $\pm$ 7} & 0 $\pm$ 0 & -6 $\pm$ 9 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 \\
 time pilot & 5229 & 3568 & 6167 $\pm$ 73 & 7035 $\pm$ 908 & 10294 $\pm$ 1449 & 11124 $\pm$ 1753 & 14094 $\pm$ 652 & \bf{17301 $\pm$ 1200} \\
 tutankham & 168 & 11 & 218 $\pm$ 1 & 232 $\pm$ 34 & 213 $\pm$ 14 & 164 $\pm$ 49 & \bf{280 $\pm$ 8} & 269 $\pm$ 19 \\
 up n down & 11693 & 533 & 11652 $\pm$ 737 & 14255 $\pm$ 1658 & 89067 $\pm$ 12635 & \bf{103557 $\pm$ 51492} & 93931 $\pm$ 56045 & 61326 $\pm$ 6052 \\
 venture & 1188 & 0 & 319 $\pm$ 158 & 97 $\pm$ 76 & 0 $\pm$ 0 & 0 $\pm$ 0 & \bf{1433 $\pm$ 10} & 815 $\pm$ 114 \\
 video pinball & 17668 & 16257 & 429936 $\pm$ 71110 & 322507 $\pm$ 135629 & 229402 $\pm$ 153801 & 294724 $\pm$ 140514 & \bf{876503 $\pm$ 61496} & 870954 $\pm$ 135363 \\
 wizard of wor & 4756 & 564 & 3601 $\pm$ 873 & 9198 $\pm$ 4364 & 8953 $\pm$ 1377 & \bf{12723 $\pm$ 3420} & 6534 $\pm$ 882 & 9149 $\pm$ 641 \\
 yars revenge & 54577 & 3093 & 20648 $\pm$ 1543 & 23915 $\pm$ 13939 & 21596 $\pm$ 1917 & 61755 $\pm$ 4798 & 43120 $\pm$ 21466 & \bf{86101 $\pm$ 4136} \\
 zaxxon & 9173 & 32 & 4806 $\pm$ 285 & 6920 $\pm$ 4567 & \bf{16544 $\pm$ 1513} & 1324 $\pm$ 1715 & 13959 $\pm$ 613 & 14874 $\pm$ 214 \\
\hline
\end{tabular}
\caption{Raw scores across all games with random starts.}
\label{tl:raw.score}
\end{table}

\newpage


\begin{figure}[!ht]
\begin{centering}
    \includegraphics[width=\textwidth]{DQN_allgames.jpeg}
    \caption{Training curves for all Atari games comparing DQN and \algoinit{}-DQN.}
    \label{fig:all_games_dqn}    
    \end{centering}
\end{figure}

\newpage

\begin{figure}[!ht]
\begin{centering}
    \includegraphics[width=\textwidth,height=0.96\textheight]{Dueling_allgames.jpeg}
    \caption{Training curves for all Atari games comparing Duelling and \algoinit{}-Dueling.}
    \label{fig:all_games_Dueling}    
    \end{centering}
\end{figure}

\newpage

\begin{figure}[!htp]
\begin{centering}
    \includegraphics[width=\textwidth,height=0.96\textheight]{ICLR_all_a3c.jpeg}
    \caption{Training curves for all Atari games comparing A3C and \algoinit{}-A3C.}
    \label{fig:all_games_a3c}    
    \end{centering}
\end{figure}


 
%
\end{document}


symbolsdef.tex
% Misc symbols
%\newcommand{\HCT}{\textit{HCT}\xspace}
%\newcommand{\HCTiid}{\textit{HCT}-iid\xspace}
%\newcommand{\HCTgamma}{\textit{HCT}-$\Gamma$\xspace}
%\newcommand{\comp}{\mathsf{c}}

\newcommand{\Exp}{\mathds{E}}
\newcommand{\Expk}{\mathds{E}_{k}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\Ind}{\mathds{1}}
\newcommand{\Rmax}{R_{\rm max}}
\newcommand{\riskyopt}{\succcurlyeq_{\rm ro}}
\newcommand{\cid}{\succcurlyeq_{\rm CID}}
\newcommand{\so}{\succcurlyeq_{\rm so}}
\newcommand{\single}{\succcurlyeq_{\rm sc}}
\newcommand{\ssd}{\succcurlyeq_{\rm ssd}}
\newcommand{\pp}{\mathrel{+}\mathrel{+}}
\newcommand{\Xc}{\mathcal{X}}
\newcommand{\Yc}{\mathcal{Y}}
\newcommand{\Pc}{\mathcal{P}}
\newcommand{\Qc}{\mathcal{Q}}
\newcommand{\Ec}{\mathcal{E}}
\newcommand{\Fc}{\mathcal{F}}
\newcommand{\Gc}{\mathcal{G}}
\newcommand{\Rc}{\mathcal{R}}
\newcommand{\Sc}{\mathcal{S}}
\newcommand{\Ac}{\mathcal{A}}
\newcommand{\Mc}{\mathcal{M}}
\newcommand{\Tc}{\mathcal{T}}
\newcommand{\Vc}{\mathcal{V}}
\newcommand{\Dc}{\mathcal{D}}
\newcommand{\Bc}{\mathcal{B}}
\newcommand{\Hc}{\mathcal{H}}
\newcommand{\A}{\mathcal A}
\renewcommand{\S}{\mathcal S}
\newcommand{\X}{\mathcal X}
\newcommand{\D}{\mathcal D}
\newcommand{\G}{\mathcal G}
\newcommand{\K}{\mathcal K}
\newcommand{\calP}{\mathcal P}
\newcommand{\calI}{\mathcal I}
\newcommand{\barH}{\overline{H}}
\newcommand{\hh}{\hat h}
\renewcommand{\L}{\mathcal L}
\newcommand{\Hyp}{\mathcal H}
\newcommand{\Y}{\mathcal Y}
\newcommand{\B}{\mathcal B}
\newcommand{\C}{\mathcal C}
\newcommand{\F}{\mathcal F}
\newcommand{\E}{\mathbb E}
\newcommand{\W}{\mathcal W}
\newcommand{\Z}{\mathcal Z}
\newcommand{\calE}{\mathcal E}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\Cov}{\textnormal{Cov}}
\newcommand{\V}{\mathbb V}
\newcommand{\Prob}{\mathbb P}
\newcommand{\I}{\mathbb I}
\newcommand{\N}{\mathcal N}
%\newcommand{\M}{\mathcal M}
\newcommand{\tM}{\widetilde{M}}
%\newcommand{\T}{\mathcal{T}}
\newcommand{\balpha}{\boldsymbol \alpha}
\newcommand{\bmu}{\boldsymbol \mu}
\newcommand{\bSigma}{\boldsymbol \Sigma}
\newcommand{\bP}{\mathbf{P}}
\newcommand{\bhP}{\widehat{\mathbf{P}}}
\newcommand{\bT}{\boldsymbol{T}}
\newcommand{\bX}{\boldsymbol{X}}
\newcommand{\bY}{\boldsymbol{Y}}
\newcommand{\bx}{\boldsymbol{x}}
\newcommand{\MV}{\textnormal{MV}}
\newcommand{\hMV}{\widehat{\textnormal{MV}}}
\newcommand{\barmu}{\bar\mu}
\newcommand{\hpi}{\hat\pi}
\newcommand{\tDelta}{\widetilde{\Delta}}
\newcommand{\hmu}{\widehat{\mu}}
\newcommand{\hrho}{\hat\rho}
\newcommand{\heps}{\hat\eps}
\newcommand{\hnu}{\hat\nu}
\newcommand{\trho}{\tilde\rho}
\newcommand{\brho}{\bar\rho}
\newcommand{\hM}{\widehat{M}}
\newcommand{\hN}{\widehat{N}}
\newcommand{\tmu}{\widetilde{\mu}}
\newcommand{\tpi}{\widetilde{\pi}}
\newcommand{\barvar}{\bar\sigma^2}
%\newcommand{\hvar}{\hat\sigma^2}
\newcommand{\tvar}{\tilde\sigma^2}
\newcommand{\R}{\mathcal{R}}
\newcommand{\htheta}{\hat{\theta}}
\newcommand{\hR}{\widehat{\mathcal{R}}}
\newcommand{\tR}{\widetilde{\mathcal R}}
%\newcommand{\var}{\sigma^2}
\newcommand{\invdelta}{1/\delta}
\newcommand{\boldR}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\newcommand{\mvlcb}{\textnormal{\texttt{MV-LCB }}}
\newcommand{\ucb}{\textnormal{\textsl{UCB }}}
\newcommand{\ucbv}{\textnormal{\textsl{UCB-V }}}
\newcommand{\mvlcbt}{\textnormal{\texttt{MV-LCB(t) }}}
\newcommand{\mom}{\textnormal{MoM}}
\newcommand{\me}{\textnormal{ME}}
\newcommand{\mt}{\textnormal{MT}}
\newcommand{\eh}{1/(1-\gamma)}
\newcommand{\ehf}{\frac1{1-\gamma}}


\newcommand{\cvar}{\textnormal{C}}
\newcommand{\hcvar}{\widehat{\textnormal{C}}}
\newcommand{\hvar}{\widehat{\textnormal{V}}}


\newcommand{\avg}[2]{\frac{1}{#2} \sum_{#1=1}^{#2}}
\newcommand{\hDelta}{\widehat{\Delta}}
\newcommand{\hGamma}{\widehat{\Gamma}}




%\newcommand{\todo}[1]{{\bf[#1]}}

\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}

\newcommand{\beqa}{\begin{eqnarray}}
\newcommand{\eeqa}{\end{eqnarray}}

\newcommand{\beqan}{\begin{eqnarray*}}
\newcommand{\eeqan}{\end{eqnarray*}}


\renewcommand{\P}{\mathbb{P}}
\renewcommand{\Pr}{\mathbb{P}}
\newcommand{\Q}{\mathbb{Q}}
%\newcommand{\E}{\mathbb{E}}
\newcommand{\Esp}{\mathbb{E}}
\newcommand{\Var}{\mathbb{V}}
\newcommand{\indic}[1]{\mathbb{I}\{#1\}}
\newcommand{\EE}[1]{\E\left[#1\right]}
%\newcommand{\Prob}[1]{\P\left(#1\right)}
\newcommand{\wh}{\widehat}
\newcommand{\wt}{\widetilde}

\let\R\undefined %sometimes it is defined as something I don't know
\newcommand{\R}{\mathbb{R}}
\newcommand{\Real}{\mathbb{R}}
\newcommand{\Normal}{\mathcal{N}}

\newcommand{\eqdef}{\stackrel{\rm def}{=}}

\newcommand{\cl}[2][ (]{
\ifthenelse{\equal{#1}{ (}}{\left (#2\right)}{}
\ifthenelse{\equal{#1}{[}}{\left[#2\right]}{}
\ifthenelse{\equal{#1}{\{}}{\left\{#2\right\}}{}
}

\newcommand{\inset}[3][C]{
\ifthenelse{\equal{#1}{C}}{{#2}\in\mathcal{#3}}{}
\ifthenelse{\equal{#1}{T}}{{#2}\in{#3}}{}
}

\newcommand{\ESum}[4][C]
{\ifthenelse{\equal{#1}{C}}{\underset{\inset{#3}{#4}}{\sum}#2}{}
 \ifthenelse{\equal{#1}{T}}{\underset{\inset[N]{#3}{#4}}{\sum}#2}{}
\ifthenelse{\equal{#1}{U}}{\overset{#4}{\underset{#3}{\sum}}#2}{}
\ifthenelse{\equal{#1}{X}}{\sideset{}{_{#3}^{#4}}{\sum}#2}{}
\ifthenelse{\equal{#1}{S}}{\sideset{}{_{#3}^{#4}}{\sum}#2}{}
\ifthenelse{\equal{#1}{O}}{{\underset{ (#3,#4)}{\sum}}#2}{}
\ifthenelse{\equal{#1}{I}}{{\underset{#3}{\sum}}#2}{}}

\newcommand{\VF}[2][N]{
\ifthenelse{\equal{#1}{L}}{V^{\pi}_{\lambda} (#2)}{}
\ifthenelse{\equal{#1}{C}}{V{^{\pi} (#2)}}{}
\ifthenelse{\equal{#1}{T}}{V^*_{\bar{\pi}} (#2)}{}
\ifthenelse{\equal{#1}{CO}}{V{^{*} (#2)}}{}
\ifthenelse{\equal{#1}{Mx}}{V^{\pi}_{\infty} (#2)}{}
\ifthenelse{\equal{#1}{Mxo}}{V^{\pi^*}_{\infty} (#2)}{}
\ifthenelse{\equal{#1}{Mn}}{V^{\pi}_{-\infty} (#2)}{}
\ifthenelse{\equal{#1}{Mno}}{V^{\pi^*}_{-\infty} (#2)}{}
}

\newcommand{\Eval}[1][null]{
\ifthenelse{\equal{#1}{null}}{\mathbb{E}}{\mathbb{E}_{#1}}
}

\newcommand{\M}[1][]{
\mathcal{M}_{#1}
}


\newcommand{\qv}[1][null]{
\ifthenelse{\equal{#1}{null}}{Q^*}{Q^{#1}}
}

\newcommand{\T}[1][null]{
\ifthenelse{\equal{#1}{null}}{\mathcal{T}}{\mathcal{T}^{#1}}
}



\newcommand{\subLim}[2]{
\underset{#1\rightarrow#2}{\lim}
}

\newcommand{\Norm}[2][]
{
\left\|#2\right\|_{#1}
}

\newcommand{\bldsym}{\boldsymbol}


% Propositions
%\newtheorem{lemma}{Lemma}
\newtheorem{assumption}{Assumption}
%\newtheorem{corollary}{Corollary}
%\newtheorem{proposition}{Proposition}
%\newtheorem{definition}{Definition}
%\newtheorem{theorem}{Theorem}
%%\newtheorem{proof}{Proof}

% Misc
\newcommand{\TODO}[1]{(\textbf{TODO: {#1}})}
%\newcommand{\remark}[1]{\textbf{Remark #1.}}


iclr2018_conference.bbl
\begin{thebibliography}{45}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Auer \& Ortner(2007)Auer and Ortner]{auer2007logarithmic}
Peter Auer and Ronald Ortner.
\newblock Logarithmic online regret bounds for undiscounted reinforcement
  learning.
\newblock \emph{Advances in Neural Information Processing Systems},
  19:\penalty0 49, 2007.

\bibitem[Azar et~al.(2017)Azar, Osband, and Munos]{azar2017minimax}
Mohammad~Gheshlaghi Azar, Ian Osband, and R{\'e}mi Munos.
\newblock Minimax regret bounds for reinforcement learning.
\newblock \emph{arXiv preprint arXiv:1703.05449}, 2017.

\bibitem[Bellemare et~al.(2015)Bellemare, Naddaf, Veness, and
  Bowling]{bellemare2015arcade}
Marc Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling.
\newblock The arcade learning environment: An evaluation platform for general
  agents.
\newblock In \emph{Twenty-Fourth International Joint Conference on Artificial
  Intelligence}, 2015.

\bibitem[Bellemare et~al.(2016)Bellemare, Srinivasan, Ostrovski, Schaul,
  Saxton, and Munos]{bellemare2016unifying}
Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton,
  and Remi Munos.
\newblock Unifying count-based exploration and intrinsic motivation.
\newblock In \emph{Advances in Neural Information Processing Systems}, pp.\
  1471--1479, 2016.

\bibitem[Bellemare et~al.(2017)Bellemare, Dabney, and
  Munos]{bellemare2017distributional}
Marc~G Bellemare, Will Dabney, and R{\'e}mi Munos.
\newblock A distributional perspective on reinforcement learning.
\newblock In \emph{International Conference on Machine Learning}, pp.\
  449--458, 2017.

\bibitem[Bellman \& Kalaba(1965)Bellman and Kalaba]{bellman1965dynamic}
Richard Bellman and Robert Kalaba.
\newblock \emph{Dynamic programming and modern control theory}.
\newblock Academic Press New York, 1965.

\bibitem[Bertsekas(1995)]{bertsekas1995dynamic}
Dimitri Bertsekas.
\newblock \emph{Dynamic programming and optimal control}, volume~1.
\newblock Athena Scientific, Belmont, MA, 1995.

\bibitem[Bishop(1995)]{bishop1995training}
Chris~M Bishop.
\newblock Training with noise is equivalent to {T}ikhonov regularization.
\newblock \emph{Neural computation}, 7\penalty0 (1):\penalty0 108--116, 1995.

\bibitem[Blundell et~al.(2015)Blundell, Cornebise, Kavukcuoglu, and
  Wierstra]{blundell2015weight}
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra.
\newblock Weight uncertainty in neural networks.
\newblock In \emph{Proceedings of The 32nd International Conference on Machine
  Learning}, pp.\  1613--1622, 2015.

\bibitem[Fix \& Geist(2012)Fix and Geist]{fix2012monte}
Jeremy Fix and Matthieu Geist.
\newblock Monte-{C}arlo swarm policy search.
\newblock In \emph{Swarm and Evolutionary Computation}, pp.\  75--83. Springer,
  2012.

\bibitem[Fortunato et~al.(2017)Fortunato, Blundell, and
  Vinyals]{fortunato2017bayesian}
Meire Fortunato, Charles Blundell, and Oriol Vinyals.
\newblock Bayesian recurrent neural networks.
\newblock \emph{arXiv preprint arXiv:1704.02798}, 2017.

\bibitem[Gal \& Ghahramani(2016)Gal and Ghahramani]{gal16}
Yarin Gal and Zoubin Ghahramani.
\newblock Dropout as a bayesian approximation: Representing model uncertainty
  in deep learning.
\newblock In Maria~Florina Balcan and Kilian~Q. Weinberger (eds.),
  \emph{Proceedings of The 33rd International Conference on Machine Learning},
  volume~48 of \emph{Proceedings of Machine Learning Research}, pp.\
  1050--1059, New York, New York, USA, 20--22 Jun 2016. PMLR.
\newblock URL \url{http://proceedings.mlr.press/v48/gal16.html}.

\bibitem[Geist \& Pietquin(2010{\natexlab{a}})Geist and
  Pietquin]{geist2010kalman}
Matthieu Geist and Olivier Pietquin.
\newblock Kalman temporal differences.
\newblock \emph{Journal of artificial intelligence research}, 39:\penalty0
  483--532, 2010{\natexlab{a}}.

\bibitem[Geist \& Pietquin(2010{\natexlab{b}})Geist and
  Pietquin]{geist2010managing}
Matthieu Geist and Olivier Pietquin.
\newblock Managing uncertainty within value function approximation in
  reinforcement learning.
\newblock In \emph{Active Learning and Experimental Design workshop (collocated
  with AISTATS 2010), Sardinia, Italy}, volume~92, 2010{\natexlab{b}}.

\bibitem[Graves(2011)]{graves2011practical}
Alex Graves.
\newblock Practical variational inference for neural networks.
\newblock In \emph{Advances in Neural Information Processing Systems}, pp.\
  2348--2356, 2011.

\bibitem[Hazan et~al.(2016)Hazan, Levy, and Shalev-Shwartz]{hazan2016graduated}
Elad Hazan, Kfir~Yehuda Levy, and Shai Shalev-Shwartz.
\newblock On graduated optimization for stochastic non-convex problems.
\newblock In \emph{International Conference on Machine Learning}, pp.\
  1833--1841, 2016.

\bibitem[Hinton \& Van~Camp(1993)Hinton and Van~Camp]{hinton1993keeping}
Geoffrey~E Hinton and Drew Van~Camp.
\newblock Keeping the neural networks simple by minimizing the description
  length of the weights.
\newblock In \emph{Proceedings of the sixth annual conference on Computational
  learning theory}, pp.\  5--13. ACM, 1993.

\bibitem[Hochreiter \& Schmidhuber(1997)Hochreiter and
  Schmidhuber]{hochreiter1997flat}
Sepp Hochreiter and J{\"u}rgen Schmidhuber.
\newblock Flat minima.
\newblock \emph{Neural Computation}, 9\penalty0 (1):\penalty0 1--42, 1997.

\bibitem[Houthooft et~al.(2016)Houthooft, Chen, Duan, Schulman, De~Turck, and
  Abbeel]{houthooft2016vime}
Rein Houthooft, Xi~Chen, Yan Duan, John Schulman, Filip De~Turck, and Pieter
  Abbeel.
\newblock {VIME}: Variational information maximizing exploration.
\newblock In \emph{Advances in Neural Information Processing Systems}, pp.\
  1109--1117, 2016.

\bibitem[Jaksch et~al.(2010)Jaksch, Ortner, and Auer]{jaksch2010near}
Thomas Jaksch, Ronald Ortner, and Peter Auer.
\newblock Near-optimal regret bounds for reinforcement learning.
\newblock \emph{Journal of Machine Learning Research}, 11\penalty0
  (Apr):\penalty0 1563--1600, 2010.

\bibitem[Kearns \& Singh(2002)Kearns and Singh]{kearns2002near}
Michael Kearns and Satinder Singh.
\newblock Near-optimal reinforcement learning in polynomial time.
\newblock \emph{Machine Learning}, 49\penalty0 (2-3):\penalty0 209--232, 2002.

\bibitem[Lattimore et~al.(2013)Lattimore, Hutter, and
  Sunehag]{lattimore2013sample}
Tor Lattimore, Marcus Hutter, and Peter Sunehag.
\newblock The sample-complexity of general reinforcement learning.
\newblock In \emph{Proceedings of The 30th International Conference on Machine
  Learning}, pp.\  28--36, 2013.

\bibitem[Lillicrap et~al.(2015)Lillicrap, Hunt, Pritzel, Heess, Erez, Tassa,
  Silver, and Wierstra]{lillicrap2015continuous}
Timothy~P Lillicrap, Jonathan~J Hunt, Alexander Pritzel, Nicolas Heess, Tom
  Erez, Yuval Tassa, David Silver, and Daan Wierstra.
\newblock Continuous control with deep reinforcement learning.
\newblock \emph{arXiv preprint arXiv:1509.02971}, 2015.

\bibitem[Lipton et~al.(2016)Lipton, Gao, Li, Li, Ahmed, and
  Deng]{lipton2016efficient}
Zachary~C Lipton, Jianfeng Gao, Lihong Li, Xiujun Li, Faisal Ahmed, and
  Li~Deng.
\newblock Efficient exploration for dialogue policy learning with {BBQ}
  networks \& replay buffer spiking.
\newblock \emph{arXiv preprint arXiv:1608.05081}, 2016.

\bibitem[Mnih et~al.(2015)Mnih, Kavukcuoglu, Silver, Rusu, Veness, Bellemare,
  Graves, Riedmiller, Fidjeland, Ostrovski, et~al.]{mnih2015human}
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei~A Rusu, Joel Veness,
  Marc~G Bellemare, Alex Graves, Martin Riedmiller, Andreas~K Fidjeland, Georg
  Ostrovski, et~al.
\newblock Human-level control through deep reinforcement learning.
\newblock \emph{Nature}, 518\penalty0 (7540):\penalty0 529--533, 2015.

\bibitem[Mnih et~al.(2016)Mnih, Badia, Mirza, Graves, Lillicrap, Harley,
  Silver, and Kavukcuoglu]{mnih2016asynchronous}
Volodymyr Mnih, Adria~Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy
  Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.
\newblock Asynchronous methods for deep reinforcement learning.
\newblock In \emph{International Conference on Machine Learning}, pp.\
  1928--1937, 2016.

\bibitem[Mobahi(2016)]{mobahi2016training}
Hossein Mobahi.
\newblock Training recurrent neural networks by diffusion.
\newblock \emph{arXiv preprint arXiv:1601.04114}, 2016.

\bibitem[Moriarty et~al.(1999)Moriarty, Schultz, and
  Grefenstette]{moriarty1999evolutionary}
David~E Moriarty, Alan~C Schultz, and John~J Grefenstette.
\newblock Evolutionary algorithms for reinforcement learning.
\newblock \emph{Journal of Artificial Intelligence Research}, 11:\penalty0
  241--276, 1999.

\bibitem[Osband et~al.(2014)Osband, Van~Roy, and Wen]{osband2014generalization}
Ian Osband, Benjamin Van~Roy, and Zheng Wen.
\newblock Generalization and exploration via randomized value functions.
\newblock \emph{arXiv preprint arXiv:1402.0635}, 2014.

\bibitem[Osband et~al.(2016)Osband, Blundell, Pritzel, and
  Van~Roy]{osband2016deep}
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van~Roy.
\newblock Deep exploration via bootstrapped {DQN}.
\newblock In \emph{Advances In Neural Information Processing Systems}, pp.\
  4026--4034, 2016.

\bibitem[Osband et~al.(2017)Osband, Russo, Wen, and Van~Roy]{osband2017deep}
Ian Osband, Daniel Russo, Zheng Wen, and Benjamin Van~Roy.
\newblock Deep exploration via randomized value functions.
\newblock \emph{arXiv preprint arXiv:1703.07608}, 2017.

\bibitem[Ostrovski et~al.(2017)Ostrovski, Bellemare, Oord, and
  Munos]{ostrovski2017count}
Georg Ostrovski, Marc~G Bellemare, Aaron van~den Oord, and Remi Munos.
\newblock Count-based exploration with neural density models.
\newblock \emph{arXiv preprint arXiv:1703.01310}, 2017.

\bibitem[Oudeyer \& Kaplan(2007)Oudeyer and Kaplan]{oudeyer07intrinsic}
Pierre-Yves Oudeyer and Frederic Kaplan.
\newblock What is intrinsic motivation? {A} typology of computational
  approaches.
\newblock \emph{Frontiers in neurorobotics}, 1, 2007.

\bibitem[Plappert et~al.(2017)Plappert, Houthooft, Dhariwal, Sidor, Chen, Chen,
  Asfour, Abbeel, and Andrychowicz]{plappert2017parameter}
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard~Y
  Chen, Xi~Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz.
\newblock Parameter space noise for exploration.
\newblock \emph{arXiv preprint arXiv:1706.01905}, 2017.

\bibitem[Puterman(1994)]{puterman1994markov}
Martin Puterman.
\newblock \emph{{Markov decision processes: discrete stochastic dynamic
  programming}}.
\newblock John Wiley \& Sons, 1994.

\bibitem[{Salimans} et~al.(2017){Salimans}, {Ho}, {Chen}, and
  {Sutskever}]{2017arXiv170303864S}
Tim {Salimans}, J.~{Ho}, X.~{Chen}, and I.~{Sutskever}.
\newblock {Evolution Strategies as a Scalable Alternative to Reinforcement
  Learning}.
\newblock \emph{ArXiv e-prints}, 2017.

\bibitem[Schmidhuber(2010)]{schmidhuber2010formal}
J{\"u}rgen Schmidhuber.
\newblock Formal theory of creativity, fun, and intrinsic motivation
  (1990--2010).
\newblock \emph{IEEE Transactions on Autonomous Mental Development}, 2\penalty0
  (3):\penalty0 230--247, 2010.

\bibitem[Schulman et~al.(2015)Schulman, Levine, Abbeel, Jordan, and
  Moritz]{schulman2015trust}
J.~Schulman, S.~Levine, P.~Abbeel, M.~Jordan, and P.~Moritz.
\newblock Trust region policy optimization.
\newblock In \emph{Proc. of ICML}, pp.\  1889--1897, 2015.

\bibitem[Singh et~al.(2004)Singh, Barto, and Chentanez]{singh2004intrinsically}
Satinder~P Singh, Andrew~G Barto, and Nuttapong Chentanez.
\newblock Intrinsically motivated reinforcement learning.
\newblock In \emph{NIPS}, volume~17, pp.\  1281--1288, 2004.

\bibitem[Sutton \& Barto(1998)Sutton and Barto]{sutton1998reinforcement}
Richard~S Sutton and Andrew~G Barto.
\newblock \emph{Reinforcement learning: An introduction}.
\newblock Cambridge Univ Press, 1998.

\bibitem[Sutton et~al.(1999)Sutton, McAllester, Singh, and
  Mansour]{sutton1999policy}
Richard~S. Sutton, David~A. McAllester, Satinder~P. Singh, and Yishay Mansour.
\newblock Policy gradient methods for reinforcement learning with function
  approximation.
\newblock In \emph{Proc. of NIPS}, volume~99, pp.\  1057--1063, 1999.

\bibitem[Thompson(1933)]{thompson1933likelihood}
William~R Thompson.
\newblock On the likelihood that one unknown probability exceeds another in
  view of the evidence of two samples.
\newblock \emph{Biometrika}, 25\penalty0 (3/4):\penalty0 285--294, 1933.

\bibitem[van Hasselt et~al.(2016)van Hasselt, Guez, and Silver]{van2016deep}
Hado van Hasselt, Arthur Guez, and David Silver.
\newblock Deep reinforcement learning with double q-learning.
\newblock In \emph{Proc. of AAAI}, pp.\  2094--2100, 2016.

\bibitem[Wang et~al.(2016)Wang, Schaul, Hessel, Hasselt, Lanctot, and
  Freitas]{wang2016Dueling}
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado~van Hasselt, Marc Lanctot, and
  Nando~de Freitas.
\newblock Dueling network architectures for deep reinforcement learning.
\newblock In \emph{Proceedings of The 33rd International Conference on Machine
  Learning}, pp.\  1995--2003, 2016.

\bibitem[Williams(1992)]{williams1992simple}
Ronald~J Williams.
\newblock Simple statistical gradient-following algorithms for connectionist
  reinforcement learning.
\newblock \emph{Machine learning}, 8\penalty0 (3-4):\penalty0 229--256, 1992.

\end{thebibliography}
