Towards Automatic Variant Analysis of Ancient Devotional Texts

We address in this paper the issue of text reuse in liturgical manuscripts of the middle ages. More specifically, we study variant readings of the Obsecro Te prayer, part of the devotional Books of Hours often used by Christians as guidance for their daily prayers. We aim at automatically extracting and categorising pairs of words and expressions that exhibit variant relations. For this purpose, we adopt a linguistic classification that allows to better characterize the variants than edit operations. Then, we study the evolution of Obsecro Te texts from a temporal and geographical axis. Finally, we contrast several unsupervised state-of-the-art approaches for the automatic extraction of Obsecro Te variants. Based on the manual observation of 772 Obsecro Te copies which show more than 21,000 variants, we show that the proposed methodology is helpful for an automatic study of variants and may serve as basis to analyze and to depict useful information from devotional texts.

Introduction
Among the most popular texts of the late middle ages were Books of Hours, used by Christians as a guidance book for their daily prayers. Appearing in the thirteenth century, in France, the Netherlands, and England and, later on, in Italy, Spain, and many other European countries, Books of Hours constitute one of the bestsellers of the late medieval period. Books of Hours evolved over the years and additional texts were included. Mostly written in Latin, they often include parts in Vernacular languages (esp. French). The whole was arranged in a particular repetitive structure that varied in its details depending on times of the day, seasons, liturgical use, patrons, origin (Wieck, 1988;Hindman and Marrow, 2013), etc.
Despite their success, the content of Books of Hours has been rarely studied on a large-scale in NLP, mainly due to the lack of available transcriptions. few of them are available. One textual element of Books of Hours which offers an opportunity for study is Obsecro Te. This devotional prayer to the Virgin Mary was manually transcribed and annotated based on 772 Books of Hours (Plummer and Clark, 2015). More than 21,000 textual variants were recorded. Plummer and Clark (2015) observed and reported three types of variants present in the Obsecro Te dataset, that is: (i) addition (marked "+", e.g. "peccatis + vel mortalibus" for criminalibus peccatis / criminalibus peccatis vel mortalibus), (ii) substitution (marked ":", e.g. "opera misericordia: misericordia opera" for opera misericordia / misericordia opera), and (iii) omission (marked "-", e.g. "-gloriosam" for ostendem michi gloriosam / ostende michi). This classification is roughly based on a surface assessment and does not allow a more fine-grained analysis of variants characteristic while no linguistic information is included. In order to study in a more precise way Obsecro Te variant readings, we adopt a linguistic classification based on both synformic and conceptual (similar words form) concepts (Laufer, 1988;Daille, 2017). Clark's variants consist in addition, suppression or omission operations at the word level. The same operation groups diverse linguistic operations. Substitution operation for instance, may refer to flexional variants (crucem / cruce), paradigmatic variants obtained by synonymic substitution (gratie / indulgencie), etc. Also, two consecutive substitution operations may characterise variant permutation (opera misericordia / misericordia opera). We conduct an automatic empirical study of the main unsupervised stateof-the-art approaches dealing with variant extraction and discuss our findings according to the proposed linguistic variant classification. Finally, we study variant-relation phenomena and the evolu-  tion of Obsecro Te readings from a temporal and geographical axis and discuss several aspects of Books of Hours. This work constitutes a first step in the automatic study of Book of Hours content in order to discover the similarities and differences in practices of the middle age. The similarities can for instance serve to detect structural, geographical or terminological correlations between Books of Hours. Whether issued from different regions of the same country or from different countries of medieval Europe.

Books of Hours and Obsecro Te
Books of Hours contain a set of prayers to be used at eight hours of the day. The structure and content of Books of Hours vary from one book to another and this particularity is certainly due to the nature of textual transmission in a world before the printing press. Books of Hours did not appear as such until the thirteenth century. Before, other types of books were used. For their daily prayers, Christians adopted the Psalter previously used by the Jews for their devotions. Over the years, a number of additional texts came to enrich the Psalter, such as, antiphons, canticles, hymns, readings from the Bible, etc. The whole was arranged in a repetitive structure that varied in its details depending on times of the day and seasons. Also, a calendar was used to record local saints, days and feast's seasons. Finally, rubrics were employed as guidance on what to say and when to say it. This resulted in a complex book known as breviary. The breviary was used by clerks and was not intended to be used by lay people for whom it was too complex. However, the desire of lay people to imitate monastic practices resulted in the creation of a simpler book, that was easier to use: the Book of Hours. Amongst the prayers in Books of Hours is the Obsecro Te, a supplication to the Virgin Mary. As the content of a Book of Hours may vary due to writing choice, local liturgical practices, etc., we aim in this paper to study the amount and nature of variants of Obsecro Te. Table 1 shows an example of the first lines of two copies of Obsecro Te. Red are the variants according to an arbitrary lines alignment of the two texts (Plummer and Clark, 2015). As highlighted by the passages in red, several variants can be observed. In line 3, for instance, the words "et spes" in Obsecro Te 1 are added between the words "salus" et "in" ((Plummer and Clark, 2015) notes that "salus + et spes", while in line 4, the words "et" and "Fons misericordie" are omitted in Obsecro Te 2. Also, at lines 7-8, the Annunciation is addressed with the expression per Gabrielem annunciatus ( Obsecro Te 1), while Obsecro Te 2 expands upon the passage by specifying the announcer, the archangelum, and the effect et conceptus. If the reasons of such variants are a matter of interpretation, we aim at depicting the most common ones. For that purpose, we define in the next section our proposed classification of the observed variants before presenting an empirical study for variant extraction and categorisation.

Obsecro Te Variant Categorization
We introduce in this section a new variant classification inspired by similar lexical forms (Synforms) introduced in (Laufer, 1988) and the terminological variant typology proposed in (Daille, 2017) applying to nominals.

Similar Lexical Forms (Synforms)
The concept of synforms was first introduced to deal with lexical confusions of English learners (Laufer, 1988). Synforms are defined at the word level and can be classified on the basis of their similarity features. Words can be different in their affix and similar in their root, different in one phoneme, consonant or vowel. Usually, ten categories including letter addition, substitution and omission, are reported (Laufer, 1988;Kocic, 2008). These categories include: productive synforms with the same root and different suffixes (considerable / considerate, successful / successive); non-productive synforms with the same root and different suffixes (credible / credulous, capable / capacious); synforms which, although identical in consonants, have different vowels (base / bias, manual / menial); synforms with identical phonemes except for one consonant (price / prize, extend / extent), etc.

Lexical Similarity at the Word Ngram Level (N-Synforms)
We extend the similar lexical forms concept (Laufer, 1988;Kocic, 2008) to the word ngram level. Nonetheless, we do not exploit the ten categories presented in (Laufer, 1988), as it deals with confusions of English learners. Therefore, we keep the word level categorization of unigrams as defined in Daille (2017) and extend it using linguistic operations often applied to complex terms and to ngrams. Base on the copies of the Obsecro Te prayer and the variant annotations in (Plummer and Clark, 2015), we propose a linguistic representation of variant's typology that can be applied to word ngrams of any length. Our typology includes basic linguistic variants at the word level (orthography, inflexion, derivation), lexical substitution, as well as operations specific to sequence of words (reduction, expansion and permutation). Figure 1 illustrates our typology. We describe the proposed categorization as follows: Orthography letter substitution (consonant or vowel) like dilecto / delecto;

Inflexion latin inflexions like crucem / cruce;
Derivation is defined as an operation which creates a new lexical unit from one existing word through modification processes such as affixation or convertion dilecto (Adj)/ dilectissimo (Adj superlative); Lexical substitution refers to any operation of substitution of a lexical unit by another. Lexical substitution allows variants in semantic relation, such as synonymy (tribuas / concedas), near-synonymy (gratie / indulgencie) and other variants with no clear semantic relation such as (tribuas / obtineas); Expansion refers to several linguistic operations such as modification which specifies the nominal phrase, predication which inserts the nominal phrase into a nominal argument structure, coordination that emphasize an aspect (criminalibus peccatis / criminalibus peccatis vel mortalibus); Reduction removes one of the lexical constituents of ngrams such as ostendem michi gloriosam / ostendem michi; Permutation of the n-gram elements such as criminalibus peccatis / peccatis criminalibus.
Of course, like any typology, ours does not claim to be exhaustive. Nonetheless, it can be extended, if necessary, to other linguistic operations like composition. Also, variants that combine multiple operations like lexical substitution and expansion or substitution exist but they are marginal.

