arXiv:1709.05638v1 [] 17 Sep 2017

Reinforcement Learning Based Conversational
Search Assistant
Aarushi Arora
IIT Delhi, Hauz Khas
Delhi, India
aarushi.arora043@gmail.com

Milan Aggarwal
Adobe Systems Inc, Noida
Uttar Pradesh, India
milaggar@adobe.com
Shagun Sodhani
Adobe Systems Inc, Noida
Uttar Pradesh, India
sshagunsodhani@gmail.com

Balaji Krishnamurthy
Adobe Systems Inc, Noida
Uttar Pradesh, India
kbalaji@adobe.com

Abstract
In this work, we develop an end-to-end Reinforcement Learning based architecture
for a conversational search agent to assist users in searching on an e-commerce
marketplace for digital assets. Our approach caters to a search task fundamentally
different from the ones which have limited search modalities where the user can
express his preferences objectively. The system interacts with the users to display
search results to the queries, and gauges user’s intent and context of the conversation
to choose the next action and reply. To train the agent in the absence of true
conversation data, a virtual user is constructed to model a human user using
the query and session logs from a major stock photography and digital assets
marketplace. The system provides an alternative that is more engaging than the
traditional search while maintaining similar effectiveness. This work provides a
mechanism to build and deploy bootstrapped version of an effective conversational
agent from readily available query log data. The system can then be used to acquire
true conversational data and be fine-tuned further. The methodology discussed in
this paper can be extended to e-commerce domains in general.

1

Introduction

Search is a fundamental feature of most e-commerce platforms. The conventional search interface
typically enables a user to search for items and provides filtering capabilities. But the overall process
is not very flexible. The typical user work flow goes like this: the user types in her search query,
applies some filters and goes through the results obtained. Based on the results, she updates her
search query. This iterative interaction between the user and the e-commerce platform promotes the
need for incorporating conversations as a modality of interaction between the user and the platform.
Conversational search is envisioned as a promising paradigm for e-commerce platforms. Chat based
systems can be used to make the entire search process less tedious and more intuitive, user-friendly
and human-like by providing a more interactive and engaging experience to the customer.
Rule-based systems were one of the first attempts made to develop conversational agents [3]. Recent
work in this domain has been done through deep learning and use of conversational data [8, 14].
Reinforcement Learning (RL) is an evolving field and is still being explored for its use case in search.
In this work, we focus on developing an RL based architecture for a conversational agent to provide
contextual assistance to customers for searching on an e-commerce marketplace for digital assets
where the end user can interact with the agent using natural language based dialogues.

Presently, RL based chat bots have been used in search tasks, such as hotel reservation, which have
limited and objective search modalities without much scope for an open-ended discussion about the
search task. For example, when booking a restaurant, the user may specify preferences in terms
of distance and budget which makes it more of a slot filling exercise. In our case, the user starts
with a very broad idea, in terms of the kind of asset he needs and this idea gets refined as the search
progresses. In such scenarios, the search process can not be reduced to a sequential application of
filters and a conversational agent can help the user in expressing intent and narrowing down the
search results. Further, since we can not model the user’s preferences with a fixed set of facets, we
have a very large search space to explore - a problem that most other goal oriented reinforcement
learning agents do not face.
Our conversational agent observes state of conversation taking place along side the search to decide
its next action. We model state of the conversation as an amalgamation of history of conversation
and the quality of the search results returned so far. Action space for the agent has been modeled
to enable it to assist the user with her search. To train our agent, we developed a virtual user model
which simulates the behavior of an actual search user. The user model was developed using query
and session log data from a major internet-based stock photography and digital assets marketplace.1
We assess the effectiveness of our agent by a) evaluating improvement in agent’s performance while
interacting with modeled user during training; b) conducting user testing with creative designers who
are consumers of the marketplace and collecting feedback on metrics like search effectiveness and
engagement.
The major contributions of this work are a) modeling a reinforcement learning based conversational
agent which assists users in asset search by making it convenient and interactive, and also boosting
some key metrics for the marketplace in the process (e.g. the number of asset downloads); b)
developing a virtual user model from search log data which is used for simulating a real user while
training the RL agent. This provides a methodology to carry out the training phase particularly when
real conversational data is unavailable.
The rest of the paper is organized as follows: Section 2 discusses related work. We describe our
proposed reinforcement learning model for conversational search and implementation details in
section 3 and section 4 respectively. Section 5 discusses the experiments conducted to evaluate our
proposed system followed by conclusion in section 6.

