# CIRCLE: Multi-Turn Query Clarifications with Reinforcement Learning

Pierre Erbacher
Sorbonne Université
Paris, France
<EMAIL_ADDRESS>
&Laure Soulier
Sorbonne Université
Paris, France
<EMAIL_ADDRESS>

###### Abstract

Users often have trouble formulating their information needs into words on the
first try when searching online. This can lead to frustration, as they may
have to reformulate their queries when retrieved information is not relevant.
This can be due to a lack of familiarity with the specific terminology related
to their search topic, or because queries are ambiguous and related to
multiple topics. Most modern search engines have interactive features that
suggest clarifications or similar queries based on what others have searched
for. However, the proposed models are either based on a single interaction or
evaluated on search logs, hindering the naturalness of the interactions. In
this paper, we introduce CIRCLE, a generative model for multi-turn query
Clarifications wIth ReinforCement LEarning that leverages multi-turn
interactions through a user simulation framework. Our model aims at generating
a diverse set of query clarifications using a pretrained language model fine-
tuned using reinforcement learning. We evaluate it against well established
google suggestions using a user simulation framework.

##  1 Introduction

The recent advances in deep learning have fostered the Information retrieval
(IR) community to design more effective ranking models Khattab and Zaharia
(2020); Hofstätter et al. (2021). Although they rely on the notion of
semantics aiming at bridging the gap between the query and the document
vocabularies, the formulation of information needs into expressive and
complete queries remains a critical step for solving IR tasks. This is
particularly the case when the information need is complex or multi-faceted,
or either when the resulting query is ambiguous or vague. In parallel to the
cognitive aspect of the information modeling, one of the reason from the user
side might be the lack of knowledge and vocabulary associated to the searched
domain. Bhavnani (2001); White et al. (2008); Wildemuth (2004) show that users
searching information outside their expertise domain use under specified
queries, leading to less effective search results. Even when users are seeking
information in previously experienced search topics, users may still not be
able to express intent using the right vocabulary. Arguello et al. Arguello et
al. (2021) define the Tip of the Tongue Phenomenon (TOT) as the cognitive
state where users are unable to retrieve known items from memory, for example
names or words associated to the search intent, also leading to less effective
queries.

To tackle this issue, the IR community has focused its attention on the
understanding of users’ information needs, starting with post-hoc
reformulation methods and sliding more and more towards proactive interactive
approaches Dalton et al. (2020). Early approaches have investigated query
reformulation aiming at rewriting the query to improve the results returned by
a search engine by using more appropriate words Amati and Van Rijsbergen
(2002); Lavrenko and Croft (2001); Rocchio (1971); Zukerman and Raskutti
(2002); Nogueira et al. (2018); Lv and Zhai (2010); Pal et al. (2013);
Ermakova et al. (2016); Lavrenko and Croft (2017). However, these methods
assume the most probable topic for a query and does not always resolve the
ambiguity. Other strategies have been proposed in the reformulation process
such as the search/query diversification Agrawal et al. (2009); Cai et al.
(2016); Carbonell and Goldstein (1998); MacAvaney et al. (2021); Nogueira et
al. (2019c); Santos et al. (2010); Dang and Croft (2012) to increase the query
coverage or the leveraging of search history to infer user’s profile or
session context Matthijs and Radlinski (2011); Kong et al. (2015); Harvey et
al. (2013); Xiang et al. (2010); Bennett et al. (2012). But these approaches
might first frustrate the user with the release of top-ranked documents not
always relevant Wang and Zhu (2009) or be hindered with the user’s behavior’s
variability over time Zamani et al. (2020b).

Rather than reformulating queries or adapting ranking models to the user, a
promising approach is to include the user in the clarification process by
interacting with him/her thought clarifying questions or query suggestions
Aliannejadi et al. (2019); Erbacher et al. (2022a); Zamani et al. (2020a); Wu
et al. (2018a); Guo et al. (2011); Santos et al. (2012). While a lot of
progress as been made in this area, proposed work have multiple limitations.
They are limited to a single interaction turn Zamani et al. (2020a); Wu et al.
(2018a); Guo et al. (2011); Santos et al. (2012). Aliannejadi et al. (2019)
show the benefit of multi-turn clarification, however the method relies on
limited crowd-sourcing and predefined sequences of interactions for specific
topics. Very recently, Erbacher et al. (2022a) has proposed a simulation
framework enabling to model the interactions between the user and an IR system
aiming at clarifying questions and retrieving document rankings.

In this paper, we introduce a multi-turn query clarification model aiming at
generating new and diverse query suggestions between each interaction turn.
Our model relies on pre-trained language models and leverages both supervised
learning and reinforcement learning to clarify the initial query issued by the
user. More particularly, we fine-tune the language model with a policy at the
sequence generation level for predicting the next token in the sequence such
as in Ouyang et al. (2022). In addition, our policy contributes to the
generation of a set of clarification queries which are optimized to balance
diversity and effectiveness. Based on Erbacher et al. (2022a), we integrate
our multi-turn query clarification model into their proposed simulation
framework to mimic user-system interactions. It is worth noting that in such
framework we expect our model to embed a multi-turn level policy that
optimizes the trajectory over all interactions. We let this perspective for
future work since it will imply a very sparse reward, and training such policy
is more complex.

To show the benefit of multi-turn interactivity and evaluate the effectiveness
of our model, we conduct an experimental evaluation using the MS Marco dataset
in a simulated framework. We compare our results against well-established
search engines that can rely on logs of billions of users to construct query
suggestions.

Figure 1: Multi-turn Query clarification framework

##  2 Related Work

###  2.1 Query Clarifications