Variant Extraction Approaches
We introduce in this section four unsupervised state-of-the-art approaches to the task of variant extraction: Edit distance (Levenshtein, 1966), Jaccard Index (Jaccard, 1901), distributional bag of words (Harris, 1971) and its adaptation to variable length variants extraction and finally, distributed word embeddings (Mikolov et al., 2013;Arora et al., 2017).

Edit Distance (Levenshtein)
Edit distance, also known as the distance of Levenshtein (Levenshtein, 1966), aligns local similari-ties and differences between strings and calculates string-alignment. Distance is calculated from the number of necessary operations (insertions, deletions and substitutions) for transforming the string x into the string y. Among the edit distance applications, we find plagiarism detection and orthographic corrections. Edit distance formula is represented as follows: where D(i,j) represents the distance between two ngrams i et j and Suppcost(i), InsCost(i) represent respectively the deletion, insertion costs of i. Finally, SubCost(i, j) represents the substitution cost of i by j. When the three cost functions are put to 1, Edit distance is equivalent to Levensthein distance. The use of Edit Distance is based on the observation that several Obsecro Te variants may be synformic (graphically similar). For instance, salvatione is very close to salvationis or salvationem. In this case, Edit distance score is 2 between salvatione and salvationis (the letter e is substituted by i and the addition of s) and a score of 1 between salvatione and salvationem (addition of the letter m).

Jaccard Index
Jaccard Index (JI) (Jaccard, 1901) measures the degree of similarity between two sets. This is represented by the number of elements in common normalized by the elements of the two sets. One advantage of Jaccard Index is that it is insensitive to element's position and for this reason is not affected by element's permutation. This particularity makes the JI well suited to semantic variants of permutation type, such as crucifixum vulneratum and vulneratum crucifixum. In this case, JI score is 0 which means that the pair of variants is similar according to permutation property. JI formula is as follows: where the two sets A and B correspond to two word ngrams, with B a variant candidate. The intersection and union are both considered at the character level.

Distributional Bag of Words
In the distributional Bag of Words (BoW) approach each word w is represented by its context vector (Harris, 1971). The context vector of w gathers all the words with which it appears in the corpus within a size n context window. The context window represents a set of surrounding words often close to the sentence level size. To measure the similarity between words, the cosine (Salton and Lesk, 1968) is applied between the context vector of w and all the word context vectors of the corpus. The closest word to w is a potential variant. We adapt BoW approach and extend it to the ngram level. The procedure remains the same, the main change lying in the context representation of each variant. Let us consider the following example: Levitae autem in tribu familiarum suarum non sunt numerati cum eis. The context vector of familiarum suarum is represented by the following ngrams: Unigrams: Levitae, autem, in, tribu, non, sunt, numerati, cum, eis; Bigrams: Levitae autem, autem in, in tribu, non sunt, sunt numerati, numerati cum, cum eis; 3grams: Levitae autem in, autem in tribu, non sunt numerati, sunt numerati cum, numerati cum eis; 4grams: Levitae autem in tribu, non sunt numerati cum, sunt numerati cum eis; and 5grams: non sunt numerati cum eis. Once the context vectors have been computed, an association measure is used as a way to better characterize the contextual relation between the head of the vector (familiarum suarum) and its constituents. We consider three different association measures: mutual information (Fano, 1961), discounted odds ratio (Evert, 2005) and log-likelihood (Dunning, 1993). Finally, to extract the candidates, we compute cosine similarity (Salton and Lesk, 1968) between all ngrams of the corpus. Our adaptation takes into account broken ngrams. Hence, in addition to the above cited ngrams, based on non sunt numerati cum eis, we add the following bigrams: non numerati, non cum, non eis, sunt cum, sunt eis, numerati eis. Therefore, we assume that the unigrams sunt, numerati, and cum may not appear or were omitted.

Word Embeddings
In the word embedding approach, each variant is represented by an embedding vector which is a linear combination of the word embeddings composing the variant (Arora et al., 2017). For instance, Embedding(w j ) (3) where A is a variant and n the number of words composing A. Embedding(w j ) corresponds to the chosen embedding model of w j . We use two pre-trained models: Word2Vec 1 and FastText 2 .