2

Related work

Building autonomous and intelligent conversational agents have been one of the most popular areas
of machine learning over the last decade. There have been various instances of such conversational
agents, as spoken dialogue systems [4, 13, 17] or text-based chat bots [5, 7, 8, 14, 16]. There have
been attempts to model the conversation problem as a goal-oriented task where the agent aims to
complete the given task by end of the conversation. Given this goal-oriented nature of the problem,
use of RL is proposed as the machine learning paradigm to train the conversational agent. The idea
has already been explored for designing an indoor wayfinding system [5] which assists the users
to navigate to their destination using text-based interface. The system integrates spatial knowledge
with dialogue management which enables the agent to adapt to a dynamic environment. In general,
designing such systems relies on modeling the states and features manually. To minimize human
intervention while providing input for training such agents in spoken dialogue systems, simulated
speech outputs have been used to bypass spoken language unit [4].
An alternate approach to modeling conversational agents is to use end-to-end dialog models which
are not restricted to any particular domain and save the effort of handcrafting the features. Neural
Conversational Model, based on the SEQ2SEQ (sequence to sequence) framework, has been proposed
that uses an encoder-decoder architecture to maximize the likelihood of next utterance, given the
previous utterances [14]. The resulting model is able to generate grammatically correct sentences
though they tend to lack consistency. The model prefers generic statements like "I don’t know"
over diverse statements which make it repetitive and less engaging. To make the model generate
consistent responses and adopt a specific persona, speaker-addressee models were incorporated within
SEQ2SEQ framework [7] which integrate speaker attributes into the target part of SEQ2SEQ model.
1

The marketplace aggregates sellers and buyers of digital assets like photographs, images, videos and vector
graphics through internet.

2

Despite these enhancements, the nature of the objective function is such that the model can not
capture the actual objective of performing coherent and meaningful conversation with real humans.
To overcome these issues, deep Reinforcement Learning has been combined with Neural Conversational Model to foster sustained conversations based on the long-term success of dialogues [8]. The
system uses LSTM based encoder-decoder model (like SEQ2SEQ framework) where its parameters
represent a policy which defines the probability of different utterances for next turn given the history of the conversation. Initial policy is decided on basis of maximum likelihood estimation [14].
These parameters are further tuned using policy gradient [12] through rewards to maximize ease of
answering, information flow and semantic coherence. This model tends to start a less relevant topic
and sometimes the dialogue generated repeats itself in a cycle. Automated rewards using heuristics
mentioned above do not capture every aspect of an ideal conversation. We have instead modeled
rewards manually considering different combinations of user and agent action history.
Domain independent reinforcement learning based dialogue system have been developed [13] which
uses User Satisfaction (US) as the sole criteria while modeling rewards disregarding Task Success(TS)
completely. User Satisfaction is a much harder and subjective metric to measure than Task Success
and requires annotating each turn of training dialogues for reward modeling. In contrast, we have
modeled our virtual user and the conversational agent using only the query and session log data alone
(which is readily available) without needing to annotate the existing data. Further, we have modeled
the extrinsic rewards with reward shaping in addition to TS while training our RL agent. There are
other RL based information seeking agents which aim to extract information from the environment
by sequentially asserting a minimal set of questions but these have not been designed and evaluated
on tasks involving human interaction in a search task [1].
Question answering systems are closely related to conversational agents where the task is to reason
over multiple statements to answer a query. Memory Networks [16] use memories to store context
internally in a compressed form for later use. The input sentences are sequentially mapped to a
feature space and stored in the memory. The final output is predicted first in the feature space by
choosing appropriate memory locations. This output is then translated to a natural language response
using an RNN. While these models are useful for designing chat based answering systems, they
alone are not sufficient to be used as conversational search agent since a conversational search is not
restricted to question answering and has an extended set of requirements.
End to end models are inherently difficult to evaluate due to the subjectivity involved in measuring
shortcomings and success of a dialogue [6]. A set of question answering specific tasks have been
developed to test the reasoning and deduction ability of dialogue systems [15]. These test beds
have been further extended to judge system performance on goal-oriented tasks such as providing
recommendations, issuing calls to a knowledge base etc [2, 6]. Our proposed system is not specific
to question answering only rather it guides the user with the goal of making search convenient.
Evaluation becomes much more complex for task oriented systems due to absence of any label which
tells whether the intended task had been completed or not. We have evaluated our system using
feedback from humans and also based on interactions with a simulated user model.
Since chat based search comprises a sequence of dialogue turns between a user and an agent,
success of conversation depends on sequence of agent actions. Recurrent neural networks (RNN)
have been successfully used in language modeling task where given an input sequence, the system
predicts the next word/sentence in the sequence. Such a system can be trained under supervised
learning framework [9] where the next word/sentence in the sequence is fed as target label. To make
conversational search an interactive process, along with returning the search results, our agent can
take several actions like encouraging the user to provide more context around their search. This might
give an impression that our problem could be broadly modeled as a sequence prediction problem where given the conversational history (sequence of actions), we try to predict the next best action.
Unfortunately, in the case of conversational search, no unique supervised labels can be provided to
determine fitness of different actions at any of the intermediate stages. Even if the final outcome label
describing success/failure of search is made available, it is difficult for the RNN model to capture
significance of each intermediate action and understand how they led to the final outcome.
Reinforcement Learning can provide an edge over RNN as under RL framework intermediate rewards
can be given to the agent based on state of conversational search and recent actions taken. The
agent can learn applicability of these actions through these intermediate rewards as well as the final