Interactive query clarification is a task that allows the user to be more
involved in the query refinement process by interacting with the system
Radlinski and Craswell (2017). Most modern search engines now assist the user
with clarification panels or query suggestions in order to help refine and
clarify their information need. While being referred to by different names in
the literature, these suggestions serve the same purpose: to provide
additional information to the user that may be relevant to their query. The
format of both is also similar, typically appearing as a list of options for
the user to choose from Zamani et al. (2020a); Wu et al. (2018b); Ding et al.
(2018a, b); Santos et al. (2012); Mustar et al. (2020). This task can also be
drawn as a multi-turn framework in which the user and the system interact
iteratively Radlinski and Craswell (2017); Zhang et al. (2020); Tang and Yang
(2019); Erbacher et al. (2022a); Aliannejadi et al. (2019); Dalton et al.
(2020). In the pioneering work Aliannejadi et al. (2019), the authors propose
a conversation framework that consists in iteratively selecting a clarifying
question at each conversation’s turn. The main drawback of this approach, is
that the conversation is defined a priori from (query/clarifying
questions/user answers) triplets, crowdsourced and restrained to a limited
number of topics. Zamani et al. Zamani et al. (2020a) propose to use
reformulation logs collected on real user to construct clarification panels.
For a given query, they consider the most probable terms added by users when
reformulating their queries. Additionally, they generate a clarifying
questions associated to the topic using a LM. However, this model only
consider one interaction with the user. Erbacher et al. Erbacher et al.
(2022a) address the multi-turn clarification framework involving a user
simulation to mimic user answer. However, suggestions are only generated based
on the initial user query and are not updated between interaction turns. This
means that the maximal search performance is limited by the diversity in the
pool. In our work, we do regenerate iteratively the set of query
clarifications based on previous user feedback. This means that we don’t rely
on a selection function as in Erbacher et al. (2022a) because our model can
generate sets of reasonable size.

###  2.2 Sequence level training

Learning from users interaction is becoming a hot machine learning paradigm in
IR. The community shows a growing interest for Reinforcement Learning (RL)
algorithms since IR systems deals with sequential interaction with users Zhang
et al. (2020); Montazeralghaem et al. (2020); Chandramohan et al. (2011); Chen
et al. (2019); Nogueira et al. (2019a); Tang and Yang (2019); Nogueira and Cho
(2017). For instance, in Nogueira et al. (2019a); Nogueira and Cho (2017), the
authors proposed to use reinforcement learning for query expansion, the model
was trained to maximize the expected recall of relevant documents. In Chen et
al. (2019), the authors used Reinforcement Learning to learn the user click
policy. In the context of language generation, RL can be used to adjust the
model’s output distribution to improve its performance on a specific task. One
of the main difficulties in training a language model from scratch with RL is
the large action space, this is why previous works used pretrained LM to
constrain the exploration Bahdanau et al. (2016); Ranzato et al. (2016);
Donati et al. (2021); Ziegler et al. (2019); Nogueira et al. (2019a); Nogueira
and Cho (2017); Ouyang et al. (2022). These methods are used for various NLP
task with non-differentiable automatic reward function. In Ranzato et al.
(2016), authors use automatic metrics BLEU Papineni et al. (2002) for
translation task. Some work also use human feedback to fine-tune their model
Ouyang et al. (2022); Ziegler et al. (2019). Authors fine-tuned a large LM
using Proximal Policy Optimization to generate better summarization according
to a reward model trained on real human feedback. Liu et al Liu et al. (2020)
proposed to fine-tune their LM to generate more diverse paraphrase. However,
in their work they use the ROUGE score between the generated sequences and a
reference sequence while in this work we use a fixed reference model as an
anchor. In this paper we use Reinforcement Learning to fine-tune the LM to
generate diverse sets of query suggestions. The model maximizes a
dissimilarity metric while being grounded to a reference model.

##  3 A generative model for multi-turn query clarification with reinforcement
learning

###  3.1 General overview

Our model, called CIRCLE, aims at generating a set of query clarifications
using reinforcement learning and is evaluated within the sequential
interaction framework proposed in Aliannejadi et al. (2019); Erbacher et al.
(2022a). This framework shown in the figure 1 consists in iteratively
proposing query suggestions to the user in response to his/her query. The user
feedback collected at each interaction step are used to generate the following
set of suggestions. A retrieval model can be launched at each interaction to
retrieve documents and evaluate the quality of the selected query. Formally,
let consider the user query as a sequence of token $x=w_{0},...,w_{t-1}$
sampled from a distribution of queries $D$, the goal is to learn a model using
policy $\pi(w_{t}|w_{t-1},...,w_{0})$ that completes the sequence $x$
producing the set of queries $Y=Y=\\{y_{1},...y_{K}\\}$. Queries are separated
with a $<sep>$ token in the sequence.

With this in mind, our model is based on the following intuitions:

  * •

Language models, well-known in the literature Radford et al. (2019), have
demonstrated their skills in generating sequences. We will therefore rely on
decoders to generate query clarifications on the basis of an initial
information need.

  * •

To provide choice to the user, we need to generate a set of query
clarifications. We leverage supervised pairs of (initial query-set of query
suggestions) to fine-tune the model to generate set of query clarifications in
an auto-regressive learning. In other words, decoder only architecture is
exploited to generate a sequence of tokens that expresses the sequence of
query clarifications, separated with a special token.

  * •

To force the diversity of the different generated query clarifications within
the sequence, we exploit reinforcement learning techniques estimating the
similarity between clarifications while maintaining the distribution near the
supervised model.

###  3.2 Query clarification Policy

The objective of our CIRCLE policy is to generate a set of query
clarifications which are both 1) grounded near the user query and 2) enough
diverse to let the user explore the potential universe of keywords able to
specify his/her need. To do so, our model is based on a reinforcement learning
approach designed on the top of a supervised Language Model (LM). It is worth
noting that the reinforcement learning approach is focused at the iteration
level to generate more diverse sets of query suggestions for each turn, but
does not embed a multi-turn level policy.

