# Embedding-based Retrieval in Facebook Search

Jui-Ting Huang<EMAIL_ADDRESS>Facebook Inc. ,  Ashish Sharma
<EMAIL_ADDRESS>Facebook Inc. ,  Shuying Sun<EMAIL_ADDRESS>Facebook
Inc. ,  Li Xia<EMAIL_ADDRESS>Facebook Inc. ,  David Zhang<EMAIL_ADDRESS>Facebook Inc. ,  Philip Pronin<EMAIL_ADDRESS>Facebook Inc. ,  Janani
Padmanabhan<EMAIL_ADDRESS>Facebook Inc. ,  Giuseppe Ottaviano<EMAIL_ADDRESS>Facebook Inc. and  Linjun Yang<EMAIL_ADDRESS>Microsoft

(2020)

###### Abstract.

Search in social networks such as Facebook poses different challenges than in
classical web search: besides the query text, it is important to take into
account the searcher’s context to provide relevant results. Their social graph
is an integral part of this context and is a unique aspect of Facebook search.
While embedding-based retrieval (EBR) has been applied in web search engines
for years, Facebook search was still mainly based on a Boolean matching model.
In this paper, we discuss the techniques for applying EBR to a Facebook Search
system. We introduce the unified embedding framework developed to model
semantic embeddings for personalized search, and the system to serve
embedding-based retrieval in a typical search system based on an inverted
index. We discuss various tricks and experiences on end-to-end optimization of
the whole system, including ANN parameter tuning and full-stack optimization.
Finally, we present our progress on two selected advanced topics about
modeling. We evaluated EBR on verticals111In Facebook search, verticals are
based on result types, e.g., people, page, group, etc. for Facebook Search
with significant metrics gains observed in online A/B experiments. We believe
this paper will provide useful insights and experiences to help people on
developing embedding-based retrieval systems in search engines.

Embedding, deep learning, search, information retrieval

††journalyear: 2020††copyright: rightsretained††conference: Proceedings of the
26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; August
23–27, 2020; Virtual Event, CA, USA††booktitle: Proceedings of the 26th ACM
SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’20), August
23–27, 2020, Virtual Event, CA, USA††doi: 10.1145/3394486.3403305††isbn:
978-1-4503-7998-4/20/08††ccs: Information systems Retrieval models and
ranking††ccs: Information systems Search engine architectures and
scalability††ccs: Computing methodologies Learning latent representations

##  1\. Introduction

Search engines have been an important tool to help people access the huge
amount of information online. Various techniques have been developed to
improve search quality in the last decades, especially in web search engines
including Bing and Google. Since it is difficult to accurately compute the
search intent from query text and represent the semantic meaning of documents,
search techniques are mostly based on various term matching methods (Baeza-
Yates and Ribeiro-Neto, 2011), which performs well for the cases that keyword
match can address. It still remains a challenging problem for _semantic
matching_ (Li and Xu, 2014), which is to address desired results that are not
exact match of the query text but can satisfy users’ search intent.

In the last years, deep learning has made significant progress in speech
recognition, computer vision, and natural language understanding (LeCun et
al., 2015). Among them _embedding_ , which is also called _representation
learning_ , has been proven to be successful techniques contributing to the
success (Bengio et al., 2013). In essence, _embedding_ is a way to represent a
sparse vector of ids as a dense feature vector, which is also called _semantic
embedding_ in that it can often learn the semantics. Once the embeddings are
learned, it can be used as a representation of query and documents to apply in
various stages of a search engine. Due to the huge success of this technique
in other domains including computer vision and recommendation system, it has
been an active research topic in information retrieval community and search
engine industry as the next generation search technology (Mitra and Craswell,
2018).

In general, a search engine comprises a recall layer targeting to retrieve a
set of relevant documents in low latency and computational cost, usually
called _retrieval_ , and a precision layer targeting to rank the most desired
documents on the top with more complex algorithms or models, usually called
_ranking_. While embeddings can be applied to both layers, it usually has more
opportunities to leverage embeddings in the retrieval layer, since it is at
the bottom of the system which is often the bottleneck. The application of
embeddings in retrieval is called _embedding-based retrieval_ or _EBR_ for
short. Briefly, embedding-based retrieval is a technique to use embeddings to
represent query and documents, and then convert the retrieval problem into a
nearest neighbor (NN) search problem in the embedding space.

EBR is a challenging problem in search engines because of the huge scale of
data being considered. Different from ranking layers which usually takes
hundreds of documents into consideration per session, retrieval layer needs to
process billions or trillions of documents in the index of a search engine.
The huge scale imposes challenges on both training of embeddings and serving
of embeddings. Second, different from embedding-based retrieval in computer
vision tasks, search engine usually needs to incorporate both embedding-based
retrieval and term matching based retrieval together to score documents in the
retrieval layer.

Facebook search, as a social search engine, has unique challenges compared
with traditional search engines. In Facebook search, the search intent does
not only depend on query text but is also heavily influenced by the user who
is issuing the query and the context where the searcher is. Because of this,
embedding-based retrieval in Facebook search is not a text embedding problem,
as is actively researched in the IR community (Mitra and Craswell, 2018).
Instead it is a more complex problem that requires understanding of text,
user, and the context altogether.

To deploy embedding-based retrieval in Facebook search, we developed
approaches to address challenges on _modeling_ , _serving_ , and _full-stack
optimization_. In modeling, we proposed _unified embedding_ , which is a two
sided model where one side is search request comprising query text, searcher,
and context, and the other side is the document. To effectively train the
model, we developed approaches to mine training data from search log and
extract features from searcher, query, context, and documents. For fast model
iteration, we adopted a recall metric on an offline evaluation set to compare
models.

Building retrieval models for search engine has its unique challenges, such as
how to build a representative training task for models to learn effectively
and efficiently. We investigated two different directions, _hard mining_ to
address the challenge of representing and learning retrieval tasks
effectively, as well as _ensemble embedding_ to divide the model in multiple
stages where each stage has different recall and precision tradeoff.

After the model is developed, we need to develop ways to effectively and
efficiently serve the model in the retrieval stack. While it is
straightforward to build a system combining the candidates from existing
retrieval and embedding KNN, we found it is suboptimal because of several
reasons: 1) it has huge performance cost from our initial experiment; 2) there
is high maintenance cost because of dual index; 3) the two candidate sets
might have significant overlap which makes it inefficient overall. Thereafter,
we developed a hybrid retrieval framework to integrate embedding KNN and
Boolean matching together to score documents for retrieval. To this purpose,
we employed Faiss (Johnson et al., 2017) library for embedding vector
quantization and integrated it with inverted index based retrieval to build a
hybrid retrieval system. Besides addressing the above challenges, this system
has two main advantages: 1) it enables the joint optimization of embedding and
term matching to address Search retrieval problem; 2) it supports embedding
KNN constrained by term matching, which not only helps address the system
performance cost issue but also improves the precision of embedding KNN
results.

Search is a multi-stage ranking system where retrieval is the first stage,
followed by various stages of ranking and filtering models. To wholly optimize
the system to return those new good results and suppress those new bad results
in the end, we performed later-stage optimization. In particular, we
incorporated embeddings into ranking layers and built a training data feedback
loop to actively learn to identify those good and bad results from embedding-
based retrieval. Figure 1 is an illustration of embedding-based retrieval
system. We evaluated EBR on verticals for Facebook Search with significant
metrics gains observed in online A/B experiments.

Figure 1. Embedding Based Retrieval System Overview

The paper is organized as follows. We start with modeling to present our
solutions about loss function, model architecture, training data and feature
engineering in Section 2 and Section 3. Next we discuss about details on model
serving and system implementation in Section 4. We discuss the techniques we
developed on later-stage optimization to unleash the power from embedding-
based retrieval end to end in Section 5. Finally, we dedicate Section 6 to
selected topics on advanced modeling techniques, followed by conclusions in
Section 7.

##  2\. Model

We formulate the search retrieval task as a recall optimization problem.
Specifically, given a search query, its target result set
$T=\\{t_{1},t_{2},...t_{N}\\}$, and top $K$ results returned by a model,
$\\{d_{1},d_{2},...d_{K}\\}$, we want to maximize recall by the top $K$
results,

(1) $recall@K=\frac{\sum_{i=1}^{K}d_{i}\in T}{N}.$

The target results are the documents related to the given query based on
certain criteria. For example, it could be results with user clicks, or
relevant documents based on human rating.

We formulate the recall optimization as a ranking problem based on distances
computed between a query and documents. The query and documents are encoded
with a neural network model into dense vectors, on which we use cosine
similarity as the distance metric. We propose to use triplet loss (Schroff et
al., 2015) to approximate the recall objective to learn the neural network
encoder, which is also called embedding model.

While semantic embedding is commonly formulated as text embedding problem in
information retrieval, it is insufficient for Facebook search, which is a
personalized search engine that considers not only text query but also
searcher’s information as well as the context in a search task to satisfy
users’ personalized information need. Taking people search as an example,
while there might be thousands user profiles named ”John Smith” on Facebook,
the actual target person that a user searches for with query ”John Smith” is
likely to be their friends or acquaintances. To model this problem, we propose
_unified embedding_ which considers not only text but also user and context
information in deriving embeddings.

###  2.1. Evaluation Metrics

While our end goal is to deliver quality improvement end to end through online
A/B test, it is important to develop offline metrics to quickly evaluate model
quality before online experiments and isolate problems from complicated online
experiment setup. We propose to run KNN search in the whole index and then use
_recall@K_ as defined in equation 1 as the model evaluation metric. In
particular, we sampled 10000 search sessions to gather the query and target
result set pairs for the evaluation set and reported averaged _recall@K_ over
10000 sessions.