3

reward which it gets at the end of the search. We demonstrate the applicability of an RL agent which
interfaces with the end users using Natural Language Processing (NLP) and assists in asset search.

3

System model

The key aspect of our proposed architecture is the RL agent which receives user message parsed by a
natural language unit and then takes an action based on which a response to the user is generated. We
provide a brief overview of reinforcement learning paradigm followed by description of our model.
3.1

Reinforcement learning

Reinforcement Learning is based on training an agent to learn how to operate in an environment E. A
policy determines the choice of action the agent takes from an action set A after observing the state s
of the environment [11]. When the agent performs an action, state of the environment changes to
a new state and the agent gets a corresponding reward. An optimal policy maximizes cumulative
reward the agent gets based on the actions taken till the final absorbing state is reached.
The agent can be trained through Q-learning algorithm which consists of a Q-function. This function
maps every state-action pair to a Q-value which is a numerical measure of the long-term reward
the agent gets by taking a particular action in a given state. Q-learning learns these Q-values
iteratively through training over episodes. Suppose the agent takes an action a in state s such that the
environment makes a transition to a state s0 , the Q-value for the pair (s, a) is updated as follows:
Qi+1 (s, a) = (1 − α)Qi (s, a) + α(r + γmaxa0 Qi (s0 , a0 ))
where α is the learning rate, i refers to ith user dialogue in the episode, r is the immediate reward
for performing action a in state s. The Q-value for a state-action pair (s, a) is updated by taking a
weighted mean of its current value and a cumulative reward. This cumulative reward is the sum of
immediate reward r and discounted maximum value that can be obtained in the next state s0 . In our
case, an episode is one entire conversation between the user and the agent. In the subsequent sections,
we explain the state and action space modeling, followed by reward modeling in this scenario.
3.2

Agent action space

The agent action space A is defined as the set of all possible actions which the agent can take. Action
space is designed to enable the conversational agent to interact with the user and help her in searching
the desired assets conveniently through an interactive conversation. The set of agent actions can be
divided into two sets - the set of probe intent actions - P and general actions - G as described in Table
1 and Table 2 respectively.
Table 1: Probe intent actions
Action

Description

probe use case
probe to refine
cluster categories

ask about where assets will be used
ask the user to further refine query if less relevant search results are retrieved
ask the user to select from categorical options related to her query