In what follows, we described these two components of our model.

Supervised LM learning

Numerous work heavily relies on LM and, particularly their decoding mechanism
to generate sets of sequences Vijayakumar et al. (2016); Yuan et al. (2018);
Meng et al. (2020); Holtzman et al. (2019); Ye et al. (2021). As LM are
initially trained on a large corpus to predict the next word, given previous
words in some text Radford et al. (2019) $P(w_{t}|w_{t-1},...,w_{0})$, they
manage to learn common pattern and word associations in natural languages. In
this work we propose to rely on a pretrained LM to fine-tune it to complete
sequences of queries. Following Yuan et al. (2018), our objective is to fine-
tune the pretrained LM to generate sequences of query suggestions
$Y=\\{y_{1},...y_{K}\\}$ given an input query $x$ using the cross-entropy
loss. Query suggestions are separated with a $<sep>$ token in the sequence. In
this work we use a decoder only architecture, this means that the sequence can
be written: $x<sep>y_{1}<sep>...y_{K}$

Despite various decoding tricks already used in the literature Vijayakumar et
al. (2016); Holtzman et al. (2019), generating set of sequences using LM
decoders suffer from the lack of diversity within the generated set as new
decoded sequences are not conditioned on other previously decoded sequences.
We present in what follows our strategy to control the diversity of generated
query clarification set by using reinforcement learning.

Reinforcement Learning. To improve the diversity of generated suggestions, the
language model is also fine-tuned using the proximal policy optimization (PPO)
Schulman et al. (2017) algorithm to maximize the expected reward $R$. Given a
state $s_{t}=(w_{t-1},...,w_{0})$ the policy predicts the next token $w_{t}$
maximizing the expected reward:

$\mathbb{E}_{\pi}(R)=\mathbb{E}_{x\sim D,Y\sim\pi(.|x)}[R(x,Y)]$ (1)

With $R$ the reward function and $\pi$ the policy, $x$ the user query and
$Y=\\{y_{1},...y_{K}\\}$ the set of query suggestions.

The value function (critic) used in PPO is initialized to the parameters of
the reference model. However, the last linear layer is randomly initialized.
For each state, this model predicts a value $V(s_{t})$ used to compute an
estimation of the advantage function $A=R(x,Y)-V(s_{t})$. The critic is
optimized to minimize the following loss function:

$L_{v}=\sum^{T}_{t=0}|R(x,Y)-V(s_{t})|^{2}$ (2)

Using PPO the policy objective is written:

$\displaystyle L_{\pi}$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\pi}[min(A(w_{t},s_{t})\frac{\pi(w_{t}|s_{t})}{\pi_{\text{old}(w_{t}|s_{t})}},$
$\displaystyle
A(w_{t},s_{t})clip(1-\epsilon,\frac{\pi(w_{t}|s_{t})}{\pi_{\text{old}(w_{t}|s_{t})}},1+\epsilon))]$

Note that, PPO smooths the policy $\pi$ update by constraining it to be close
to the previous policy $\pi_{\text{old}}$ by clipping the gradients.

In this work, we want to improve the diversity in the set generated of our
supervised model. For this purpose, the reward function used in this work is
composed of 2 parts:

  * •

$r(x,Y)$ :Following Liu et al. (2020) we compute the dissimilarity between
between generated queries in the set:

$r=-\sum_{y_{i}\in\hat{Y}}\sum_{y_{j}\in\\{\hat{Y}\setminus
y_{i}\\}}sim(y_{i},y_{j})$ (4)

where $sim$ is a similarity metric computed between queries described in 7 .

  * •

The second part ensures that the policy stays near the supervised model. For
this, we follow Stiennon et al. (2020), and add a KL term that penalizes the
divergence between the policy $\pi$ and the reference model $\pi^{ref}$. This
KL regularization makes sure the policy stays grounded near a fixed reference
model. This guaranties that generated sequences by the policy are not far from
generated sequences from the reference model. Otherwise, our model would
likely generate diverse but random sequences. The reward function can be
written as:

$R(x,Y)=r(x,Y)-\beta\log[\frac{\pi^{RL}(Y|x)}{\pi^{ref}(Y|x)}]$ (5)

###  3.3 Model training and inference

Figure 2: Fine-tuning GPT2 with PPO

The figure 2 shows the training of CIRCLE. The training is composed of 3 main
steps:

  1. 1.

Conditioned on the initial user query, the policy generates a trajectory,
namely a sequence containing multiple queries. Queries are chained with
$<sep>$ token. We control the number of generated queries using stopping
criteria counting the number of $<sep>$ token.

  2. 2.

The reward is computed using the equation 5.

  3. 3.

The generated sequence is feed into the reference model and the policy.
Resulting log-probabilities and reward are used to update the policy using PPO
using the equations 2 and 3.2

During evaluation, the model is conditioned on the user query but also on the
suggestions selected by the user at each interaction turn. This means that at
each step $i$ the model complete the following sequence:

$\text{input: }<bos>x<sep>y_{1}^{+}<sep>...y_{i}^{+}$

with $q_{t=1}^{+}$ the selected query at step $i$ and $x$ the initial user
query.

##  4 Evaluation protocol

The goal of this paper is to show that improving the diversity in the queries
suggested to the user helps cover a wider range of topics and therefore better
helps in the clarification process. To do so, the effectiveness of different
models is evaluated in terms of how much they improve search performance in a
multi-turn clarification framework. Therefore, we rely on classic IR metrics
to evaluate these models. The user’s actions are simulated based on various
hypothesis.

###  4.1 Dataset

The experiment is conducted on MS Marco 2020 passages Nguyen et al. (2016)
which is an open domain datasets regrouping 8.8M passages and more than 500K
Query-Passage relevance pairs. As Nogueira et al. (2019b), we trained our
model on the train set of Msmacro and evaluate our model on a subset of the
dev set (1200 queries sampled from 59 000).

