\documentclass[a4paper,11pt]{amsart}
\usepackage[utf8]{inputenc}\usepackage[T1]{fontenc}

\title{Deep Banana Eater -- A Deep Q-Network reinforcement learning agent}
\author{Julian Wergieluk}\address{}\email{julian.wergieluk@risklab.com}
\input{preamble}
\input{commands}

\usepackage[url=false,backend=biber]{biblatex}
\addbibresource{literature.bib}

\begin{document}

\maketitle

\begin{abstract}
This short note provides a concise description of the model architecture and
learning algorithms of the agent developed in this project. We also report learning
performance of the agent and provide a list of possible future model improvements.
\end{abstract}
\renewcommand*{\thefootnote}{}\footnote{\today{}}

\section{Description of the learning algorithm}

%Requirement: The report clearly describes the learning algorithm, along with the chosen hyperparameters. It also describes the model architectures for any neural networks.

The algorithm used to solve the problem posed in this project closely resembles
the algorithm proposed in \cite{mnih2015humanlevel}.

The agent is trained over a given number of episodes labeled with $n = 1,\cdots, 1800$.
Each episode is divided into turns $t = 1,\cdots, 300$.
The state space $\mathcal S$ of the environment is continuous and given by
$\mathcal S = \mathbb R^{37}$, whereas the action space $\mathcal A = \left\{
0,1,2,3 \right\}$ is discrete and independent of the current environment state
(i.e.\ all four actions are available irrespective of the current state). The state-action value
function $Q_{\theta}: \mathcal S \times \mathcal A \mapsto \mathbb R$ maps a
state-action pair to an estimated expected discounted cumulative reward
generated by an agent following a greedy policy $\pi_{\theta}$ derived from $Q_{\theta}$.
The parameter vector $\theta$ determining the state-action value function
$Q_{\theta}$ takes values in a finite-dimensional vector space $\mathbb R^{p}$. 

We count the turns across the episodes of a training session using the variable $T =
300(n-1) + t$. At each turn $T$ during the training time the agent chooses an
action using an $\varepsilon$-greedy policy derived from $Q_{\theta(T)}$ and
$\varepsilon = \varepsilon(T) = \operatorname{exp}\left( -T \lambda \right)$ with
constant decay rate $\lambda = 0.00002$ (see Figure \ref{fig:epsilon}).

Also, at each turn $t<300$, the experience tuple $\left( S_{t}, A_{t}, R_{t+1}, S_{t+1}
\right)$ is saved to the replay buffer. If the turn number $t$ is divisible by
$4$ and the replay buffer contains more than $B=128$ saved tuples, the $Q$
function parameters $\theta$ are updated as follows: The algorithm
samples $B$ experience tuples (without replacements) from the replay buffer, and
for each tuple $(S_0, A_0, R_1, S_1)$ the following loss value 
$L_\theta(S_0, A_0, R_1, S_1)$ is calculated
\begin{align*}
L_\theta(S_0, A_0, R_1, S_1) &= \left[ 
        R_1 + \gamma \operatorname{max_{a\in\mathcal A}} Q_{\theta}(S_1, a) - 
        Q_{\theta}(S_0, A_0)
    \right]^2.
\end{align*}
Assume that for each $(s, a) \in \mathcal S \times \mathcal A$ the function
$\theta \mapsto Q_{\theta}(s,a)$ is differentiable. It follows that the
function $\theta\mapsto L_\theta(S_0, A_0, R_1, S_1)$ is also differentiable.
We can calculate the (total) derivative $\frac{d L}{d\theta}$ and use the ADAM
optimizer to update the parameter vector $\theta$ with the aim of minimizing
the loss $L_{\theta}$. We perform this minimization step for each experience
tuple in the sampled experience batch.

To ensure the validity of the minimization step, we use a deep neural network
with two fully connected layers to represent the function Q. The parameter
vector $\theta$ contains the weight and bias parameters of that neural network.

The neural network architecture is as follows: 

\verbatiminput{qnet.txt}

\begin{table}
%\centering
\caption{List of hyperparameters and their values}
\begin{tabular}{|l|l|l|}
    \hline
Hyperparameter & Value \\ 
    \hline \hline
    Learning rate of the ADAM optimizer & 0.0005 \\
    Q-network update frequency & every 4 turns \\
    Replay buffer size & 100,000 \\
    Batch size & 128  \\
    Discount factor ($\gamma$) & 0.99 \\
    $\varepsilon$ & Decays from $1$ to $0$ with \\
    & the decay rate $\lambda = 0.00002$. \\
    \hline
\end{tabular}
\label{tab:hyperparameters}
\end{table}

\section{Training analysis}

Despite its simplicity, the agent described in this report is able to solve the
environment after completing less than $1000$ episodes. In fact, in a training
session depicted in Figure \ref{fig:avg-scores} the agent surpasses the average
cumulative score of $13$ around episode $900$ and reaches the average
cumulative reward of almost $16$ at the end of the training session.

\begin{figure}[tb]
    \centering
    \includegraphics[width=\textwidth]{{avg-scores}.png}
    \caption{Rolling window average of the cumulative reward for each episode
    in a training session consisting of $1800$ episodes. The threshold average
    cumulative reward of $13$ is reached around episode $900$.}
    \label{fig:avg-scores}
\end{figure}

\begin{figure}[tb]
    \centering
    \includegraphics[width=\textwidth]{{epsilon}.pdf}
    \caption{Decay of the $\varepsilon$ parameter as function the 
    training episode number.}
    \label{fig:epsilon}
\end{figure}

\section{Ideas for future work}

The training performance of the agent could be improved by implementing some or
all of the ``rainbow'' improvements summarized in \cite{hessel2018rainbow}.  In
particular, the prioritized experience replay is easy to implement and would
likely lower the number of training episodes needed to reach the threshold of
13 reward points. 

%\nocite{meucci2009review, goodman2007}
\printbibliography

\end{document}

% vim: spelllang=en_us:spell:
