Boosting Search Engines with Interactive Agents
Authors: Leonard Adolphs
Benjamin Börschinger
Christian Buck
Michelle Chen Huebscher
Massimiliano Ciaramita
Lasse Espeholt
Thomas Hofmann
Yannic Kilcher
Sascha Rothe
Pier Giuseppe Sessa
Lierni Sestorain
Venue: ICLR 2022 Submitted (2022)
Keywords: query refinement
reinforcement learning
self-supervised learning
question answering
search engines
large language models

Abstract: This paper presents first successful steps in designing agents that learn meta-strategies for iterative query refinement. 
Our approach uses machine reading to guide the selection of refinement terms from aggregated search results.

Agents are then empowered with simple but effective search operators to exert fine-grained and transparent control over queries and search results.

We develop a novel way of generating synthetic search sessions, which leverages the power of transformer-based language models through (self-)supervised learning. We also present a reinforcement learning agent with dynamically constrained actions that learns interactive search strategies from scratch. 

We obtain retrieval and answer quality performance comparable to recent neural methods using a traditional term-based BM25 ranking function. We provide an in-depth analysis of the search policies.

Under review as a conference paper at ICLR 2022
BOOSTING SEARCH ENGINES WITH INTERACTIVE AGENTS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper presents first successful steps in designing agents that learn meta- strategies for iterative query refinement. Our approach uses machine reading to guide the selection of refinement terms from aggregated search results. Agents are then empowered with simple but effective search operators to exert fine-grained and transparent control over queries and search results. We develop a novel way of generating synthetic search sessions, which leverages the power of transformer- based language models through (self- (self-)supervi Jsueervied learning. We also present a reinforcement learning agent with dynamically constrained actions that learns interactive search strategies from scratch. We obtain retrieval and answer quality performance comparable to recent neural methods using traditional term term-based BM25 ranking function. We provide an in-depth analysis of the search policies.
INTRODUCTION
Can machines learn to use search engine as an interactive tool for finding information? Web search is the portal to a vast ecosystem of general and specialized knowledge, designed to support humans in their effort to seek relevant information and make well-informed decisions. Utilizing search as
tool is intuitive, and most users quickly learn interactive search strategies characterized by sequential reasoning, exploration, and synthesis (Hearst) 2009 Rutter et al. 2013 Russell 2019). The success of web search relies on machines learning human notions of relevance, but also on the users' ability to (re-)formulate appropriate queries, grounded in tacit understanding of strengths and limitations of
search engines. Given recent breakthroughs in language models (LM) (Vaswani et al., [2017] Devlin
al. 2019 Brown et al. 2020 as well as reinforcement learning (RL) (Mnih et al.) [2013] Silver et al. interactively use search engines. However, the lack of expert search sessions puts supervised learning out of reach, and RL is often ineffective in complex natural language understanding (NLU) tasks. The feasibility of autonomous search agents hence remains an open question, which inspires our research.
2016 Berner et al. 2019). it seems timely to ask whether, and how, agents can be trained to
We pursue design philosophy in which search agents operate in structured action spaces defined as generative grammars, resulting in compositional, productive, and semantically transparent policies. Further domain knowledge is included through the use of well-known models and algorithms from NLU and information retrieval (IR). Most notably, we develop a self-supervised learning scheme for generating high-quality search session data, by exploiting insights from relevance feedback (Rocchio 1971). used to train a supervised LM search agent based on T5 (Raffel et al.. 2020). We also build an RL search agent based MuZero (Schrittwieser al. 2020) and BERT (Devlin et al. 2019), which performs planning via rule-constrained Monte Carlo tree search and a learned dynamics model.
We run experiments on an open-domain question answering task, OpenQA (Lee et al. 2019). Search agents learn diverse policies leading to deep, effective explorations of the search results. The MuZero agent outperforms a B.225 (Robertson & Zaragoza 2009) search function running over a Wikipedia index, on both retrieval and answer quality metrics. Thus, providing novel evidence for the potential of knowledge-infe -nffused RL in hard NLU tasks. The T5 agent can more easily leverage large pre-trained encoder-decodedd and proves superior to MuZero. Furthermore, a straightforward ensemble of agents is comparable in performance to a state of the art neural retrieval system, DPR (Karpukhin et al. 2020), while relying solely interpretable, symbolic retrieval operations. This suggests new challenges for future work; e.g., involving hybrid architectures and policy synthesis
WWe open-source the code and trained checkpoints for both agents: anonymized during review.

---

Under review as a conference paper at ICLR 2022
1o: who won the us open
PS/MR
Agent
PS/MR
Agent
Agent
PS
Op
17
91 90
TT: QT-1 (contents "pga")
(Litle:" "termis" A2)
BM25
BMM25
BM25
Figure I: Schematic agent interaction with the search environment (Lucene-BM25) for an ambiguous query (tennis/golf). After receiving a set documents (Dt), the corresponding observation (o,) is compiled by ranking all documents U D; by their Passage Score (PS), and creating snippets for the top-k documents around the answers extracted by the Machine Reader (MR). Note that PS/MR always condition on Zo- In step 1, q1, the agent doubles the weight term 'tennis' in document titles (we use the Lucene query syntax). In the last step, yr. the agent excludes from search results all documents containing the term 'pga' (golf), then outputs the top-k documents found in the session.
2
LEARNING FOR INTERACTIVE SEARCH
It has been a powerful vision for more than 20 years to design search engines that are intuitive and simple to use. Despite their remarkable success, search engines are not perfect and may not yield the most relevant result(s) in one shot. This is particularly true for rare and intrinsically difficult queries, which may require interactive exploration by the user to be answered correctly and exhaustively. Contextual query refinement is common technique (Jansen et al.) 2009). even among children (Rutter al. 2015), used to improve search by combining evidence from previous results and background knowledge (Huang& & Efthimiadis 2009). Such refinements often rely inspecting result snippets and titles or on skimming the content of tapkranked documents. This process is iterative and may be repeated produce sequence of queries q0; 91,-.... fr until (optimistically) satisfactory answer found. It seems natural to mimic this interactive process by a search agent, which learns the basic step of generating a follow-up query from previous queries and their search results.
Furthermore, it is noteworthy how power users apply dedicated search operators and sophisticated investigative strategies to solve deep search puzzles (Russell) 2019). In particular, unary operators offer a great deal of fine-grad -ee-graindd control and transparency and as such are highly effective in expert hands. We concentrate on three operators: '+', which limits results to documents that contain a specific term, which excludes results that contain the term, and 'x," which boosts term weight in the BM25 score computation by factor i R. For instance see also Figure [ the query 'who won the us open', may lead to both tennis and golf-related results. An expert searcher could zero-in on the tennis intent by excluding golf-related terms and boosting tennis-related ones. As we show in this paper, these operators are also pivotal in designing interactive search agents.
2.1 RESULT AGGREGATION FOR CONTEXTUAL REFINEMENT
Web searchers expect the best answer to be among the top two hits on the first results page (Hearst 2009 85) and pay marginal attention the bottom half of the 10 blue links (Granka et 2004 Joachims et al. 2005| Nielsen & Pernice 2009 Strzelecki 2020). Likewise, search agent considers only the top documents returned by the search engine every step, where 5. During a search session the agent maintains a list of the top-k documents overall, which is returned at the end.
To aggregate results we use a machine reader (MR, ef. (Raipurkar et al. 2016)). Specifically, we use DPR-like reader/passage scorer (Karpukhin et al. 2020), which builds upon pre-trained BERT model. Beyond identifying the most promising answer span within each result document d, the system also estimates the probability of d containing the (unspecified) answer P(d 9 ANSWER g) E [0: 1). This probability can be viewed as a Passage Score (PS) that induces a calibrated ranking across all result documents within session.
2

---