###  4.2 Metrics

In accordance to the evaluation objectives, we rely on IR metrics to assess
the effectiveness of the model in the multi-turn clarification framework but
also to assess the diversity of proposed suggestions, we define different
metrics.

$\bullet$ To measure the quality of the selected query clarification, we
evaluate the effectiveness of document ranking issued from this query using
the well-known Mean Reciprocal Rank (MRR).

$\text{MRR}=\frac{1}{|Y|}\sum^{|Y|}_{i}\frac{1}{\text{rank}_{i}}$ (6)

with $\text{rank}_{i}$ the position of the first relevant document for the
query $y_{i}\in Y$

$\bullet$ To measure the similarity between document rankings at different
iterations, we rely on the Rank-Biased Overlap (RBO) Webber et al. (2010).
This measures the similarity between incomplete and non-conjoint rankings and
also values more heavily top ranked document. The more diverse the rankings
are, the lower the score is.

$\text{RBO}(S,T,p)=(1-p)\sum^{\infty}_{d=1}p^{d-1}.A_{d}$ (7)

With S, T are two document rankings, d is the actual depth of the ranking.
$A_{d}$ expresses the agreement (the size of the intersection of both ranking)
at depth $d$: $A_{d}=\frac{|S_{:d}\cap T_{:d}|}{d}$ . $p$ determines the
weight given the top ranked document.

###  4.3 User Simulation

Because real human feedback is time-consuming and costly, the information
retrieval community often relies on user simulation to train or evaluate
models Erbacher et al. (2022b); Eckert et al. (1997); Komatani et al. (2005);
Pietquin (2004); Schatzmann et al. (2006); Scheffler and Young (2000). We
therefore design user simulation based on hypothesis that users does not
always fully cooperate with IR systems. For instance a user may not know what
suggestions might help. The goal is not to have realist behavior but to see
the robustness and the limits of the proposed model. The proposed user
simulation follows an epsilon greedy policy in which the user chooses a random
action with a probability epsilon, and chooses the best known action with
probability $1-\epsilon$. The $\epsilon$ parameter enables a wide range of
different possible user behaviors from the most cooperative user to the most
random user.

It is worth noting that in our evaluation framework the user do not have stop
criteria to end the search session. This allows us to observe all possible
scenarios and record performance at every interaction turn. Moreover, we do
not take into account the position bias that would be inducted by the position
of the suggestions when presented to the user.

###  4.4 Baselines

We evaluated various methods to generate sets of query clarifications. These
baselines are tested under different scenarios following the evaluation
framework described in previous sections.
Google suggestions: Suggestions generated by Google search engine through
their public API. Because google suggestions only rely on the previous
considered query. We mimic multi-turn interaction by iteratively switching the
previous query with the selected query by the user. Depending on the queries’
specificity, between 1 and 10 google suggestions are proposed. We report the
mean number of suggestions in the table 1. The suggestions also depends on the
language and the geographic location. In this work we use English for the
United States. This can be considered as a strong baseline, thanks to its
billions of users logs and feedback 111How Google autocomplete works in
Search: https://blog.google/products/search/how-google-autocomplete-works-
search/. However, we do acknowledge that the performance of these suggestions
might be truncated because these suggestions are not specific for the Msmarco
corpus and might be affected by current trends.
Interact+Kmean: This is the multi turn model proposed by Erbacher et al.
(2022a). We evaluated this model using the K-mean selection mechanism as
suggested by the authors, selecting the best 2 ranked queries from different
cluster in the pool of 64 queries.
Beam search: We fine-tuned a GPT2 model to perform one to one reformulations.
We use beam search to generate a set of query suggestions.
Supervised: we use a GPT2 fine-tuned using supervised learning to complete
sequences of queries. This model was trained on Google Suggestions collected.
This baseline is the supervised version of our CIRCLE model without the
reinforcement learning fine-tuning.
CIRCLE: The overall version of our model, including the fine-tuning using
Reinforcement Learning to leverage more diverse sets of query suggestions.

###  4.5 Implementation details

For the IR model, we opted for a Bert-base Dense retrieval model Hofstätter et
al. (2021). This model was trained on Msmarco-passages to maximize the dot
product between queries and their associated relevant passages. We used this
model to compute documents embeddings. Embeddings are stored and indexed using
Faiss HSWN32 index Johnson et al. (2021). We used the pretrained GPT2 provided
by Wolf et al. (2019). The same model is used to compute queries embeddings.
For supervised learning we used a learning rate of $lr=2e^{-}5$ with batch
size of 128. We trained the model on 3 epochs. For finetuning with
reinforcement learning we use a learning rate of $lr=0.8e^{-}6$ with batch
size of 128. The exploration is constrained to $top_{p}=0.9$ and $top_{k}=20$.
We use $\beta=0.01$ and a clip ratio $\epsilon=0.1$. The similarity metric
used is the RBO 7. We use greedy decode the circle model using greedy
decoding. We used $p=0.9$ in the RBO metrics. This means that the first ten
documents are weighting for $85\%$ of the overall score.

##  5 Results

In this section, we report results that were assessed by following the
evaluation protocol described above.

###  5.1 Retrieval Performance

In the table 1, we report IR scores of different approaches to generate sets
of suggestions on a subset of the devset of Msmsarco passages. We set the user
fully cooperative ($\epsilon=0$). Models are evaluated using the MRR metric
(Equation 6).