###  2.2. Loss Function

For a given triplet $(q^{(i)},d^{(i)}_{+},d^{(i)}_{-})$, where $q^{(i)}$ is a
query, $d^{(i)}_{+}$ and $d^{(i)}_{-}$ are the associated positive and
negative documents, respectively, the triplet loss is defined as

(2) $L=\sum_{i=1}^{N}\max(0,D(q^{(i)},d^{(i)}_{+})-D(q^{(i)},d^{(i)}_{-})+m),$

where $D(u,v)$ is a distance metric between vector $u$ and $v$, $m$ is the
margin enforced between positive and negative pairs, and $N$ is the total
number of triplets selected from the training set. The intuition of this loss
function is to separate the positive pair from the negative pair by a distance
margin. We found that tuning margin value is important – the optimal margin
value varies a lot across different training tasks, and different margin
values result in 5-10% KNN recall variance.

We believe that using random samples to form negative pairs for the triplet
loss can approximate the recall optimization task. The reason is as follows.
If we sample $n$ negatives for each one positive in the training data, the
model will be optimizing for recall at _top one position_ when the candidate
pool size is $n$. Assuming the actual serving candidate pool size is $N$, we
are approximately optimizing recall at top $K\approx N/n$. In Section 2.4, we
will verify this hypothesis and provide comparisons of different positive and
negative label definitions.

###  2.3. Unified Embedding Model

To learn embeddings that are optimizing the triplet loss, our model comprises
three major components: a query encoder $E_{Q}=f(Q)$ which produces a query
embedding, a document encoder $E_{D}=g(D)$ which produces a document
embedding, and a similarity function $S(E_{Q},E_{D})$ which produces a score
between query $Q$ and document $D$. An encoder is a neural network which
transforms an input into a low-dimensional dense vector, also known as
embedding. In our model, these two encoders $f(\cdot)$ and $g(\cdot)$ by
default are two separate networks but have the option of sharing part of the
parameters. As for similarity function, we choose cosine similarity as it is
one of the commonly used in embedding learning (Huang et al., 2013):

(3) $S(Q,D)=\cos(E_{Q},E_{D})=\frac{\langle E_{Q},\
E_{D}\rangle}{\|E_{Q}\|\cdot\|E_{D}\|}.$

The distance to be used in the loss function in Equation 2 is hence the cosine
distance defined as $1-\cos(E_{Q},E_{D})$.

The inputs to the encoders are what distinguishes unified embedding from
conventional text embedding model. Unified embedding encodes textual, social
and other meaningful contextual features to represent query and document,
respectively. For example, for query side we can include searcher location and
their social connections, whereas for the document side we can include
aggregated location and social clusters about a Facebook group by taking
groups search as an example.

Most of features are categorical features of high cardinality, which could be
either one-hot or multi-hot vectors. For each categorical feature, an
embedding look-up layer is inserted to learn and output its dense vector
representation before feeding into encoders. For multi-hot vectors, a weighted
combination of multiple embeddings is applied for the final feature-level
embedding. Figure 2 illustrates our unified embedding model architecture, and
we will discuss more about feature engineering in Section 3.

Figure 2. Unified Embedding Model Architecture

###  2.4. Training Data Mining

Defining positive and negative labels for a retrieval task in a search ranking
system is a non-trivial problem. Here we compared several options based on the
model recall metric. For negative, we experimented with the following two
options of negatives in our initial study, while using click as positive:

  * •

_random samples_ : for each query, we randomly sample documents from the
document pool as negatives.

  * •

_non-click impressions_ : for each query, we randomly sample those impressed
but not clicked results in the same session as negatives.

The model trained using non-click impressions as negative has significantly
worse model recall compared to using random negative: absolute 55% regression
in recall for people embedding model. We believe it is because these negatives
bias towards hard cases which might match the query in one or multiple
factors, while the majority of documents in index are easy cases which do not
match the query at all. Having all negatives being such hard negatives will
change the representativeness of the training data to the real retrieval task,
which might impose non-trivial bias to the learned embeddings.

We also experimented with different ways of mining positives and have
interesting findings as follows:

  * •

_clicks_ : it is intuitive to use clicked results as positives, since clicks
indicates users’ feedback of the result being a likely match to users’ search
intent.

  * •

_impressions_ : the idea is that we treat retrieval as an approximation to
ranker but can execute fast. Thereafter, we want to design the retrieval model
to learn to return the same set of results that will be ranked high by the
ranker. In this sense, all results shown or impressed to the users are equally
positive for retrieval model learning.

Our experimental results showed that both definitions are equally effective;
models trained using click vs impressions, given the same data volume,
resulted in similar recalls. Additionally, we experimented with augmenting
click-based training data with impression-based data, however we did not
observe additional gain over the click-based model. It showed that adding
impression data does not provide additional value, and the model does not
benefit from increased training data volume either.

Our above study suggested that using click as positive and random as negative
can provide a reasonable model performance. On top of it, we further explored
hard mining strategies to improve the model’s ability of differentiating
between similar results. We will present more details in Section 6.1.

##  3\. Feature Engineering

One of the advantages of unified embedding model is that it can incorporate
various features other than text to improve the model performance. We observed
consistently across different verticals that unified embedding is more
effective than text embedding. For example, there are +18% recall improvement
when switching from text to unified embeddings for events search, and +16%
recall improvement for groups search. The effectiveness of unified embeddings
highly depends on the success of identifying and crafting informative
features. Table 1 shows the incremental improvement by adding each new feature
category to the group embedding model (with text features as baseline). In
this section we discuss several important features that contributed to the
major model improvements.

Table 1. Group Embedding Improvement with Feature Engineering

Unified Embedding Abs. Recall Gain \+ location features \+ 2.20% \+ social
embedding features \+ 1.77%

Text features. Character n-gram (Huang et al., 2013) is a common approach to
represent text for text embedding. Its advantages compared to word n-grams are
two folds. First, due to its limited vocabulary size, the embedding lookup
table has a smaller size and can be learned more effectively during training.
Second, the subword representation is robust to out-of-vocabulary problem the
we encounter for both query (e.g. spelling variations or errors) and document
sides (due to large content inventory in Facebook). We compared models trained
with character n-grams vs word n-grams and found the former can yield a better
model. However, on top of character trigrams, including word n-gram
representations additionally provides small but consistent model improvement
(+1.5% recall gain). Note that since the cardinality of word n-grams is
usually very high (e.g. 352M for query trigrams), hashing is needed to reduce
the size of embedding lookup table. But even with the downside of hash
collision, adding word n-ngrams still provides extra gain.

For a Facebook entity222Facebook entity includes people (profile), group,
page, and event., the main field to extract text features is name for people
entities or title for non-people entities. Compared to Boolean term matching
techniques, we found embeddings trained with purely text features are
particularly good at addressing the following two scenarios:

  * •

Fuzzy text match. For example, the model is able to learn to match between
query ”kacis creations” and the Kasie’s creations page while the term-based
match cannot.

  * •

Optionalization. In the case of query ”mini cooper nw”, the model can learn to
retrieve the expected group Mini cooper owner/drivers club by dropping ”nw”
for an optional term match.

Table 2. Top Similar Groups Before and After Adding Location Embeddings

Searcher Location: Louisville, Kentucky Query: ”equipment for sale” Text Model
Text + Location Model 1 equipment for sale 1 Kentucky Farm Equipment for sale
2 EQUIPMENT FOR SALE WORLDWIDE 2 Pre-Owned Farm Equipment for Sale in KY,
Southern Indiana and Tennessee 3 EQUIPMENT SALE 3 Farm Equipment For Sale In
Ky 4 Equipment for Sale or Wanted 4 Central Ky Farm Equipment For Sale 5
Musical Equipment For Sale or Trade 5 sed Farm Equipment for sale or trade
East Ky. 6 Used Heavy Equipment For Sale in US 6 Farm Equipment KY for Sale 7
Sale equipment 7 kentucky hay and farm equipment for sale

Location features. Location match is advantageous in many search scenarios
such as searching for local business/groups/events. In order for embedding
models to consider locations in generating the output embeddings, we added
location features into both query and document side features. For query side,
we extracted searcher city, region, country, and language. For document side,
we added publicly available information, such as explicit group location
tagged by the admin. Together with text features, the model was able to
successfully learn implicit location match between query and results. Table 2
shows a side-by-side comparison of top similar documents returned by text
embedding model versus text + location embedding model for groups search. We
can see the model with location features can learn to fuse location signals
into embeddings, ranking documents that has the same location as the searcher
who is from Louisville, Kentucky to higher positions.

Social embedding features. To leverage the rich Facebook social graph to
improve unified embedding model, we trained a separate embedding model to
embed users and entities based on the social graph. This can help incorporate
the comprehensive social graph into a unified embedding model which may not
have full social graph information otherwise.

##  4\. Serving

###  4.1. ANN

We deployed an inverted index based ANN (approximate near neighbor) search
algorithms to our system because of the following advantages. First, it has
smaller storage cost due to the quantization of embedding vectors. Second, it
is easier to be integrated into the existing retrieval system which is based
on inverted index. We employed Faiss library (Johnson et al., 2017) to
quantize the vectors and then implemented the efficient NN search in our
existing inverted table scanning system.

There are two major components for the embedding quantization, one is the
_coarse quantization_ which quantizes embedding vectors into coarse clusters
typically through _K-means_ algorithm, and the other is _product quantization_
(Jegou et al., 2011) which does a fine-grained quantization to enable
efficient calculation of embedding distances. There are several important
parameters we need to tune:

  * •

_Coarse quantization._ There are different algorithms for coarse quantization.
It is useful to compare between IMI (Lempitsky, 2012) and IVF (Sivic and
Zisserman, 2003) algorithms. And it is important to tune number of coarse
clusters _num_cluster_ , which will affect both perf and recall.

  * •