Experimental Data
To evaluate the automatic extraction of Obsecro Te variants, we exploit the Beyond Use 3 database which contains variants extracted manually from 772 manuscripts (Plummer and Clark, 2015 In order to study the impact of variant length, we build four distinct evaluation lists. Each one corresponds to an ngram size. Hence, we obtain a list of unigrams that contains only unigrams as variants; a list of bigrams that contains only bigrams as variants and so on. We do not go beyond fourgrams because very few ngrams are characterized by a length longer than four in the corpus. We finally build a fifth list that contains all the ngrams of the four previous lists as well as ngram variants of any length (20% of the variants have a variant of a different size).

Results
Our experimental procedure targets three points: (i) an empirical evaluation of Obsecro Te reading similarity; (ii) an empirical evaluation of automatic variant extraction; (iii) a qualitative variant analysis with regard to linguistics, geographic and diachronic changes.

Similarity of Obsecro Te Texts
There is substantial variation in the text of the prayer Obsecro Te. As has been shown in (Wieck, 1988;Plummer and Clark, 2015), the manual analysis of 772 Obsecro Te prayers revealed several dissimilarities as well as the existence of more than 21,000 variants. Figure 2 illustrates the simi-  larities between 80 randomly 4 selected Obsecro Te texts. The similarity is measured in terms of word overlap. Strong similarities are shown by the dark red colour, while weak similarities by dark blue. Figure 2 shows that none of the 80 sampled Obsecro Te texts are identical. This empirical finding confirms the observations of Clark and supports the idea that different copies of the prayer Obsecro Te differ substantially from one another.

Automatic Variant Extraction
In this section, we aim at evaluating unsupervised approaches to variant extraction. Hence, no clue, such as verse or segment alignment, is considered in variant modelling. This leads to the assumption that any ngram extracted from the corpus is a variant candidate. The side effect of this assumption is its error productivity while many ngrams are not variants. Table 2 illustrates the results of the implemented approaches. Edit distance shows the best results for unigram variants. Nonetheless, its performance significantly drops when variants are of length greater than 1. This can be explained by the large number of permutations that are not identified by Edit distance. Jaccard Index obtains better results than Edit distance for ngrams greater than 1, which means that conversely to Edit distance, it better handles the permutation phenomenon. Our adaptation of the bag of words approach (BOW (LL)) using log-likelihood shows the best results on the entire evaluation list (ALL). This indicates that BOW (LL) better handles variants of variable length. The lower results of BOW (MI) and BOW (OR)  lead to the assumption that these two association measures fail to capture strong ngram association relations. The lack of training data can also explain this behaviour. The word embedding approach (w2v) shows the best Map scores for ngrams greater than 1. This suggests that w2v is the most appropriate when variants are not unigrams. The lower results for unigrams can be explained by the nature of the embedding models. Indeed, w2v and fastText are pre-trained models and many Obsecro Te words are not present in these models. Finally, a linear combination of the approaches has been carried out without significant improvements.
If some phenomena can be detected such as synforms at the word level (with Edit distance for unigrams), permutations using Jaccard index, or lexical substitution using bag of words and embedding vector approaches, other phenomena are more dif-ficult to handle, such as expansion and reduction variants where the two segments are of variable length. We also report that some words and expressions are often substituted by connectors (et, a, que, de, in...), such as sanctam / et, de filio tuo / a, vulneratum / et, in omnibus / et in. Very frequent connectors represent one of the most difficult variants to extract as they show a big discrepancy of distribution between the two elements.

Qualitative Variant Analysis
Variant categories can be analysed based on Edit distance, Jaccard Index, BoW and Embedding scores as follow: (i) if Edit distance score is lower than few characters (generally 3), we can effectively pinpoint, thanks to a regular expression, one of the three synformic categories (orthographic, inflectional or derivational); (ii) if Jaccard index score is equal to 0, we face a permutation; (iii) if we combine two criteria, i.e., high Edit distance score and low Jaccard index score, we extract variants that exhibit both expansion and permutation; (iv) lexical substitution variants can be extracted using BoW or Word embedding approaches. A high cosine similarity score has also been used to give more confidence about lexical substitution variants.
Based on the observation that a large number of variants (406) appears in less than five copies of Obsecro Te, we divide our analysis into two parts: rare variants and frequent variants. Table 3 reports some examples of variants identified by our automatic extraction. For rare variant pairs (salvationem / salvatione, for instance), each reported left side variant appears only in one copy, while its right side counterpart variant appears in hundreds of copies. Rare variants may indicate either a rare usage or a misspelling error. On the other hand, frequent variants may offer a high confidence in their usage.
We observe inflectional variants as rare or frequent variants: salvationem (singular accusative) and victoria (singular) appear only once in the corpus, while salvatione (singular ablative) and victoriam (singular accusative) appear respectively 961 and 966 times. In one case the accusative mode is used, while in the other, the ablative is used. Misspellings as rare variants: viserum and vicerum are both misspellings of viscerum. Lexical substitution applies mostly to frequent variants and leads to semantic variants. Synonym lexical substitu-  tion, such as domina /virgo, is encountered in every grammatical category (noun, verb, adjective, preposition). One exception is the rare variant ancilla tua / famulo tuo, the result of two linguistic operations, lexical substitution and inflection, that may refer to a customisation of Books of Hours according to its owner, either a woman or a man. We expect that looking to the whole text of Books of Hours and increasing the number of Books of Hours, this variant will be more frequent. Indeed, Books of Hours are personal objects, and are not intended to be shared. Finally, the last example of rare variants shows the application of two lexical operations, reduction and lexical substitution. Figure 3 illustrates the number of Obsecro Te (and therefore, Books of Hours) produced between 1375 and 1530 and used in this experiment 5 . This  (Plummer and Clark, 2015) has a strong focus on the mid-fifteenth century, with a maximum of 80 copies ascribed to the year 1455. Figure 3 illustrates the number of witnesses by year using the arithmetic mean between the extreme dates, which explains the peaks on round numbers, par-corpus illustrates how the production of Books of Hours increased until the second half of the fifteenth century and decreased afterwards. A larger corpus suggests that production reached it highest level during the last third of the fifteenth century (Stutzmann, 2019). An empirical overview through approximately a century and half of Book of Hours production, does not allow to draw a direct relation in the diachronic change of Obsecro Te prayer copies. Nonetheless, our method allows to target a variant category and to observe its years of use and origins. Table 4 provides some examples of rare 3gram variants of which it is not always obvious to assign a linguistic category. We can notice that rare 3gram variants are often expansion of frequent bigrams omni auxilio consilio / omni consilio. Figures 4 and 5 illustrate the use of rare orthographic 3gram variants that have less than ten character substitutions (respectively per year and per origin). This is performed by fixing the edit distance score to 10 (which means a maximum of ten substitutions) and choosing only the variants that appear only once in the corpus. We obtain for instance, the variant pair obtained by lexical substitution petitionibus et requestis / orationibus et requestis, where the former appears only once and the latter appears 983 times. From a geographic perspective, Netherlands is the country that produces this synformic category followed by Paris. Both places are the ones producing the ticularly those ending in 0 and 5, and the important variation from one year to another largest number of copies, so that it comes as no surprise that scribes generates more variants, including the rare ones that we have isolated here. From a temporal perspective, however, we see that 3gram variants mostly appeared in 1465 and 1470. This is unexpected, since the maximum number of manuscripts in the corpus is for the years 1450 and 1455. This increase is perhaps correlated with the higher production levels of Books of Hours in the last third of the century (not strictly represented in Clark's corpus) whose variety would be reflected in Clark's corpus, but this would not explain why the 1460s and 1470s are more variant than the end of the century. We may now formulate an original hypothesis, that we observe here a loosening of the copying discipline for the Obsecro Te as a very common text, perhaps due to the multiplication of workshops or to other causes such as text memorisation, resulting in the emergence of many new, isolated variants. Even though our analysis cannot draw factual conclusions for now, it can nonetheless guide experts to analyse such phenomena.

Conclusion
We conducted for the first time a large-scale study of medieval devotional texts for the purpose of variant analysis. We used linguistic operations rather than edition operations to characterise variants in order to facilitate the interpretation of variants. We also design a suitable methodology for their detection that we hope will help medievalists in their research. If the automatic variant extraction is encouraging, further investigations are certainly needed to distinguish between orthographic in one hand, and inflectional and derivative variants in the other hand. Some computational methods well designed to deal with a particular variant detection fail when they face problematic cases: word embedding approach does not succeed to detect lexical substitutions showing a difference of distributions between the two elements, typically those substitutions that imply connectors. None of the methods is adapted to discover expansion and reduction at the n-gram level. This work constitutes a first step in the automatic study the content of Book of Hours in order to discover temporal and geographical correlations between Books of Hours, whether issued from different regions of the same country or from different countries of medieval Europe.


extfieldsofstudy:
Mathematics
Computer Science

text:
Reinforcement Learning and Video Games

Reinforcement learning has exceeded human-level performance in game playing AI with deep learning methods according to the experiments from DeepMind on Go and Atari games. Deep learning solves high dimension input problems which stop the development of reinforcement for many years. This study uses both two techniques to create several agents with different algorithms that successfully learn to play T-rex Runner. Deep Q network algorithm and three types of improvements are implemented to train the agent. The results from some of them are far from satisfactory but others are better than human experts. Batch normalization is a method to solve internal covariate shift problems in deep neural network. The positive influence of this on reinforcement learning has also been proved in this study.

The applications of Artificial Intelligence are widely used in recent years. As one part of them, Reinforcement Learning has achieved incredible results in game playing. An intelligent agent will be created and trained with reinforcement learning algorithms to fulfill this tasks. In the Future of Go Summit 2017, Alpha Go which is an AI player trained with deep reinforcement learning algorithms won three games against the world best human player in Go. The success of reinforcement learning in this area shock the world and many researches are launched such as driverless cars. Deep learning methods such as convolutional neural network contributes a lot to this because these techniques solves the problem of dealing with high dimension input data and feature extraction.
T-rex Runner is a dinosaur game from Google Chrome offline mode. The aim of the player is to escape all obstacles and get higher score until reaching the limitation which is 99999. The moving speed of the obstacles will increase as time goes by which make it difficult to get the highest score.
The code of this project can be found in this link which is written in Python.

Aim of the project
The aim of this project is to create an agent using different algorithms to play T-rex Runner and compare the performance of them. Internal covariate shift is the change of distribution in each layer of during the training which may result in longer training time especially in deep neural network. To cope with this problem, batch normalization use linear transformation on each feature to normalize the data with the same mean and variance. The same problem may also occur in deep reinforcement learning because the decision is based on neural network. Beyond the comparison of different reinforcement learning algorithms, this project will also investigate the effect of batch normalization. The overall objectives of this project are list below.
• Create an agent to play T-rex Runner • Compare the difference among different reinforcement learning algorithms • Investigate the effect of batch normalization in reinforcement learning

Overview
This study opens with a literature review on deep learning and reinforcement learning. Each section includes the history of the field and the techniques related to this study. Chapter 3 includes the description of the game and the choice of algorithms according the literature review. The entire processing step will be shown as well as the architecture of the model. The design of the experiments and the evaluation methods are presented in this chapter too. Chapter 4 shows the result of all the experiments and the discussion of each experiment. Chapter 5 presents the conclusion of this study and the proposed future works.

Literature Survey
This chapter introduces the techniques used in developing an agent to play T-rex Runner.
There are two main sections which are Deep Learning and Reinforcement Learning. Brief history and some milestones will be described and some important methods will be shown in detail.

Deep Learning
Deep learning is a class of Machine Learning model based on Artificial Neural Network (ANN). There two kinds of deep learning model which is widely used in recent years. Recurrent Neural Network is one of them which shows its power in Natural Language Processing. The other one plays an important role in deep reinforcement learning called Convolutional Neural Network (CNN). It is one of the most effective models for computer vision problems such as object detection and image classification. This section gives a brief introduction of deep learning and detailed information about convolutional neural network.

History of Deep Learning
An artificial neural network is a computation system inspired by biological neural networks which were first proposed by McCulloch, a neurophysiologist [24]. In 1957, Perceptron was invented by Frank [31]. Three years later, his experiments show this algorithm can recognize some of alphabets [32]. However, Marvin proved that a single layer perceptron cannot deal with XOR problem [25]. This stopped the development of ANN until Rumelhart et al. show that some useful representations can be learned with multi-layer perceptron, which is also called neural network, and backpropagation algorithm [33] in 1988. One year later, LeCun et al. first used a five-layer neural network and backpropagation to solved digit classification problem and achieved great results [21]. His innovative model is known as LeNet which is the beginning of the convolutional neural network.
The origin of CNN was proposed by Fukushima named Neocognitron which was a selforganized neural network model with multiple layers [10]. This model achieved a good result in object detection tasks because it is not position-sensitive. As mentioned before, LeCun et al. invented LeNet and got less than 1% error rate in mnist handwritten digits dataset in 1998 [21]. The model used convolutions and sub-sampling which is called convolution layer and pooling layer today to convert the original images into feature vectors and perform classification with fully connected layers. At the same time, some neural network models show some acceptable results in face recognition [20], speech recognition [51] and object detection [49]. But the lack of reliable theory caused the research of CNN to stagnate for many years.
In the ImageNet Large Scale Visual Recognition Challenge (ILSVRC) 2012 [9], Alex and his team got 16.4% error rate with an eight-layer deep neural network (AlexNet) [19]. This was a significant result compared with the one from second rank participant which was 26.2%. Beyond LeNet, AlexNet used eight layers to train the classifier with data augmentation, dropout, ReLU, which mitigated overfitting problem. Another significant discovery was that parallel computing with multiple GPUs can largely decrease the training time.
Two years later, Simonyan and Zisserman introduced a sixteen-layer neural network (VG-GNet) and won the first prize in ILSVRC 2014 classification and localization tasks [41]. This model got the state-of-the-art result with 7.3% error rate at that time. VGGNet also proved that using smaller filter size and deeper network can improve the performance of CNN. The size of all filters in the model was no greater than 3 × 3 while the first two layers in AlexNet were 11 × 11 and 5 × 5. In the same year, GoogLeNet [46], the best model of ILSVRC 2014 classification and detection tasks, first used inception which was proposed by Lin [23] to solve vanishing gradient problem. Inception replaced one node with a network which was consisted of several convolutional layers and pooling layers then concatenate them before passing to the next layer. This change made the feature selection between two layers more flexible. In other words, it can be updated by the backpropagation algorithm.
Another problem of the deep neural network was degradation resulting in high training error caused by optimization difficulty. To solve that problem, He et al. proposed a deep residual learning framework (ResNet) using a residual mapping instead of stacking layers directly [12]. This model won the championship in ILSVRC 2015 with only 3.57% error rate. His experiments show that this new framework can not only solve degradation problems but also can improve the computing efficiency. ResNet There were many variants based on ResNet such as Inception-ResNet [45] and DenseNet [14]. The former one combined improved inception techniques into ResNet. Every two convolutional layers were connected in the later model. This change mitigated vanishing gradient problems and improved the propagation of features.

Deep Neural Network and Activation Function
A neural network or multi-layer perceptron consists of three main components: the input layer, the hidden layer, and the output layer. Each unit in one layer called a neuron. The input data are fed into the input layer conducting linear transformation through weights in the hidden layer. Finally, the result will be given non-linear ability through activation function and fed into the output layer.
Activation function enables the network to learn more complicated relationships between inputs and outputs. There are three widely used activation functions shown in Figure 2.1: sigmoid, tanh and ReLU. ReLU is the most commonly used one in three because it has a low computational requirement and better performance in solving vanishing gradient problems compared with the other two. To illustrate the entire process in neural network, here is an example in Figure 2.2. Given an input data T = {(x 1 , y 1 ), (x 2 , y 2 ), (x 3 , y 3 ), (x 4 , y 4 ) | x i ∈ R m } and a randomly generated weight [w 1 , w 2 , w 3 , w 4 ] T in the hidden layer, the output of the neural network isŷ and the activation of the hidden layer is f . Therefore, the estimated valueŷ i can be calculated bŷ where b is the bias of the hidden layer and m is the number of features. If the number of hidden layers in the neural network is greater than two, this is also called Deep Neural Network (DNN). Consider a simple DNN with three hidden layers shown in Figure 2.3. Given the same input X = [x 1 , x 2 , x 3 , x 4 ] T in matrix form and W i is the weight between (i − 1)-th and i-th layer, the output of i-th layer a i can be calculated by where f i is the activation function between (i − 1)-th and i-th layer and z i = a i−1 W i , especially a 0 = X. The dimension of those variables are shown in Table 2.1

Parameter Description Dimension
Weight between input layer and hidden layer 1 Weight between hidden layer 1 and hidden layer 2 Weight between hidden layer 2 and hidden layer 3 Weight between hidden layer 3 and output layer 8 × 1

Backpropagation Algorithm
Section 2.1.2 introduces the way to estimated label using deep neural network. In order to optimize this estimation, a cost function J is used to quantify the difference between the estimated valueŷ and the true value y. To give a simple example, Mean Square Error [1] which is often applied to regression problems is used in this section to illustrate how the backpropagation algorithm works. Equation 2.6 shows the form of mean square error.
where x is the input data and w represent all weights used in the model. Thus, the optimization problem can be described as following Stochastic Gradient Descent (SGD) is an effective way to solve this optimization problem if J(w, x) is convex. However, it still shows acceptable results in deep neural network even though there is no guarantee for global optimal point in non-convex optimization [11]. Instead of finding the optimal point directly, SGD optimize the objective function 2.7 iteratively by following equation where η is the learning rate which can control the update speed of the weight. Using gradient methods such as SGD to optimize the cost function in neural network is called backpropagation algorithm. Considering the deep neural network shown in 2.3 and the techniques of matrix calculus [13], the gradient of J with respect to W 4 is where is element-wise matrix multiplication and ∇f 4 (z 4 ) is the gradient with respect to z 4 . Results for other W i can be calculated in a similar way. With equation 2.8, W i can be updated during each iteration by

Convolutional Neural Network
Compared with a common deep neural network, a convolutional neural network has two extra components which are convolutional layer and pooling layer. The convolutional layers make use of several trainable filters to select different features. The pooling layer reduces the dimension of the data by subsampling.
In the convolution layer, the output of the last layer is convolved by trainable filters with element-wise matrix multiplication. The size and the number of each filter are defined by the user and the initial value is randomly generated. The moving step of a filter in each convolution layer is decided by stride. In order to keep the information of the border during the forward propagation, a series of zeros attached to the border of the image called padding. Figure 2.4 shows how the result of one neuron in a convolution layer comes from and how the filter (x, y, z, w) will be updated in every iteration in backpropagation. The reason for using a pooling layer is not only for dimension reduction but also for detecting invariant features including translation, rotation, scale from the input [37]. There are two types of operations in pooling layer: max pooling and average pooling. In max pooling, only the maximum value in user-defined windows will be chosen while all values in the window will make contributions to the output in average pooling. The choice of operation is dependent on tasks and Boureau has made a theoretical comparison between those two [6]. Both max and average operation are shown in Figure 2.5. A complete convolutional neural network consists of several convolutional layers, pooling layers, and fully connected layers. The fully connected layer is the same concept of DNN which used the flatten vector of the last output of the other two layers as input. Considering a classification problem as shown in Figure 2.6, an image with a size of 64 × 64 is fed into CNN and output a scalar which represents its class. The backpropagation algorithm in convolutional neural network is a little different from described in section 2.1.3 because of two extra layer type. In average pooling layer, the error will be divided by t × t which is the size of the filter and propagate to the last layer. In max pooling layer, the position of the maximum value will be stored when forward propagating and the error will be directly passed through that position. In convolutional layer, backpropagation can be calculated through basic differentiation. Consider the convolution operation in Figure 2 is the output matrix in Figure 2.4. The differentiation of δ with respect to y, z, w can be computed in a similar way.

Batch Normalization
With the increasing depth of the neural network, the training time becomes longer. One of the reason is the distribution of input in each layer changes when updating the weight which is called Internal Covariate Shift. In 2015, Ioffe proposed Batch Normalization (BN) which make the distribution in each layer more stable and achieve shorter training time [15]. In each neuron, the input can be normalized by Equation 2.13 Var[x] + (2.13) where is used to avoid zero variance. Now data in each neuron follow the distribution with mean 0 and standard deviation 1. However, this changes the representation ability of the network which may lead to the loss of information in the earlier layer. Therefore, Ioffe used another linear transformation to restore that representatioñ where m and n are learnable parameters, especially, the result is the same as original when m = Var[x] and n = E[x]. The mean and variance during training will be stored and will be treated as the mean of the variance of test data. In their experiment, BN can not only deal with Internal Covariate Shift problems but also mitigate vanishing gradient problems.

Reinforcement Learning
Reinforcement Learning (RL) is a class of machine learning aiming at maximum the reward signal when making decisions. The basic component of reinforcement learning is the agent and the environment. As shown in Figure 2.7, the agent will receive feedback including observation and reward from the environment after each action. To generate a better policy, it will keep interacting with the environment and improve its decision-making ability step by step until the policy converges.

History of Reinforcement Learning
In recent years, reinforcement learning becomes popular because of Alpha Go, a program that can beat human expert in Go [40]. In the Future of Go Summit 2017, Alpha Go Master shocked the world by winning all three games against Ke Jie, the world best player in Go. But the research of reinforcement learning started very early. According to Sutton, the early history of RL can be divided into two main threads [43].
One of them was optimal control. To cope with arising optimal control problems which were called "multi-stage decision processed" in 1954, the theory Dynamic Programming (DP) was introduced by Bellman [5]. In the theory, he proposed the concept of "functional equation", which was often called the Bellman equation today. Although DP was one of the most effective approaches to solve optimal control problems at that time, the high computational requirements which is called "the curse of dimensionality" by Bellman were not easy to solve [4]. Three years later, he built a model called Markov Decision Processes (MDPs) to describe a kind of discrete deterministic processes [3]. This deterministic system and the concept of value function which is described in the Bellman equation consists of the basic theory of modern reinforcement learning.
In optimal control thread, solving problems required full knowledge of the environment and it was not a feasible way to deal with most problems in the real world. The trial-and-error thread focused more on the feedback rather than the environment itself. The first expression about the key idea of trail-and-error including "selectional" and "associative" called "Law of Effect" was written in Edward Thorndike's book "Animal Intelligence" [47]. Although supervised learning was not "selectional", some researchers still mistook it for reinforcement learning and concentrated on pattern recognition [8,55]. This led to rare researches in actual trial-and-error learning until Klopf recognized the difference between supervised learning and RL: the motivation to gain more rewards from the environment [16,17]. However, there were still some remarkable works such as the reinforcement learning rule called "selective bootstrap adaptation" by Widrwo in 1973 [54].
Both of two threads came across in modern reinforcement learning. Temporal Difference (TD) learning was a method that predicts future values depend on the current signal which originated from animal learning psychology. This idea was first proposed and implemented by Samuel [35]. In 1972, Klopf developed the idea of "generalized reinforcement" and linked the trial-and-error learning with animal learning psychology [16]. In 1983, Sutton developed and implemented the actor-critic architecture in trial-and-error learning based on the idea from Klopf [2]. Five years later, he proposed TD(λ) algorithms which used additional step information for update policy and made TD learning a general prediction method for deterministic problems [42]. One year later, Chris used optimal control methods to solve temporal-difference problems and developed the Q-learning algorithm which estimated delayed reward by action value function [53]. In 1994, an online Q-learning was proposed by Rummery and Niranjan which was known as SARSA [34]. The difference between Q-learning and SARSA was that the agent used the same policy during the learning process in SARSA while it always chooses the best action based on value function in Q-learning.
With the development of the deep neural network, DeepMind proposed Deep Q-learning Network (DQN) algorithm which used a convolutional neural network to solve high dimensionality of the state in reinforcement learning problems [27]. Two years later, they modified DQN by adding a target policy to improve its stability [28]. The highlight of the DQN was not only the combination of deep learning and RL but also the experience replay mechanism.
To solve dependency problems when optimizing CNN, Mnih et al. stored the experiences to memory in each step and randomly sampled a mini-batch to optimize the neural network based on the idea from Lin [22]. In 2015, this mechanism was improved by measuring the importance of experience with temporal difference error [36]. Meanwhile, Wang proposed Dueling DQN which used an advantage function learning how valuable a state was without estimating each action value for each state [52]. This new neural network architecture was helpful when there was no strong relationship between actions and the environment. In 2016, DeepMind proposed Double DQN which show the higher stability of the policy by reducing overestimated action values [50].
Although a series of algorithms based on DQN show human-level performance on Atari games, they still failed to deal with some specific games. DQN was a value-based method which meant the choice of action was depend on the action values. However, choosing action randomly may be the best policy in some games such as Rock−paper−scissors. To deal with this problem, Sutton proposed policy gradient which enabled the agent to optimize the policy directly [44]. Based on this, OpenAI proposed a new family of algorithms such as Proximal Policy Optimization (PPO) [38]. PPO used a statistical method called importance sampling which was used to estimate a distribution by sampling data from another distribution and this simple modification show a better performance in RoboschoolHumanoidFlagrun.
Since the basic policy gradient method sampled data from completed episodes, the variance of the estimation was high because of the high dimension action space. Similar to valuebased method, Actor-critic method was proposed to solve this problem [18]. Compared with the policy gradient, this method used a critic to evaluate the chosen action. This made the policy can be updated after each decision which not only reduced the variance but also accelerated the convergence. The famous improved actor-critic based algorithm is asynchronous advantage actor-critic (A3C) [26]. Similar to Dueling DQN, this method used advantage function to estimate value function and performed computing in parallel which can largely increase the learning speed.

Markov Decision Processes
As mentioned in Section 2.2.1, the interaction between the agent and the environment can be modeled as a Markov Decision Process which is based on Markov property. Markov property describes a kind of stochastic processes that the probability of next event occurring only depend on the current event.
Definition 1 (Markov property [39]) Given a state S t+1 at time t+1 in a finite sequence To describe how the decision is made, a policy π is required to define the behaviour of the agent.

Definition 3 (Policy [39])
A policy is a distribution over actions given states In MDP, the agent is expected to get as many rewards as it can from the environment. However, maximizing the reward at time-step t makes the agent short-sighted which means it only considers the reward from the next action rather the total reward of one episode. Therefore, return is defined as the concept "reward" which the agent is expected to maximize.
Definition 4 (Return [39]) The return G t is the total discounted reward R t from time-step t.
The value of the discount factor represents how far-sighted the agent will be. If this value is 1, the agent will treat every reward in the future as the same. But this will also make the agent confused about which decision is not appropriate. At this point, the behavior of the agent can be described as in Figure 2.8 Since the return is defined in a random process, similar to reward function, the expectation of it can be defined as following which is also called value function.

Definition 5 (State Value Function [39])
The state-value function v π (s) of an MDP is the expected return starting from state s, and then following policy Definition 6 (Action Value Function [39]) The action-value function q π (s, a) is the expected return starting from state s, taking action a, and then following policy π With the Definition 5, 6 and the definition of the expectation, we can simply write v π (s) = a∈A π(a|s)q π (s, a) where A is a set of action the agent can choose.

Bellman Equation
Since we define the Markov decision process in Section 2.2.2, the behavior of the agent can be described mathematically. As mentioned in Section 2.2.1, this problem can be solved by the Bellman equation.
Theorem 1 (Bellman Expectation Equation [39]) The state-value function can be decomposed into immediate reward plus discounted value of successor state The action-value function can similarly be decomposed Here is a simple proof for Equation 2.24. According to the Definition 4, the return at time t can be decomposed into two parts: the immediate reward and the discounted return at time Due to the linearity of expectation, G t+1 can be replaced by q π (S t+1 , A t+1 ) and then we obtain the Bellman equation for action-value function. The state-value function can be proved in the same way. With the definition of optimal value function Definition 7 (Optimal Value Function [39]) The optimal state-value function v * (s) is the maximum value function over all policies The optimal action-value function q * (s, a) is the maximum action-value function over all policies q * (s, a) = max π q π (s, a) (2.28)

Theorem 1 can be extended to Bellman optimality equation
Theorem 2 (Bellman Optimality Equation [39]) The optimal state-value function can be decomposed into maximum immediate reward plus discounted optimal value of successor The optimal action-value function can similarly be decomposed Here is a simple proof for It is easy to prove that there is always an optimal policy for any Markov decision process and it can be found by maximizing action-value function.

Exploitation vs Exploration
If the agent has complete knowledge of the environment, in the other word, the transition probability P a ss can be calculated given state s and action a, Equation 2.30 can be solved by an iterative method with appropriate γ. However, this method is unable to deal with an unknown environment because a large amount of information has to be collected to estimate P a ss before the convergence of action value function. If the q function tends to be stable before the environment has been fully explored, the performance of the model would be far from satisfactory, especially in high action space situation.
To deal with this problem, -greedy selection [43] is introduced to ensure the agent make enough exploration before the convergence of the action value function. Instead of choosing the best action estimated by q function, there is a probability of to randomly select from all actions. The mathematical expression of this method is shown as following where m is the number of actions. This method may have a bad effect on the performance of the agent at first several episodes during the training but it can widen the horizon of the agent in long term view.

Temporal Difference Learning
As mentioned in Section 2.2.4, most environment in the real world is unknown. To solve this problem, a method called Monte Carlo (MC) is used to sample data for estimating value function. The agent can learn the environment from one episode experience and the value function can be approximated by the mean of the return instead of the expectation. The mathematical expression can be described as following where S t is the state at time t, S(S t ) is the sum of return and N (S t ) is the counter to record the visit number of state S t . There are two kinds of visit: first visit and every visit. The former one means the model only need to record the first visit of state S t in one episode while all visit of S t in one episode will be taken into consideration in every visit. Simplify equation 2.38, we can get the recurrence equation where η is the learning rate which can control the update speed of the value function and s is the state at time t. where s and a is the state and action at time t, s and a is the state and action at time t + 1. Equation 2.41 shows an iterative method to get the optimal action value function q * (s, a).
With this equation and -greedy policy, the RL problem can be solved by Sarsa [34]. choose action a 0 following -greedy policy from q(s, a)
Algorithm 2 Q learning 1: set learning rate α, number of episodes N , explore rate , discount factor γ 2: set q(s, a) ← 0, ∀s, a 3: for episode ← 1 to N do 4: initialize time t ← 0 5: get state s 0 from the environment 6: while episode is incomplete do 7: choose action a t following -greedy policy from q(s, a) 8: take action and get next state s t+1 , reward r t+1 from the environment 9: update q(s t , a t ) ← q(s t , a t ) + α r t+1 + γ max a q(s t+1 , a) − q(s t , a t ) 10: end while 12: end for In algorithm 2, there are two policies during the iteration. When choosing the action a t+1 from q(s, a) given s t+1 , Sarsa uses -greedy policy while Q learning uses greedy policy. But both of them are choosing a t with -greedy policy. Considering the example of Cliff Walking shown in Figure 2.9 from Sutton's book [43], every transition in the environment will get −1 reward except next state is the cliff which the agent will get −100 reward, Sarsa is more likely to choose the safe path while Q learning tends to choose the optimal path with -greedy policy. But both of them can reach the optimal policy if reducing the value of .

Deep Q Network
Q learning is a powerful algorithm to solve simple reinforcement problems. However, it is unable to deal with continuous states or continuous actions. To solve the former problem, deep learning method can be used to approximate action value function.
Generally, states are image data observed by the agent and convolutional neural network is an effective way to extract features from this kind of data in convolution layers and feed them into the fully connected layer to approximate q function. Several consistent stationary images will be stacked into one input data to make the model understand that the agent is moving. But the input data is highly dependent, the performance of the model will be largely affected by the dependency.
As mentioned in Section 2.2.1, DeepMind introduced experience replay pool which will store the experience into the memory and sample some of them to optimize the neural network model in 2013 [27]. Using Q learning, deep learning and experience replay pool, the improved algorithm named Deep Q Network (DQN) shows incredible performance on Atari games according to their paper. Two years later, they found the agent became more stable by using two network [28]. This algorithm can be described as below All states in Algorithm 3 have to be pre-processed before feeding into a neural network model. Based on Deep Q Network, there are three kinds of improved algorithms considering the stability of the training process, the importance of each experience and new neural network architecture. Double DQN [50] utilizes the advantage of two networks. Instead of finding the optimal q value from target network q (s, a) directly, this method chooses the optimal action from the policy network and find the corresponding q value in the target network. Use the term in Algorithm 3, the change can be illustrated as following Algorithm 3 Deep Q Network 1: initialize policy network q(s, a) with random weights 2: set learning rate α, number of episodes N , explore rate , discount factor γ 3: set batch size M , update step T 4: set target network q (s, a) = q(s, a) 5: for episode ← 1 to N do 6: initialize time t ← 0 7: get state s 0 from the environment 8: while episode is incomplete do 9: choose action a t following -greedy policy from policy network q(s, a) 10: take action and get next state s t+1 , reward r t+1 from the environment 11: store transition (s t , a t , s t+1 , r t+1 ) in experience replay pool 12: random sample M batch experience (s k , a k , s k+1 , r k+1 ) from the pool 13: calculate corresponding q(s k , a k ) from policy network q(s, a) 14: calculate y k using target network q (s, a) y k = r k+1 if next state is completed r k+1 + γ max a q (s k+1 , a) otherwise 15: optimize the policy model with gradient (y k − q(s k , a k )) 2

16:
replace target network with policy network when reach the update step T 17: end while 19: end for y k = r k+1 if next state is completed r k+1 + γq (s k+1 , arg max a q(s k+1 , a)) otherwise (2.42) Prioritized Experience Replay (PER) introduced a way to efficiently sample transitions from the experience replay pool [36]. Instead of uniform random sampling, there is a priority of each transition where p i > 0 is the priority of transition i and α is the indicator of the priority, especially α = 0 when using uniform random sampling. The priority can be measured by TD error δ i , which is the following term Based on TD error, p(i) can be calculated in two way. The first is proportional prioritization which uses the absolute value of TD error where is to avoid zero prioritization. The other one is rank-based where rank(i) is the rank of transition by sorting TD error δ i . According to Schaul, both proportional based and rank based prioritization can speed-up the training but the later one is more robust which has better performance when meeting outliers.
However, the random sampling is abandoned after adding priority mechanism which will result in high bias. In other words, those transitions with small TD error are unlikely to be sampled and the distribution is changed. Therefore, the final model may far from the optimal policy and performance of the agent even be lower than DQN. Important sampling (IS) [29] is an effective technique to estimate a distribution by sample data from a different distribution. Given a probability density function p(x) over distribution D, with the definition of the expectation where E p [·] denotes the expectation for x ∼ p and f is the integrand. Given another probability density function q(x), the expectation can be written as following where E q [·] denotes the expectation for x ∼ q. With Monte Carlo integration, the expectation E p [f (x)] can be estimated by where i is sampled from x. if p(i) is uniform distribution and q(i) refers to Equation 2.43, we have adding a tunable parameter β, we obtain the importance-sampling weights where β will decay from a user-defined initial value to 1 and the bias completely disappears when β = 1. Term max i w i is used to normalize the weight to increase stability. Use the term in Algorithm 3, the update of q function can be modified as following where δ k is TD error and η is learning rate.
Dueling DQN architecture used a new concept called advantage function which is the subtraction of the action value function and state value function [52].
A π (s, a) = q π (s, a) − v π (s) (2.53) As shown in Figure 2.10, dueling network architecture use summation of two steams which is advantage function and state value function to get the q function. The state values can be updated more accurately with this method. Chapter 3

Methodology
This chapter gives the requirements of the project, introduces the design of reward function and shows the preprocessing steps of the input image. The choice of the model, as well as the architecture, will be discussed. Experiment design and evaluation methods will be illustrated in the last.

Software Requirement
Considering the readability of the code, widely used additional frameworks such as Torch, Python is a suitable choice for this project. OpenCV is used to preprocess the image getting from the environment. Numpy is a Python library which accelerates matrices operations with C. This enables the user to write efficient scientific computing code with Python. There are plenty of deep learning frameworks like Tensorflow which has many extensive API and is widely used in industrial products. However, it will take a relatively long time for the beginner to fully understand the usage of Tensorflow. Pytorch is a recently developed framework which is described as "Numpy with GPU". The simplicity of Pytorch makes more and more academic researchers using it to implement their new ideas in a much easier way. Because T-rex Runner is running on Chrome, the latest Chrome is used here. Gym is a game library developed by OpenAI [7]. This framework provides a built-in environment for some famous games such as Atari 2600 and it is easy for the user to customize their own environment. Table 3.1 shows all software requirement in this project.

Hardware Requirement
As the game is running on Chrome, it is hard to use a Linux server to perform the experiments.
Although headless Chrome is a plausible choice, there are some environmental issues during the investigation. Therefore, all experiments will be running on the laptop from the author. There will be some limitation such as 6GB GPU memory limits the size of experience replay  pool. Therefore, parameters related to hardware limitation will be suitably chosen without tuning in this project.

Game Description
T-rex Runner is a dinosaur game from Google Chrome offline mode. Everyone can access this link on Chrome to play the game. The target for players is to control the dinosaur overcoming as many obstacles as possible. The current score of the game will increase by time if the dinosaur keeps alive as shown at the top right corner of Figure 3.1 as well as the highest score. As shown in Figure 3.2, the dinosaur has three actions to choose in every state: do nothing, jump or duck. Environment plays an important role in reinforcement learning because the agent will improve the policy based on the feedback from it. However, it is difficult to quantify the rewards for each action as well as the return for an entire episode. In most research for RL algorithms, modifying reward will not be taken into consideration but it will significantly impact the  For example, shaping reward shows a better performance in Andrew's experiment [30]. It adds a new term F to modify the original reward based on the goal The closer the agent towards the goal, the larger the F is. However, the aim of this project is to train the agent to play the game and compare the performance between different algorithms. So the effect of reward function will not be taken into consideration and a fixed reward function will be used across all experiments.
Since there is no previous study on T-rex Runner with reinforcement learning, the design of reward function is a hard part of this project. Intuitively, the best design is awarding the agent for jumping over the obstacles and penalizing it for hitting the obstacles. The jumping reward will gradually increase as time goes by. However, object detection in moving pictures is required to fulfill this goal. As this task is out of the requirements of this project, we proposed a naive reward design as shown in Algorithm 4. The basic idea of Algorithm 4 is giving a relatively small reward to the agent if it is alive and penalize it when hitting an obstacle. Zero reward for jumping is set to make the dinosaur only jumps if it is very close to obstacles. The unexpected jump will limit the movement in the next few states.

Algorithm 4 Reward Design in T-rex Runner
Although there are three kinds of action in this game as introduced in Section 3.2, duck is optional because the agent can overcome the obstacle using jump under the same circumstances. Considering most obstacles in the game are cactus which can only be overcome by jumping, only two actions (do nothing and jump) will be used in this investigation.

Model Selection
Since there are only two actions in T-rex Runner, according to the literature review on deep reinforcement learning in Section 2.2.1, value-based methods are proved to be powerful to handle this game. Although policy-based methods such as proximal policy gradient is a good choice too, only DQN, double DQN, DQN with prioritized experience replay and dueling DQN will be investigated in this project due to the time limitation.
Deep Q network which is shown in Algorithm 3 is a basic reinforcement learning algorithm using deep learning. According to the result from DeepMind, it is expected to achieve at least human-level results with only DQN.
Double DQN mitigates the q value overestimation problems utilizing two advantage of two networks as shown in Equation 2.42 but it is not expected to achieve a higher performance in this experiment because there is only two actions. The bad effect of overestimation problems is not obvious under this circumstance.
Dueling DQN adds an advantage function which is the subtraction of action value function and state value function before the output layer in the convolutional neural network as shown in Equation 2.53. Since the evaluated game in [52] is a similar racing game overcoming obstacles compared with T-rex Runner, this algorithm is expected to have a better performance than DQN.
Prioritized Experience replay improves training efficiency by changing the distribution of the stored transitions. It assigns the weight for each experience by TD error. There are two ways to calculate prioritization which is proportional based method and rank-based method. According to the [36], the former one has a relatively better performance, only this method will be implemented in this investigation due to the time limitation. The performance is expected to be the same as DQN because there is no change in the algorithm but it may be faster to reach the same performance.

Image Preprocessing
Following the preprocessing step in [27,28], the raw observed image which is in RGB representation will be converted to gray-scale representation. To make the network easier to recognize dinosaur and obstacles, unnecessary objects such as clouds and scores will be removed. In this step, the color of the background and the object are reversed in order to perform erosion and dilation. These two basic morphological operations can help reduce small bright color which is often noisy data. Finally, the image is resized to 84 × 84 following the recipe from DeepMind. Since the movement should be recognized by the neural network, perform the same preprocessing step for last four frames in the history and stack those four as one data point which is also the input of CNN. The entire process is shown in Figure 3.3.

Convolutional Neural Network Architecture
There are two kinds of convolutional neural network used in this project. The basic DQN is proposed in [27,28] which used three convolutional layers and two fully connected layers. The reason for not using pooling layer is to detect the movement of the agent. Both max pooling and average pooling may make the neural network ignore a very small change in the image. Therefore, there are only convolutional layers in this architecture. The architecture for training the agent using DQN is shown in Figure 3 Dueling architecture is proposed in [52] which divided the q network into two parts. One of them is only related to the state value function v(s), the other one is advantage function A(s, a) which is affected by both state and action. The final action value function is the summation of those two.
q(s, a; θ, ω 1 , ω 2 ) = v(s; θ, ω 1 ) + A(s, a; θ, ω 2 ) (3.2) where θ is the shared parameter of CNN, ω 1 is the value function only parameter and ω 2 is the advantage function only parameter. Both DQN and Dueling DQN are using Algorithm 3, the only difference is the neural network architecture. RMSprop [48] which is an adaptive gradient method based on stochastic gradient descent will be used as the optimization algorithm in this project. This is the same optimization method used by DeepMind [27,28]. Figure 3.5 shows the process of dueling DQN.

Hyperparameter Tuning
Before the comparison of algorithms, hyperparameter tuning is required to get high-performance models. As mentioned before, the memory size is fixed to 3 × 10 5 due to the hardware limitation. Because there is no previous study on this game, and the hyperparameters list in [28] have a bad result on this game. All other hyperparameters have to be set to a suitable value. Grid search is performed to find a workable combination of those parameters.
Due to the time limitation, all parameters will only be slightly modified and only one hyperparameter will vary during each tuning experiment. The choice of the parameter will consider both score and stability. Each parameter will be tuned with 800 episodes.

Comparison of different Deep Q Network Algorithms
There are three improved reinforcement algorithms based on DQN mentioned in Section 2.2.6. Double DQN makes the performance of the agent more stable by solving the overestimated q value problem. Prioritized experience replay improves the training efficiency by sample more valuable transitions. Dueling DQN modifies the neural network architecture to get a better estimation of state values.
In this experiment, DQN will be first used to train the agent based on the hyperparameters tuned in Section 3.6.1 and this result will be treated as a baseline across all the experiments. Double DQN, DQN with prioritized experience replay and Dueling DQN will be applied to the agent separately. The performance of those three is expected to be better than DQN according to the related papers. Due to time limitation, no combination of those three algorithms will be performed in this project. This section only compares the performance of each algorithm.

Effect of Batch Normalization
As mentioned in Section 2.1.5, it is proved that batch normalization can reduce training time and mitigate the vanishing gradient problem in a convolutional neural network. However, there is no evidence that this method has the same effect on reinforcement learning. This section will perform experiments on this point. Based on the experiment in Section 3.6.2, adding batch normalization in each convolutional layer and compared with the results with the outcome in previous experiments.

Evaluation
To evaluate the performance of the agent, DeepMind used trained agent playing the game for 30 times for up to 5 min and -greedy policy with = 0.05 [28]. Considering only one game is investigated in this project, the average score will be used instead of average reward because the number of jumps in each episode will affect the total reward according to the designed reward function. The greedy policy will be used in the evaluation stage instead of -greedy policy because the later one will bring randomness to the decision which will affect the performance of the trained model. Therefore, the trained agent will play the game for 30 times without time limitation and using greedy policy. All outcomes will be compared with the results from a human expert.
The average scores during the training stage will be shown graphically. This is a clear way to show the learning efficiency of each algorithm. Both graphical and statistical results such as mean, variance and median will be analyzed. However, only statistical results will be analyzed in the testing stage because the trained model for each algorithm are the same and there is no increasing trend can be shown like in the training stage. These results will be visualized with a boxplot.

Hyper Parameter Tuning
The value of hyperparameters may affect the performance of the model. However, there are so many parameters in reinforcement learning including optimization algorithm parameters such as learning rate. This may take a long time to find the optimal combination of these parameters using a grid search. Since there is no metric like accuracy in RL which can easily reflect the performance of the model, we assume each parameter is independent of others. Therefore, each parameter can be tuned one after another. Because the objective of this project is to compare the performance between different algorithms and the effect of batch normalization, those tuned parameters by DQN will be used across all the experiments. The start hyperparameters of DQN are shown in    score unstable after 50th epoch. Considering the stability and 200 epochs will be trained in formal experiment, 2 × 10 −5 will be chosen as learning rate.

Batch Size
Batch size defines how many transitions will be used to update the neural network which may affect the training speed. But as mentioned in 2.2.1, too big size will cause the dependency problems which may largely affect the performance of the model. As shown in Figure 4.2, the average score of three curves at epoch 80 are all around 800. Among those three, the most stable one is batch size 128.

Epsilon
-greedy policy determines the probability of exploration. In some games, especially with high action spaces, this value can affect how good the model will converge. However, there are only two actions in T-rex Runner so it is unnecessary to random choose action at the begin. Instead of initializing to 1 as DeepMind did in their paper [28], the start value is set to 0.1 in this model. All experiments achieve acceptable results in Figure 4.3 except the one with fixed = 0.1. In this case, we select from 0.1 to 0.0001 but either of those three can be chosen according to this graph. This experiment also demonstrates the positive effect of linear annealing for .

Explore Step
Explore step is the number of steps required to anneal from 0.1 to 0.0001. As mentioned that hyperparameters related to exploration will not affect too much in this game. The most stable one will be selected from Figure 4.4 which is 1 × 10 5 .

Gamma
Discount factor decides how far-sighted the agent will be. Too small value will make the agent consider more about the current reward and too big value will make the agent pay the same attention to rewards after this time point. This may confuse the agent about which action leads to a high or low return.

Training Results
The tuned hyperparameters from the previous experiment are listed in Table 4   A gradually increased average score can be seen from this graph. This not only proves that the agent can play the game through DQN but also shows that the design of the reward function is relatively reasonable. This result will be treated as a baseline and will be used to compare with other algorithms.

Double DQN
Double DQN has a similar performance in training compared with DQN. As mentioned before, the effect of q overestimation is not so significant in T-rex Runner because there are only two actions. As shown in Figure 4.7, there are four data points with average scores below 200 while all average scores are above this value in DQN.

Dueling DQN
Surprisingly, dueling DQN shows an incredible training performance after 150th epoch while the curve before that time seems similar. In Figure 4.8, the average score is above 5000 which is ten times higher than the maximum average score in DQN. However, these scores have a high variance which fluctuates widely between 1000 and 5000. From the graph, the training process of dueling DQN is stable before 150th epoch and end up with an increasing trend.
Since we tuned all hyperparameters based on DQN, these values may not be the best for dueling network which results in the stable and relatively low average scores before 150th epoch.

DQN with Prioritized Experience Replay
Another important finding in this section is the performance of prioritized experience replay. This is expected to have a shorter training time and a higher performance compared with DQN. But the result shown in Figure 4.9 suggests that the agent failed to learn to play the game with this method. There are two reasons for that. One problem is from the algorithm. Compared with DQN, there are two extra steps have been applied to PER: weight calculation and prioritization update. Following the implementation in [36], sum tree which is a data structure with time complexity O(log N ) for sampling and updating is used to store transitions instead of a linear list to accelerate memory related manipulation. The training time of PER is twice more than the one of DQN because of the batch size. Since we know that all sampled transitions will be traversed when updating the prioritization, the larger batch size is the longer time is required to perform this operation. Table 4.3 shows that this process is very time-consuming even using the batch size 32. These data are extracted from the training results choosing the same score of 43. The step size is the average value from ten records.  The other problem is from the game. Because this game is based on Chrome, it continues running when performing optimization while the game from official OpenAI Gym is paused during this operation. Therefore, there is a delayed time before sending the action to Chrome. This influence is enlarged in prioritized experience replay since the time for update operation with batch size 128 takes approximately 10 times longer than normal DQN.

Algorithm
Change the choice of hyperparameter can mitigate the first problem but the result is not as good as other algorithms. One thing we can expect is PER is unable to help the agent to get a higher score under this circumstance because the game speed will increase as time goes by. Since the time for updating the prioritization will not change too much, the time interval between two consistent decisions will be longer. This may limit the performance of the model. To eliminate the high computational effect from updating prioritization, the best way is to redevelop the game but due to the time limitation and the primary objective of this study, this result will be used as we can still compare the effect of batch normalization on this algorithm.

Batch Normalization
Since the aim of this experiment is to find how batch normalization affects DQN algorithms, each result will be compared with the one without batch normalization which is shown in Figure 4.10. From Figure 4.10, we can see that batch normalization can increase the mean of average scores in all experiments. But this also brings high variance which makes the average score diverge. According to the top-left graph, the first time for DQN agent to reach the average 1000 is approximately 150th epoch while the agent using DQN with batch normalization reach the same average score at 60th epoch and it is easy for it to get the higher score after that time. Double DQN curve has a similar trend but batch normalization in both of them also result in wide fluctuation. It is hard to say whether dueling network benefits from the batch normalization because there is a significant increase trend on the bottom left graph. However, it is still can be seen that BN enable the agent to reach the same performance much earlier from 20th epoch to 90th epoch. For DQN with prioritized experience replay, even the performance is limited by the game itself, the one with batch normalization still can get a relatively higher score.

Further Discussion
As graphical results and some explanation of them are shown above, this part will discuss numerical results from the experiments. Table 4.4 shows some statistical data fro training process. The maximum score is pointless in most games but considering T-rex Runner is a racing game, we still include this in the  Ignoring the result from prioritized experience replay because of the inappropriate game environment, all algorithms achieve great results according to Table 4.4. Two algorithms with dueling network stand out from them. The one with batch normalization has the mean over 1000 which is 200 more than the one without BN. But the later one got the maximum score of 25706 which means the agent can keep running for around half an hour in one episode. However, both of them have high variance which exceed the mean.
Double DQN both with BN and without BN perform worse than DQN. This indicates that double DQN may reduce the performance in low dimension action space. But batch normalization shortens the gap between those two algorithms which can be seen from the median and 75% percentile.
Although most of statistical metrics are improved by batch normalization, the variance is much higher than before. As shown in the table, the variance from DQN with BN is twice more than the one without BN. Only the variance from dueling network is lower after BN. But it is reasonable because there is an incredible increase in the very later stage of the training shown in Figure 4.10.

Testing Results
After training the agent for 2000 episodes, we use the latest model with greedy policy and play T-rex Runner for 30 times with each algorithm. Figure 4.11 shows the boxplot of those results as well as the collected data from the human expert. It is obvious that the agent trained by DQN with prioritized experience replay fail to learn to play the game because of the game environment issue discussed in the last section. It is surprising that the performance of double DQN is far from satisfactory even though it has similar training results compared with DQN. Table 4.5 shows that the mean of DQN results is three times higher than the one from double DQN. Dueling DQN algorithm achieves the highest score even though it still has the highest variance which is three times more than the variance from DQN. According to Table 4.5, batch normalization improves the performance of the model regardless of algorithms and even the mean of DQN with PER is increased. However, it is not easy to say the effect of BN in dueling DQN is positive or not. From Figure 4.11, the one without BN has more outliers which results in high variance even though its mean is higher. Consider the median which is not sensitive with the outlier data, the one with BN is better and the minimum score is more than 200 which stands out from other algorithms. Since score 43 indicates the first time the agent meets the obstacle, it is easy to infer that all trained model fails to jump over the first cacti at least once except dueling DQN with BN. But dueling DQN is not fully trained which can be seen from the training result in Figure 4.8. That's also one reason for high variance as we can see in the boxplot. The agent trained with dueling DQN achieved over 8000 at least three times.

Conclusions and Future Works
The project aims to create an agent trained by four types of algorithms to play T-rex Runner and investigate the influence of batch normalization in reinforcement learning.
The former aim is reached except the prioritized experience replay due to the game environment issue. However, all other algorithms are successfully implemented and achieve great results, especially DQN and dueling DQN. Both of them can achieve better results than human experts. Batch normalization has shown relatively positive effects for all DQN algorithms in this project despite the unstable average score in the training stage.
In further studies, the game environment should be first redeveloped to add a pause function when the neural network is calculating q values or doing optimization. Prioritized experience replay can be tested after that. In this project, only the proportional based method has been implemented, so rank-based prioritization can also be investigated in the future. Further combination of algorithms can be developed such as dueling DQN with prioritized experience replay. Policy-based algorithms such as PPO can also be implemented to train the agent.
There is one interesting idea which has not been implemented yet. Considering the moving speed of the obstacles are gradually increasing, we can divide the game into several stages. Each stage has a neural network which is initialized by the previous stage and will be trained independently. The intuition of this idea is that the consequence of jumping will change when the agent is running in different stages. This may also be one of the reasons for a high variance because when the agent has learned how to get a better score in the later stage, it forgets the best policy in the early stage.