i=0 (No interaction) i=1 i=2 i=3 i=4 i=5 User Query 0.2419 - - - - - Google
Suggestions k = $\sim$(7.5/5.4/5.3/5.3/4.7) 0.2419 0.3820 0.3997 0.4034 0.4043
0.4049 Interact+Kmean Erbacher et al. (2022a)/ k=2 (Kmean 64) 0.2419 0.1990
0.2195 0.2370 0.2478 0.2551 Beam Search k = 2 0.2419 0.2108 0.1872 0.1636
0.1536 0.1467 Beam Search k = 4 0.2419 0.3169 0.2686 0.2573 0.2457 0.2434 Beam
Search k = 8 0.2419 0.3740 0.3469 0.3416 0.3295 0.3259 Supervised k = 2 0.2419
0.2859 0.3017 0.3080 0.3074 0.3102 Supervised k = 4 0.2419 0.3030 0.3298
0.3350 0.3357 0.3354 Supervised k = 8 0.2419 0.3224 0.3614 0.3654 0.3649
0.3660 CIRCLE k = 2 0.2419 0.2824 0.3063 0.3174 0.3277 0.3290 CIRCLE k = 4
0.2419 0.3006 0.3250 0.3478 0.3614 0.3734 CIRCLE k = 8 0.2419 0.3244 0.3555
0.3737 0.3844 0.3889

Table 1: Effectiveness results on the subset of MS Marco passage 2020 dev set
(1200 queries - 1 relevant document per query), k the size of the set of
suggestions for interaction.

###  5.2 Suggestions Coverage

In this section, we analyze the coverage of proposed suggestions models. To
analyze this, we compute the mean similarity between ranking associated to
each suggestion using the RBO metric (Equation 7).

| Google Suggestions k = 5.64 | Beam search k=8 | Supervised k=8 | CIRCLE k=8
---|---|---|---|---
Mean RBO | 0.3243 | 0.3610 | 0.3998 | 0.3604

Table 2: This table shows the mean ranking similarity between different model
suggestions. The metric used is the RBO. The more diverse the rankings are,
the lower the score is.

###  5.3 Impact of user cooperation

In this section we assess performance of the Google suggestions and CIRCLE
interacting with non-perfect user. The objective is to observe the robustness
of models with variable feedback quality. The user is following a greedy
epsilon policy with epsilon ranging from $0.0$ to $0.5$.

Figure 3: Google suggestions: Impact of the interactions with various user
hypothesis on the system efficiency. The observed score is the MRR@1000.
Figure 4: CIRCLE: Impact of the interactions with various user hypothesis on
the system efficiency. The observed score is the MRR@1000.

##  6 Results Analysis

In the table 1, we see that Google suggestions are a strong baseline for this
task. With only an average of $5.64$ query suggestions it manages to reach a
MRR of $0.4049$. For $k=8$ , the beam search manage to reach a MRR of $0.3740$
in the first interaction. However, the score decreased with each subsequent
interaction. This can be explained because the model takes as input only the
last selected query and therefore the model generation can diverge if
generated queries are less efficient than in the previous turn and because the
user always select one of the generated queries. CIRCLE manage to improve the
mean score from $0.3244$ in the first interaction to $0.3889$ in the last
interaction. Against $0.3224$ to $0.3660$ for the supervised model. This means
that the additional RL fine-tuning was beneficial to improve the overall
performance. The table 2 shows that Google suggestions have a good coverage of
possible user needs with a mean RBO of $0.3243$ while proposing only an
average of $5.64$ query suggestions. Surprisingly, the beam search also has a
good coverage with a RBO of $0.3610$. We can see that the RL fintuning improve
the mean RBO between the supervised and CIRCLE. CIRCLE and the beam search
have sensibly the same RBO. We can see in the figures 3 and 4 that none of the
proposed model is robust to non-cooperative user. We observe that our model is
abit more resilient with a non fully-cooperative user. This is explained
because our model takes as input all the sequence of previously selected
queries including the initial user query. Whereas google suggestions and beam
search only consider the last selected query as input. This means that when
the user select a query not-relevant for his/her information need, the new
generated suggestions diverges from the initial user query.

##  7 Conclusion and perspectives

In this work, we consider the multi-turn interactive query clarification
problem for information retrieval. We propose CICRLE, a gpt2 model that
generates a sequence of queries suggestions conditionally to one or several
queries. By using reinforcement learning, we manage to increase the set
diversity compared to the supervised model. Additionally, this model completes
sequences composed of past feedback (selected queries) to generate new sets of
queries iteratively, showing the benefit of multi-turn clarification. We
especially when with non non-perfect user, relative to google suggestions.
However, there are several downsides: the proposed model is far from Google
suggestions performances, and it requires several interactions with the user
to perform better than the beam search. Additionally, the proposal model does
not embed strategy at interaction level, and was not optimized on any user
behavior or IR metrics. There are several ways this work can be extended.
1)The policy can be trained to maximize a utility function with multi turn
interaction with the user. The quality of interaction between user/system
could benefit strongly. However, the main difficulties are that the rewards
are very sparse, and incorporating interaction feedback in the model is
challenging during the training. 2)The performance of the model may be
improved by using a loss invariant to queries permutation during supervised
training. Note that we tried to reproduce the method in Ye et al. (2021) and
apply it with a pretrained LM on query suggestions task. However, we were not
able to control the language model generation with the control code without
deteriorating the generation quality. 3)The model can be extended to leverage
search session or multi-facets information needs. Generated suggestions based
on multiple user information needs and therefore multiple queries requiring
user simulation to mimic search session Câmara et al. (2022).