Under review as a conference paper at ICLR 2022
An observation representing the session at any given step is built by extracting fixed-length token window centered at the answer span predicted by the reader for each document. In addition, we include the document titles. Finally, the query tokens and refinements describing 9t also included. This leads to a segmented observation token sequence Or which is truncated to length I 512 a common input length for pre-trained transformer-han based LMs (cf. Appendix for details, examples). We then use BERT or T5 to produce an embedding S, from which the search agent will generate the next query. If denote the result set for qt by Dr, then we get diagrammatically
yo> Gt search ongine
MR/PS
L.M
agent
Ot
St
gr++1
Do
Dr
oiservation
encading
generation
We focus the case where 4++11 is obtained from qe through augmentation. This may add a keyword w E Ddts, where yddh is the search index vocabulary, with the usual disjunctive search engine semantics structured search term formed by the of unary operators ('+','",'xx)) and fields.
2.2 ROCCHIO QUERY EXPANSIONS
In the absence of training sessions from human expert users, we propose to generate synthetic search sessions in a sulf-supervised manner, making use of set question- ansserr pairs (g, a). We initialize q0=q and aim to find sequence of refinements that make progress towards identifying documents containing the answer o, based on a reward function q + Dr + rt E [0: (cf. 4 A query is not further refined, if either 2=20 (maximal length) if no score increasing refinement can be found.
To create candidate refinements, we make use of the idea relevance feedback as suggested in Rocchio [97II.. An elementary refinement called Rocchio expansion then takes the form
4++1 := qi Aq. Ag. == [+| | TITLE CONTENT] We, we E Eg := = UE UE (2)
where i is the boosting coefficient and Mn refers to a set of terms accessible to the agent. By that mean terms that occur in the top PS-ranked session documents. We use superscripts to refer to the vocabulary of the question (q), titles (T), answers (a: or bodies (3) of documents in o,. Note that adding terms & Σ, would make refinements difficult to reproduce for agent and thus would provide supervision of low utility.
Another aspect of creating sessions described above has to do with the search complexity of finding optimal sequences of Rocchio expansions. We consider q- = + a as the "ideal" query, whose results define the vocabulary Σ,, For efficiency reasons, we further constrain the terms to be added via exact matches, term boosting or term exclusions by defining respective constrained dictionaries
E E, E Σ = E,,
This means it is possible to upgrade accessible terms, Wt, to exact matches, weight boosting, if they also occur in the ideal result set (w, E Σ.); and to exclude accessible terms if they not present in the ideal results (w, E Σt). We have found experimentally that this leads to good trade-off between the quality of Rocchio expansions and the search effort to find them. The search for sequences of Rocchio expansions is done heuristically, More details, pseudo-code illustrating the procedure and examples can be found in 5 Appendix Appendix G
2.3 SELP-SUPERVISED T5 AGENT
We suggest to train generative search agent in supervised manner by making use of synthetic search sessions generated by Rocchio expansions. We use T5, a pretrained transformer encoder-decoder model which achieves state-of-the-arr results multiple NLU tasks. As search agent, T5 predicts single new search expansion from an observed state. the spirit of everything-is-stte estring-prediction both state and expansions are represented as plain strings. See Appendix for full example.
Our T5 agent is trained via Behavioral Cloning (BC) Michie 1990). We treat each step in a Rocchio session as single training example. As is common sequence prediction tasks, entropy loss for optimization. BC is perhaps the simplest form of Imitation Learning (IL), and has been proven effective variety of application domains (Sharma et al. 2018 Rodriguezz-errandde
the cross-
3

---

Under review as a conference paper at ICLR 2022
et al. 2019). In query refinement task, it allows inherit the expressive power of the Rocchio query expansions and, differently from other IL approaches (Ross et al. 2011 Ho & Ermon 2016 Ding 2020), requires only offline interactions with the search engine. Crucially, this enables scaling to the large action spaces and model sizes typical of recent LMs. Our T5 agent can also he described Decision Transformer with fixed max return (Chen al. 202TT
At test time, we start with the initial query and incrementally add new expansions, querying the trained T5 model in every step. We then use the refined query retrieve new documents and continue until either the set of new documents is empty or we reach the maximum number of steps. Throughout the session, we maintain the top-5 documents among all those retrieved.
3 REINFORCEMENT LEARNING: MUZERO AGENT
MuZero (Schrittwieser et al. 2020) is a state-of-the-art agent characterized by learnable model of the environment dynamics. This allows the use of Monte Carlo tree search (MCTS) to predict the next action, in the absence of an explicit simulator. In our use case, MuZero aims to anticipate the latent state implied by each action with regard to the results obtained by the search engine. For instance, in the example of Figure [ it may learn to predict the effect of boosting the term 'tennis'. This approach to planning is intuitive for search, as searchers learn to anticipate the effect of query refinements while not being able to predict specific results. Furthermore, this offers performance advantage of many orders of magnitude against executing queries with the real search engine.
3.1 GRAMMAR GUIDEE SEARCH
To map observations to states, the MuZero agent employs a custom BERT with additional embedding layers to represent the different parts (cf. Appendix B for details). Compared to T5, MuZero has more challenging starting point: its BERT-based representation function is pre-trained on less data, has fewer parameters (1 10M vs. billions) and single vector, [CLS]. Moreover, it cannot as easily exploit supervised signals. However, it can more openly explore the space of policies, e.g. independent of the Rocchio expansions. Through many design iterations, we have identified it to be crucial to structure the action space of the MuZero agent and constrain admissible actions and refinement terms dynamically based on context. This provides Nomain-informel inductive bias that increases the statistical efficiency of learning a policy via RL.
cooss-attention predictions conditioned
We take inspiration from generative, specifically context-free grammars (CFGs) (Chomsky 1956)
and encode the structured action space as a set of production rules, which will be selected in (fixed) tow-nown, left-to-right order. query refinement generated as follows
Q + UQQ U + Op Field W, Op + +| |
Field * TITLE CONTENT,
(4)
which allows for adding plain or structured keywords using unary operators. The selection of each refinement term W proceeds in three steps, the first two can be described by the rules
W W W/ W W With W Ex x E (,, With
Didh (5)
which means that the agent first decides on the origin of the refinement term, i.e., the query or the different parts of the top-scored result documents, and afterwards selects the term from the corresponding vocabulary. As the term origin correlates strongly with its usefulness as a refinement term, this allows to narrow down the action space effectively. The agent is forced to pick a term from the larger vocabulary (1.6M terms) of the search index Edd during MCTS, as there no observable context to constrain the vocabulary.
The third level in the action hierarchy concerns the selection of the terms. We have found advantageous to make use of subword units; specifically, BERT's 30k lexical rules involving word pieces, to generate terms sequentially, starting from a term prefix and adding one or more suffixes. Note that this part of the generation is context-sensitive, in the vocabulary. We make use of tries to efficiently represent each Σn and amortize computation. The grammar-guided MCTS is explained in detail in Appendix F
restrict the generation to words present
4

---

Under review as a conference paper at ICLR 2022
4 THE OPENQA ENVIRONMENT
We evaluate search agents in the context of open-domain question answering (Open-QAt (Voorhees 2000 Chen al. 2017). Given question g. we seek documents 'D that contain the answer using a search engine, the environment. Following common practice, we use Lucene-BM22 with default settings the English Wikipedia. BM25 has provided the reference probabilistic IR benchmark for decades (Robertson & Zaragoza 2009), only recently outperformed by neural models (Lee et al. 2019). The Lucene system provides search operators comparable commercial search engines.
Exploration-based learning is vulnerable to discovering adversarial behaviors. As safeguard we design a composite reward. The score of a results set D. given q, interpolates three components. The first is the Normalized Discounted Cumulative Gain (NDCG) at k. See Eq. 64, where wi = logg (i+1) EE
log2(j 1)
1 are normalizing weights, and rel(d))) = i, E d, 0 otherwise:
a) NDCG&(((1) Σ we rel(d))).
B) NNCEMM
Σ wi em(d:/g)-
(6)
NDCG is popular metric in IR it accounts for rank position, it is comparable across queries. and it is effective at discriminating ranking functions (Wang et al. 2013). NDCG alone can have drawbacks: on "easy" questions a score of can be achieved in short meritless episodes, while on "hard" ones it may be impossible to find first valid step, since Eq. takes discrete values. Hence, we introduce a second component, NDCEM, (Eq. (6)) where em((]]) = if the answer extracted from d by the reader exactly matches a, 0 otherwise. NDCEM, helps validate results by promoting high-ranking passages yielding correct answer spans. Finally, to favour sigh-confidence result sets we add the normalized Passage Score of the top results, leading to the following scoring function
k PS((g)g) E [0,1] (7)
(x(a)) == (1--A-A2)--NT
Based on 77). we define the search step reward
Tt 5s(Drlg)) - (s(
(8)
We train the MuZero agent directly on the reward. The reward is sparse, as none is issued in between search steps. The T5 agent is trained indirectly on it via the induction of Rocchio sessions (cf. (2.2).
EXPERIMENTS
We use the OpenQA-NQ data (Lee et al. 2019), derived from Natural Questions (Kwiatkowski et al. 2019), consisting of Google queries paired with answers extracted from Wikipedia. The data includes 79,168 train questions, 8,757 dev questions and 3,610 for test. We use the provided partitions and Wikipedia dump. Following Lee et (2019) we pre-process Wikipedia into blocks of 288 tokens, for total of 13M passages. We evaluate each system on the top-5 288-token passages returned. Model selection and data analysis are performed on NQ Dev, using the reward (Eq. 8) as the objective.
We generate synthetic search sessions using Rocchio expansions for grammars: GO (only simple terms), G1 (only term boosting), G2 (++' and '²), G3 (GO+G2) and G4 (GO+GI+G2), We use the reward above with =0 A2=0.6, after search against the quality metries (cf. Appendix C. We select possible values, i E {0.1, 2, 4, 6, 8). for term boosting weights. At each step, we attempt at most M BM25 searches, based on the current observation o,, to find an expansion that improves the reward. To further improve efficiency, we sort the terms in o by Lucene's 's IDF score and keep the top N. We set --100 For NQ Train, and G4, we find 298,654 Rocchio expansions from 77,492 questions. Similarly, we generate sessions for the NQ Dev and Test to estimate headroom.
5.1 AGENTS TRAINING AND INFERENCE
The DPR reader/selector and MuZero's 's he function use 12-layer BERT systems To train the former, generate for each query in NQ Train 200 candidate passages from our BM25 system, picking
BeRTThase, initialized from
Shub.
12, 12_H___1 768
12/1
5

---

Under review as a conference paper at ICLR 2022
Table 1: Results on NQ Test, For DPR Top- (155)
performance we report the most recent numbers, is slightly lower (47.3 and 68. respectively).
the published performance Karpukhin et al. 2020
Metric
BM25
PS(Do)
MZ
T5-G1
MZ+T5s
DPR
RQE-G4
NDCG@5
21.51
24.82
32.23
44.27
46.22
65.24
Top-1
28.67
44.93
47.97
52.60
54.29
52.47
73.74
Top-5
53.76
53.76
59.97
66.59
71.05
72.24
88.17
EM
28.53
41.14
32.60
44.04
44.35
41.50
62.35
one positive and 23 negative passages for each query at random whenever the query is encountered during training. The reader/scorer is not trained further.
The MuZero implementation scaled and distributed via an agent-learner setup (Espeholt et al. 2018)
in the SEED RL (Espeholt et al.) (2020) framework allowing for centralized batching of inference for effective use of accelerators. MuZero is trained on NQ Train for a total of 1.6 million steps (s=10 days) using 500 CPU-based actors and 4 Cloud TPU v2 for inference and training on the learner For each step, 100 simulations are performed. During training, we limit sessions to a maximum of 20 steps. The agent also decide to stop early by selecting dedicated stop action. Training of MuZero can be improved by providing advice to the actors. An actor may receive information about which terms W, should be promoted, W/ E Ej, demoted, wy E Ey. The probability of an episode receiving advice starts at 0.5 and decays linearly to O in one million steps.
For the T5 agent start from the pretrained T5-11B (11 billion parameters) public checkpoint and continue training on the NQ Train expansions. Training took about 5 days using 16 Cloud TPU v3. At inference time, we found that fixing the sessions to 20 steps worked best for both T5 and MuZero. We report detailed training configurations and ablations in Appendix D
5.2 RESULTS
Table summarizes the results NQ Test. We evaluate passage retrieval quality by means of ranking (NDCG@5) and precision (Top-1, Top-5) metrics. We also report Exact Match (EM) to evaluate answer quality. Our baseline is Lucene's BM25 one-shot search. Reranking the same BM25 documents by the PS score (PS(Do)) is easy and improves performance on all metries, particularly noticeable on Top-1 and EM providing more informative comparison. The last column (RQE-G4) reports the metrics of the episodes generated by the Rocchio Query Expansion process (2.) using the grammar with all operators (G4). RQEs use the gold answer and can be seen as a, possibly conservative, estimate of the performance upper bound. As the external benchmark we use DPR (Karpukhin et al.] 2020), a sfate-of-the-a OpenQA neural retriever based on dual encoders, the dominant architecture for deep learning- based ad hoc retrieval (Craswell et al. 2020).
The MuZero agent (MZ) outperforms both BM25 and PS(Do). While this result may seem trivial, it marked milestone that required many iterations to achieve. The challenges for RL in IR, and NLU, are extreme in terms of state and action space dimensionality, data sparsity etc. (Zhang et al., 2021). We propose ideas for tackling some of these key challenges by fitting out agents with domain knowledge in principled ways, with the grammar-gune guided MCTS as the centerpiece, The best MuZero converges to policy which uses only term boost actions with weight of 2 (Figure 2a). This agent is not able to find better pertrrrprforming, diverse policies. This is an extreme case of more general pattern. Different sub-gra -ob-grammars represent different tacties; e.g., '+' and *-2 affect the accessible documents in irreversible ways, while boosting only affects ranking. It is challenging for all agents, and particularly MuZero, to modulate effectively multiple sub-policies.
Training T5 is less involved than MuZero. This allows us to evaluate all 5 grammars. The best one, 'T5-G1" in Table [ is limited term boosting (GI), but it learns use all available weight values (Figure 2a In terms of Top-1 this agent outperforms the published and the most recently posted DPR results but has worse Top-5 than both. Results for all five T5 agents are found in Table A.5 A.5
'For details, see https://cloud. www.oudwwwoooo.oooooooo wowolle.com/puu.. "Top-5 is identical to BM25 since the documents are the same. https: / thub. com/ htt.://ooooaaacceeeeeeee ttt./aacccooekeercccihcac

---

Under review as a conference paper at ICLR 2022
MZ
Frequency in Top-5 Does
0.4
MZ
Relative Frequency
0.8
T5-G1
T3-G1
RQE-G4
RQE-G4
0.3
0.6
0.4
0.1
0.0
+oodleuts
+tille
Aiale
09
$1 100
101 250
251 500
1080
> 1009
6
501
(a) Distribution of action types.
(b) Depth of documents explored.
Figure 2
In the last experiment we combine all trained agents, the five T5 agents and the MuZero one, in one ensemble. We simply rank the union of all the documents returned by the ensemble, by means of the PS score on each document. This ensemble ("MZ+T5s' in Table has slightly better precision than the recent DPR in top position, and slightly worse for the Top-5. This results indicates that the ability to orchestrate diverse sub-policies may indeed be the key to future progress for search agents. The current SOTA for Top-5 is 74.0 (Qu et al. 202I).
We conclude by discussing answer quality. Agents routinely produce answer spans, predicted by the reader/scorer, to build observations. The MR/PS component is trained once, before the agents, on the output of BM25. However, agents deeply change results. As Figure 2b shows, they dig deep in the original BM25 ranking. This is positive, as behavior discovery is one of the main motivations for researching exploratory methods like RL. As a consequence, though, the MR/PS component effectively operates out of distribution and the EM numbers of the internal reader are not competitive with recent methods, 6.6 all the numbers including on NQ Dev.
Ideally, one would co-train the observation builder with the search agent. However, combining the two would introduce sigmificant engineering complexity in the current architecture. For instance, one could interleave training the two as in DQNs (Mnih et al. (2013). A simpler alternative is to add the answer prediction task to the T5 agent. Retrieval-augmennedd answer generation known to produce strong results (Izacard & Grave 2021). Multitasking would simplify the design of the generative agents and possibly produce better models. We make a first step in this direction by training one single, dedicated T5 agent. The system uses training input the top-5 documents of the RQE-G4 episodes, but its task is to generate the gold answer, instead of the query expansion. By using the output of the "T5-G1" and 'MZ+T5s' agents, the EM performance of the answer generation T5 is comparable to methods that build on DPR, such as RAG (Lewis et al. 2020b) (44.5 EM). Although not as good as FID (Izacard & Grave 202T) that condition many more (100) documents. The performance of the MuZero agent is lower here, we believe this is due its more idiosyncratic results.
5.3 DISCUSSION AND FUTURE WORK
Table illustrates an example where the T5-G4 agent switches policy mid-session. This agent is trained on the full grammar (G4) and can use all search operators. The question is about basketball records and BM25 does not find good results. In the first three steps the agent focuses on re-ranking by boosting terms like 'per' (from the phrase 'per game" in the results for qo) and 'scorer'. This produces a good hit and answer span ( ('Pete Maravich') at position 1 of step 3. The agent then switches to filtering mode, to zero in on documents containing the predicted answer term. This is a clear instance of successful policy synthesis. However it is gamble, as predicted answers can be incorrect and filtering actions not reversible. This suggests that the action space may benefit by including more control actions, e.g. to undo or go back to a specific state, to better support safe exploration and the emergence of meta policies. We plan to investigate this in future work.
7

---

Under review as a conference paper at ICLR 2022
Table 2: Example of T5-G4 agent session exhibiting multiple tactics. We only report three steps and the top-3 results, for brevity. In red the answer spans wrongly predicted by the internal reader (in blue when correct). The score for the result set at each step is that of Equation
40
who averaged the most points in college basketball history
[score: 0.027]
d1
Title: Gary Hill (hasketball)
of four that team who averaged double figures in points, Senior Larry Jones was OCU's leading scorer at 19.7 points game, sophomore Bud Koper added 15.9...
d2
Title: Kevin Foster (basketball)
his senior year, Foster averaged 21 points per game and was named the MVP and All-District 18-5A First Team. He was also Texas top- 30 player his final season
d3
Title: Paul Cummins (basketball)
... big home win over Army. As a freshman, Cummins high-scored with 13 points against final-four team Louisville (2004). After graduating in 2008, Cummins played for
q3
"qo' (contents:"per".. (6) "cootents.""ccree"""""" 44) (contents:"3">0
[score: 0.330]
d1
Title: Alphonso Ford
... seasons. With 3,165 career points scored in the NCAA Division I, he is 4th on the all-time scoring list, behind only Pete Maravich, Freeman Williams, and Lionel
d2
Title: Buzzy Wilkinson
Buzzy Wilkinson Richard Warren "Buzzy" Wilkinson (November 18, 1932 January 15, 2016) was an American basketball player who was selected by the Boston Celtics in
dg Title: Gary Hill (basketball)
...bbcoomig one of four on that team who averaged double figures in points. Senior Larry Jones was OCU's leading scorer at 19.7 points game, sophomore Bud Koper...
'qs" +contents: "<comtents""mrravichh" "maravich")
[score: 0.784]
di
Title: Alphonso Ford
seasons. With 3,165 career points scored in the NCAA Division I, he is 4th on the all-time scoring list, behind only Pete Maravich, Freeman Williams, and Lionel
d2 Title: Pete Maravich
... had posted a 3-20 record in the season prior to his arrival. Pete Maravich finished his college career in the 1970 National Invitation Tournament, where LSU finished fourth...
da
Title: 1970 National Invitation Tournament
... representee the final college games for LSU great Pete Maravich, the NCAA's all-time leading scorer. Maravich finished his three-year career with 3,667 points ...
The previous point extends to the agents' architecture. It is reasonable to hypothesise that the superior performance of T5 is due to two main factors. T5s bigger models, trained on more data, and have a more expressive prediction process based on encoder-decoders. In addition, they finetuned on self-supervised tasks which provides significant headroom. While T5-like LMs seem the obvious choice forward there are open questions concerning exploration. It is not clear how much the model can generalize being trained offline and never being exposed its own prediction. This moves the learning problem back towards RL. We plan to investigate approaches like Decision Transformers (Chen al. 2021) next, as a natural framework for expressing the search task within LMs, while at the same time bringing back in key RL concepts such as expected returns and learning also from negative experiences, possibly produced by different sources; e.g., MuZero.
We would like to note that pre-trained language models of the kind used here have been shown to capture societal biases (Tan Celis 2019: Webster et al. 2020). which motivates broad discussion about potential harms and mitigations (Blodgett et al.) 2020, Bender et al. 2021). We have reason to believe our architectures would exacerbate biases, but the overall problems may persist. We also hope that end-to-end optimization methods based composite rewards, as in this proposal, can contribute to solve some of these challenges; e.g., by providing means of adversarial testing, and by including relevant metrics directly in the objective design.
While our agents yield performance comparable to neural retrievers they rely solely on interpretable, symbolic retrieval operations. Exploration and transparency core objectives of our framework.
8

---

Under review as a conference paper at ICLR 2022
6 RELATED WORK
Query optimization is an established topic in IR. Methods range from hand-crafted rules (Lawrence &
Giles 1998) to data-driven transformation patterns (Agichtein et al. 2001). Narasimhan al. (2016)
use RL to query the web for information extraction. NNgueera & Cho (017)) and Buck et al. 2018
use RL-trained agents to seek good answers by reformulating questions with seq2seq models. These
methods are limited to one-step episodes and queries to plain natural language. This type of modeling closely related to the use of RL for neural machine translation, whose robustness currently dehated (Choshen et al. 2020 Kiegeland & Kreutzer 202T). Montazeralghaem et al. (2020) propose feature-based network to score potential relevance feedback terms to expand query. Das et al. (2019) propose to perform query reformulation in embedding (continuous) space and find that it can outperform the sequence-base
approach. Xiong et al. (202T) successfully use relevance feedback by jointly encoding the question and the text of its retrieved results for multi-hop QA. Other work at the intersection of IR and RL concerns bandit methods for news recommendation (Li et al.) (010)) and learning rank (Yue & Joachims 2009). Recently, interest in Deep RL for IR has grown ZZhngg et al. 2021). There, the search engine is the agent, and the user the environment. In contrast, we view the search problem from the user perspective and thus consider the search engine the environment.
The literature on searchers' behavior is vast, see c.g. St.tzellecki (020) for an overview of eye-tracking studies. While behavior evolves with interfaces, users keep parsing results fast and frugally, attending to just a few items. From a similar angle, Yuan et al. (2020) offer promising findings on training QA agents with RL for remplate-basee information gathering and answering actions. Most of the work in language-related RL is otherwise centered on synthetic navigation/arcade environments (Hu ct al. 2019). This line of research shows that RL for text reading can help transfer (Narasimhan et al., 2018) and generalization (Zhong et al.) 2020) in synthetic tasks but skirts the challenges of more realistic language-basee based problems. On the topic of grammars, Neu & Szepesvári (2009) show that Inverse RL can learn parsing algorithms in combination with PCFGs (Salomaa 1969).
Current work in OpenQA focuses on the search engine side of the task, typically using dense neural passage retrievers based dual encoder framework instead of BM25 (Lee et al. 2019 Karpukhin et al. 2020). Leveraging large pre-trained language models to encode the query and the paragraphs separately led to performance boost across multiple datasets, not just in the retrieval metrics but also in exact-match score. While Karpukhin et al. (2020) use an extractive reader on the top-k returned paragraphs. [ewis al. (2020b) further improves using a generative reader (BART (Lewis al. 2020ab). This design combines the strengths of parametric memory - the pre-trained LM - with a non-parametric memory- the retrieved Wikipedia passages supplied into the reader's 's context. This idea of combining a dense retriever with generative reader is further refined in Izacard & Grave (202T), which fuses multiple documents in the decoding step. A recent line of work is concerned with constraining the model in terms of the number of parameters retrieval corpus size while remaining close to state-of-the-art performance (Min et al. (002T) This effort led to synthetic dataset of 65 million probably asked questions (Lewis et al.] (021) used to do a nearest neighbor search on the question - no learned parameters needed or train a closed-book generative model.
7 CONCLUSION
Learning to search sets an aspiring goal for AI, touching on key challenges in NLU and ML, with far reaching consequences for making the world's knowledge more accessible. Our paper provides the following contributions. First, we open up the area of search session research to supervised language modeling. Second, we provide evidence for the ability of RL to discover successful search policies in a task characterized by multi-step episodes, sparse rewards and a high-dimensional, compositional action space. Lastly, we show how the search process can be modeled via transparent, interpretable machine actions that build on principled and well-established results in IR and NLU.
Our findings seem to agree with long-standing tradition in psychology that argues against radical behaviorism - i.c., pure reinforcement-drivve learning, from tabula rasa - for language (Chomsky 1959). RL agents require a remarkable share of hard-wired domain knowledge. LM-based agents are easier to put to use, but they need abundant task-specific data for fine tuning. Supplied with the right inductive bias, LM and RL search agents prove surprisingly effective. Different architectures learn different policies, suggesting broad possibilities in the design space for future work.

---

Under review as a conference paper at ICLR 2022
Reproducibility statement The code for this paper has already been open sourced (reference omitted for anonymity) and included with the supplementary material. We will make sure results fully reproducible by updating the open source code based the final version of the paper after completion of the review process.
REFERENCES
Eugene Agichtein, Steve Lawrence, and Luis Gravano. Learning search engine specific query transformations for question answering. In Proceedings of WWW10, pp. 169-178, 2001.
Emily M. Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAceT '21, pp. 610-623, New York, NY, USA, 2021. doi: 10. (45/4441188.34459999
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer. Shariq Hashme, Chris Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondè de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, llya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota with large scale deep reinforcement learning. https://araii.ergla///991... 06680, 2019.
Su Lin Blodgett, Solon Barocas, Hal Daumé III, and Hanna Wallach, Language (technology) is power: A critical survey of "bias" in NLP. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 5454-5476, 2020. doi: 10. 12200
URL
org 2020 acl.aa..cllle 485
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901, 2020.
Christian Buck, Jannis Bulian, Massimiliano Ciaramita, Andrea Gesmundo, Neil Houlsby, Woj- ciech Gajewski, and Wei Wang. Ask the right questions: Active question reformulation with reinforcement learning. International Conference on Learning Representations, 2018
Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. Reading Wikipedia to answer open- domain questions. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pp. 1870-1879, 2017.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Michael Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling, arXiv preprint (tti::2006.1144000 2021.
N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 13-121, 1956.
N. Chomsky. Review of B. F. Skinner, Verbal Behavior. Language, 39:26 58, 1959.
Leshem Choshen, Lior Fox, Zohar Aizenbud, and Omri Abend. On the weaknesses of reinforcement learning for neural machine translation. In International Conference on Learning Representations, 2020.
Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Fernando Campos, and Ellen M. Voorhees. Overview of the trec 2020 deep learning track. ArXiv, abs/2 102./1002.7662, 2020.
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, and Andrew McCallum. Multi-step retriever- reader interaction for scalable open-domain question answering. International Conference on Learning Representations, 2019.
10

---

Under review as a conference paper at ICLR 2022
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre- Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Papers), pp. 4171-4186, 2019.
Zihan Ding. Imitation Learning, pp. 273-306. Springer Singapore, 2020.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In Proceedings of the 35th International Conference on Machine Learning, pp. 1407-1416, 2018.
Lasse Espeholt, Raphaël Marinier, Piotr Stanczyk, Ke Wang, and Marcin Michalski. Seed rl: Scalable and efficient deep-rl with accelerated central inference. In International Conference on Learning Representations, 2020.
Laura A. Granka, Thorsten Joachims, and Geri Gay. Eye-tracking analysis of user behavior www search. In Proceedings of the 27th Annual International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 478-479, 2004.
Marti Hearst. Search user interfaces. Cambridge University Press, Cambridge; New York, 2009.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, 2016.
Hengyuan Hu, Denis Yarats, Qucheng Gong, Yuandong Tian, and Mike Lewis. Hierarchical deci- sion making by generating and following natural language instructions. In Advances in Neural Information Processing Systems, volume 32, 2019.
Jeff Huang and Efthimis Efthimiadis. Analyzing and evaluating query reformulation strategies in web search logs. In CIKM, pp. 77-86, 2009.
Gautier Izacard and Edouard Grave. Leveraging passage retrieval with generative models for open domain question answering. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, 2021.
B. Jansen, D. L. Booth, and A. Spink. Patterns of query reformulation during web searching. Journal of the Americun Society for Information Science and Technology, 60(7):1358-1371, 2009.
Thorsten Joachims, Laura Granka, Bing Pan, Helene Hembrooke, and Geri Gay. Accurately interpret- ing clickthrough data as implicit feedback. In Proceedings of the 28th Annual International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 154-161, 2005.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
Samuel Kiegeland and Julia Kreutzer. Revisiting the weaknesses of reinforcement learning for neural machine translation. In Proceedings of NAACL, 2021.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfilld Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, Kenton Lee, Kristina N. Toutanova, Llion Jones, Ming- Wei Chang, Andrew Dai, Jakob Uszkoreit, Quoe Le, and Slav Petrov. Natural questions: a benchmark for question answering research. Transactions of the Association of Computational Linguistics, 2019.
Steve Lawrence and C, Lee, Giles. Context and page analysis for improved web search. IEEE Internet Computing, 2, 1998.
Kenton Lee, Ming- Wei Chang, and Kristina Toutanova. Latent retrieval for weakly supervised open domain question answering. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 6086-6096, 2019.
11

---

Under review as a conference paper at ICLR 2022
Mike Lewis. Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. BART: Denoising saquence-to-sequenee pre-training for natural language generation, translation, and comprchension. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACI. 2020, pp. 7871-7880, 07 2020a.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmentt generation for powlledee-nttnssing nlp tasks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 9459-94777 2020b.
Patrick Lewis, Yuxiang Wu, Linqing Liu, Pasquale Minervini, Heinrich Küttler, Aleksandra Piktus, Pontus Stenetorp, and Sebastian Riedel. Paq: 65 million probably questions and what you can do with them, 2021.
L. Li, W. Chu, J. Langford, and R.E. Schapire. A contextual-bame approach to personalized news article. In Proceedings of WWW, 2010.
M; Hayes-Miches J Michie, D; Bain. Cognitive models from subcognitive skills. IEE control engineering series, 1990.
Sewon Min, Jordan Boyd-Grabel Chris Alberti, Danqi Chen, Eunsol Choi, Michael Collins, Kelvin Guu, Hannaneh Hajishirzi, Kenton Lee, Jennimaria Palomaki, Colin Raffel, Adam Roberts, Tom Kwiatkowski, Patrick Lewis, Yuxiang Wu, Heinrich Küttler, Linqing Liu, Pasquale Minervini, Pontus Stenetorp, Sebastian Riedel, Sohee Yang. Minjoon Seo, Gautier Izacard, Fabio Petroni, Lucas Hosseini, Nicola De Cao. Edouard Grave, Ikuya Yamada, Sonse Shimaoka, Masatoshi Suzuki, Shumpei Miyawaki, Shun Sato, Ryo Takahashi, Jun Suzuki, Martin Fajcik, Martin Docekal, Karel Ondrej. Pavel Smrz, Hao Cheng, Yelong Shen, Xiaodong Liu, Pengcheng He, Weizhu Chen, Jianfeng Gao, Barlas Oguz, Xilun Chen, Vladimir Karpukhin, Stan Peshterliev, Dmytro Okhonko, Michael Schlichtkrull, Sonal Gupta, Yashar Mehdad, and Wen tau Yih. NeurIPS 2020 EfficientQA Competition: Systems, Analyses and Lessons Learned, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. In NIPS Deep Learning Workshop. 2013.
Ali Montazeralghaem. Hamed Zamani, and James Allan. A reinforcement learning framework for relevance feedback. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 59 59-68, 2020.
Karthik Narasimhan, Adam Yala, and Regina Barzilay. Improving information extraction by acquiring external evidence with reinforcement learning. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, 2016.
Karthik Narasimhan, Regina Barzilay, and Tommi S. Jaakkola. Deep transfer in reinforcement learning by language grounding. Journal of Artificial Intelligence Research, 63, 2018
Gergely Neu and Csaba Szepesvári. Training parsers by inverse reinforcement learning. Machine Learning, 77, 2009.
Jakob Nielsen and Kara Pernice. Eyetracking Web Usability. New Riders Publishing, 2009.
Rodrigo Nogueira and Kyunghyun Cho. Task-oriented query reformulation with reinforcement learning. In Proceedings of EMNLP, 2017.
Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu. Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. RocketQA: An optimized training approach to dense passage retrieval for open-domain question answering. In Proceedings of the 202/ Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021.
URL https::/// / /ataaaaaannttooooooeee org/ 2021 naacl maaacl-main 466
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(14 1677, 2020.
12

---

Under review as a conference paper at ICLR 2022
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383-2392, 2016.
Stephen Robertson and Hugo Zaragoza. The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval, (()):333-388) 2009.
J. Rocchio. Relevance feedback in information retrieval. In G. Salton (ed.), The Smart retrieval system experiments in automatic document processing, pp. 313-323. Englewood Cliffs, NJ: Prentice-Hall, 1971.
Erick Rodríguez- Mndrrguuz--Hemaanderr Hernandez, Juan Irving Vasquez-Gomez, and Juan Carlos Herrera-Lozada. Flying through gates using behavioral cloning approach. In 2019 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 1353-1358, 2019.
Stephane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 627-635, 11-13 Apr 2011.
Daniel M. Russell. The Joy of Search: A Google Insider's Guide to Going Beyond the Basics. The MIT Press, 2019.
Sophie Rutter, Nigel Ford, and Paul Clough. How do children reformulate their search queries? Information Research, 20(1), 2015.
Arto Salomaa. Probabilistic and weighted grammars. Information and Control, 15:529-544, 1969.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588 (588):604-609 2020.
Shobit Sharma, Girma Tewolde, and Jaerock Kwon. Behavioral cloning for lateral motion con- trol of autonomous vehicles using deep learning. In 2018 IEEE International Conference on Electro/Informationn Technology (EIT), pp. 0228 0228-0233, 2018
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittiessrr, loannis Antonoglou, Veda Panneershelvam, Mare Lanetot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap. Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489.44994499 2016.
Artur Strzelecki. Eye-tracking studies of web search engines: A systematic literature review. Infor- mation, 1 11(6), 2020.
Yi Chern Tan and Elisa Celis. Assessing social and intersectional biases in contextualized word representations. In Advances in Neural Information Processing Systems, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, 2017.
Ellen Voorhees. The trec-8 question answering track report. In TREC, 11 2000.
Yining Wang, Liwei Wang, Yuanzhi Li, Di He, and Tie- Yan Liu. A theoretical analysis of ndog type ranking measures. In Proceedings of the 26th Annual Conference Learning Theory, pp. 25-54, 2013.
Kellie Webster, Xuezhi Wang, Ian Tenney, Alex Beutel, Emily Pitler, Ellie Pavlick, Jilin Chen, and Slav Petrov. Measuring and reducing gendered correlations in pre-trained models. https//urrisorr/ddt///00...00000 2020.
13

---

Under review as a conference paper at ICLR 2022
Wenhan Xiong, Xiang Li, Srini Iyer, Jingfei Du, Patrick Lewis, William Yang Wang, Yashar Mehdad, Scott Yih, Sebastian Riedel, Douwe Kiela, and Barlas Oguz. Answering complex open- open-domain questions with multi-hop dense retrieval. In International Conference Learning Representations, 2021.
Xingdi Yuan, Jie Fu, Marc-Alexandre Côté, Yi Tay, Chris Pal, and Adam Trischler. Interactive machine comprehension with information seeking agents. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, Online, July 2020. Association for Computational Linguisties.
Y. Yue and Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of ICML, 2009.
Weinan Zhang, Xiangyu Zhao, Li Zhao, Dawei Yin, and Grace Hui Yang. Drl4ir: 2nd workshop deep reinforcement learning for information retrieval. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2681-2684, 2021.
Victor Zhong, Tim Rocktäschel, and Edward Grefenstette. Rtfm: Generalising to new environment dynamics via reading. International Conference on Learning Representations, 2020.
14

---

Under review as a conference paper at ICLR 2022
APPENDIX
A ROCCHIO QUERY EXPANSIONS
Algorithm I provides a schematic summary of the procedure for generating Rocchio sessions. We omit the terms source for simplicity and readability, but it should be straightforward to reconstruct. Table A.7 shows an example session produced by Rocchio expansions using the full grammar.
Algorithm I: Rocchio Query Expansions
input :A question-answe pair (g. a), = 5, num num_steps = 20, = 100, M 100
output A of observation-query expansion pairs for training T5 agent RQE {(or, Aq:)}
RQE <- () q: q:
D. <- 0:
// Unique documents found in the session // The ideal query // Use search to get the top & documents // Use the agent and MR components to rerank the documents, extract answer spans to compute the snippets from the top results, and compile the observation (cf. also Appendix B
9. f- + "ooontetss"a"))
D. +- LuceneBM25 (g.)
o. + ComputeObservation (g. (.,
Σ, ComputeDicti onary (0.)
// Collect good search terms
for t - to num_steps do
D; D, LaceneeMM2 (g:);
0 f Compute@bserrvttion (q.4t, D,,k);
Σ, ComputeDictionaryy (o:);
E E. nE E + Σ, Σ.;
ComputeScore (g, k)
// Compute the score using Eq.
max_score +- 8;:
best_action + 0, wwm.mumiissse + 0:
// Evaluate all available pperators/fieldee and also without for op, field (f.,- 64 8) x {contents:, title:)) U {(",)) do
for w E TopNTerrss3LLuceeeetp (E.,N) do
(op- = ' Aw Σ V (op * Aws E Σt) A (num.tries < M) then Aq op(field'w')
q' - q: + Aq:
D' < D. U LuceneBM25 (g)); );
+ ComputeScore (q, D' k);
num_tries num tries
if 8' max_score then
max_score s'; best.action + Aqui
end else continue;
end
end
end
if max_scoree > 8 then
If the best action improves the score, add this step to the data, and continue the session a: + best.action:
RQE + RQE U (o,, bestinc
else
return RQE;
end
end
return RQE
15

---

Under review as a conference paper at ICLR 2022
B OBSERVATION BUILDING DETAILS
This section provides more details and examples about the encoding of observations for both the MuZero and the T5 agent. As described in Section 2.1 the main part of the observation consists of the top-5 documents from all results retrieved so far, U =0= Dj- The documents are sorted according to the PS score and reduced in size by extracting fixed-length snippets around the DPR reader's predicted answer. Moreover, the corresponding Wikipedia article title is appended to each document snippet. In addition to the top documents, the observation includes the original question and information about any previous refinements. While the main part of the observation is shared between the MuZero and the T5 agent, there are differences the exact representation. The following two paragraphs give a detailed explanation and example for both agents.
MuZero Agent's State (cf. 2.1 The MuZero agent uses a custom BERT (initialized from BERT- base) with additional embedding layers to represent the different parts of the observation. It consists of four individual embedding layers as depicted in Figure A At first, the standard layer for the tokens of the query, the current tree, and the current top documents DS. The second layer assigns type ID to each of the tokens representing if a token is part of the query, the tree, the predicted answer, the context, or the title of document. The last two layers add scoring information about the tokens as float values. We encode both the inverse document frequency (IDF) of a word and the documents' passage selection (PS) score. Figure A. shows a concrete example of a state used by the MuZero agent.
Layer
Query
Tree
Document Results
Tokens
qo
lo..... Im
Co Cot to. ... Ony Cr.y
Type
11
ID
ID,, ID I....... ID., ID ID:
IDF Score
md)
sk(ss) ide(l..
siF Idf(e)) iditt)........................ Al Idf(ew) k
PS Score
0
O
PS(d))..... PS((.)
Figure A.1: Schematic illustration of the MuZero search agent's state for the BERT representation function.
Table A.1: Example state of the MuZero search agent that is the input to the BERT representation function. The 'Type' layer encodes the state part information for each token. The 'IDF' and 'PS' layer are additional layers with float values of the IDF and the PS score of the input tokens, respectively.
Tokens
who
bunden
going
forwad query
avidence query
Type
[CLS]
query
query 6.77
query 0.00
query
query 0.00
query
query
query 0.00
query 0.00
query
0.00
7.77
5.13
5.53
5.28
5.77
0.00
0.00
0.00
0.00
0.00
0:00
0.00
0.00
Tokens
ISPP]
[pea]
[contcnt]
burden
Ads
[oeg]
[[ile]
soneetimes
[SEP)
Allgan
[SFP]
Type
SEP)
uree
tree
tree
Ince
thee
Ince
Irce
[SEP)
answer
answer 10.4
answer
[SEP]
IDP
0.00
0,00
0.00
9.64
9.64
0.00
0.00
4.92
0.00
10.64
10.64
1100
PS
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
-1.90
-3,90
-380
-3,80
Tokens
Kinds
for contest
cach
party
i8 vontict 0.00
diflerest
plases
Intiatiin contest
the context 0.00
baddai
Type
context 7.10
contect
contect
content 17.41
content
cuntest
contest
contest 17:41
cunteat
IDF
0.00
0.00
4.36
4.18 18
7.45
0.00
7.02
7.77
3,80
3.50
3.80
3.80
-330
3,80
3,80
3,50
-3.00
-3.00
-380
3,80
Tokens
suspicion
prebable 7.91
For 0.00
[SEP]
evidence
[SEP]
[SEP]
lifl
IDF
7.50
17.41
17.41
17.41
17.41
5.28
-2.20
12.20
12.30
-12.20
-12.20
-2.20
-2.20
-12.00
-12.20
T5 Agent's State (cf. 2..3
T5 represents the state as a flat string. The input is a concatenation of more expansions, and five results. For each result, include the answer given by the reader, the document's title, and a span centered around the answer. The prediction target simply the next expansion. See Table A.2 for a full example.
the original query,
16

---

Title: "The Chronicles of Narnia', Under review as a conference paper at ICLR 2022
Table A.2:
Example state (input) and prediction (target) of the T5 agent with linebreaks and emphasis added for readability. We use 30 token span in our experiments.
Input
Query: 'how many parts does chronicles of namna have". Contents must contain: lewis. Contents cannot contain: battle boost 2.0.
Answer: 'seven'.
Title: 'The Chronicles of Narnia'.
Result: The Chronicles of Narnia is series of seven fantasy novels by C. S. Lewis. It is considered classic of children's literature and the author's best-known work, having...
Answer: 'seven'.
Title: "The Chronicles of Narnia (film series)..
Result: "hhhe Chronicles Narmia", series novels by Lewis. From the seven books,
there have been three film adaptations so far - (2005), "" (2008) and "" (2010)...
Answer: 'seven'.
Title: 'Religion The Chronicles of Narnia'.
Result: 'Religion in The Chronicles of Narnia "The Chronicles of Narnia" is series of seven fantasy novels for children written C. S. Lewis. It is considered classic of...
Answer: 'seven'.
Result: 'Lewis's 's early life has paraliels with "The Chronicles Narnia". the age of seven, he moved with his family to a large house on the edge of Belfast...
Answer: 'Two'.
Title: "The Chronicles Narnia'.
Result: 'found in the most recent HarperCollins 2006 hardcover edition of "The Chronicles of Narnia". Two other maps produced result of the popularity of the 2005 film...
Target
Contents must contain: novels
NDCG@5
EM
Top-5
0.78
0.39
0.35
031
0.48
0.68
Figure A.2: Performance (NDCG@5, 5, EM, and Top-5, respectively) of the Rocchio episodes from NQ-dev guided by the composite score of Equation as function of the coefficients X₁ and A2-
C REWARD DETAILS
We investigate the effects of the three score components in the definition of the composite scoring function Eq. As mentioned Section 4 our experiments we have observed that using only the NDCG& score as reward signal (i.e., setting ê = X2 0 in Eq. 7 has several limitations. This motivated us to introduce the NDCEM, and PS components with the intent of: 1) providing further guidance to the agent (whenever NDCG& cannot be increased, the agent can further refine the query by increasing NDCEM;; or PS), and 2) regularizing the search episodes by making the score more robust with respect to exploratory behaviors that could lead to drift.
We run a grid search over the reward coefficients Å1, X2 and, for each their values, we evaluate the performance of the Rocchio query expansions on NQ Dev (for high throughput, select grammar G3 and set = M = 20). Figure A.2 the respective end-to-end performance in terms of our three main quality metrics: NDCG@5, EM, and Top-5.
17

---

Under review as a conference paper at ICLR 2022
The results in Figure A.2 support intents: by introducing NDCEM,, and PS scores in the reward (i.e., setting 21, A2 > 0), the Rocchio expansions can achieve significantly higher performance, in all the three metrics, with respect using only NDCG₁, score (λι X2 = 0) (notably, it improves also the NDCG@5 itself, meaning that the agent is not trading-off performance metries but it is indeed producing higher quality sessions). It is also worth pointing out the role of the NDCEM, score component, weighted by coefficient Ag. Notice that good NDCG@ @5 and Top-5 performance could be achieved also setting Ag 0 (see, e.g., the bottom-right corner Ar 1, A2 0). However, this leads to definitely worse EM results compared to when X2 > 0. Intuitively, a NDCEMr component 22 > 0 ensures that the returned documents, in addition containing the gold answer (thus having high NDCG @5 and Top-5), are also relevant for the query (thus reaching high EM). Hence, it is crucial to prevent semantic drifts. Based on these results we set À 0.2, A2 = 0.6, which is sweet spot in Figure A.2
D MODEL AND TRAINING CONFIGURATION
MuZero The MuZero agent learner, which performs both inference and training, runs on a Cloud TPU v2 with 8 cores which is roughly equivalent to 10 Nvidia P100 GPUs in terms of TFLOPS One core is allocated for training and 7 cores are allocated for inference. We use 500 CPU based actors along with 80 actors dedicated evaluation. Each agent trained for 1.6 million steps, with 100 simulations per step, at approximate speed of 10,000 steps per hour. In total, training takes about 10 days. Hyperparameters are listed in Table A.3
Table A.3: Hyperparameters for MuZero.
Parameter
Value
Simulations per Step Actor Instances Training TPU Cores
100
500
1
Inference TPU Cores
7
Initial Inference Batch Size (ha)
per core
Recurrent Inference Batch Size (fe. go)
32 per core
LSTT Units (go)
One layer of 512
Feed-forward Units (fo)
One layer of 32
Training Batch Size
16
Optimizer
SGD
Learning Rate
le-4
Weight Decay
le-5
Discount Factor (7)
.9
Unroll Length (K)
5
Max. #actions Expanded per Step
100
Max. context tokens from document title
10
Max. context tokens from document content
70
T5 The T5 agent is trained on 16 Cloud TPU v3, starting from the pre-trained T5-1 1B checkpoint. We mostly follow the suggested hyperparameter choices given by Raffel al. (2020). see Table A.4 We train for about 2 days at roughly 3 steps per second for total of 50k steps and select a checkpoint based on dev performance.
'The Cloud TPU v2 has peak performance of 180 TFLOPS httpp:://looddd.oolle...oo whereas the Nvidia P100 GPU goes up 18.7 TELOPS depending on precision com/ http///ootttteeecccece g
18

---

Under review as a conference paper at ICLR 2022
Table A.4: Hyperparameters for T5.
Parameter
Value
Number of Parameters
11B
Encoder/Decoder Layers
24
Feed-forward dimension
65536
KV dimension
128
Model dimension
1024
Number of Heads
128
Batch Size (in tokens)
65536
Dropout Rate
0.1
Learning Rate (constant)
0.0005
Optimizer
AdaFactor
Maximum input length (tokens) Maximum target length (tokens) Finetuning steps NQ Train
512
32
41400
Max. context tokens from document title Max. context tokens from document content
10
30
RESULTS
Table A.5 reports the results for the different versions the T5 agent, evaluated on dev. We don't t evaluate all agents with the generative answer system, for answer quality report only the performance of the internal machine reader (EM-MR). Table A.6 6.6le reports extended results, including for NQ Dev and the PS/MR component answer quality eval (EM-MR).
Table A.5: Results of all T5 Agents NQ Dev.
Version
NDCG@5
Top-1
Top-5
EM-MR
Reward
G0
40.75
52.12
64.93
30.22
33.30
G1
43.10
52.12
66.09
29.50
35.55
G2
41.16
51.51
63.54
30.03
33.81
G3
41.69
51.34
64.17
29.77
33.95
G4
41.53
50.98
63.49
29.70
34.25
Table A.6: Results on NQ Dev and Test.
Metric
Data
BM25
PS(Do)
MZ
T5-G1
MZ+T5s
DPR
RQE-G4
NDCG@5
Dev
19.83
22.95
30.76
43.10
45.30
64.89
Test
21.51
24.82
32.23
44.27
46.22
65.24
Top-1
Dev
28.17
43.06
46.02
52.12
54.15
74.99
Test
28.67
44.93
47.97
52.60
54.29
52.47
73.74
Top-5
Dev
50.47
50.47
57.71
66.09
70.05
88.21
Test
53.76
53.76
59.97
66.59
71.05
72.24
88.17
EM-MR
Dev 15.31
25.15
27.17
29.50
31.12
47.38
Test
14.79
25.87
28.19
30.08
30.58
41.50
46.34
EM-T5
Dev
28.98
40.70
32.48
44.75
44.47
63.78
Test
28.78
41.14
32.60
44.04
44.35
41.50
62,35
19

---

Under review as a conference paper at ICLR 2022
F DETAILS AND EXAMPLES FOR THE GRAMMAR-GUIDER MCTS
for at)
Q = WQ UQQ STOP
d+++1
- Op Field W
Po: to +f
Op
-I + A
E {0.1, 4,
Q UQQ
Field
title contents
Ph 11
Wx
V V W
W
V
V W
Op
Va
wwow E VB A
trie(E*)
HasSubstringg(u)
h. BERT & GRU
V
#w E VI A trie(E*). HasSubstring((
LSTM
π
MLP
(a) The productions of the query grammar: x identifics specific vocabulary induced by the aggregated results at time l (index omitted), Va (Vrg) is the BERT wordpiece prefix (suffix) vocabulary. wi denotes the string ending w, including the preceding wordpicces.
(b) The MuZero MCTS with grammar- guided node expansions represented as edge labelled with CFG rules.
Figure A.3
lists the detailed rules schemata for the query grammar used by the MuZero agent explained in Section 3.1 An optional STOP rule allows the agent to terminate episode and return the results collected up to that point. Using the BERT sub-word tokens as vocabulary allows us to generate a large number of words with total vocabulary size of ~30k tokens.
Figure A.3a
Our implementation of MuZero modifies the MCTS to use the query grammar for efficient exploration. Figure A..bb shows the different network components used during MCTS. Each node expansion is associated with grammar rule. When the simulation phase complete, the visit counts collected at the children of the MCTS root node provide the policy from which the next action a++1 is sampled.
Each simulation corresponds to one or more hypothetical follow-up queries (or fragments) resulting from the execution of grammar rules. The MCTS procedure executes Depth-First node expansions, guided by the grammar, to generate a query top-down, left-to-right, in a forward pass. To control the process, add two data structures to MCTS nodes: stack 7 and an output buffer wt ry contains list of unfinished non-terminals, w stores the new expansion. The stack is initialized with the start symbol 7 = [Q]. The output buffer reset, w []. after each document search. When expanding a node, the non-terminal symbol on the top of y is popped, providing the left-hand side of the rule associated with the new edge. Then, symbols on the right-hand side of the rule are pushed right-to-left onto 7. When terminal rule is applied. the terminal symbol is added to w. The next time y contains only Q, w holds the new query expansion term Age to be appended to the previous query a for search.
Figure A.4 illustrates the process. Nodes represent the stack y and output buffer w. Edges are annotated with the rule used to expand the node. We illustrate the left-branching expansion. Starting from the top, the symbol "Q" is popped from the stack, and a compatible rule, "Q = W Q". is sampled. The symbols "W" and "Q" are added the stack for later processing. The agent expands the next node choosing to use the document content vocabulary (W = W then it selects a vocabulary prefix ('dial'), adding it to the output buffer w, followed by vocabulary suffix ('ects"). At that point, the stack contains only Q and the content of w contains a new expansion, the term 'dialects'. A latent search step is simulated through MuZero's ge sub-network. Then the output buffer w is reset.
After the latent search step, the simulation forced use the full trie (W + Wok), which includes all terms in the Lucene index. This is necessary since there is no observable context that can be used restrict the vocabulary. Instead of simply adding an OR term (Q = W Q), the right branch of the example selects an expansion with unary operator and field information (Q + U Q).
20

---

Under review as a conference paper at ICLR 2022
(Q)w=
Q Q
Q UQ
7= (W. Q). = 0
y= (U. w/ !
w
U Op Field W
7= [W"."W""w 1
= Field, W. w 0
W V w
(V9, W., @Q
va dial
[W" _), [dall
W
Q w ddall
vo ects
[Q].
(dillects]
SEARCH
= W WQ
W Wm
(W Q)
Figure A.4
SEARCH SESSION EXAMPLES
Table A.7 shows an example of session produced by Rocchio expansions using the full grammar.
Table A.8 shows a session generated by the MuZero agent.
21

---

Under review as a conference paper at ICLR 2022
Table A.7: Example of Rocchio Query Expansion session.
q0
who were the judges the factor
[score: 0.043]
di Title
The X Factor (Australian TV series)
Chloe Maxwell. After "The X Factor" was revived for second season in 2010, Natalie Garonzi became the new host of "The Xtra Factor" the Seven Network's digital channel...
d2 Title: X Factor (Icclandic TV series)
the show. The judges were the talent agent and businessman Einar Bárdarson, rock musician Elínborg Halldórsdótti and pop singer Paul Oscar. Previously both Einar and Páll Óskar had been judges
qoo (contents:"confirne confirmed"
(score: 0.551]
d1 Title:
The Factor (U.S. season 2)
... Khloć Kardashian and "Extra" host Mario Lopez, replacing Steve Jones from the previous year. Simon Cowell and L.A. Reid returned as judges, while Paula Abdul and replaced...
Nicole Scherzinger
d2 Title: The X Factor (New Zealand series
... The series screened on Sunday and Monday evenings. "The Factor" was created by Simon Cowell in the United Kingdom and the New Zealand version is based on the original...
q1 (title:"2">8))
[score: 0.678)
d4 Title: The X Factor (U.S. season 2)
... It was also reported that Cowell was in talks with Britney Spears for her to join the show, reportedly offering her $15 million. On May 9, reports surfaced that Spears
ds
Title: H.F.M. (The Hunger for More
... Banks' confirmed that Cardiak produces four songs on the album. Confirmed guests include Eminem, Kanye West, Lloyd, Juelz Santana, 50 Cent, Styles P, Rackwon, Tony Yayo, Jeremih and...
q2 "ccotents:""brinny"
[score: 0.804)
dg Title: The X Factor (U.S. TV series)
Reid, former "The X Factor" judge Cheryl Cole, and Cowell's former "American Idol" colleague Paula Abdul were confirmed join Cowell in the judging panel. Cole
dismissed from the ...
d4 Title: The X Factor (New Zealand series 2)
... from the first series, Stan Walker and Melanic Blatt, were confirmed to return as judges. The other two judges from the first series, Daniel Bedingfield and Ruby Frost,
...
d,
Title: The Factor (U.S. season 2)
... It was also reported that Cowell was in talks with Britney Spears for her to join the show, reportedly offering her $15 million. On May 9, reports surfaced that Spears
q1
"qs" (contents:" "coeel""" x4)
[score: 0.926]
di Title: The X Factor (U.S. season 2)
(BM25 Rank: 15)
Khloé Kardashian and "Extra" host Mario Lopez, replacing Steve Jones from the previous year. Simon Cowell and L.A. Reid returned as judges, while Paula Abdul and replaced...
Nicole Scherzinger
d2 Title: The X Factor (New Zealand series
(BM25 Rank: 195)
... The series screened on Sunday and Monday evenings. "The Factor" was created by Simon Cowell in the United Kingdom and the New Zealand version is based on the
original...
dg Title: Louis Walsh
(BM25 Rank: 1000)
from bronchitis. He joined other season two judges: I..A. Reid, Demi Lovato and Britney Spears, and was introduced with the line, "When Simon needs an opinion from someone...
d4 Title: The X Factor (U.S. TV series) ... Reid, former "The X Factor" judge Cheryl Cole, and Cowell's former " "American Idol" collcague Paula Aduul were confirmed join Cowell the judging panel. Cole was dismissed from the...
(BM25 Rank: 206)
d5
Title: Simon Cowell
(BM25 Rank: 1000)
... the winning judge. Cowell and Reid returned for season 2, while Demi Lovato and Britncy Spears joined the judging panel as replacements for Abdul and Scherzinger. This season launched another
22

---

Under review as a conference paper at ICLR 2022
Table A.8: Example of a MuZero agent search session.
qo
who the wwe money in the bank
[score: 0.071]
d1 Title: Money in the Bank (2017)
... the pre-show and two Money in the Bank ladder matches on the main card. In the main event, Baron Corbin won the men's ladder match, earning contract for a WWE Championship match, while Carmella controversially won the first women's ' ladder match to earn SownkDown Women's 's Championship match contract. In another prominent match, Jinder Mahal defeated Randy Orton to retain the WWE Championship. The event was also notable... ...
q:
"o' "contents:"jindeds x2)
[score: 0.130]
di Title: Money in the Bank ladder match
... ...For the traditional ladder match, which had contract for match for Sownk WWE Championship. SmackDown Commissioner Shane McMahon announced AJ Styles, Shinsuke Nakamura. Dolph Ziggler, Sami Zayn, and Baron Corbin as the original five participants, United States Champion Kevin Owens was added after he convinced Shane to make him the sixth participant. Mojo Rawley had the opportunity make it seven- man match if he could defcat WWE...
42
(contents:""olphe
[score: 0.138]
"qa"
(contents:"won"
[score: 0.138]
(contents:"zayn""
[score: 0.414)
d1 Title: Money the Bank (2018)
April 23 episode of "Raw", Bobby Lashley performed one handed suspended vertical suplex Sami Zayn, which Zayn claimed gave him vertigo and why he missed the Greatest Royal Rumble, At Backlash, Lashley and Braun Strowman defeated Kevin Owens and Sami Zayn. During an interview on May episode, I Lashley spoke dearly about his family, including his three sisters. In response, Zayn said that Lashley was not a nice
"q'" "cootents:"stroowaan"" "srowwann" x2)
[score: 0.587)
d2
Title:
Kevin Owens
both men would be awarded Raw contracts by Raw Commissioner Stephanic McMahon. Later that night, Owens teaming up with Zayn, The Miz, Curtis Axel and Bo Dallas and lost Finn Bálor, Seth Rollins, Braun Strowman, Bobby Lashley and Bobby Roode a 10-man tag team match. On May episode of "Raw", lost Money the Bank qualifying match to Braun Strowman. At Backlash, Owens...
96
'qs' (contents:"first x2)
[score: 0.587]
47
qqo (contents:"rooder
[score: 0.848]
di
Title: Bobby Lashley
(BM25 Rank: >1000
... Lashley participated in the Greatest Royal Rumble the namesake event, entering at #44 and scoring two eliminations, but was eliminated by Braun Strowman. The first month of Lashley's return would see him in a number of tag-team matches, teaming with the likes of Braun Strowman, Bobby Roode, Finn Balor, Seth Rollins, and Roman Reigns, all being victorious efforts against the likes Kevin Owens, Sami Zayn, Jinder Title: Kevin Owens and Sami Zayn
d2
(BM25 Rank: > 10000
... following week, as she would award both men "Raw" contracts. Later that night, Owens and Zayn teamed up with The Miz and The Miztourage (Curtis Axel and Bo Dallas), against Finn Balor, Seth Rollins, Braun Strowman. Bobby Lashley, and another new "Raw" member Bobby Roode, but their team was defeated. The following week on "Raw", they teamed up in an unsuccessful attempt to defeat Strowman and Lashley. On the
dg Title: Money in the Bank (2018)
(BM25 Rank: 282)
... April 23 episode of "Raw". Bobby Lashley performed one-handed suspended vertical suplex on Sami Zayn, which Zayn claimed gave him vertigo and why missed the Greatest Royal Rumble. At Backlash, Lashley and Braun Strowman defeated Kevin Owens and Sami Zayn. During interview on the May 7 episode, Lashley spoke dearly about his family, including his three sisters. In response. Zayn said that Lashley not nice
23


Reviews:
[{"review_id": "M09fdpdklJC", "reviewer": "Reviewer_NpVB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n- Contribution in the important direction of training RL agents to find information via iterative query refinement.\n- The propose of generating synthetic search sessions via Rocchi query expansions.\n-  Achieving comparable performance in a more interpretable way with pretrained LMs and RL training.\n- The paper is well written and easy to follow\n\nWeaknesses\n\n- The results of the paper might be hard to reproduce though the authors have provided enough details. I hope that the author can provide a complete training recipe so the results will be reproducible for future work.", "summary_of_the_paper": "This paper investigates a vital direction: How can RL agents learn to use search engines to find information. The authors propose a method that leverages pre-trained models conditioned on machine reading results to guide the selection of query refinement from aggregated search documents. The method performs comparably to neural retrievers on OpenQA-NQ but operates in a more interpretable way.", "summary_of_the_review": "This paper contributes to an interesting direction - training RL agents to find information via iterative query refinement. The proposed method achieves descent performance in a more interpretable way. But one concern is the model reproductivity. It would be very helpful to have the model full training recipe for reproductivity and benchmarking.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "EYMNfgH7I3X", "reviewer": "Reviewer_NfBM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes an interesting idea to formulate an enhanced query using a grammar, in which 3 types of operators are allowed. The grammar corresponds to those used in Lucene (and other search engines). So it is quite general.\nThe key strength of the paper is its exploration of this idea in query reformulation context. RL is used to learn to reformulate the query.\nThe paper has several weaknesses:\n- While the grammar is commonly used in search engines, it is not as refined as one could expect. In pseudo relevance feedback, adding a good term into the query is only part of the task. Another part of to assign an appropriate weight to it. This second part is not taken into account in this paper, or only partially taken into account. It is assumed that a term is added with a few fixed weights. This may be suboptimal.\n- The proposed method is very expensive to train. I would assume that it is also expensive in inference (this is not reported in the paper). The high cost is not rewarded at the end: it performance is (at best) similar to that of DPR. So the question is whether it is beneficial to use the expensive solution instead of a simpler one.\n- The experiments show that the strategy G1 works the best, although the grammar allows to add other operators. It would be interesting to analyze why this happened. Especially, G4 contains all the operators, and a good model would be able to choose the best one among them. The fact that G4 is much worse than G1 indicates that the model is unable to make a good choice.\n- The retrieval using BM25 is a strong limitation to the approach. Although BM25 is a good and efficient IR method for retrieving full documents, for question answering where one deals with much shorter documents or passages, neural models are often better.\n- Reading the example provided in the paper, it does not seem that T5 or BERT has a good capability to predict the expansion term to add. Some of the added terms are not very meaningful (e.g. \"3\"). This may hint that the way new terms are chosen may not work well in practice. This could stem from T5 or BERT used, or from the general learning framework based on Rocchio's pseudo relevance feedback. More analysis is needed to understand the problem.\n- In IR, it is often the case that pseudo relevance feedback beyond a few times (usually once) is not beneficial and may easily lead to query drift. The process of expansion contains many steps of pseudo relevance feedback. Would there a high risk of query drift?\n- Finally, experiments on more datasets is desired.", "summary_of_the_paper": "This paper proposes an approach based on MuZero to learn strategies to enhance the search query. It borrows the idea of pseudo relevance feedback of Rocchio, selects terms from the top-5 retrieved results, and incorporate a term using a predefined grammar.\nThe expanded query is used by BM25 to find documents.\nThe approach is tested on NQ dataset. It is shown to achieve a performance comparable to that of DPR.\nThe key contribution of the exploration of MuZero for query enhancement, combined with the idea of Rochio. This exploration is new.", "summary_of_the_review": "+ The idea to built a structured query following a grammar is interesting. This follows the work of MuZero.\n+ The use of pseudo relevance feedback to generate candidate terms to add in this context is also interesting.\n- Unfortunately, the performance is not at the level expected.\n- The complexity of the method is very high, making it difficult to use in practice.\n- The presented grammar is used only partially in the best performing case. It is unclear if the grammar defined in this way is reasonable.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EA0z5nfN1GV", "reviewer": "Reviewer_13nH", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:**\n- This work is generally well-written with good coverage of the literature. \n- Most components are motivated and explained throughout the text. \n- There is also extensive qualitative analysis of the query expansion results.\n\n**Weaknesses:**\n- Unfortunately, despite the careful fine-tuning and modifications on the compilation of several components, results seem inferior to a neural passage retrieval model. There is a discussion on why this might be the case, and how this work provides the foundations for work on policy synthesis in search and retrieval tasks. But when comparing a distributed MuZero agent trained on 1.6 million steps (approx. 10 days) and a T5 agent with 11 billion parameters over DPR, it makes sense to also report on the number of parameters (model capacity comparison) and the total training times and the number of training examples (time/sample complexity comparison).\n- A comparison with related work on RL for query reformulation, e.g., Nogueira & Cho (2017), Buck et al. (2018) and [1]. Albeit these models have been tested in one-step episodes, there is no explanation on why these cannot be trained in a multistep refinement setting.\n- Please also include SOTA passage retrieval models, such as [2].\n\n[1] Nogueira, Rodrigo, Jannis Bulian, and Massimiliano Ciaramita. \"Learning to coordinate multiple reinforcement learning agents for diverse query reformulation.\" arXiv preprint arXiv:1809.10658 (2018).\n[2] Qu, Yingqi, et al. \"RocketQA: An optimized training approach to dense passage retrieval for open-domain question answering.\" Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021.\n\n**Questions:**\n- Just to confirm, for the Rocchio feedback, the method operates in vector space, i.e., w_t and q_t are vector representations?\n- Are results reported over multiple trials?\n- A proper ablation study over the rewards would have been useful. To my understanding from Figure A.2, if one sets $\\lambda_1 = 1$ and $\\lambda_2=0$, better performance can be achieved in terms of NDCG and Top-5, rather than the reverse (i.e.,  $\\lambda_1 = 0$ and  $\\lambda_2 = 1$). Extracting insights for EM is not so clear. Does this mean that the proposed NDCEM does not really benefit the retrieval performance? Please provide further explanations.\n\n**Minor comments:**\n- It appears there is a typo after Eq.(1): \"This may add a keyword .... $\\sum_{idx}$, the search index vocabulary,\" ==> \"$\\sum_{idx}$, where $\\sum_{idx}$ is the search index vocabulary\"\n- Please further explain the part after Eq.(3): \"This means it is possible to upgrade accessible terms to exact matches, or weight boosting, if they also occur in the *ideal result set* and to exclude accessible terms if they are not present in the *ideal results*\"\n\n**Update after rebuttal:**\nThank you to the authors for their response that clarified some of the paper details. I have read the reviews and responses and my score remains unchanged. The main motivation of transparent and interpretable agent-based query reformulation could be a significant contribution but would be better highlighted with experiments on additional datasets, further discussion on the complexity of the method and qualitative results that show the enhanced interpretability over prior \"pure RL\" works.\n(Minor clarification: Albeit a \"contemporaneous\" work, surprisingly RocketQA has been on arXiv since October 2020.)", "summary_of_the_paper": "This work designs an RL (customized BERT MuZero) agent for query reformulation, where the underlying observation is defined as an aggregation of windows of answer spans found with a machine reading module, document titles, query tokens, and refinements. The action space involves adding keywords to the query or form search terms with three operators that constrain the search space. Due to the lack of training data, synthetic search sessions are generated with a pretrained transformer model and imitation learning. The reward is a linear combination of NDCG (well-established IR ranking for non-binary relevance), a revised NDCG-like metric for exact matches (NDCEM) and a top-k Passage Score. Results on an OpenQA dataset are *close* to neural passage retrieval methods. \n\n", "summary_of_the_review": "While this is, as the authors explain, an endeavor that required customization of several components to reach comparable performance with DPR, the method proposed appears to be computationally expensive without significant improvements over neural retrieval. Alongside the lack of comparison over prior work on RL for query reformulation and the lack of discussion over other dimensions apart from performance (and maybe some qualitative analysis), the paper will benefit from further extensions and revisions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a method to improve search engines; the method is designed based on the BM25 retrieval method and is evaluated on NQ open dataset. The reviewers agree that the motivation is interesting and implementation is reasonable, but the authors have only showed the impact of their approach over one retrieval method and one dataset, which is limited and does not show if the method is general enough or not.
Decision: Reject