_Product quantization._ There are multiple variants of product quantization
algorithms, including vanilla PQ, OPQ, PQ with PCA transform. And number of
bytes for PQ _pq_bytes_ is an important parameter to tune.

  * •

_nprobe._ _nprobe_ is the parameter to decide how many clusters will be
assigned to the query embedding, which will further decide how many coarse
clusters will be scanned. This parameter will affect the perf and recall.

Figure 3. 1-Recall@10 of IVF and IMI Index Table 3. Impact of Product
Quantization on 1-Recall@10 for 128-Dimension Embedding.

Quantization Scheme 1-Recall@10 Index Scanned PCA,PQ16 51.62% 0.48% PCA,PQ16
54.11% 0.60% PQ16 67.54% 0.58% OPQ16,PQ16 70.51% 0.48% OPQ16,PQ16 74.29% 0.60%
PQ32 74.27% 0.58% PQ64 74.81% 0.58% Flat (No Quantization) 74.81% 0.58%

We built an offline pipeline to efficiently tune these parameters. Besides, we
needed to run online experiment to decide the final setting from the selected
candidates based on offline tuning. Below we will share the tricks and
learnings we got from ANN tuning.

  * •

_Tune recall against number of scanned documents._ Initially we compared
recall of different coarse quantization algorithms for the same setting of
_num_cluster_ and _nprobe_. However, from more data analysis we found that the
clusters are imbalanced, especially for IMI algorithm – around half of
clusters only got a few samples. This would cause the number of scanned
documents different for the same setting of _num_cluster_ and _nprobe_.
Therefore, we employed the number of scanned documents as a better metric to
approximate perf impact in ANN tuning, as shown in Figure 3. We measured ANN
accuracy using _1-recall@10_ , which is averaged recall of getting top result
from exact KNN search in top 10 results of ANN search.

  * •

_Tune ANN parameters when there is non-trivial model change._ We observed that
ANN performance is related with model characteristics. For example, when we
employed ensemble techniques with model trained with non-click impressions, we
found that while the model showed a better recall than baseline, the recall
was worse than baseline after applying quantization to both. It should always
be considered to tune the ANN parameters when there is a non-trivial change of
the model training task, e.g., add more hard negatives.

  * •

_Always try OPQ._ It is often useful to transform data prior to applying the
quantization. We experimented with both PCA and OPQ (Ge et al., 2013) to
transform the data, and observed that OPQ is generally more effective, as
shown in Table 3 and Figure 3. One caveat of OPQ is: as it applied rotation of
the embeddings, we might also need to retune _num_cluster_ and _nprobe_ to
have similar documents scanned.

  * •

_Choose _pq_bytes_ to be d/4._ Product quantizer compresses the vectors into
$x$ byte codes. For the choice of $x$, it is related to the dimension $d$ of
the embedding vector. Bigger $x$ results in higher search accuracy but at cost
of increased memory and latency. From empirical results, we found that the
accuracy improvement is limited after $x>d/4$.

  * •

_Tune nprobe, num_clusters, and pq_bytes online to understand the real perf
impact._ While it is important to tune ANN algorithms and parameters offline
to get a reasonable understanding of perf vs. recall trade-off, we found it is
important to deploy several configs of the ANN algorithms and parameters
online to get a better understanding of the perf impact from embedding-based
retrieval to the real system. That is important to decide the capacity budget
and reduce the scope of parameter search in offline tuning.

###  4.2. System Implementation

In order to integrate embedding-based retrieval into our serving stack, we
implemented first-class support for NN search in Unicorn (Curtiss et al.,
2013), a retrieval engine powering most search products at Facebook. Unicorn
represents each document as a bag of terms, which are arbitrary strings that
express binary properties about the document, conventionally namespaced with
their semantics. For example, a user _John_ living in _Seattle_ would have the
terms `text:john` and `location:seattle`. Terms can have payloads attached to
them.

A query can be any Boolean expression on the terms. For example, the following
query would return all the people that have _john_ and _smithe_ in the name,
and live in _Seattle_ or _Menlo Park_ :

    (and (or (term location:seattle)
             (term location:menlo_park))
         (and (term text:john)
              (term text:smithe)))

To support NN, we extended the document representation to include embeddings,
each with a given string key, and added a `(nn <key> :radius <radius>)` query
operator which matches all documents whose `<key>` embedding is within the
specified radius of the query embedding.

At indexing time, each document embedding is quantized and turned into a term
(for its coarse cluster) and a payload (for the quantized residual). At query
time, the `(nn)` is internally rewritten into an `(or)` of the terms
associated to the coarse clusters closest to the query embedding (_probes_),
and for matching documents the term payload is retrieved to verify the radius
constraint. The number of probes can be specified with an additional attribute
`:nprobe`. By implementing NN support in terms of pre-existing primitives,
instead of writing a separate system, we inherited all the features of the
existing system, such as realtime updates, efficient query planning and
execution, and support for multi-hop queries (see (Curtiss et al., 2013)).

The latter allows us to support top-K NN queries, where instead of matching by
radius we select only the K documents closest to the query, and then evaluate
the rest of the query. However, from our experimental study, we found that
radius mode can give better trade-off of system performance and result
quality. One possible reason is that radius mode enables a constrained NN
search (constrained by other parts of the matching expression) but top $K$
mode provides a more relaxed operation which needs to scan the whole index to
get top $K$ results. Hence, we use radius based matching in our current
production.

####  4.2.1. Hybrid Retrieval

By having the `(nn)` operator as part of our Boolean query language we can now
support _hybrid_ retrieval expressions, with arbitrary combinations of
embeddings and terms. This can be used for model based fuzzy matching which
can improve on cases like spelling variations, optionalization etc. while
reusing and benefiting from other parts of retrieval expression. For example,
say a mis-spelled query _john smithe_ is looking for a person named _john
smith_ in _Seattle_ or _Menlo Park_ ; the retrieval expression would look like
the one above.

That expression will fail to retrieve the user in question since the term
`text:smithe` will fail to match that document. We can add fuzzy matching to
this expression through `(nn)` operator:

    (and (or (term location:seattle)
             (term location:menlo_park))
         (or (and (term text:john)
                  (term text:smithe))
             (nn model-141795009 :radius 0.24 :nprobe 16)))

where `model-141795009` is the key for the embedding. In this case the target
user will be retrieved if the cosine distance between the query (_john
smithe_) embedding and document (_john smith_) embedding is less than 0.24.

####  4.2.2. Model Serving

We served the embedding model in the following way. After the two-sided
embedding model was trained, we decomposed the model into a query embedding
model and a document embedding model and then served the two models
separately. For query embedding, we deployed the model in an online embedding
inference service for real-time inference. For documents, we used Spark to do
model inference in batch offline, and then published the generated embeddings
together with other metadata into forward index. We did additional embedding
quantization including coarse quantization and PQ to publish it into inverted
index.

###  4.3. Query and Index Selection

To improve efficiency and quality of EBR, we performed query and index
selection. We applied the query selection technique to overcome problems like
over-triggering, huge capacity cost and junkiness increase. We did not trigger
EBR for certain queries as EBR would be poor at and provide no extra value for
them, such as easy queries with which searchers are looking for a specific
target searched and clicked before, or queries with clearly different query
intents from what the embedding model was trained for. On index side, we did
index selection to make searching faster. For example, we only chose monthly
active users, recent events, popular pages and groups.

##  5\. Later-stage Optimization

Facebook search ranking is a complex multi-stage ranking system where each
stage progressively refines the results from the preceding stage. At the very
bottom of this stack is the retrieval layer, where embedding based retrieval
is applied. Results from the retrieval layer are then sorted and filtered by a
stack of ranking layers. The model at each stage should be optimized for the
distribution of results returned by the preceding layer. However, since the
current ranking stages are designed for existing retrieval scenarios, this
could result in new results returned from embedding based retrieval to be
ranked sub-optimally by the existing rankers. To solve this problem, we
proposed two approaches:

  * •

_Embedding_ as ranking feature. Propagating embedding similarities further
down the funnel not only helps the ranker recognize new results from
embedding-based retrieval, but also provides a generic semantic similarity
measure for all results. We explored several options to extract features based
on embeddings, including cosine similarity between the query and result
embeddings, Hadamard product, and raw embeddings. From our experimental
studies, cosine similarity feature consistently showed better performance than
other options.

  * •

_Training data feedback loop_. While embedding-based retrieval can improve
retrieval recall, it might have a lower precision in comparison with term
matching. To address the precision issue, we built a closed feedback loop
based on human rating pipeline. In particular, we logged the results after
enabling embedding-based retrieval, and then sent these results to human
raters to label whether they are relevant or not. We used these human rated
data to re-train the relevance model so that it can be used to filter out the
irrelevant results from embedding-based retrieval while keeping the relevant
ones. This proved to be a useful technique to achieve high precision for the
recall improvement in embedding-based retrieval.

##  6\. Advanced Topics

Embedding-based retrieval requires extensive research to continue improve the
performance. We investigated two important areas for embedding modeling: hard
mining and embedding ensemble, to continue advance the state of the art of
embedding-based retrieval solutions.

###  6.1. Hard Mining

The data space for a retrieval task has diverse data distribution in degrees
of text/semantic/social matches, and it is important to design a training data
set for an embedding model to learn efficiently and effectively on such space.
To tackle this, hard mining is one major direction as well as an active
research area for embedding learning. However, most of the research are from
computer vision field and for the classification task (Schroff et al., 2015;
Song et al., 2015; Hermans et al., 2017; Wu et al., 2017), while search
retrieval does not have concept of ”classes” and therefore is a unique problem
for which existing techniques do not necessarily work. In this direction, we
divided our solutions into two parts: hard negative mining and hard positive
mining.