## References

  * Agrawal et al. (2009) Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong. 2009.  Diversifying search results.  In _Proceedings of the Second ACM International Conference on Web Search and Data Mining_ , WSDM ’09, page 5–14, New York, NY, USA. Association for Computing Machinery.
  * Aliannejadi et al. (2019) Mohammad Aliannejadi, Hamed Zamani, Fabio Crestani, and W. Bruce Croft. 2019.  Asking clarifying questions in open-domain information-seeking conversations.  In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR’19, page 475–484, New York, NY, USA. Association for Computing Machinery.
  * Amati and Van Rijsbergen (2002) Gianni Amati and Cornelis Joost Van Rijsbergen. 2002.  Probabilistic models of information retrieval based on measuring the divergence from randomness.  _ACM Trans. Inf. Syst._ , 20(4):357–389.
  * Arguello et al. (2021) Jaime Arguello, Adam Ferguson, Emery Fine, Bhaskar Mitra, Hamed Zamani, and Fernando Diaz. 2021.  Tip of the tongue known-item retrieval: A case study in movie identification.  In _Proceedings of the 2021 Conference on Human Information Interaction and Retrieval_ , CHIIR ’21, page 5–14, New York, NY, USA. Association for Computing Machinery.
  * Bahdanau et al. (2016) Dzmitry Bahdanau, Philemon Brakel, Kelvin Xu, Anirudh Goyal, Ryan Lowe, Joelle Pineau, Aaron C. Courville, and Yoshua Bengio. 2016.  An actor-critic algorithm for sequence prediction.  _CoRR_ , abs/1607.07086.
  * Bennett et al. (2012) Paul N. Bennett, Ryen W. White, Wei Chu, Susan T. Dumais, Peter Bailey, Fedor Borisyuk, and Xiaoyuan Cui. 2012.  Modeling the impact of short- and long-term behavior on search personalization.  In _SIGIR ’12_.
  * Bhavnani (2001) Suresh K. Bhavnani. 2001.  Important cognitive components of domain-specific search knowledge.  In _Proceedings of The Tenth Text REtrieval Conference, TREC 2001, Gaithersburg, Maryland, USA, November 13-16, 2001_ , volume 500-250 of _NIST Special Publication_. National Institute of Standards and Technology (NIST).
  * Cai et al. (2016) Fei Cai, Ridho Reinanda, and Maarten De Rijke. 2016.  Diversifying query auto-completion.  _ACM Trans. Inf. Syst._ , 34(4).
  * Câmara et al. (2022) Arthur Câmara, David Maxwell, and Claudia Hauff. 2022.  Searching, learning, and subtopic ordering: A simulation-based analysis.  _CoRR_ , abs/2201.11181.
  * Carbonell and Goldstein (1998) Jaime Carbonell and Jade Goldstein. 1998.  The use of mmr, diversity-based reranking for reordering documents and producing summaries.  In _Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’98, page 335–336, New York, NY, USA. Association for Computing Machinery.
  * Chandramohan et al. (2011) Senthilkumar Chandramohan, Matthieu Geist, Fabrice Lefèvre, and Olivier Pietquin. 2011.  User Simulation in Dialogue Systems using Inverse Reinforcement Learning.  In _Interspeech 2011_ , pages 1025–1028, Florence, Italy.
  * Chen et al. (2019) Xinshi Chen, Shuang Li, Hui Li, Shaohua Jiang, Yuan Qi, and Le Song. 2019.  Generative adversarial user model for reinforcement learning based recommendation system.  In _ICML_ , volume 97 of _PMLR_ , pages 1052–1061. PMLR.
  * Dalton et al. (2020) Jeffrey Dalton, Chenyan Xiong, Vaibhav Kumar, and Jamie Callan. 2020.  _CAsT-19: A Dataset for Conversational Information Seeking_, page 1985–1988. Association for Computing Machinery, New York, NY, USA.
  * Dang and Croft (2012) Van Dang and W. Bruce Croft. 2012.  Diversity by proportionality: An election-based approach to search result diversification.  In _Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’12, page 65–74, New York, NY, USA. Association for Computing Machinery.
  * Ding et al. (2018a) Heng Ding, Shuo Zhang, Darío Garigliotti, and Krisztian Balog. 2018a.  Generating high-quality query suggestion candidates for task-based search.  In _Advances in Information Retrieval_ , pages 625–631, Cham. Springer International Publishing.
  * Ding et al. (2018b) Heng Ding, Shuo Zhang, Darío Garigliotti, and Krisztian Balog. 2018b.  Generating high-quality query suggestion candidates for task-based search.  _CoRR_ , abs/1802.07997.
  * Donati et al. (2021) Alice Martin Donati, Guillaume Quispe, Charles Ollion, Sylvain Le Corff, Florian Strub, and Olivier Pietquin. 2021.  Learning natural language generation from scratch.  _CoRR_ , abs/2109.09371.
  * Eckert et al. (1997) Wieland Eckert, Esther Levin, and Roberto Pieraccini. 1997.  User modeling for spoken dialogue system evaluation.  In _IEEE_ , pages 80–87. IEEE.
  * Erbacher et al. (2022a) Pierre Erbacher, Ludovic Denoyer, and Laure Soulier. 2022a.  Interactive query clarification and refinement via user simulation.  sigir.
  * Erbacher et al. (2022b) Pierre Erbacher, Laure Soulier, and Ludovic Denoyer. 2022b.  State of the art of user simulation approaches for conversational information retrieval.  _CoRR_ , abs/2201.03435.
  * Ermakova et al. (2016) Liana Ermakova, Josiane Mothe, and Elena Nikitina. 2016.  Proximity relevance model for query expansion.  In _Proceedings of the 31st Annual ACM Symposium on Applied Computing_ , SAC ’16, page 1054–1059, New York, NY, USA. Association for Computing Machinery.
  * Guo et al. (2011) J. Guo, Xueqi Cheng, Gu Xu, and Xiaofei Zhu. 2011.  Intent-aware query similarity.  In _CIKM ’11_.
  * Harvey et al. (2013) Morgan Harvey, Fabio A. Crestani, and Mark James Carman. 2013.  Building user profiles from topic models for personalised search.  _Proceedings of the 22nd ACM international conference on Information & Knowledge Management_.
  * Hofstätter et al. (2021) Sebastian Hofstätter, Sheng-Chieh Lin, Jheng-Hong Yang, Jimmy Lin, and Allan Hanbury. 2021.  _Efficiently Teaching an Effective Dense Retriever with Balanced Topic Aware Sampling_, page 113–122. Association for Computing Machinery, New York, NY, USA.
  * Holtzman et al. (2019) Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. 2019.  The curious case of neural text degeneration.  _CoRR_ , abs/1904.09751.
  * Johnson et al. (2021) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021.  Billion-scale similarity search with gpus.  _IEEE Transactions on Big Data_ , 7(3):535–547.
  * Khattab and Zaharia (2020) Omar Khattab and Matei Zaharia. 2020.  _ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT_, page 39–48. Association for Computing Machinery, New York, NY, USA.
  * Komatani et al. (2005) Kazunori Komatani, Shinichi Ueno, Tatsuya Kawahara, and Hiroshi G. Okuno. 2005.  User modeling in spoken dialogue systems to generate flexible guidance.  In _User Modelling and User-Adapted Interaction_ , volume 15, pages 169–183. Springer.
  * Kong et al. (2015) Weize Kong, Rui Li, Jie Luo, Aston Zhang, Yi Chang, and James Allan. 2015.  Predicting search intent based on pre-search context.  In _Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’15, page 503–512, New York, NY, USA. Association for Computing Machinery.
  * Lavrenko and Croft (2001) Victor Lavrenko and W. Bruce Croft. 2001.  Relevance based language models.  In _Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’01, page 120–127, New York, NY, USA. Association for Computing Machinery.
  * Lavrenko and Croft (2017) Victor Lavrenko and W. Bruce Croft. 2017.  Relevance-based language models.  _SIGIR Forum_ , 51(2):260–267.
  * Liu et al. (2020) Mingtong Liu, Erguang Yang, Deyi Xiong, Yujie Zhang, Yao Meng, Changjian Hu, Jinan Xu, and Yufeng Chen. 2020.  A learning-exploring method to generate diverse paraphrases with multi-objective deep reinforcement learning.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 2310–2321, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Lv and Zhai (2010) Yuanhua Lv and ChengXiang Zhai. 2010.  Positional relevance model for pseudo-relevance feedback.  In _Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’10, page 579–586, New York, NY, USA. Association for Computing Machinery.
  * MacAvaney et al. (2021) Sean MacAvaney, Craig Macdonald, Roderick Murray-Smith, and Iadh Ounis. 2021.  Intent5: Search result diversification using causal language models.  _CoRR_ , abs/2108.04026.
  * Matthijs and Radlinski (2011) Nicolaas Matthijs and Filip Radlinski. 2011.  Personalizing web search using long term browsing history.  WSDM ’11, page 25–34, New York, NY, USA. Association for Computing Machinery.
  * Meng et al. (2020) Rui Meng, Xingdi Yuan, Tong Wang, Sanqiang Zhao, Adam Trischler, and Daqing He. 2020.  An empirical study on neural keyphrase generation.  _CoRR_ , abs/2009.10229.
  * Montazeralghaem et al. (2020) Ali Montazeralghaem, Hamed Zamani, and James Allan. 2020.  A Reinforcement Learning Framework for Relevance Feedback.  In _SIGIR_ , page 59–68.
  * Mustar et al. (2020) Agnès Mustar, Sylvain Lamprier, and Benjamin Piwowarski. 2020.  Using BERT and BART for Query Suggestion.  In _Joint Conference of the Information Retrieval Communities in Europe_ , volume 2621 of _CEUR Workshop Proceedings_ , Samatan, France. CEUR-WS.org.
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  MS MARCO: A human generated machine reading comprehension dataset.  _CoRR_ , abs/1611.09268.
  * Nogueira et al. (2018) Rodrigo Nogueira, Jannis Bulian, and Massimiliano Ciaramita. 2018.  Learning to coordinate multiple reinforcement learning agents for diverse query reformulation.  _CoRR_ , abs/1809.10658.
  * Nogueira et al. (2019a) Rodrigo Nogueira, Jannis Bulian, and Massimiliano Ciaramita. 2019a.  Multi-agent query reformulation: Challenges and the role of diversity.  In _DeepRLStructPred@ICLR_.
  * Nogueira et al. (2019b) Rodrigo Nogueira, Wei Yang, Kyunghyun Cho, and Jimmy J. Lin. 2019b.  Multi-stage document ranking with bert.  _ArXiv_ , abs/1910.14424.
  * Nogueira et al. (2019c) Rodrigo Frassetto Nogueira, Jannis Bulian, and Massimiliano Ciaramita. 2019c.  Multi-agent query reformulation: Challenges and the role of diversity.  New Orleans, Louisiana, United States.
  * Nogueira and Cho (2017) Rodrigo Frassetto Nogueira and Kyunghyun Cho. 2017.  Task-oriented query reformulation with reinforcement learning.  _CoRR_ , abs/1704.04572.
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. 2022.  Training language models to follow instructions with human feedback.  _ArXiv_ , abs/2203.02155.
  * Pal et al. (2013) Dipasree Pal, Mandar Mitra, and Kalyankumar Datta. 2013.  Query expansion using term distribution and term association.  _CoRR_ , abs/1303.0667.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: A method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting on Association for Computational Linguistics_ , ACL ’02, page 311–318, USA. Association for Computational Linguistics.
  * Pietquin (2004) Olivier Pietquin. 2004.  _A Framework for Unsupervised Learning of Dialogue Strategies_.  Ph.D. thesis, Faculté Polytechnique de Mons, TCTS Lab (Belgique).
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Radlinski and Craswell (2017) Filip Radlinski and Nick Craswell. 2017.  A theoretical framework for conversational search.  In _Proceedings of the 2017 Conference on Conference Human Information Interaction and Retrieval_ , CHIIR ’17, page 117–126, New York, NY, USA. Association for Computing Machinery.
  * Ranzato et al. (2016) Marc’Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba. 2016.  Sequence level training with recurrent neural networks.  In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_.
  * Rocchio (1971) Joseph John Rocchio. 1971.  Relevance feedback in information retrieval.  _Gerard Salton, editor, The SMART Retrieval System - Experiments in Automatic Document Processing_ , pages 313–323.
  * Santos et al. (2012) Rodrygo L. T. Santos, Craig MacDonald, and Iadh Ounis. 2012.  Learning to rank query suggestions for adhoc and diversity search.  _Information Retrieval_ , 16:429–451.
  * Santos et al. (2010) Rodrygo L.T. Santos, Craig Macdonald, and Iadh Ounis. 2010.  Exploiting query reformulations for web search result diversification.  In _Proceedings of the 19th International Conference on World Wide Web_ , WWW ’10, page 881–890, New York, NY, USA. Association for Computing Machinery.
  * Schatzmann et al. (2006) Jost Schatzmann, Karl Weilhammer, Matt Stuttle, and Steve Young. 2006.  A Survey of Statistical User Simulation Techniques for Reinforcement-Learning of Dialogue Management Strategies.  _The Knowledge Engineering Review_ , pages 0–1.
  * Scheffler and Young (2000) Konrad Scheffler and Steve Young. 2000.  Probabilistic simulation of human-machine dialogues.  In _ICASSP, IEEE_ , volume 2, pages 1217–1220. IEEE.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_.
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021.
  * Tang and Yang (2019) Zhiwen Tang and Grace Hui Yang. 2019.  Dynamic search - optimizing the game of information seeking.  _CoRR_ , abs/1909.12425.
  * Vijayakumar et al. (2016) Ashwin K. Vijayakumar, Michael Cogswell, Ramprasaath R. Selvaraju, Qing Sun, Stefan Lee, David J. Crandall, and Dhruv Batra. 2016.  Diverse beam search: Decoding diverse solutions from neural sequence models.  _CoRR_ , abs/1610.02424.
  * Wang and Zhu (2009) Jun Wang and Jianhan Zhu. 2009.  Portfolio theory of information retrieval.  In _Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’09, page 115–122, New York, NY, USA. Association for Computing Machinery.
  * Webber et al. (2010) William Webber, Alistair Moffat, and Justin Zobel. 2010.  A similarity measure for indefinite rankings.  _ACM Trans. Inf. Syst._ , 28(4).
  * White et al. (2008) Ryen W. White, Susan Dumais, and Jaime Teevan. 2008.  How medical expertise influences web search interaction.  In _Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’08, page 791–792, New York, NY, USA. Association for Computing Machinery.
  * Wildemuth (2004) Barbara M. Wildemuth. 2004.  The effects of domain knowledge on search tactic formulation.  _J. Am. Soc. Inf. Sci. Technol._ , 55(3):246–258.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _CoRR_ , abs/1910.03771.
  * Wu et al. (2018a) Bin Wu, Chenyan Xiong, Maosong Sun, and Zhiyuan Liu. 2018a.  Query suggestion with feedback memory network.  _Proceedings of the 2018 World Wide Web Conference_.
  * Wu et al. (2018b) Bin Wu, Chenyan Xiong, Maosong Sun, and Zhiyuan Liu. 2018b.  Query suggestion with feedback memory network.  In _Proceedings of the 2018 World Wide Web Conference_ , WWW ’18, page 1563–1571, Republic and Canton of Geneva, CHE. International World Wide Web Conferences Steering Committee.
  * Xiang et al. (2010) Biao Xiang, Daxin Jiang, Jian Pei, Xiaohui Sun, Enhong Chen, and Hang Li. 2010.  Context-aware ranking in web search.  _Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval_.
  * Ye et al. (2021) Jiacheng Ye, Tao Gui, Yichao Luo, Yige Xu, and Qi Zhang. 2021.  One2Set: Generating diverse keyphrases as a set.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4598–4608, Online. Association for Computational Linguistics.
  * Yuan et al. (2018) Xingdi Yuan, Tong Wang, Rui Meng, Khushboo Thaker, Daqing He, and Adam Trischler. 2018.  Generating diverse numbers of diverse keyphrases.  _CoRR_ , abs/1810.05241.
  * Zamani et al. (2020a) Hamed Zamani, Susan Dumais, Nick Craswell, Paul Bennett, and Gord Lueck. 2020a.  _Generating Clarifying Questions for Information Retrieval_, page 418–428. Association for Computing Machinery, New York, NY, USA.
  * Zamani et al. (2020b) Hamed Zamani, Bhaskar Mitra, Everest Chen, Gord Lueck, Fernando Diaz, Paul N. Bennett, Nick Craswell, and Susan T. Dumais. 2020b.  Analyzing and learning from user interactions for search clarification.  In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020_ , pages 1181–1190. ACM.
  * Zhang et al. (2020) Weinan Zhang, Xiangyu Zhao, Li Zhao, Dawei Yin, Grace Hui Yang, and Alex Beutel. 2020.  _Deep Reinforcement Learning for Information Retrieval: Fundamentals and Advances_, page 2468–2471. Association for Computing Machinery, New York, NY, USA.
  * Ziegler et al. (2019) Daniel M. Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul F. Christiano, and Geoffrey Irving. 2019.  Fine-tuning language models from human preferences.  _CoRR_ , abs/1909.08593.
  * Zukerman and Raskutti (2002) Ingrid Zukerman and Bhavani Raskutti. 2002.  Lexical query paraphrasing for document retrieval.  In _COLING 2002: The 19th International Conference on Computational Linguistics_.