The agent uses the probe intent actions P to explicitly query the user to learn more about her context.
For instance, the user may make a very open-ended query resulting in a very large and diverse set
of results even though none of them is a perfect match. In such scenarios, the agent may prompt
the user to refine her query or add some other details like where the search results would be used.
Alternatively, the agent may cluster the search results into different categories to aid the user in
drilling down with the search results. These actions carry the search forward and keep the user
engaged while helping to extract the user intent correctly even when the intent is not evident from the
search query.
4

Table 2: General actions
Action

Description

show results
add to cart
ask to download
ask to purchase
provide discount
sign up
ask for feedback
provide help
salutation

display results corresponding to most recent user query
suggest user bookmark assets for later reference
suggest user download some results if they suit her requirement
advise the user to buy some paid assets
offer special discounts to the user based on search history
ask the user to create an account to receive updates regarding her search
take feedback about the search so far
list possible ways in which the agent can assist the user
greet the user at the beginning; say goodbye when user concludes the search

The set G consists of generic actions like displaying assets retrieved corresponding to the user query,
providing help to the user etc. It also consists of actions which relate to promoting the business use
cases - prompting the user to download assets or prompting the user to sign up to receive the updates.
With both the probe actions and generic actions, if the user follows the agent’s suggestion, a positive
reward is given to the agent. Similarly, appropriate reward is given depending on the assessment
given by the user when inquired about feedback. Context of the conversation determines correctness
of different actions. An appropriate representation of the state of the conversation is a prerequisite for
an agent to learn fitness of different actions at different stages in the conversational search.
3.3

State space

The state space S is the set of conversation states observed by the agent. The agent performs an action
based on the state it perceives subsequent to a user dialogue. State representation has been modeled
to encapsulate facets of both search and conversation. The state s at some point in the conversation is
obtained using history of user actions - history_user,2 history of agent actions - history_agent,
discretized relevance scores of search results - score_results and a variable length_conv which
represents number of user responses in the conversation till that point.
The variables history_user and history_agent comprises of user and agent actions in last k turns
of the conversation respectively. They are modeled to capture context of the conversation as they
depict the sequence of actions taken by the user and the agent. These variables are essential to
delineate Q-values of different state-action pairs and to allow the agent to predict long-term outcome
of performing different actions based on the current state of the conversation. Experimentally chosen
value of k = 10 achieved a balance between the size of the state space and the average cumulative
reward earned by the trained system. Each user-action is represented as one-hot vector of length 7
(which is the number of unique user actions). Similarly, each agent-action has been represented as a
one-hot vector of length 12 (number of unique agent actions) The history of the last 10 user and agent
actions is represented as concatenation of these one-hot vectors. In case the current history is of less
than 10 turns, we use zero-vectors to represent the user and agent actions which are yet to take place.
The variable score_results quantifies the similarity between most recent query and the top 10 most
relevant search assets retrieved corresponding to the query. These similarity scores are normalised
(using the max and the min values) and binned into 5 classes. They have been taken in state
representation to incorporate the dependency between the relevance of probe intent actions and
quality of search results retrieved. Similarly, length_conv has been included since appropriateness
of other agent actions like sign up may depend on the duration for which the user has been searching.
All the variables in state representation take discrete values resulting in a discrete state space.
Message typed in the search space by the user is parsed by a rule-based natural language unit(NLU)
and mapped to the corresponding user action. This mapping is context dependent and is used to
instantiate history_user accordingly. Possible user actions have been discussed in Table 3.
2

history_user includes most recent user action to which agent response is pending in addition to remaining
history of user actions.

5

3.4

Rewards