####  6.1.1. Hard negative mining (HNM)

When analyzing our embedding model for people search, we found that the top
$K$ results from embeddings given a query were usually with the same name, and
the model did not always rank the target results higher than others even
though the social features are present. This motivated us believe that the
model was not able to utilize social features properly yet, and it’s very
likely because the negative training data were too easy as they were random
samples which are usually with different names. To make the model better at
differentiating between similar results, we can use samples that are closer to
the positive examples in the embedding space as hard negatives in training.

Online hard negative mining. As model training is based on mini-batch updates,
hard negatives can be selected in every batch in a dynamic but efficient way.
Each batch comprises $n$ positive pairs
$\\{(q^{(i)},d^{(i)}_{+})\\}_{i=1}^{n}$. Then for each query $q^{(i)}$, we
formed a small document pool using all other positive documents
$\\{d^{(1)}_{+},...,d^{(j)}_{+},...,d^{(n)}_{+}|j\neq i\\}$ and select the
documents which received the highest similarity scores as the hardest
negatives to create the training triplets. Enabling online hard negative
mining was one major contributor to our modeling improvement. It consistently
improved embedding model quality significantly across all verticals: +8.38%
recall for people search; +7% recall for groups search, and +5.33% recall for
events search. We also had observations that the optimal setting is at most
two hard negatives per positive. Using more than two hard negatives will start
to regress model quality.

One limitation of online HNM is that the probability of having any hard
negative from random samples could be low and therefore cannot produce hard
enough negatives. Next, we look at how to generate harder negatives based on
the entire result pool, also known as offline Hard Negative Mining.

Offline hard negative mining. Offline hard negative mining has the following
procedure:

  1. (1)

generate top $K$ results for each query.

  2. (2)

select hard negatives based on _hard selection strategy_.

  3. (3)

retrain embedding model using the newly generated triplets.

  4. (4)

the procedure can be iterative.

We performed extensive experiments to compare offline hard negative mining and
online hard negative mining. One finding that may first seem counterintuitive
is that models trained simply using hard negatives cannot outperform models
trained with random negatives. A further analysis suggested that the ”hard”
model put more weights on non-text features but did worse in text match than
the ”easy” model. Therefore, we worked to adjust the sampling strategy and
finally produce a model that can outperform online HNM model.

The first insight is about _hard selection strategy_. We found that using the
hardest examples is not the best strategy. We compared sampling from different
rank positions and found sampling between rank 101-500 achieved the best model
recall. The second insight is about _retrieval task optimization_. Our
hypothesis is that presence of easy negatives in training data is still
necessary, as a retrieval model is to operate on an input space which
comprises data with mixed levels of hardness, and the majority of which are
very easy negatives. Therefore, we explored several ways of integrating random
negatives together with hard negatives, including transfer learning from an
easy model. From our empirical study the following two techniques showed
highest effectiveness:

  * •

Mixed easy/hard training: blending random and hard negatives in training is
advantageous. Increasing the ratio of easy to hard negatives continues to
improve the model recall and saturated at easy:hard=100:1.

  * •

Transfer learning from ”hard” model to ”easy” model: while transfer learning
from easy to hard model does not produce a better model, transfer learning
from hard to easy achieved further model recall improvement.

Last but not least, computing exhaustively KNN for each data point in the
training data is very time-consuming, and the total model training time will
become unrealistic due to the limited computing resources. It is important to
have an efficient top K generation for the offline hard negative mining
algorithm. Approximate nearest neighbor search is a practical solution here to
reduce the total computational time significantly. Furthermore, running ANN
search on one random shard is sufficient to generate effective hard negatives,
as we only rely on _semi-hard_ negatives during training.

####  6.1.2. Hard positive mining

Our baseline embedding model used clicks or impressions as positives, which
the existing production can already return. To maximize the complementary gain
by embedding based retrieval, one direction is to identify new results that
have not been retrieved successfully by the production yet but positive. To
this aim, we mined potential target results for failed search sessions from
searchers’ activity log. We found that the positive samples mined in this way
is effective to help model training. Model trained using hard positives alone
can achieve similar level of model recall as click training data while the
data volume is only 4% if it. It can further improve model recall by combining
both hard positives and impressions as training data.

###  6.2. Embedding Ensemble

We learned from HNM experiments that both easy and hard examples are important
for EBR model training – we need hard examples to improve model precision, but
easy example are also important to represent the retrieval space. The model
trained using random negatives simulates the retrieval data distribution and
is optimized for recall at a very large $K$, but it has poor precision at top
$K$ when $K$ is small. On the other hand, the model trained to optimize
precision, e.g. models trained using non-click impressions as negatives or
offline hard negatives, is good at ranking for smaller set of candidates but
failed for retrieval tasks. Thereafter we propose to combine models trained
with different levels of hardness by a _multi-stage approach_ , in which the
first stage model focuses on recall and the second stage model specializes at
differentiating more similar results returned by the first stage model. We
shared the same spirit as the cascaded embedding training in (Yuan et al.,
2017), which ensembled a set of models trained with different level of
hardness in a cascaded manner. We explored different forms of ensemble
embeddings, including weighted concatenation and cascade model and found both
effective.

Weighted Concatenation. As different models provided different cosine
similarity scores for (query, document) pair, we used weighted sum of cosine
similarity as the metric to define how close this pair is. To be more
specific, given a set of models $\\{M_{1},\cdots,M_{n}\\}$ and their
corresponding weights, $\alpha_{1},\cdots,\alpha_{n}>0$, for any query $Q$ and
document $D$, we define the weighted ensemble similarity score $S_{w}(Q,D)$
between $Q$ and $D$ as

$S_{w}(Q,D)={\sum}_{i=1}^{n}\alpha_{i}\cos(V_{Q,i},\ U_{D,i}),$

where $V_{Q,i},1\leq i\leq n$, represent query vector of $Q$ by model $M_{i}$,
and $U_{D,i},1\leq i\leq n$, represent document vector of $D$ by model
$M_{i}$. For the serving purpose, we needed to ensemble multiple embedding
vectors into a single representation, for query and document sides,
respectively, that can satisfy the above metric property. We can prove that
applying weighting multiplication to one side of normalized vector can satisfy
the need. Specifically, we constructed the query vector and document vector in
the following way:

(4)
$E_{Q}=\big{(}\alpha_{1}\frac{V_{Q,1}}{\|V_{Q,1}\|},\cdots,\alpha_{n}\frac{V_{Q,n}}{\|V_{Q,n}\|}\big{)},$

and

(5)
$E_{D}=\big{(}\frac{U_{D,1}}{\|U_{D,1}\|},\cdots,\frac{U_{Q,n}}{\|U_{Q,n}\|}\big{)}.$

It is easy to see that the cosine similarity between $E_{Q}$ and $E_{D}$ is
proportional to $S_{w}(Q,D)$:

(6) $\begin{split}\cos(E_{Q},\
E_{D})&=\frac{S_{w}(Q,D)}{\sqrt{\sum_{i=1}^{n}\alpha_{i}^{2}}\cdot\sqrt{n}}.\end{split}$

With above, we served the ensemble embedding in the same way as described in
Section 4. The choices of weights were empirical which could be based on
performance on the evaluation data set.

We explored several model options for the second stage embedding models. The
experiments showed that models trained using non-click impressions achieved
the best kNN recall (4.39% recall improvement over the baseline model).
However, it suffered from much more accuracy loss compared to single model
when applying embedding quantization, and therefore the actual benefit
diminished when serving it online. We found that to have a best recall after
embedding quantization, the best strategy was to ensemble a relatively easier
model with offline hard negative mining model, for which the hardness level of
training negatives had been modified and tuned. This ensemble candidate had
slightly lower offline model improvement but was able to achieve significant
recall improvement online.

Cascade Model. Unlike the parallel combination as in weighted ensemble,
cascade model runs the second stage model on the output of the first stage
model, in a serial fashion. We compared different second-stage model options.
We found that models trained using non-click impressions was not a good
candidate; the overall improvement was much smaller than the weighted ensemble
approach. Moreover, the gain diminished as number of results to be reranked by
the second-stage model increases. However, using offline hard negative model
for the second stage achieved 3.4% recall improvement over the baseline. It
was a more suitable model candidate for cascade because the constructed
training data for offline HNM were exactly based on the output of the first-
stage model.

Additionally, we explored another cascade model composition. We observed that
while unified embedding overall had greater model recall compared to text
embedding, it generated new text match failures because of its shifted focus
to social and location matches. To enhance the text matching capability of the
model hence improve the model precision we adopted the cascade strategy: using
text embedding to pre-select text-matching candidates and then using unified
embedding model to re-rank result to return the final top candidates. It
achieved significant online improvement compared to using unified embedding
model alone.

##  7\. Conclusions

It has long term benefits to introduce semantic embeddings into search
retrieval to address the semantic matching issues by leveraging the
advancement on deep learning research. However, it is also a highly
challenging problem due to the modeling difficulty, system implementation and
cross-stack optimization complexity, especially for a large-scale personalized
social search engine. In this paper, we presented our approach of unified
embedding to model semantics for social search, and the implementation of
embedding-based retrieval in a classical inverted index based search system.

It is only the first step to implement the unified embedding model and
embedding-based retrieval system. There is still a long way to go to optimize
the system end to end to make it perform well in terms of result quality and
system performance. We introduced our experience in model improvement, serving
algorithm tuning, and later-stage optimization. We believe this will be
valuable experience to help people onboard embedding-based retrieval faster in
real search engines. The successful deployment of embedding-based retrieval in
production opens a door for sustainable improvement of retrieval quality by
leveraging the latest semantic embedding learning techniques. We introduced
our progress and learnings from the first step along this direction,
especially on hard mining and embedding ensemble.

There are tremendous opportunities ahead to continuously improve the system.
In the future, there are two main directions to pursue. One is to go _deep_.
In terms of modeling we could apply the latest advanced models such as BERT
(Devlin et al., 2018) or build task-specific models to address particular
segments of problems. We could investigate deeper in different stages
including serving algorithm tuning and ranking model improvement, guided by
full-stack failure analysis to identify the opportunities of improvements in
different stacks. The other is to go _universal_. We could leverage the pre-
trained text embedding models to develop a universal text embedding sub-model
to be applied in different tasks. Furthermore, we could develop a universal
query embedding model across all use cases.

## References

  * (1)
  * Baeza-Yates and Ribeiro-Neto (2011) Ricardo Baeza-Yates and Berthier Ribeiro-Neto. 2011.  _Modern Information Retrieval: The Concepts and Technology behind Search_ (2nd ed.).  Addison-Wesley Publishing Company, USA.
  * Bengio et al. (2013) Y. Bengio, A. Courville, and P. Vincent. 2013\.  Representation Learning: A Review and New Perspectives.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 35, 8 (Aug 2013), 1798–1828.
  * Curtiss et al. (2013) Michael Curtiss, Iain Becker, Tudor Bosman, Sergey Doroshenko, Lucian Grijincu, Tom Jackson, Sandhya Kunnatur, Soren Lassen, Philip Pronin, Sriram Sankar, Guanghao Shen, Gintaras Woss, Chao Yang, and Ning Zhang. 2013\.  Unicorn: a system for searching the social graph.  _Proceedings of the VLDB Endowment_ 6, 11, 1150–1161.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  _CoRR_ abs/1810.04805 (2018).  arXiv:1810.04805 http://arxiv.org/abs/1810.04805
  * Ge et al. (2013) Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013\.  Optimized Product Quantization for Approximate Nearest Neighbor Search. In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Hermans et al. (2017) Alexander Hermans, Lucas Beyer, and Bastian Leibe. 2017\.  In Defense of the Triplet Loss for Person Re-Identification.  _CoRR_ abs/1703.07737 (2017).  arXiv:1703.07737 http://arxiv.org/abs/1703.07737
  * Huang et al. (2013) Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. 2013\.  Learning Deep Structured Semantic Models for Web Search Using Clickthrough Data. In _Proceedings of the 22nd ACM International Conference on Information and Knowledge Management_ _(CIKM ’13)_. Association for Computing Machinery, New York, NY, USA, 2333–2338.
  * Jegou et al. (2011) Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011\.  Product Quantization for Nearest Neighbor Search.  _IEEE Trans. Pattern Anal. Mach. Intell._ 33, 1 (Jan. 2011), 117–128.
  * Johnson et al. (2017) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2017\.  Billion-scale similarity search with GPUs.  _arXiv preprint arXiv:1702.08734_ (2017).
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey E. Hinton. 2015\.  Deep learning.  _Nature_ 521, 7553 (2015), 436–444.
  * Lempitsky (2012) Victor Lempitsky. 2012\.  The Inverted Multi-Index. In _Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ _(CVPR ’12)_. IEEE Computer Society, USA, 3069–3076.
  * Li and Xu (2014) Hang Li and Jun Xu. 2014\.  _Semantic Matching in Search_.  Now Publishers Inc., Hanover, MA, USA.
  * Mitra and Craswell (2018) Bhaskar Mitra and Nick Craswell. 2018.  An Introduction to Neural Information Retrieval.  _Foundations and Trends® in Information Retrieval_ 13, 1 (December 2018), 1–126.
  * Schroff et al. (2015) Florian Schroff, Dmitry Kalenichenko, and James Philbin. 2015\.  FaceNet: A unified embedding for face recognition and clustering.. In _CVPR_. IEEE Computer Society, 815–823.  http://dblp.uni-trier.de/db/conf/cvpr/cvpr2015.html#SchroffKP15
  * Sivic and Zisserman (2003) Josef Sivic and Andrew Zisserman. 2003.  Video Google: A Text Retrieval Approach to Object Matching in Videos. In _Proceedings of the Ninth IEEE International Conference on Computer Vision - Volume 2_ _(ICCV ’03)_. IEEE Computer Society, USA, 1470.
  * Song et al. (2015) Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. 2015\.  Deep Metric Learning via Lifted Structured Feature Embedding.  _CoRR_ abs/1511.06452 (2015).  arXiv:1511.06452 http://arxiv.org/abs/1511.06452
  * Wu et al. (2017) Chao-Yuan Wu, R. Manmatha, Alexander J. Smola, and Philipp Krähenbühl. 2017\.  Sampling Matters in Deep Embedding Learning.  _CoRR_ abs/1706.07567 (2017).  arXiv:1706.07567 http://arxiv.org/abs/1706.07567
  * Yuan et al. (2017) Yuhui Yuan, Kuiyuan Yang, and Chao Zhang. 2017.  Hard-Aware Deeply Cascaded Embedding. In _The IEEE International Conference on Computer Vision (ICCV)_.


# On Improving Deep Reinforcement Learning for POMDPs