Reinforcement Learning is concerned with training an agent in order to maximize some notion of
cumulative reward. In the domain of conversations, we realize that an action taken at time t might not
be the best action in the long run and involves a long term versus short term reward trade-off leading
to the classic exploration-exploitation trade-off. For example, if the user requests for more assets
corresponding to a query, the agent might take two actions, one which gives it an immediate reward
and another which does not yield an immediate reward but increases its cumulative reward later by
leading to better search. The agent might always show search results and if the user likes some of
those assets, the agent would get a positive reward. Alternatively, if the agent probes the user for her
use case and provides some options to choose from, the immediate reward might be less, however, the
reward in the long run will be more. The total reward which the agent gets in one complete dialogue
comprises of three kinds of rewards and can be expressed in the form of following equation :
P
Rtotal (dialogue) = RT C (dialogue) + t∈turns (Rextrinsic (t) + Rreward shaping (t))
First type is based on the completion of the task (Task Completion TC) which is purchase/download
in our case. The second reward setting is where we capture the response that the user gives subsequent
to an agent action in the form of instantaneous extrinsic rewards provided at every discrete time step.
These rewards are categorized as high, moderate or low depending on the state of conversation and
action taken by the user following an agent action. For example, if the agent prompts the user to add
an asset to the cart and the user does follow the prompt, the agent gets a high reward because the user
played along with the agent while if the user refuses, a low reward is given to the agent. A moderate
reward will be given if user adds to cart without agent’s prompt. These rewards ensure that the agent
is explicitly rewarded for taking steps towards Task Success and not just on Task Completion. Further,
the agent does not have to wait till the end of the episode to get the rewards.
The third reward setting is reward shaping which has been used to counter the problem of slowness
in convergence [10]. In this scheme, the extrinsic rewards from the environment are augmented
with additional rewards. These rewards are determined and provided at every turn in the dialogue
according to number of ‘click result’, ‘add to cart’, ‘download’ and ‘cluster category click’ options
exercised by the user till that turn in the dialogue. We have modeled all the rewards on a negative
scale preserving a relative order between them according to goodness/fitness of agent actions in the
context of the conversation.
3.5

Training RL agent

The RL agent is trained to learn the optimal action policy. Actions taken by the agent should assist
the user and must be coherent with respect to context of the conversation. Training the agent to learn
Q-values over the modeled states and actions requires actual conversations which are not available.
To bypass this issue, we propose a user model, that simulates a typical user, to train the agent.
3.5.1

User model

Conversational search data between the user and a search assistant is required to train the RL agent
during conversational episodes. Such data is not usually available as conversational agents are not
commonly deployed in the context of e-commerce search. Consequently, in order to bootstrap the
training process we designed a virtual human user to imitate a real human user for the search task.
We developed an environment comprising of a conversation setup for training the RL agent where a
modeled virtual human user responds to agent’s dialogue. The virtual human user has been modeled
using query sessions data from a major stock photography and digital asset marketplace which contain
information on queries made by real users, the corresponding clicks and other interactions with the
assets. This information has been used to generate a user which simulates human behavior while
searching and converses with the agent during training. We map every record in the query log to one
of user actions as depicted in Table 3. To simulate our virtual user, we used the query and session log
data of approximately 20 days.
The user is modeled as a finite state machine by extracting conditional probabilities - P (U ser Action
u| History h of U ser Actions). The probability can be computed by performing a statistical
analysis on the query and session log data. These probabilities are employed for sampling next
6

Table 3: Mapping between query logs and user actions
User action

Mapping used

new query

first query searched in a session or when most recent query searched
has no intersection with previous ones
query searched by user has some intersection with previous queries
clicking on next set of results for same query indicated by offset
field in log data
user clicking on search results being shown
when user adds some of searched assets to her cart for later reference
when user clicks on filter options like orientation or size, she is
essentially looking for a variation of her search query
when user searches for assets similar (having same series or model)
to those already being displayed

refine query
request more
click result
add to cart
cluster category click
search similar

user action given the fixed length history of her actions in a conversation while training. The agent
performs an action in response to the sampled user action. Subsequent to the action performed by the
agent, a sampled user action is used to determine the reward the agent gets for the action taken. Table
4 shows a snippet of conditional probability matrix of user actions given the history of last 3 user
actions.
Table 4: Snippet of conditional probability matrix obtained from session data on query logs
User action

User action history

Probability

Click assets
More assets
Refine query
add to cart

More assets, click assets, similar click
New query, refine query, add to cart
similar click, new query, new query
filter options, new query, filter options