Pengfei Zhu1, Xin Li2, Pascal Poupart3, Guanghui Miao4,
1,2,4 Beijing Institute of Technology, Beijing, China
3 Waterloo, Ontario
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Deep Reinforcement Learning (RL) recently emerged as one of the most
competitive approaches for learning in sequential decision making problems
with fully observable environments, e.g., computer Go. However, very little
work has been done in deep RL to handle partially observable environments. We
propose a new architecture called Action-specific Deep Recurrent Q-Network
(ADRQN111ADRQN is implemented in Caffe. The source is available at
https://github.com/bit1029public/ADRQN.) to enhance learning performance in
partially observable domains. Actions are encoded by a fully connected layer
and coupled with a convolutional observation to form an action-observation
pair. The time series of action-observation pairs are then integrated by an
LSTM layer that learns latent states based on which a fully connected layer
computes Q-values as in conventional Deep Q-Networks (DQNs). We demonstrate
the effectiveness of our new architecture in several partially observable
domains, including flickering Atari games.

##  1 Introduction

Deep reinforcement Silver et al. (2016) learning combines reinforcement
learning and deep learning, and has shown great success in solving a number of
very challenging tasks that can be easily modeled as conventional
reinforcement learning problems, but cannot be solved by conventional
reinforcement learning approaches due to the high dimensionality of the state
space, e.g., continuous control Lillicrap et al. (2015), high-dimensional
robot control Stadie et al. (2015), and Atari Learning Environment benchmarks
(ALE) Bellemare et al. (2013).

Specifically, Deep Q-Networks (DQNs) can be used to effectively and
efficiently play many Atari 2600 games Mnih et al. (2015). The idea is to
extract convolved features of the frames as states and to approximate the
Q-function over the states with a deep neural network. For instance, a DQN is
trained to estimate the expected value of a policy based on the the past four
frames as input in Atari 2600 games. For most Atari 2600 games, four frames
are sufficient to approximate the current state of the game. Generally
speaking, the Atari games are treated as MDP problems, and DQNs are used to
approximate the value functions of these MDPs. However, for some other real-
world tasks including some Atari 2600 games, the problem is really a partially
observable Markov decision process (POMDP) where the state of the environment
may be partially observable or even unobservable, to the point where
arbitrarily long histories of observations are needed to extract sufficient
features for optimal action selection. Unfortunately, DQN is not suitable for
those problems due to the assumption of complete observability of the state.

While POMDPs can naturally model planning tasks with uncertain action effects
and partial state observability, finding an optimal policy is notoriously
difficult. Some previous POMDP techniques focus on identifying a finite subset
of beliefs that are sufficient to approximate all reachable beliefs in order
to decrease computational complexity Kurniawati et al. (2008); Li et al.
(2007).

Model | Input | Problem Addressed | Description
---|---|---|---
DQN | $s_{t}$ | model-free MDP | full knowledge of the state required
DBQN | $b_{t}$ | model-based POMDP | updated belief state required
DRQN | $\langle o_{1},o_{2},\cdots,o_{t}\rangle$ | model-free POMDP | observations as the input
DDRQN | $\langle a_{0},a_{0},\cdots,a_{t-1}\rangle$ | model-free POMDP | decoupled actions and observations required
$\langle o_{1},o_{2},\cdots,o_{t}\rangle$
ADRQN | $\langle(a_{0},o_{1}),(a_{1},o_{2}),\cdots,(a_{t-1},o_{t})\rangle$ | model-free POMDP | action-observation pairs required as input
Table 1: A comparison among state-of-the-art deep Q-learning approaches

Recent advances in deep learning suggest a new way of thinking for solving
POMDP problems. However, very little work leverages deep reinforcement
learning in partially observable environments. Among this work, Egorov (2015)
adopted DQNs to solve conventional POMDP problems. A policy is obtained with a
DQN that maps concatenated observation-belief vector pairs to an optimal
action. Their work (we call it DBQN) is designed for model-based
representations of the environment where the transition, observation and
reward functions are already known. Thus, the belief can be estimated
precisely with Bayes’ theorem and can serve as input to the neural network.
However, in most real-world POMDP problems, the environment dynamics are
unknown. To address this, Hausknecht and Stone (2015) adapted the fully
connected structure of DQN with a recurrent network Hochreiter and Schmidhuber
(1997), and called the new architecture Deep Recurrent Q-Network (DRQN). The
proposed model recurrently integrates arbitrarily long histories of
observations to find an optimal policy that is robust to partial
observability. However, DRQNs consider only observation histories without
explicitly including actions as part of the histories. This impacts negatively
the performance of the approach as demonstrated in Sec. 4. Lample and Chaplot
(2016) combined DRQN with handcrafted features to jointly supervise the
learning process of 3D games in partially observable environments, however the
approach suffers from the same problem as DRQN since it overlooks action
histories. Foerster et al. (2016) extended DRQN to handle partially observable
multi-agent reinforcement learning problems by proposing a deep distributed
recurrent Q-networks (DDRQN). The action history is explicitly processed by an
LSTM layer and fed as input to a Q-network. In DDRQN, each action is forcibly
decoupled from its associated observation despite the fact that action-
observation pairs are the key to belief updating. As a result, the decoupling
of actions and observations in DDRQN impacts negatively belief inference.

In this paper, we propose a new architecture called Action-based Deep
Recurrent Q-Network (ADRQN) to improve learning performance in partially
observable domains. Actions are encoded via a fully connected layer and
coupled with their associated observations to form action-observation pairs.
The time series of action-observation pairs is processed by an LSTM layer that
learns latent states based on which a fully connected layer computes Q-values
as in conventional DQNs. We demonstrate the effectiveness of our new
architecture in several Atari 2600 games. Table 1 summarizes the main
differences between ADRQN and other state-of-the-art deep Q-learning
techniques.

##  2 Background

In this section, we give a brief review of Deep Q-Networks (DQNs), Partially
Observable Markov Decision Processes (POMDPs) and Deep Recurrent Q-networks
(DRQNs).

###  2.1 Deep Q-Networks

A sequential decision problem with known environment dynamics is usually
formalized as a Markov Decision Process (MDP), which is characterized by a
4-tuple $\langle S,A,P,R\rangle$. At each step, an agent selects an action
$a_{t}\in A$ to execute with respect to its fully observable current state
$s_{t}\in S$ and based on its policy $\pi$. It receives an immediate reward
$r_{t}\sim R({s_{t}},{a_{t}})$ and transitions to a new state $s_{t+1}$. The
objective of reinforcement learning is to find the policy that maximizes the
expected discounted rewards $R_{t}$

${R_{t}}={r_{t}}+\gamma{r_{t+1}}+{\gamma^{2}}{r_{t+2}}+\cdots$ (1)

where $\gamma\in[0,1]$ is the discount factor. In MDPs, an optimal policy can
be computed by value iteration Sutton and Barto (1998).

Q-Learning Watkins and Dayan (1992) was proposed as a model-free technique for
reinforcement learning problems with unknown dynamics. It estimates the value
of executing an action in a given state followed by an optimal policy $\pi$.
This value is called the state-action value, or simply Q-value as defined
below:

${Q^{\pi}}(s,a)=E^{\pi}({R_{t}}|{s_{t}}=s,{a_{t}}=a)$ (2)

The Q-values can be learned iteratively according to the following rule while
the agent is interacting with the environment:

$Q(s,a)=Q(s,a)+\alpha(r+\gamma\mathop{\max}\limits_{{a^{\prime}}}Q(s^{\prime},a^{\prime})-Q(s,a))$
(3)

In tasks with a large number of states, a common trick is to use a function
approximator to estimate the Q-function. For instance, DQN Mnih et al. (2015)
uses a neural network parameterized by $\theta$ to represent
$Q({s},{a};{\theta})$. Neural networks with at least one (non-linear) hidden
layer and sufficiently many nodes can approximate any function arbitrarily
closely. DQN is optimized by minimizing the following loss function:

$L({\theta_{i}})={E_{s,a,r,s^{\prime}}}\left[{{{\left({(y_{i}^{target}-Q(s,a;{\theta_{i}})}\right)}^{2}}}\right]$
(4)

where
$y_{i}^{target}=r+\gamma\mathop{\max}\limits_{{a^{\prime}}}Q({s^{\prime}},{a^{\prime}};\theta^{-}_{i})$
denotes the target value of the action $a_{t}$ given state $s_{t}$. Here
$\theta_{i}^{-}$ is cloned from ${\theta_{i}}$ every fixed numbers of
iterations. DQN uses experience replay Lin (1993) to store previous samples
$e_{t}=\langle s_{t},a_{t},r_{t},s_{t+1}\rangle$ up to a fixed size memory
$D_{t}$. The Q-network is then trained by uniformly sampling mini-batches of
past experiences from the replay memory. An important factor for the
efficiency of DQN in AlphaGo and the Atari games is the assumption of full
state observability that allows the neural network to use only one (or a few)
observation(s) as input. Thus, DQN suffers inaccuracy in tasks with partially
observable states.

###  2.2 Partially Observable Markov Decision Processes (POMDPs)

POMDPs generalize MDPs for planning under partial observability. A POMDP is
mathematically defined as a tuple $\langle\mathcal{S,A,Z},T,O,R\rangle$,
consisting of a finite set of states $\mathcal{S}$, a finite set of actions
$\mathcal{A}$, a transition function
$T:\mathcal{S}\times\mathcal{A}\rightarrow\Pi(\mathcal{S})$, where
$\Pi(\mathcal{S})$ represent the set of probability distributions on
$\mathcal{S}$, a reward function depending on the state and the action just
performed $R:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{R}$, a finite set
of observations $\mathcal{Z}$ and an observation function
$O:\mathcal{S}\times\mathcal{A}\rightarrow\Pi(\mathcal{Z})$, where
$\Pi(\mathcal{Z})$ represent the set of probability distribution on
$\mathcal{Z}$. As the true states are not fully observable any more, a belief
is used to estimate the current state, defined as the probability mass
function over the states and denoted as $b=(b(s_{1}),b(s_{2}),...b(s_{|S|}))$,
where $s_{i}\in\mathcal{S},b(s_{i})\geq 0$, and
$\sum_{s_{i}\in\mathcal{S}}{b(s_{i})=1}$. Given the current belief $b_{t}$,
performing action $a_{t}$ and get the next observation $z_{t+1}$, then the
next belief $b_{t+1}=SE(b_{t},a_{t},z_{t+1})$ is estimated as follows:

$b_{t+1}(s_{j})=\frac{O(s_{j},a_{t},z_{t+1})\sum_{s_{i}\in\mathcal{S}}T(s_{i},a_{t},s_{j})b_{t}(s_{i})}{P(z_{t+1}|a_{t},b_{t})}$
$P(z_{t+1}|a_{t},b_{t})=\sum_{s_{j}\in\mathcal{S}}O(s_{j},a_{t},z_{t+1})\sum_{s_{i}\in\mathcal{S}}T(s_{i},a_{t},s_{j})b_{t}(s_{i})$
(5)

The expected immediate reward for an agent performing action $a$ at the belief
state $b$ is computed as
$\rho(b,a)=\sum_{s_{i}\in\mathcal{S}}{b(s_{i})R(s_{i},a)}$. The transition
function among beliefs becomes:

$\tau(b,a,b^{\prime})=\sum_{z\in\mathcal{Z}}p(b^{\prime}|b,a,z)P(z|b,a)$ (6)

where $p(b^{\prime}|b,a,z)=1$ if $b^{\prime}=SE(b,a,z)$, and $0$ otherwise. An
optimal policy $\pi:\mathcal{R}^{|\mathcal{S}|}\rightarrow\mathcal{A}$ can be
computed by value iteration:

$V(b)=\max\limits_{a}[\rho(b,a)+\gamma\sum_{b^{\prime}}{\tau(b,a,b^{\prime})V(b^{\prime})}]\vspace{-2mm}$
(7)

where $\gamma$ is a discount factor for the past history. In practice, it is
common to have the optimal policy represented by a set of linear functions (so
called $\alpha$-vectors) over the belief space, with the maximum “envelop” of
the $\alpha$-vectors forming the value function Shani et al. (2013).

###  2.3 DRQN

DQN assumes that the agent has full knowledge of the state of the environment,
i.e., the agent’s observation is equivalent to the state of environment.
However, in practice, this is rarely true, even in some Atari games. For
example, one frame of _Pong_ does not reveal the ball’s velocity and its
moving direction. In the game of _Asteroids_ , parts of the image are
concealed for several consecutive frames to challenge the player. Hence, these
games are naturally POMDP problems. While the strategy of DQN is to utilize
several consecutive frames as the input in the hope of deducing the full
state, this works well only when a short limited history is sufficient to
characterize the state of the game. For more complex games, the performance of
DQN decreases sharply.

To tackle problems with partially observable environments by deep
reinforcement learning, Hausknecht and Stone (2015) proposed a framework
called _Deep Recurrent Q-Learning_ (DRQN) in which an LSTM layer was used to
replace the first post-convolutional fully-connected layer of the conventional
DQN. The recurrent structure is able to integrate an arbitrarily long history
to better estimate the current state instead of utilizing a fixed-length
history as in DQNs. Thus, DRQNs estimate the function
$Q({o_{t}},{h_{t-1}}|\Theta)$ instead of $Q({s_{t}},{a_{t}}|\Theta)$, where
$\Theta$ denotes the parameters of entire network, $h_{t-1}$ denotes the
output of the LSTM layer at the previous step, i.e.,
$h_{t}=LSTM({h_{t-1},o_{t}})$. DRQN matches DQN’s performance on standard MDP
problems and outperforms DQN in partially observable domains. Regarding the
training process, DRQN only considers the convolutional features of the
history of observations instead of explicitly incorporating the actions.
However as we argued in Sec. 1 and Eq. 2.2 in Sec. 2.2, the action performed
is crucial for belief estimation. To that effect, we propose a new
architecture for deep reinforcement learning with actions incorporated in
histories to further improve the performance of deep RL in POMDPs. In the
sequel, we will refer to our proposed architecture as ADRQN (action-specific
deep recurrent Q-learning Network).

##  3 ADRQN - Action-specific Deep Recurrent Q-Network

Inspired by the aforementioned works, our goal is to propose a model-free deep
RL approach that incorporates the influence of the performed action through
time. More specifically, we couple the performed action and the obtained
observation as the input to the Q-network. The architecture222‘IP’ means inner
product, i.e., fully connect layer. of our model is shown in Fig. 1.

Figure 1: The input action is an 18-D vector followed by a fully connected
(IP) layer with 512-D outputs. A single $84\times 84$ frame will be convolved
as the observation via three convolutional layers with 32 8$\times$8 filters
with stride 4, 64 4$\times$4 filters with stride 2, and 64 3$\times$3 filters
with stride 1, respectively. The 512-D outputs of LSTM are fed to another
fully connected layer and produce 18-D Q-values corresponding to 18 actions in
Atari games.

Our first attempt to couple the action and observation was to concatenate a
fixed representation of the action with the observation vector directly, i.e.,
we utilized one-hot vectors to represent each action $a\in\mathcal{A}$.
However, such concatenation did not yield good performance because the lengths
of the action and observation vectors differ largely which leads to numerical
instability. In Atari games as well as many real-world POMDPs, the number of
actions is far less than the dimensionality of the state representation. In
conventional DQNs and DRQNs, the suggested dimensionality of the convolved
features encoding the current state or observation is 3136 (after passing
several convolutional and reshaping layers), while the number of actions is
only 18 for the Atari games. To address this imbalance, we embed the one-hot
action vectors by a fully connected layer into a higher dimensional vector
(512-D is our experiments). Thus the representations of the actions and the
observations are now more balanced.

Compared with DQN and DRQN, our model is able to remember the past actions,
particularly the last performed action. Thus, we modified
$(s_{t},a_{t},r_{t},s_{t+1})$ the transition in the experience replay
mechanism of DQN to $\langle\\{a_{t-1},o_{t}\\},a_{t},r_{t},o_{t+1}\rangle$ in
order to allow the framework to fetch the action-observation pair more
conveniently. During the decision process for a given frame within training or
the updating process of the neural network, the LSTM layer requires a sequence
of action-observation pairs as its input. Thus, we store the transitions
sequentially $\langle\\{a_{t-1},o_{t}\\},a_{t},r_{t},o_{t+1}\rangle$ within
each episode in the replay memory.

Ideally, the best strategy to estimate precisely the current state for a
model-free POMDP problem is to integrate the entire transition history of each
episode, which usually includes thousands of transitions for an Atari game.
This also means that the LSTM layer needs to be unrolled for a large number of
time steps which will increase significantly the training cost. In our
experiments, the LSTM layer is unrolled for 10 time steps during training. We
take this setting for three points. From the perspective of learning from
whole history, this setting can be more satisfy to our original idea compared
to a smaller setting of the length. Second is that this setting can also
guarantee the efficiency of experiments. It allows that our experiments can be
finished within several days. And last point is to make a better comparison to
DRQN as it take a same setting of 10. Such empirical setting has proved its
efficacy to our framework.

The entire process of our proposed approach is presented in Algorithm 1.
First, we initialize the parameters of the Q-network and the Target network
with $\theta$ and $\theta^{-}$ respectively. For each episode, the first
selected action is initialized to no-operation, the first hidden layer’s input
is initialized with a zero vector and the first observation of each episode is
initialized with the preprocessed first frame. At each time step, if the
observation does not indicate “game over” (the end of the episode), we select
an action based on the $\epsilon$-greedy strategy and execute the action.
Accordingly, the immediate reward and the next observation of the screen will
be obtained. The transition, once obtained, will be sequentially stored in the
history of the current episode. To update the Q-network, we randomly sample a
sequence of transitions $\langle a_{j-1},o_{j},a_{j},r_{j},o_{j+1}\rangle$ to
fit the unrolled LSTM layer. Then, the hidden layer $h_{j-1}$ of the Q-network
and the hidden layer $h_{j}$ of the target network are obtained. The
difference between these two network Q-values (i.e., Q-value $y_{j}$ and
Q-network value $Q(h_{j-1},a_{j-1},o_{j},a_{j};\theta)$) is used as the loss
function to update the network parameters $\theta$ via back propagation.

Algorithm 1 Action-specific Deep Recurrent Q-Network

1:Initialize the replay memory _D_ , # of iterations _M_

2:Initialize Q-Network and Target-Network with $\theta$ and $\theta^{-}$
respectively

3:for episode = 1 to _M_ do

4: Initialize the first action $a_{0}=no\,operation$, $h_{0}=\textbf{0}$

5: Init.the first obs.$o_{1}$ with the preprocessed first screen

6: while $o_{t}\not=terminal$ do

7: Select a random action $a_{t}$ with the probability $\epsilon$

8: Else select
$a_{t}=\mathop{\operatorname*{argmax}}_{a}Q(h_{t-1},a_{t-1},o_{t},a;\theta)$

9: Execute action $a_{t}$

10: Obtain reward $r_{t}$ and resulting observation $o_{t+1}$

11: Store transition $\langle\\{a_{t-1},o_{t}\\},a_{t},r_{t},o_{t+1}\rangle$
as one record of the current episode in _D_

12: Randomly sample a minibatch of transition sequences $\langle
a_{j-1},o_{j},a_{j},r_{j},o_{j+1}\rangle$ from _D_

13: Compute Q-value of target network
$y_{j}=\\!\left\\{{\begin{array}[]{*{20}l}r_{j},&{\begin{array}[]{*{20}l}o_{j+1}\\!=\\!terminal\end{array}}\\\
r_{j}\\!+\\!\gamma\mathop{\max}\limits_{{a}}Q(h_{j},a_{j},o_{j\\!+\\!1},a;\theta^{-}),&{\begin{array}[]{*{1}l}o_{j+1}\\!\not=\\!terminal\end{array}}\\\
\end{array}}\right.$

14: Compute the gradient of
$(y_{j}-Q(h_{j-1},a_{j-1},o_{j},a_{j};\theta))^{2}$ to update $\theta$

15: end while

16:end for

##  4 Experiments

We evaluate the training and testing performance of ADRQN with several Atari
games and their flickering version.

###  4.1 Experiments setup

  * •

Flickering Atari game: Hausknecht and Stone (2015) introduced a flickering
version of the Atari games, which modified the Atari games by obscuring the
entire screen with a certain probability at each time step, which introduces
partial observability and therefore yields a POMDP. In their framework, before
a frame is sent to the neural network as input, each raw screen is either
fully observable or fully obscured with black pixels.

  * •

Frame skip Scheme. We adopted the frame skip technique Bellemare et al.
(2013). This mechanism is commonly used in most previous works of deep
reinforcement learning to efficiently simulate the environment. In this
mechanism, an agent performs the selected action $a_{i}$ for $k+1$ consecutive
frames and treats the transition from the first frame $f_{0}$ to frame
$f_{k+1}$ as the effect of action $a_{i}$, i.e. $\langle
f_{0},a_{i},f_{1},...,a_{i},f_{k+1}\rangle$=$\langle
f_{0},a_{i},f_{k+1}\rangle$. Thus, a large number of frames can be skipped to
accelerate the training process, but with a tolerable performance loss. In our
experiments, $k$ is set to 4.

  * •

Hyperparameters. In our experiments, we also adopt experience replay and set
the replay memory size to $\emph{D}=400,000$ (i.e., storing 400,000
transitions). When selecting an action, we follow the $\epsilon\\!-\\!greedy$
policy with $\epsilon=1-\frac{0.9*iter}{explore}$, where $iter$ is the current
number of iterations performed and $explore$ is the number of iterations that
epsilon reaches to a given value. In our setting, $\epsilon$ will reach 0.1
and $explore$ was set to $1,000,000$. The discount factor $\gamma$ was set to
0.99. The target network is updated by cloning the weights of the Q-network
every $10,000$ iterations. And we unrolled the LSTM to 10 time step when
training as we said in Section 3.

  * •

Random Updates. As suggested in Hausknecht and Stone (2015), random updates
can achieve the similar performance as conventional sequential updates of the
entire episode, but with much lower training cost. Random updates consist of
selecting randomly a series of transitions from one episode as the input. In
our framework, this corresponds to utilizing a sequence of action-observation
pairs to perform the updates. The initial hidden input $h_{0}$ of the RNN is
set to the zero vector at the beginning of the update.

###  4.2 Training

Figure 2: Training results for Pong

Figure 3: Training results for Frostbite

Compared to the other approaches, the key idea of our framework is to
construct action-observation pairs as input to the LSTM layer to retain more
representative features for the Q-network to learn recurrently. The actions
are first encoded with one-hot vectors, then processed by a fully connected
layer to construct a higher-dimensional vector that is concatenated with the
output of the third convolutional layer for better numerical stability. As the
LSTM layer will be unrolled for 10 time steps, we need to ensure that there
are enough transitions to be stored in the replay memory _D_ so that we can
sample a minibatch of the transition sequences of length 10 each time we
update the entire network. In our experiments, we update the entire network
until the replay memory is full. Moreover, the scores obtained by playing the
games are not always stable since small changes of the weights may have a
significant impact on the outcome Mnih et al. (2013). And, it may bring the
instability to the policy which the network have learned. Thus, we adopt an
adaptive setting as done in most previous works by replacing negative rewards
by -1 and positive rewards by +1.

When training the flickering versions of Atari games, we set the probability
of obscuring a frame to 0.5 as a compromise. A lower probability may prevent
learning due to a large loss of information, and a higher probability may be
less convincing that the transformed version is a POMDP. Besides, it is a fair
setting to evaluate generalization performance since it divides the test
interval into two subintervals evenly. The games _Pong_ and _Frostbite_ are
both trained under the setting of full observation and a 0.5 probability of
obscuring a frame. The training performances of _Pong_ and _Frostbite_ are
shown in Fig. 3 and 3 respectively. The reported scores are based on averages
of 10 and 100 episodes respectively.

We compared our model ADRQN with DRQN and DDRQN on several Atari games. As
DDRQN is proposed for addressing multi-agent POMDP problems and it disabled
experience replay mechanism, we adapted it to a single-agent version which
also adopts the replay memory mechanism. Fig. 3 and Fig. 3 show that ADRQN
matches the performance obtained by DRQN and DDRQN, and even performs slightly
better than them in the conventional setting (full observation), while the
improvements of ADRQN over DRQN and DDRQN in partially observable settings are
very obvious. Additionally, when trained under the setting of the observation
probability as 0.5, ADRQN can obtain significant improvements in
_Frostbite_(Fig. 3). We believe the gain comes from the use of
$\langle$action, observation$\rangle$ pair which speeds up the training
process in partially observable environments. In general, our proposed model
can lead to higher scores in partially observable settings during the training
process, which supports the argument that action-observation pairs are
important in POMDP problems.

###  4.3 Testing Evaluation

Model |  DRQN($\pm$_std_) |  DDRQN($\pm$_std_) |  ADRQN($\pm$_std_)
---|---|---|---
Pong | $18.3(\pm 2.0)$ | $18.6(\pm 1.2)$ | $18.54(\pm 2.3)$
Chp.Cmd. | $1790(\pm 744.3)$ | $1455(\pm 596.0)$ | $1648(\pm 658.1)$
Asteroids | $983.8(\pm 366.9)$ | $1096.6(\pm 351.9)$ | $1025.4(\pm 360.9)$
Double dunk | $-12.8(\pm 3.8)$ | $-13(\pm 4.5)$ | $-15.2(\pm 3.4)$
Frostbite | $2412(\pm 394.5)$ | $2245.5(\pm 585.8)$ | $2290.5(\pm 571.7)$
Table 2: Testing results from standard setting Model |  DRQN($\pm$_std_) |  DDRQN($\pm$_std_) |  ADRQN($\pm$_std_)
---|---|---|---
Pong | $1.6(\pm 7.8)$ | $1.9(\pm 8.4)$ | $\textbf{7}(\pm 4.6)$
Chp. Cmd. | $1090(\pm 409.2)$ | $1040(\pm 392.8)$ | $\textbf{1608}(\pm 707.9)$
Asteroids | $871.4(\pm 339.8)$ | $1033(\pm 396.1)$ | $\textbf{1040.2}(\pm 431.5)$
Double dunk | $-14.4(\pm 3.2)$ | $-13(\pm 2.5)$ | $-13(\pm 3.6)$
Frostbite | $673.5(\pm 503.0)$ | $393(\pm 347.4)$ | $\textbf{2002.5}(\pm 734.653)$
Table 3: Testing results with flickering setting (obs. prob. is 0.5)

We also evaluate the well-learned DRQN, DDRQN and ADRQN models on the five
games and their flickering version. We replay each game based on the learned
model 50 times to obtain the average scores as our final results. The epsilon
value used in testing evaluation for $\epsilon\\!-\\!greedy$ is set to 0, as
we consider the model has been well trained and there is no need for the
exploration. Table 2 summarizes the results obtained with full observations.
The results shows that ADRQN has a similar performance with DRQN and DDRQN in
general in full observable environments. While Table 3 demonstrates that ADRQN
significantly outperforms DRQN and DDRQN when trained with half of the frames
obscured in all five games. And particularly, that ADRQN can get a similar
score as it get in full observable setting in the game Chopper Command and
game Frostbite which further demonstrates the advantage of our model. An
interesting observation is that the testing results are generally better than
the results obtained during the training process for all three models. This
may be explained by the fact that different distribution of the concealed
frames may render the problem more or less observable, to the extent that
better results may be obtained in some cases. Another explanation is that no
exploration is needed for selecting action or making a decision after a policy
is well trained, thus leads to better results.

###  4.4 Generalization Performance

To further demonstrate the advantages of ADRQN in dealing with environmental
changes, we evaluate the generalization performance of DRQN, DDRQN and ADRQN
on the flicking versions of the games.

POMDP to MDP Generalization: After being trained with observation probability
of 0.5, we test the learned policy in settings with observation probabilities
$(0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0)$. The results are shown in Fig.
5. We observe that all of three models consistently perform better with the
increase of observation probability in game Pong, and also perform better with
the observation probability changed in game Frostbite. ADRQN consistently
outperforms DRQN and DDRQN in these two games, and has a large advantage in
game Frostbite which further demonstrates that our model can better respond to
environmental changes.

MDP to POMDP Generalization: After being trained as an MDP by setting the
observation probability to 1, we test the learned policy with different
settings of the obscured probability. As shown in Fig.5, all the performances
achieved by the three models drop sharply as we increase the amount of missing
information. Fig.5 clearly demonstrate that ADRQN is relatively robust
compared to DRQN and DDRQN.

(a) Game Pong

(b) Game Frostbite

Figure 4: POMDP to MDP Generalization Performance

(a) Game Pong

(b) Game Frostbite

Figure 5: MDP to POMDP Generalization Performance

##  5 Brief Discussion

Someone may argue that action information could be viewed as redundant in the
context of a fixed policy. That is if you know the entire sequence of
observations and there is a fixed deterministic policy, then one can fill in
the missing actions directly. We agree with this argument and we guess that’s
why the existing state-of-the-art work i.e. DRQN overlooked the action
observation pair. However, with the adoption of a recurrent model, the
observation history is inevitably truncated to ensure training efficiency.
Thus, a proper action sequence cannot be inferred from the truncated history.
For a complex partially observable task, the set of observations is infinite.
It would be even harder to infer the actions from the finite observation
history. Intuitively, an explicit incorporation of the coupled action-
observation pair would help a lot especially during the training process.

##  6 Conclusion

In this paper, we propose an action-specific deep recurrent Q-Network (ADRQN)
to enhance the learning performance in partially observable domains. We first
encode actions via MLP and couple them with the features of observations
extracted from CNN to form action-observation pairs. Then an LSTM layer is
utilized to integrate a time series of action-observation pairs to infer the
latent states. Finally, a fully connected layer will address Q-values
computing to guide the overall learning process which is similar to
conventional DQNs. We have demonstrated the effectiveness of our proposed
approach in several POMDP problems in comparison to the state-of-the-art
approaches.

## References

  * Bellemare et al. [2013] Marc G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling.  The arcade learning environment: An evaluation platform for general agents.  J. Artif. Intell. Res. (JAIR), 47:253–279, 2013.
  * Egorov [2015] Maxim Egorov.  Deep reinforcement learning with pomdps.  2015\.
  * Foerster et al. [2016] Jakob N. Foerster, Yannis M. Assael, Nando de Freitas, and Shimon Whiteson.  Learning to communicate to solve riddles with deep distributed recurrent q-networks.  CoRR, abs/1602.02672, 2016.
  * Hausknecht and Stone [2015] Matthew J. Hausknecht and Peter Stone.  Deep recurrent q-learning for partially observable mdps.  CoRR, abs/1507.06527, 2015.
  * Hochreiter and Schmidhuber [1997] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural Computation, 9(8):1735–1780, 1997.
  * Kurniawati et al. [2008] Hanna Kurniawati, David Hsu, and Wee Sun Lee.  SARSOP: efficient point-based POMDP planning by approximating optimally reachable belief spaces.  In Robotics: Science and Systems IV, Eidgenössische Technische Hochschule Zürich, Zurich, Switzerland, June 25-28, 2008, 2008\.
  * Lample and Chaplot [2016] Guillaume Lample and Devendra Singh Chaplot.  Playing FPS games with deep reinforcement learning.  CoRR, abs/1609.05521, 2016.
  * Li et al. [2007] Xin Li, William Kwok-Wai Cheung, Jiming Liu, and Zhili Wu.  A novel orthogonal nmf-based belief compression for pomdps.  In Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20-24, 2007, pages 537–544, 2007.
  * Lillicrap et al. [2015] Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  CoRR, abs/1509.02971, 2015.
  * Lin [1993] Long-Ji Lin.  Reinforcement learning for robots using neural networks.  Technical report, DTIC Document, 1993.
  * Mnih et al. [2013] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller.  Playing atari with deep reinforcement learning.  CoRR, abs/1312.5602, 2013.
  * Mnih et al. [2015] Volodymyr Mnih, Kavukcuoglu Koray, Silver David, Rusu Andrei A, Veness Joel, Bellemare Marc G, Graves Alex, Riedmiller Martin, Fidjeland Andreas K, Ostrovski Georg, et al.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529–533, 2015.
  * Shani et al. [2013] Guy Shani, Joelle Pineau, and Robert Kaplow.  A survey of point-based pomdp solvers.  Autonomous Agents and Multi-Agent Systems, pages 1–51, 2013.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  Nature, 529(7587):484–489, 2016.
  * Stadie et al. [2015] Bradly C. Stadie, Sergey Levine, and Pieter Abbeel.  Incentivizing exploration in reinforcement learning with deep predictive models.  CoRR, abs/1507.00814, 2015.
  * Sutton and Barto [1998] Richard S. Sutton and Andrew G. Barto.  Reinforcement learning: An introduction.  IEEE Trans. Neural Networks, 9(5):1054–1054, 1998.
  * Watkins and Dayan [1992] Christopher J. C. H. Watkins and Peter Dayan.  Technical note q-learning.  Machine Learning, 8:279–292, 1992.