0.41
0.13
0.40
0.01

The query and session log data has been taken from an asset search platform where the marketer
can define certain offers/promotions which kick in when the user takes certain actions (eg the user
views 10 or more assets created by an artist then the user is prompted to add some images to cart
(via a pop-up box). User’s response to such prompts on the search interface is used to model the
effect of RL agent on virtual user’s sampled action subsequent to different probe actions by the
agent. This ensures that our conditional probability distribution covers the whole probability space of
user behavior. Some agent actions such as greeting and providing help options cannot be modeled
using the data. Since they make the search process interactive without affecting the user behavior
significantly, their effect has not been incorporated in the user model design. These approximations
are made in order to train a bootstrapped model which can engage with and assist real users in their
search work flow. The data collected as part of conversations with real humans can be used to further
train the learning agent.

4

Implementation details

We developed a multi-component architecture to facilitate conversational search. It consists of chat
interface, Natural Language Unit (NLU), search engine and the RL agent. Figure 1 illustrates various
architectural components and flow of control between them during one dialogue turn in a conversation.
Details of these components have been discussed below.
4.1

Chat Interface

Chat interface comprises of a two-pane window, one for text dialogues and other for viewing search
results. The chat interface allows the user to convey queries in form of dialogue in an unrestricted
format. The user message is parsed by NLU which deduces user action from the input message. The
7

Figure 1: Architecture diagram(left) and chat-search interface(right)

NLU additionally obtains and redirects the query to search engine if the user action is new query
or ref ine query. User action and search engine output are forwarded to RL agent by NLU. The
RL agent performs an action according to the learned policy based on which a formatted response
is displayed on chat interface by the NLU. In addition to inputting the message, the chat interface
provides functionality for other user actions such as liking a search result, adding assets to cart etc.
4.2

Natural Language Unit

The NLU is a rule based unit which utilizes dependencies between words and their POS tags in
a sentence to obtain query and user action.3 The query is formulated sequentially by locating the
primary keyword and then determining the surrounding keywords. A distinction between the user
actions new query and ref ine query is made depending on whether the current primary keyword
is present in previous queries. A database is used to store the user queries to incorporate context of
conversation while formulating the search query to be sent to the search engine.
4.3

Search Engine

The search engine seeks assets from asset database corresponding to the search query formulated by
NLU. The asset database comprises of about 5 million assets of different types like images, videos etc.
Assets are indexed in asset database using tags and other metadata for retrieval during the search.4 .
The search engine also fetches and clusters assets having tags similar to most relevant assets retrieved
to formulate related categorical asset options. Relevance scores of retrieved assets are calculated on
the basis of the degree of match between asset metadata and the query. These scores are dispatched
with fetched assets and categorical options to the NLU.

5

Experiments and results

We evaluate the performance of our conversational agent with help of both the modeled user and
professional designers.
5.1

Evaluation using user model

At different time steps during the training, we measure the average cumulative reward obtained by
our agent, by simulating conversations between the agent and the modeled user. We show one such
instance of the conversation between the modeled user and our trained conversational agent.
User : I want images of computers <new query>
Agent : Some categories that we have related to your query are: mainframe computers, sleek
3

User the message is parsed using Stanford CoreNLP v3.6.0 toolkit available at http://stanfordnlp.
github.io/CoreNLP/other-languages.html
4
Assets are indexed using Apache Solr, a text-based search platform

8

computers, mobile computers, technology computers; click to select an option <cluster categories>
User : technology computers <cluster category click>
Agent : Where will you use these images? <probe use case>
User : i want to use them in my shop <refine query>
Agent : Results for your query <show results>
User : can you show me more images <request more>
Agent : You could add the images to your cart, click on the cart icon <add to cart>
User : no <negation>
Agent : Here are some of the images <show results>
User : more <request more>
Agent : Check out some images that we have <show results>
User : more <request more>
Agent : Signing up takes a moment, just give me your email id <sign up>
User : ABC@XYZ.com <affirmation>
Agent : Here you go, these are some of the best matches for your query <show results>
User : show some more images <request more>
Agent : Refine your query further to get better results <probe to refine>
User : people shop <refine query>
Along with each utterance, we have marked the current action of the user or the system with bold
text. The last action of the agent was to prompt the user to refine her query. Since the user actually
refined her query, the agent gets a positive reward. Alternatively, had the user ignored the prompt and
performed some other action, the agent would have received a negative reward.
In Figure 2, the cumulative reward gained by the agent in an episode is plotted (on the y-axis) against
number of training episodes (on the x-axis). The cumulative reward acquired increases with number
of episodes indicative of agent learning the optimal action policy. Improved cumulative reward per
episode also conveys improvement in quality of search since the agent could gain more rewards while
interacting with the virtual user through the search episode. Moreover, the training phase is equivalent
to a testing setting with the user simulator. We experimented with different values of learning rate
and discount factor and set their final values to 0.1 and 0.5 respectively based on experimental trends
in cumulative reward curve and sample conversation between the agent and the virtual user.
The state representation comprises of actions taken by the user and the agent in the last 10 dialogue
turns (10 actions each of the user and the agent). Since the user action space contains 7 unique
actions and the agent action space comprises of 12 unique actions, this leads to a vast search space
for the agent to learn over. Training over large number of episodic conversations are needed in
order to learn the Q-function effectively. We plotted the cumulative reward per episode against the
number of training episodes ranging from 500 to 20000 and experimentally determined 15000 as
the optimal number up to which the cumulative reward improved and reached a steady value. We
have used table storage method in which Q-values of different state-action pairs are updated through
Q-learning. Though our state-action space is vast and use of artificial neural networks have been
successful for approximating Q-values, we trained our model on large number of dialogues with
simulated user. After sufficient number of training dialogues the Q-values and cumulative reward per
episode converged. There is further scope of exploring neural network for approximating Q-value
function and comparing it with the table storage method.
5.2

Human evaluation

To evaluate the effectiveness of our system when interacting with professional designers, we created a
series of tasks for them to complete using both our conversational agent and search interface provided
by stock photography marketplace. The selected tasks are such that our evaluators (designers)
frequently perform these tasks as part of their jobs. The designers were asked to find images to
design a logo or a poster for either a Hollywood film review website or a 24-hour grocery store. The
search tool to be used - conversational agent vs the standard search interface - was also specified. We
collected feedback, from 10 designers, for both the search modalities across the different set of tasks.
In terms of evaluation metrics, we asked designers to compare the two systems subjectively in terms
of how fast, easy, interactive and engaging the search experience was. The designers rated our system
to be as fast, easy and effective as the standard search interface, provided by the stock market place,
while being more engaging.
9

Figure 2: Plot of cumulative reward per episode vs number of training episodes. Limiting value of
episodic cumulative reward is zero since all immediate rewards are modeled on a negative scale.

The evaluators were further asked to rate the quality of conversation with RL agent assisted search
interface objectively in terms of being helpful, friendly, robotic, incoherent and pushy. 60% evaluators
rated our conversational system to be helpful and 50% found it friendly while only 10% evaluators
found it incoherent and pushy. Effectively, we evaluated the agent’s performance in terms of (1)
information flow - ability to provide new and useful information to the user while maintaining the
context, without being repetitive and pushy and (2) ease of answering - the ease with which the user
can interact and respond to the agent. We note that 70% evaluators marked the system as robotic
which highlights the importance of generating variations in the agent’s responses. We intend to pursue
this aspect as a future work.
The designers are well versed with the use of conventional search interface making them a good choice
group for performing a thorough evaluation of our system. It should be noted that the designers are
used to the conventional search interface and were introduced to our conversational search interface
for the first time. Even then, the designers did not face any significant cognitive load when using the
new interface. This indicates that our conversational agent provides an easier and more engaging
workflow as an alternative to conventional search. Even though we bootstrapped training using
modeled user, our system learns to converse with actual users. This shows that Reinforcement
Learning is a very promising paradigm for enabling conversational search.

6

Conclusion

In this paper, we develop an end-to-end Reinforcement Learning based conversational agent to
interact with customers to help them search for images suited to their use-case. Though the system
is bootstrapped using a virtual user (as real conversational data is not usually available), our agent
performs at par with conventional search and makes the overall experience more interactive and
engaging. As the next step, we would deploy our system to capture true conversational data to fine
tune the system. There are several issues worthy of further research. The NLP and RL modules
can be integrated such that the template responses given by the agent can be replaced by generating
natural responses. By decoupling the reward mechanism for the RL agent from the natural language
response generation, we allow for improving the two systems independently. In this paper, we focus
only on the first part and the second part can be further explored. The design of state and action space
in RL problems takes significant time which also makes every situation an absolutely new task to
be solved. To approach this issue, another system can be designed which helps in the automation of
state space characterization with the help of system query logs.
10

References
[1] Philip Bachman, Alessandro Sordoni, and Adam Trischler. Towards information-seeking agents.
arXiv preprint arXiv:1612.02605, 2016.
[2] Antoine Bordes and Jason Weston. Learning end-to-end goal-oriented dialog. arXiv preprint
arXiv:1605.07683, 2016.
[3] Justine Cassell, Catherine Pelachaud, Norman Badler, Mark Steedman, Brett Achorn, Tripp
Becket, Brett Douville, Scott Prevost, and Matthew Stone. Animated conversation: rule-based
generation of facial expression, gesture & spoken intonation for multiple conversational agents.
In Proceedings of the 21st annual conference on Computer graphics and interactive techniques,
pages 413–420. ACM, 1994.
[4] Heriberto Cuayáhuitl. Simpleds: A simple deep reinforcement learning dialogue system. In
Dialogues with Social Robots, pages 109–118. Springer, 2017.
[5] Heriberto Cuayáhuitl and Nina Dethlefs. Spatially-aware dialogue control using hierarchical
reinforcement learning. ACM Transactions on Speech and Language Processing (TSLP), 7(3):5,
2011.
[6] Jesse Dodge, Andreea Gane, Xiang Zhang, Antoine Bordes, Sumit Chopra, Alexander Miller,
Arthur Szlam, and Jason Weston. Evaluating prerequisite qualities for learning end-to-end
dialog systems. arXiv preprint arXiv:1511.06931, 2015.
[7] Jiwei Li, Michel Galley, Chris Brockett, Georgios P Spithourakis, Jianfeng Gao, and Bill Dolan.
A persona-based neural conversation model. arXiv preprint arXiv:1603.06155, 2016.
[8] Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky. Deep
reinforcement learning for dialogue generation. arXiv preprint arXiv:1606.01541, 2016.
[9] Tomas Mikolov, Martin Karafiát, Lukas Burget, Jan Cernockỳ, and Sanjeev Khudanpur. Recurrent neural network based language model. In Interspeech, volume 2, page 3, 2010.
[10] Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In ICML, volume 99, pages 278–287,
1999.
[11] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction, volume 1.
MIT press Cambridge, 1998.
[12] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient
methods for reinforcement learning with function approximation. In Advances in neural
information processing systems, pages 1057–1063, 2000.
[13] Stefan Ultes, Paweł Budzianowski, Inigo Casanueva, Nikola Mrkšic, Lina Rojas-Barahona,
Pei-Hao Su, Tsung-Hsien Wen, Milica Gašic, and Steve Young. Domain-independent user
satisfaction reward estimation for dialogue policy learning. Proc. Interspeech 2017, pages
1721–1725, 2017.
[14] Oriol Vinyals and Quoc Le. A neural conversational model. arXiv preprint arXiv:1506.05869,
2015.
[15] Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart van Merriënboer,
Armand Joulin, and Tomas Mikolov. Towards ai-complete question answering: A set of
prerequisite toy tasks. arXiv preprint arXiv:1502.05698, 2015.
[16] Jason Weston, Sumit Chopra, and Antoine Bordes. Memory networks. arXiv preprint
arXiv:1410.3916, 2014.
[17] Tiancheng Zhao and Maxine Eskenazi. Towards end-to-end learning for dialog state tracking
and management using deep reinforcement learning. arXiv preprint arXiv:1606.02560, 2016.

11

