# MA4DIV: Multi-Agent Reinforcement Learning for Search Result Diversification

Yiqun Chen  GSAI, Renmin University of ChinaBeijingChina
<EMAIL_ADDRESS>,  Jiaxin Mao  GSAI, Renmin University of
ChinaBeijingChina<EMAIL_ADDRESS>,  Yi Zhang  Baidu Inc.BeijingChina
<EMAIL_ADDRESS>,  Dehong Ma  Baidu Inc.BeijingChina<EMAIL_ADDRESS>,
Long Xia  Baidu Inc.BeijingChina<EMAIL_ADDRESS>,  Jun Fan  Baidu
Inc.BeijingChina<EMAIL_ADDRESS>,  Daiting Shi  Baidu Inc.BeijingChina
<EMAIL_ADDRESS>,  Zhicong Cheng  Baidu Inc.BeijingChina
<EMAIL_ADDRESS>,  Simiu Gu  Baidu Inc.BeijingChina<EMAIL_ADDRESS>and  Dawei Yin  Baidu Inc.BeijingChina<EMAIL_ADDRESS>
###### Abstract.

The objective of search result diversification (SRD) is to ensure that
selected documents cover as many different subtopics as possible. Existing
methods primarily utilize a paradigm of ”greedy selection”, i.e., selecting
one document with the highest diversity score at a time. These approaches tend
to be inefficient and are easily trapped in a suboptimal state. In addition,
some other methods aim to approximately optimize the diversity metric, such as
$\alpha$-NDCG, but the results still remain suboptimal. To address these
challenges, we introduce Multi-Agent reinforcement learning (MARL) for search
result DIVersity, which called MA4DIV. In this approach, each document is an
agent and the search result diversification is modeled as a cooperative task
among multiple agents. This approach allows for directly optimizing the
diversity metrics, such as $\alpha$-NDCG, while achieving high training
efficiency. We conducted preliminary experiments on public TREC datasets to
demonstrate the effectiveness and potential of MA4DIV. Considering the limited
number of queries in public TREC datasets, we construct a large-scale dataset
from industry sources and show that MA4DIV achieves substantial improvements
in both effectiveness and efficiency than existing baselines on a industrial
scale dataset.

Search Result Diversification; Learning to Rank; Multi-Agent Cooperation;
Reinforcement Learning

##  1\. Introduction

How to provide diverse search results to users is an important yet complicated
problem in information retrieval. The search result diversification (SRD)
(Agrawal et al., 2009) means that for a user’s search query, we need to
provide search results that cover a wide range of subtopics to meet the
requirements of users who may have multiple interpretations or intentions.
Many diversity-aware metrics, such as $\alpha$-NDCG (Clarke et al., 2008),
ERR-IA (Chapelle et al., 2011), S-recall (Zhai et al., 2015), have been
proposed to evaluate the effectiveness of search result diversification. Since
the diversity of a given document is affected by the documents that precede
it, optimizing some of the diversity metrics is an NP-Hard problem
(Carterette, 2011). Therefore, the diversity of search results has become an
important and challenging research topic.

The typical search result diversification method includes heuristic methods
and learning-based methods. These methods use ”greedy selection” to
sequentially select documents to build a diversified ranking list in a step-
by-step manner. At each step, the ranking model selects the best document for
the current ranking position according to the additional utility it can bring
to the whole ranking list. Different methods use different criteria in the
greedy selection. Maximal marginal relevance (MMR) (Carbonell and Goldstein,
1998) algorithm proposes maximal marginal, which is defined as the sum of
query-document dependencies, and takes the maximum document distance as the
utility. xQuAD (Santos et al., 2010) is another widely used diverse ranking
model which defines the utility to explicitly account for relationship between
documents retrieved for the original query and the possible sub-queries. In
recent years, many methods based on machine learning (Zhu et al., 2014; Xu et
al., 2017; Li et al., 2009; Mihalkova and Mooney, 2009; Qin et al., 2023) have
been proposed to solve the search result diversification task. For example,
the relational learning to rank (R-LTR) (Zhu et al., 2014) and its variants
utilize a linear combination of correlation features and novelty features.

All above methods focus on estimating the utility of candidate documents
directly based on user queries and previously selected documents, but fail to
explicitly model and fully utilized the utility that the user has gain in
examining previous documents. Xia et al. (2017) propose the MDP-DIV framework
to model the search result diversification ranking as Markov Decision Process
(MDP) (Puterman, 2014), and uses a reinforcement learning algorithm (Williams,
1992) to optimize the ranking model. While MDP-DIV still use a ”greedy
selection” to select next candidate result, it can easily lead to sub-optimal
ranking list. $\mathrm{M^{2}Div}$ (Feng et al., 2018) introduces Monte Carlo
Tree Search (MCTS) (Coulom, 2006) for high-quality exploration. This method
helps to alleviate the problem of being stuck in a sub-optimal solution at a
cost of increasing training and inference time.

Besides these greedy selection methods that sequentially score and select each
candidate results, some recent studies DALETOR (Yan et al., 2021) and MO4SRD
(Yu, 2022) propose to simultaneously score all candidate documents and obtain
the whole ranking list by sorting these scores in a descending order. This
paradigm can greatly improve the inference efficiency as the documents can be
scored in parallel. In addition, DALETOR and MO4SRD propose a differentiable
proxy for the non-differentiable diversity metric $\alpha$-NDCG (Clarke et
al., 2008), which enables a gradient-based optimization for the diversity
metric. However, since the optimization goal is an approximation to the real
evaluation metric, the solution may still be sub-optimal.

To summarize, although the problem of search result diversification has been
extensively investigated, existing methods still have some limitations in
terms of the effectiveness and efficiency. From the perspective of
effectiveness, the heuristic-based methods (e.g. (Carbonell and Goldstein,
1998; Santos et al., 2010)) and the approximation-based methods (e.g.(Yan et
al., 2021; Yu, 2022)) may be sub-optimal in optimizing the end diversity
metric, such as $\alpha$-NDCG and ERR-IA. From the perspective of efficiency,
those RL-based approaches face a intrinsic challenge of exploring a huge space
of all possible rankings, which inevitably leads to sub-optimal solution (Xia
et al., 2017) or high time-complexity in both training and inference (Feng et
al., 2018).

In this paper, in order to alleviate the problems of existing methods
mentioned above, we propose to formalize the diverse ranking as a multi-agent
cooperation process. Since Multi-Agent reinforcement learning (MARL) algorithm
is used to optimize the DIVersity ranking model, we call this new method
MA4DIV. Specifically, by treating each document as an independent agent within
a Decentralized Partially Observable Markov Decision Process (Dec-POMDP)
setting, we simulate a fully cooperative multi-agent task. In this setup, each
agent (document) makes action selections based on observations that include
the features of both the query and the documents, aiming to maximize a shared
reward function that is directly related to the diversity evaluation metrics
of search results. Considering permutation equivariant (Pang et al., 2020)
property of the ranking task, our MA4DIV framework leverages the Multi-Head
Self-Attention (MHSA) for capturing the intricate relationships between
documents. Furthermore, MA4DIV employs value decomposition (Rashid et al.,
2018) to optimize global diversity directly by the structures of mixing
network and hypernetworks during training.

The advantages of our MA4DIV over existing works include:

(1) Compared to ”greedy selection” paradigm, MA4DIV simultaneously predicts
the ranking scores of all documents, which can improve the efficiency of
ranking process and alleviate the local optimum problem.

(2) The ranking scores of all documents and a ranked documents list with
diversity can be obtained in one time step. Therefore, MA4DIV has higher
exploration efficiency than single-agent RL algorithms, such as MDP-DIV and
$\mathrm{M^{2}Div}$, which must go through an entire episode to explore a
diversity ranking list.

(3) The training of the MA4DIV model does not require any approximations of
different diversity metrics as they can be directly optimized as reward in the
multi-agent reinforcement learning process.

In order to demonstrate the effectiveness and efficiency of MA4DIV, we
conducted experiments on TREC benchmark datasets and Baidu dataset. The
experimental results on TREC datasets showed that, MA4DIV achieved the state-
of-the-art performance on some evaluation metrics, and training time was
significantly shorter than baselines. Considering the small number of queries
in TREC dataset (only 198 valid queries), we built a larger diversity dataset
based on the real Baidu search engine data, which is called DU-DIV. On the DU-
DIV dataset, MA4DIV achieved the state-of-the-art performance on all
evaluation metrics, and demonstrated a substantial improvement in exploration
efficiency and training efficiency.

##  2\. RELATED WORK

###  2.1. Search Result Diversification

The construction of a diverse ranking list in search is commonly formalized as
a sequential document selection process or a process of greedy sequential
decision-making. The aim is to design effective criteria for estimating the
utility a document can bring, which is believed to depend not only on the
document itself but also on the preceding documents. Various models have been
proposed to guide this selection.

Carbonell and Goldstein introduced the maximal marginal relevance criterion
(Carbonell and Goldstein, 1998), which uses a linear combination of query-
document relevance and document novelty to determine the document to be
selected. This process is iterative, with the marginal relevance score updated
as the number of documents in the result set increases. An extension of this
concept, the probabilistic latent MMR model (Guo and Sanner, 2010), was
proposed by Guo and Sanner.

Approaches such as xQuAD (Santos et al., 2010) directly model different
aspects of a query, estimating utility based on the relevance of retrieved
documents to identified sub-queries or aspects. Hu et al. (Hu et al., 2015)
proposed a utility function that leverages hierarchical intents of queries,
aiming to maximize diversity in the hierarchical structure. Other researchers,
like He et al. (He et al., 2012), have proposed combining implicit and
explicit topic representations to create better diverse rankings, while
Gollapudi and Sharma (Gollapudi and Sharma, 2009) proposed an axiomatic
approach to result diversification.

Machine learning techniques have also been applied to construct diverse
ranking models, often adhering to the sequential document selection or greedy
sequential decision-making framework. These techniques aim to automatically
learn the utility function based on training queries. Several researchers have
defined utility as a linear combination of handcrafted relevance and novelty
features (Zhu et al., 2014; Xia et al., 2015; Xu et al., 2017). In (Xia et
al., 2016), novelty can be modeled using deep learning models such as neural
tensor networks. Radlinski et al. (2008) propose to learn a diverse ranking of
documents directly based on users’ clicking behavior.

Reinforcement learning algorithms also are proposed to improve the
effectiveness of ”greedy selection” paradigm in search result diversification.
MDP-DIV (Xia et al., 2017) consider the diverse ranking process as a Markov
Decision Process (MDP). In MDP-DIV, agent select one document in one time
step, so a ranked list can be obtained after an episode. And the episode
reward can be any metrics, such as $\alpha$-DCG. While Feng et al. (2018)
think that ”greedy selection” paradigm is easily lead to local optimum, so
$\mathrm{M^{2}Div}$ is proposed to introduce Monte Carlo Tree Search (MCTS)
into MDP ranking process. In this way, $\mathrm{M^{2}Div}$ does alleviate the
problem that tend to fall into local optimum by conducting high-quality
exploration, but also brings expensive training and inference costs.

There are other methods which approximate the diversity evaluation metrics to
be differentiable and optimize the approximated metrics directly through the
loss function. Based on score-and-sort paradigm, DALETOR (Yan et al., 2021)
and MO4SRD (Yu, 2022) are proposed to derive differentiable diversification-
aware losses which are approximation of different diversity metrics, such as
$\alpha$-NDCG.

###  2.2. Reinforcement Learning for IR

Xu et al. (Wei et al., 2017) formulate a ranking process as an MDP and train
the ranking model with a policy gradient algorithm of REINFORCE (Williams,
1992). Singh et al. (Singh and Joachims, 2019) propose PG Rank algorithm to
enhance the fairness of ranking process with reinforcement learning methods.
PPG (Xu et al., 2020) uses pairwise comparisons of two sampled document list
with in a same query, which makes an unbiased and low variance policy gradient
estimations. Yao et al. (Yao et al., 2020) model the interactions between
search engine and users with a hierarchical Markov Decision Process, which
improves the personalized search performance. RLIRank (Zhou and Agichtein,
2020) implement a learning to rank (LTR) model for each iteration of the
dynamic search process. Zou et al. (2019) formulate the ranking process as a
multi-agent Markov Decision Process, where the interactions among documents
are considered in the ranking process. However, Zou et al. (2019) conduct the
single-agent reinforcement learning algorithm REINFORCE to optimize the
ranking model.

###  2.3. Multi-Agent Reinforcement Learning

Value decomposition (Sunehag et al., 2017; Rashid et al., 2018; Wang et al.,
2020b, a; Chen et al., 2022b, a) and Actor-Critic (Lowe et al., 2017; Zhang et
al., 2022, 2023a, 2023b; Yu et al., 2022) are two typical branches of multi-
agent reinforcement learning (MARL). Among these, QMIX (Rashid et al., 2018)
is the algorithm that first obtains the global utility function by nonlinear
combination of individual utility functions, which can assign the global
reward to each agent implicitly and nonlinearly. In this paper, we conduct the
framework of QMIX as a reference to optimize the diverse ranking process.

##  3\. Background

###  3.1. Dec-POMDP

In this work, we consider the process of diversity ranking as a fully
cooperative multi-agent task which is usually modeled as a Decentralized
Partially Observable Markov Decision Process (Dec-POMDP) (Oliehoek and Amato,
2016). Dec-POMDP is formally defined as a tuple
$G=\left\langle\mathcal{S},\mathcal{A},\mathcal{P},r,\mathcal{Z},\mathcal{O},n,\gamma\right\rangle$.
$s\in\mathcal{S}$ is the global state of the environment. Each agent
$i\in\mathcal{G}\equiv\\{1,\dots,n\\}$ chooses an action $a^{i}\in A$ which
forms the joint action $\textbf{a}\in\mathcal{A}\equiv A^{n}$. The state
transition function is modeled as
$\mathcal{P}(s^{\prime}|s,\textbf{a}):\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to[0,1]$.
The reward function which is modeled as
$r(s,\textbf{a}):\mathcal{S}\times\mathcal{A}$ is shared by all agents and the
discount factor is $\gamma\in[0,1)$. It follows partially observable settings,
where agents do not have access to the global state. Instead, it samples
observations $z\in\mathcal{Z}$ according to observation function
$\mathcal{O}(s,i):\mathcal{S}\times\mathcal{A}\to\mathcal{Z}$. Each agent has
an action-observation history trajectory $\tau^{i}\in
T\equiv(\mathcal{Z}\times\mathcal{A})^{*}$, on which it conditions a
stochastic policy $\pi^{i}(u^{i}|\tau^{i}):T\times\mathcal{A}\to[0,1]$. In our
algorithm, the joint policy $\pi$ is based on action-value function
$Q^{\pi}_{tot}(s_{t},\textbf{a}_{t})=\mathbb{E}_{s_{t+1}:\infty,\textbf{a}_{t+1}:\infty}[\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}|s_{t},\textbf{a}_{t}]$.
The final goal is to get the optimal action-value function $Q^{*}$.

###  3.2. Diversity Evaluation Metrics

In this section, we introduce three diversity evaluation metrics, namely
$\alpha$-NDCG (Clarke et al., 2008), ERR-IA (Chapelle et al., 2011) and
S-recall (Zhai et al., 2015). The basic setting is that there are $n$
documents in a query, and each document may cover 1 to $m$ subtopics.

####  3.2.1. $\alpha\textrm{-}NDCG$

Firstly, the $\alpha$ discounted cumulative gain ($\alpha\textrm{-}DCG$) is
defined as Equation (1).

(1)
$\alpha\textrm{-}DCG=\sum^{n}_{i=1}\sum^{m}_{l=1}\frac{y_{il}(1-\alpha)^{c_{li}}}{log_{2}(1+r_{i})}$

$y_{il}=1$ means that subtopic $l$ is covered by document $i$ and $y_{il}=0$
is the opposite. $\alpha$ is a parameter between 0 to 1, which quantifies the
probability of a reader getting the information about a specific subtopic from
a relevant document. $r_{i}$ is the ranking position of document $i$, and
$c_{li}$ is the number of times that the subtopic $l$ being covered by the
documents on the prior positions to $r_{i}$. Specifically, $c_{li}$ is defined
as $c_{li}=\sum_{j:r_{j}\leq r_{i}}y_{jl}$.

Then, dividing the $\alpha\textrm{-}DCG$ of a given documents list by the
$\alpha\textrm{-}DCG_{ideal}$ of an ideal ranking list yields the normalized
$\alpha\textrm{-}NDCG$,

(2)
$\alpha\textrm{-}NDCG=\frac{\alpha\textrm{-}DCG}{\alpha\textrm{-}DCG_{ideal}}$

The metric of top $k$ documents in a given list, called $\alpha-NDCG@k$, is
usually used to measure the diversity of the documents list.

####  3.2.2. $ERR\textrm{-}IA$

The $ERR\textrm{-}IA$ is defined in Equation (3).

(3)
$ERR\textrm{-}IA=\sum^{n}_{i=1}\frac{1}{r_{i}}\sum^{m}_{l=1}\frac{1}{m}\left(\prod_{j:r_{j}\leq
r_{i}}(1-\frac{2^{y_{jl}}-1}{2^{y_{l}^{max}}})\right)\frac{2^{y_{jl}}-1}{2^{y_{l}^{max}}}$

If $y_{il}$ is a binary label ($y_{il}$ = 0 or 1), the Equation (3) can be
rewritten as Equation (4).

(4)
$ERR\textrm{-}IA=\sum^{n}_{i=1}\frac{1}{r_{i}}\sum^{m}_{l=1}\frac{1}{m}\frac{y_{il}}{2^{c_{li}+1}}$

Similar to $\alpha\textrm{-}NDCG@k$, $ERR\textrm{-}IA@k$ is also often used in
practice.

####  3.2.3. $S\textrm{-}recall$

The $S\textrm{-}recall$ is always defined on top $k$ documents of a ranked
list, i.e.,

(5)
$S\textrm{-}recall@k=\frac{\left|\cup^{k}_{i=1}subtopics(d_{i})\right|}{\left|\cup^{n}_{i=1}subtopics(d_{i})\right|}$

Obviously, $S\textrm{-}recall@k$ represents the proportion of subtopics number
recalled in the first top $k$ documents to the number of subtopics contained
in the whole document list.

###  3.3. Test Collection for Diversified Search

Suppose there is a given query $\mathbf{q}$ which is associated with a set of
candidate documents
$\textbf{D}=\\{\mathbf{d_{1}},\dots,\mathbf{d_{n}}\\}\in\mathcal{D}$, where
query $\mathbf{q}$ and each document $\mathbf{d_{i}}$ are represented as
$L$-dimensional preliminary representations, i.e., the $L$-dimensional vector
given by the BERT model (Devlin et al., 2018), and $\mathcal{D}$ is the set of
all candidate documents. Our objective is to sort the documents in the
candidate set $\mathcal{D}$ in such a way that the documents ranked higher
cover as many subtopics as possible, thereby improving the diversity
evaluation metrics.

To compute the diversity metrics introduced above, we need to collect a test
collection with relevance labels at the subtopic level. Therefore, a test
collection with $N$ labeled queries can be formulated as:

$\\{(q^{k},D^{k}),J^{k}\\}_{k=1}^{N}$

where $J^{k}$ is a binary matrix with $n\times m$ dimensions. $J^{k}(i,l)=1$
means that document $\mathbf{d_{i}}$ covers the $l$-th subtopic in the given
query $q^{k}$ and $J^{k}(i,l)=0$ otherwise.

##  4\. The MA4DIV Model

In this section, we first describe how to formulate the search results
diversification problem as a Dec-POMDP by introducing the basic elements in
the MA4DIV framework. Then, we present the architecture of the MA4DIV
framework, as shown in Figure 1, and elaborate the implementation of the Agent
Network, Ranking Process, and Mixing Network. Finally, we will give an
algorithm to train the MA4DIV.

###  4.1. Essential Elements of MA4DIV

In Section 3.1, we define the process of diversity ranking as a Dec-POMDP.
Next, we introduce the essential elements of Dec-POMDP specified to our
MA4DIV:

Agents $\mathcal{G}$: We model each document $i\in\\{1,\dots,n\\}$ as agent
$i\in\mathcal{G}\equiv\\{1,\dots,n\\}$. In the setting of multi-agent
cooperation, each document implements the ranking process by cooperating with
each other.

Observation $\mathcal{O}$: Observation represents the localized information
that each agent receives. Each agent makes decisions based on its respective
observation $\bm{o_{i}}$. The defination of $\bm{o_{i}}$ is shown as Equation
(6).

(6) $\bm{o_{i}}=\left\\{\mathbf{q},\mathbf{d_{i}},\textbf{D}\right\\}$

where $\mathbf{q}$ is embedding vector of the given query, $\mathbf{d_{i}}$ is
embedding vector of document $i$ and
$\textbf{D}=\\{\mathbf{d_{1}},\dots,\mathbf{d_{n}}\\}$ represents the
embedding vectors of all documents.

State $\mathcal{S}$: State signifies global information and holds a pivotal
role in multi-agent cooperation. It is through the utilization of state
$\mathcal{S}$ that effective collaboration between agents (documents) can be
established, resulting in a diverse and high-quality ranking list. State is
defined $\bm{s}$ as:

(7) $\displaystyle\bm{s}$ $\displaystyle=\\{\mathbf{q},\textbf{D}\\}$

From Equation (7) we can see that state $\bm{s}$ contains information for the
given query $\mathbf{q}$ and information for all documents
$\textbf{D}=\\{\mathbf{d_{1}},\dots,\mathbf{d_{n}}\\}$.

Actions $\mathcal{A}$: The action space $a_{i}\in\mathcal{A}$ of the MA4DIV
algorithm is defined as a set of discrete ranking scores
$s_{i}\in\\{1,\dots,\mathcal{|A|}\\}$. When making decisions, agent $i$ will
select an action $a_{i}$ from $\mathcal{A}$. The corresponding score $s_{i}$
serves as the basis for agent $i$ (document $i$) to assess the level of
diversity to itself.

Upon the selection of joint-action $\mathbf{a}=\\{a_{1},\dots,a_{n}\\}$ by all
agents based on joint-observation
$\mathbf{o}=\\{\bm{o_{1}},\dots,\bm{o_{n}}\\}$, the ranking scores of
candidate documents list
$\textbf{D}=\\{\mathbf{d_{1}},\dots,\mathbf{d_{n}}\\}$ can be obtained as
$\mathbf{scores}=\\{s_{1},\dots,s_{n}\\}$. By sorting all documents according
to $\mathbf{scores}$, a ranked document list by diversity level can be
achieved, called $\mathbf{D_{ranked}}$.

Reward $\mathcal{R}$: The reward function should guide the parameter updates
of the model to achieve diversity of ranked documents. In search result
diversification, there are some evaluation metrics, such as $\alpha$-NDCG, are
used to evaluate the diversity of a ranked document list. So it’s natural to
consider these metrics as reward functions. In this paper, we define the
reward function as $\alpha$-NDCG at top $k$ positions:

(8) $\mathcal{R}\left(\mathbf{D_{ranked}}\right)=\alpha\textrm{-}NDCG@k$

Episode $\mathcal{E}$: In typical MDP, an episode contains multiple decision
steps. So the objective function is cumulative rewards in an episode with a
discount factor $\gamma$, defined as:

(9) $G_{t}=\sum_{k=0}^{n-1-t}\gamma^{k}\mathcal{R}_{t+k+1}$

where $n$ is the step number in an episode.

However, the episode in MA4DIV contains only one step. Since the complete
ranked document list can be obtained in one time step, the reward can then be
calculated for end-to-end training. Therefore, instead of implementing a
multi-step decision through a state transition function, an episode can
contain only one step. And the final objective function of MA4DIV can be
written as:

(10) $G=\mathcal{R}=\alpha\textrm{-}NDCG@k$

###  4.2. Agent Network

Figure 1. The Framework of MA4DIV.

In Figure 1, the green modules represent the Agent Network, which share
parameters with each other. On the left side of Figure 1 is the detailed
structure of the Agent Network. It can be seen that we concatenate
$\\{\mathbf{q},\mathbf{d_{i}},\mathbf{e_{i}}\\}$, which is precisely the
observation for agent $i$ defined in Equation (6). And $\mathbf{e_{i}}$ is a
vector with high-level cross feature between document $i$ and all other
documents, computed by Multi-Head Self-Attention (MHSA) module:

The MHSA module is an essential component in Transformer (Vaswani et al.,
2017) and its variants. Given an input matrix
$\mathbf{X}\in\mathbb{R}^{n\times L}$, where $n$ and $L$ denote the number of
documents in candidiate document set D and the embedding vector dimension of
$\mathbf{d_{i}}$. MHSA computes a weighted sum of all the input tokens for
each token. The weight (also called attention score) between two tokens is
calculated using their similarity.

Specifically, MHSA first linearly projects the input matrix into query
$\mathbf{Q}$, key $\mathbf{K}$, and value $\mathbf{V}$ matrices, i.e.,
$\mathbf{Q}=\mathbf{X}\mathbf{W}_{Q}$, $\mathbf{K}=\mathbf{X}\mathbf{W}_{K}$,
and $\mathbf{V}=\mathbf{X}\mathbf{W}_{V}$, where $\mathbf{W}_{Q}$,
$\mathbf{W}_{K}$, and $\mathbf{W}_{V}$ are learnable weight matrices with
dimensions $L\times d_{k}$, $L\times d_{k}$, and $L\times d_{v}$ respectively,
and $d_{k}$ and $d_{v}$ are the dimensions of keys/values. Then, the attention
score between each two tokens is computed as
$\mathbf{A_{s}}=\text{softmax}(\frac{\mathbf{Q}\mathbf{K}^{T}}{\sqrt{d_{k}}})$.
The output of MHSA is $\mathbf{O}=\mathbf{A_{s}}\mathbf{V}$, with
$\mathbf{O}\in\mathbb{R}^{n\times d_{v}}$.

MHSA further enhances the model capacity by applying the above process
multiple times in parallel, which is called multi-head mechanism. Suppose
there are $h$ heads, the output after multi-head is
$\mathbf{O}=[\mathbf{O}_{1};\mathbf{O}_{2};\cdots;\mathbf{O}_{h}]\mathbf{W}_{O}$,
where $[\cdot]$ denotes concatenation, and $\mathbf{O}_{i}$ and
$\mathbf{W}_{O}$ are the output of the $i$-th head and a learnable weight
matrix with dimensions $h\cdot d_{v}\times d$, respectively. Finally,
$\mathbf{O}$ is reshaped to output $\mathbf{e_{i}}$ as Equation (11):

(11)
$\\{\mathbf{e_{1}},\dots,\mathbf{e_{i}},\dots,\mathbf{e_{n}}\\}=\mathbf{MHSA}([\mathbf{d_{1}},\dots,\mathbf{d_{n}}])$

Why do we employ the MHSA module to obtain $\mathbf{e_{i}}$ rather than using
other networks like MLP to compute the cross features of all documents
directly? The main reason is as follows:

According to (Pang et al., 2020), the ranking model should satisfy the
permutation invariance property which is described as following Defination:

###### Definition 0 (Permutation Invariance).

The target ranking for a given set is the same regardless of the order of
documents in the set. In other words, no matter how exchange the positions of
$d_{i}$ and $d_{j}$ in inputs information, it will not affect the final
ranking result.

A method to construct a ranking model in accordance with Permutation
Invariance involves initially attributing scores to the documents via a
permutation equivariant scoring function, followed by ordering based on these
scores. Pang et al. (2020) also proved that the multi-head attention block is
permutation equivariant. Therefore, the MHSA module is used to compute higher-
level cross feature vectors between documents.

Then, the action-values $Q_{i}^{a_{m}},m\in\\{1,\dots,|\mathcal{A}|\\}$ are
calculated according to Equation (12). Specifically,
$Q_{i}^{a_{m}}=Q(\bm{o_{i}},a_{m})$ represents the expected reward of taking a
specific action $a_{m}$ in a given observation $\bm{o_{i}}$ for agent $i$,
which is defined in Equation (13).

(12)
$\displaystyle\\{Q_{i}^{a_{1}},\dots,Q_{i}^{a_{m}},\dots,Q_{i}^{a_{n}}\\}$
$\displaystyle=\mathbf{MLP}\left(\\{\mathbf{q},\mathbf{d_{i}},\mathbf{e_{i}}\\}\right)$

(13) $\displaystyle Q_{i}^{a_{m}}$ $\displaystyle=Q(\bm{o_{i}},a_{m})$
$\displaystyle=\mathbb{E}[\mathcal{R}|\bm{o}=\bm{o_{i}},a=a_{m}]$

In reinforcement learning (RL), a popular approach to select the action-value
is the $\varepsilon$-greedy policy, which is used to balance exploration and
exploitation during the learning process.

Specifically, with a probability of $1-\varepsilon$, the agent $i$ chooses the
action-value $Q_{i}^{a_{*}}$ which has the highest estimated value ($\max
Q_{i}^{a_{m}}$) for the current observation $\bm{o_{i}}$, and the
corresponding chosen action is
$a_{*}^{i}=\arg\max_{a_{m}}Q_{i}^{a_{m}},\forall
m\in\\{1,\dots,|\mathcal{A}|\\}$. This is the exploitation part, where the
agent makes the best decision based on the current model. On the other hand,
with a probability of $\varepsilon$, the agent $i$ chooses an action-value
uniformly at random from $\mathcal{|A|}$ action-values. This is the
exploration part, where the agents try to discover new permutations of the
candidate documents set. Mathematically, this process can be written as
Equation (14):

(14) $Q_{i}^{a_{*}}=\begin{cases}\max Q_{i}^{a_{m}},\forall
m\in\\{1,\dots,|\mathcal{A}|\\}&\text{with
}p\textrm{=}1\textrm{-}\varepsilon\\\ \text{random }Q_{i}^{a_{m}},\forall
m\in\\{1,\dots,|\mathcal{A}|\\}&\text{with }p\textrm{=}\varepsilon\end{cases}$

In the training process, the value of $\varepsilon$ is often initially set to
a high value (e.g., 1.0), and gradually decayed to a low value (e.g., 0.05)
over training steps $t$ ($\varepsilon(t)=\max(0.05,1-\frac{t}{T})$), allowing
the agent to explore the environment extensively at the beginning, and then
exploit more as its knowledge increases. In the testing process, we set
$\varepsilon=0$ to get the optimal policy.

In this way, the $\varepsilon$-greedy policy used in MA4DIV helps to balance
the trade-off between exploration and exploitation, which promotes to explore
more different ranking permutation. And it’s more conducive to update the
parameters of the Agent Network.

###  4.3. Ranking Process

In the ranking process, the agents receive a query q and the associated
documents $\textbf{D}=\\{\mathbf{d_{1}},\dots,\mathbf{d_{n}}\\}$. As shown in
Figure 1, each agent $i$ select its own action-value $Q_{i}^{a_{*}}$ and the
corresponding action $a_{*}^{i}$ according to Equation (14). Because the
action space $\mathcal{A}$ is defined as discrete ranking scores, that is,
each action $a_{m}$ corresponds to a ranking score. So the ranking scores of
all documents can be obtained as $\mathbf{scores}=\\{s_{1},\dots,s_{n}\\}$.
Finally, a ranked document list $\mathbf{D_{ranked}}$ is obtained based on the
descending order of $\mathbf{scores}$.

We show the pseudo-code of ranking process in Algorithm 1.

1Inputs: Give the query q and documents
$\textbf{D}=\\{\mathbf{d_{1}},\dots,\mathbf{d_{n}}\\}$.

2 Select Actions: Each agent $i$ select action-value $Q_{i}^{a_{*}}$ to get
$\\{Q_{1}^{a_{*}},\dots,Q_{i}^{a_{*}},\dots,Q_{n}^{a_{*}}\\}$ and
$\\{a_{*}^{1},\dots,a_{*}^{i},\dots,a_{*}^{n}\\}$ base on Equation (14).

3 Getting Scores: Get the corresponding ranking scores
$\mathbf{scores}=\\{s_{1},\dots,s_{i},\dots,s_{n}\\}$.

4 Sorting: Sort the candidate documents in D based on $\mathbf{scores}$.

Output: Get a ranked document list $\mathbf{D_{ranked}}$.

Algorithm 1 The Ranking Process of MA4DIV

###  4.4. Value-Decomposition for MA4DIV

After the ranking process, the reward $\mathcal{R}$ is obtained according to
Equation (8) based on $\mathbf{D_{ranked}}$. Obviously, $\mathcal{R}$ is a
scalar while there are $n$ action-values
$\\{Q_{1}^{a_{*}},\dots,Q_{n}^{a_{*}}\\}$ for all agents. $\mathcal{R}$ is the
evaluation of the global ranking effect, while $Q_{i}^{a_{*}}$ is related to
the score of a single document. Therefore, we cannot use $\mathcal{R}$ to
directly update the action-value functions of all agents.

The MARL algorithms based on value decomposition, such as (Sunehag et al.,
2017; Rashid et al., 2018; Wang et al., 2020b), consider that there is the
global utility function $Q_{tot}^{*}$ can be decomposed into the action-value
functions $Q_{i}^{a_{*}}$ of all individual agents. $Q_{tot}^{*}$ represents
the action-value utility of the joint-action $\mathbf{a}$ under the joint-
observation information $\mathbf{o}$, and is also a scalar value. The
monotonic decomposition relation can be expressed as Equation (15):

(15)
$\arg\max_{\mathbf{a}}Q_{tot}^{*}(\mathbf{o},\mathbf{a})=\begin{pmatrix}\arg\max_{{a}_{1}}Q_{1}(\bm{o_{1}},{a}_{1})\\\
\vdots\\\ \arg\max_{{a}_{n}}Q_{n}(\bm{o_{n}},{a}_{n})\end{pmatrix}$

In online ranking process, all agents adopt a greedy strategy to score
documents, which is consistent with the maximization operation on the right
side of Equation (15). So we just need to learn how to maximize $Q_{tot}^{*}$.
Since $Q_{tot}^{*}$ is a global utility function and $\mathcal{R}$ is also
used to measure the global ranking effect, we can maximize $Q_{tot}^{*}$ with
$\mathcal{R}$, thus maximizing the utility of each individual agent
($Q_{i}^{a_{*}}$). The specific loss function will be introduced in the
following Section 4.6 (Equation (19)).

Furthermore, QMIX (Rashid et al., 2018) proposes a sufficient but not
necessary realization to satisfy Equation (15). Monotonicity can be enforced
by a constraint condition on the relationship of partial derivative between
$Q_{tot}^{*}$ and $Q_{i}^{a_{*}}$:

(16) $\frac{\partial Q_{tot}^{*}}{\partial Q_{i}^{a_{*}}}\geq 0,\hskip
8.5359pt\forall i\in\mathcal{G}\equiv\\{1,\dots,n\\}$

Additionally, in Equation (15) and (16), it is established that
$Q_{i}^{a_{*}}=\max
Q_{i}(\bm{o_{i}},{a}_{m}),a_{*}^{i}=\arg\max_{a_{m}}Q_{i}(\bm{o_{i}},{a}_{m}),\forall
m\in\\{1,\dots,|\mathcal{A}|\\}$.

###  4.5. Mixing & Hyper Network Structure

To convert the individual action-value functions $Q_{i}^{a_{*}}$ into the
global utility function $Q_{tot}^{*}$ and ensure compliance with Equation
(16), an architecture consisting of a mixing network and a set of
hypernetworks is designed. The right part of Figure 1 illustrates the detail
structure.

Mixing network, a fully connected network, utilizes the action-values
$\\{Q_{1}^{a_{*}},\dots,Q_{n}^{a_{*}}\\}$ from the agent network as inputs,
and then, monotonically combines these inputs to generate $Q_{tot}^{*}$. The
calculation process is shown as:

(17)
$Q_{tot}^{*}=\mathbf{W2}\cdot\mathbf{Elu}\left(\mathbf{W1}\cdot[Q_{1}^{a_{*}},\dots,Q_{n}^{a_{*}}]+\mathbf{B1}\right)+\text{B2}$

Hypernetworks, several fully connected networks, play a role in generating
mixing network weights. Firstly, each hypernetwork takes global state $\bm{s}$
as input and generate the vectors of $\mathbf{W1}$, $\mathbf{B1}$,
$\mathbf{W2}$, B2 respectively. Then, the vectors are reshaped into matrices
of appropriate size as parameters for the mixing network. Lastly, to achieve
the monotonicity constraint of Equation (16), $\mathbf{W1}$, $\mathbf{W2}$ are
limited to non-negative by an absolute activation function. However, biases
$\mathbf{B1}$, B2 do not need to be set to non-negative because biases has
nothing to do with the partial derivatives between $Q_{tot}^{*}$ and
$Q_{i}^{a_{*}}$. The hypernetworks operate as follows:

(18) $\begin{gathered}\begin{aligned}
\mathbf{W1}&=\mathbf{Reshape}\left(\left|\mathbf{FC_{{\scriptscriptstyle
W1}}}\left(\bm{s}\right)\right|\right),\mathbf{B1}=\mathbf{Reshape}\left(\mathbf{FC_{{\scriptscriptstyle
B1}}}\left(\bm{s}\right)\right)\\\
\mathbf{W2}&=\mathbf{Reshape}\left(\left|\mathbf{FC_{{\scriptscriptstyle
W2}}}\left(\bm{s}\right)\right|\right),\text{B2}=\mathbf{Reshape}\left(\mathbf{FC_{{\scriptscriptstyle
B2}}}\left(\bm{s}\right)\right)\end{aligned}\end{gathered}$

###  4.6. Training Process of MA4DIV

In this section, we introduce the complete training process for MA4DIV. The
parameters of models are $\Theta=\\{\theta,\psi,\phi\\}$ where $\theta$
represents the parameters of agent network, $\psi$ and $\phi$ are the
parameters of mixing network and hypernetworks respectively. The model
parameters $\Theta$ is updated on $N$ training data with the form of
$\\{(q^{k},D^{k}),J^{k}\\}_{k=1}^{N}$.

Algorithm 2 shows the training pseudo-code. At the beginning, parameters
$\Theta$ are initialized randomly and the replay buffer $\mathcal{M}$ is set
to $\varnothing$. A whole training epoch consists of two parts. The first part
is the stage of data generation. Given data $\mathbf{q}=q^{i}$,
$\mathbf{D}=D^{i}$, with subtopic labels $J^{i}$, tuple $\mathcal{T}$ in the
episode is obtained based on the definition in Equation (6, 7, 8). Then, store
the tuple $\mathcal{T}$ in replay buffer. Each epoch can generate a kind of
permutation of all documents $\\{D^{k}\\}_{k=1}^{N}$ in all training data. The
second part is updating models with parameters $\Theta$ for $N\\_update$
times. And the update is performed by sampling data through a mini-batch
approach from $\mathcal{M}$. The whole network is trained end-to-end by
minimizing the loss shown in Equation (19) and (20) to maximize $Q_{tot}$.

(19)
$\mathcal{L}_{TD}=\sum_{i=1}^{b}\left(y_{i}^{tot}-Q_{tot}(\textbf{o},\textbf{a},\bm{s};\Theta)\right)^{2}$

(20) $\displaystyle y^{tot}$
$\displaystyle=\mathcal{R}+\gamma\max_{a^{\prime}}Q_{tot}(\textbf{o}^{\prime},\textbf{a}^{\prime},\bm{s}^{\prime};\Theta^{\prime})$
$\displaystyle=\mathcal{R}$

1 Initialize: The parameters of network $\Theta=\\{\theta,\psi,\phi\\}$,
replay buffer $\mathcal{M}$.

2 Inputs: Training data $\\{(q^{k},D^{k}),J^{k}\\}_{k=1}^{N}$.

3

4for  _$epoch=1$ to $N\\_epoch$_ do

5 // generate data

6 for  _$i=1$ to $N$_ do

7 Current training data: $\mathbf{q}=q^{i}$, $\mathbf{D}=D^{i}$, with subtopic
labels $J^{i}$.

8 Rollout an episode following Algorithm 1.

9 Collect a tuple $\mathcal{T}$ =
($\mathbf{o},\bm{s},\mathbf{a},\mathcal{R},\mathbf{o^{\prime}},\bm{s^{\prime}}$)
during this episode.

10 Store the tuple $\mathcal{T}$ in $\mathcal{M}$.

11

12

13 // update models

14 for  _$update=1$ to $N\\_update$_ do

15 Sample a random minibatch $\bm{b}$ from $\mathcal{M}$.

16 Calculate $y^{tot}$ and loss $\mathcal{L}$ for all sampled data from
$\bm{b}$ based on Equation (20) and (19).

17 Update the parameters of networks $\Theta$ by gradient descent.

18

19

20

21Ouput: A well-trained ranking model with parameters $\Theta$.

22

Algorithm 2 The Training Process of MA4DIV Table 1. Comparisons of datasets TREC and DU-DIV. Dataset | Source | No. of Queries | No. of Documents per Query | No. of Subtopics | Representation
---|---|---|---|---|---
TREC | TREC 2009$\sim$2012 Web Track | 198 | average 211 docs/query | maximum 7 subtopics/doc | Doc2vec (Le and Mikolov, 2014)
DU-DIV | Baidu | 4473 | 15 docs/query | total 50 subtopics | BERT (Devlin et al., 2018)

In Equation (19), $b$ is the batch size of sampled data from replay buffer. In
Equation (20),
$Q_{tot}(\textbf{o}^{\prime},\textbf{a}^{\prime},\bm{s}^{\prime};\Theta^{\prime})$
is calculated based on information of the next time step, i.e.,
$\textbf{o}^{\prime},\textbf{a}^{\prime},\bm{s}^{\prime}$, in typical MDP
which contains multiple decision steps. However, we define that MA4DIV only
have one time step for an episode, so
$\textbf{o}^{\prime},\textbf{a}^{\prime},\bm{s}^{\prime}$ do not exist and
$Q_{tot}(\textbf{o}^{\prime},\textbf{a}^{\prime},\bm{s}^{\prime};\Theta^{\prime})$
equals to 0, that is $y^{tot}=\mathcal{R}$.

Table 2. Hyperparemeters of MA4DIV on different dataset. Dataset | $|\mathcal{A}|$ | $L$ | $H$ | $z$
---|---|---|---|---
TREC | 30 | 1 | 4 | 64
DU-DIV | 15 | 1 | 4 | 256

##  5\. Experiments

Our experiments mainly focus on next research questions:

(RQ.1) How does MA4DIV perform on the TREC Web Track datasets when compared to
existing diversified search baselines?

(RQ.2) How does MA4DIV perform on a large-scale industrial dataset comparing
to existing baselines?

(RQ.3) How efficient is MA4DIV in training process?

###  5.1. Datasets

We conduct experiments to address above research questions on two datasets,
TREC 2009$\sim$2012 Web Track datasets and DU-DIV dataset. TREC 2009$\sim$2012
Web Track datasets are publicly available and Xia et al. (2017) first uses
them for training and evaluating diversified search models. Almost all the
following works, such as $\mathrm{M^{2}Div}$ (Feng et al., 2018), DALETOR (Yan
et al., 2021), MO4SRD (Yu, 2022), etc., conduct experiments on these datasets.
As a widely used test collection for diversified search, the TREC Web track
dataset only contains 198 queries, and previous studies often use Doc2vec (Le
and Mikolov, 2014) to obtain the document embeddings on this dataset. In this
work, to ensure a fair and meaningful comparison with existing work, we first
compare MA4DIV with existing baselines on the this relatively small dataset.
Then, we further conduct extensive experiments on a new and larger scale
diversity dataset called DU-DIV, which is constructed based on real user data
in Baidu search engine.

The details of these two datasets are shown in Table 1. The DU-DIV dataset has
4473 queries, far more than the TREC datasets. The documents in the DU-DIV
dataset are the top-15 documents retrieved by the Baidu search engine for each
query, which makes this dataset particularly useful for the diversified
ranking task in which we need to rerank these top documents for diversity. In
the TREC web track datasets, each document contains a maximum of 7 subtopics.
In the DU-DIV dataset, we predefined 50 subtopics, such as law, healthcare,
education, etc. Each document corresponds to one or more of the predefined
subtopics. Moreover, while previous studies on the TREC web track dataset
often use the Doc2vec model to represent queries and documents in vector with
$L\textrm{=}100$ dimensions, the DU-DIV dataset utilizes the more powerful
model BERT (Devlin et al., 2018) to encode queries and documents into vectors
with $L\textrm{=}1024$ dimensions.

###  5.2. Experimental Settings

Considering that TREC datasets contain only 198 queries, this is prone to
overfitting for existing deep learning models. In addition, the average number
of documents related to each query is about 211, but a large number of these
documents do not contain any subtopics. Therefore, we reshape TREC dataset.
That is, from each of the original document lists in TREC (198 lists in total,
with an average of 211 documents per query), we subsample 30 documents at a
time to form a new document list. This process runs multiple times over a
document list associated with the same query, resulting in a reshaped dataset
with a total of 6,232 document lists (198 unique queries). And it’s crucial to
ensure that an appropriate number of the 30 documents sampled contain at least
one subtopic.

We conduct 5-fold cross-validation experiments on the reshaped TREC dataset
with the same subset split based on unique queries as in (Feng et al., 2018).
In the DU-DIV dataset, we randomly sample 80% of 4473 unique queries and their
associated document lists to the training set, and the left 20% to the test
set.

The code framework of MA4DIV is based on PyMARL2 framework (Hu et al., 2021),
which is a open-source code framework for multi-agent reinforcement learning.
The key hyperparameters of MA4DIV on two datasets are shown in Table 2.
$|\mathcal{A}|$ is the dimension of action space, i.e. the number of discrete
scores (1, …, $\mathcal{|A|}$). $L$, $H$ and z respectively represent the
number of MHSA block, attention heads and attention embedding dimensions of
MHSA.

Table 3. Performance comparison of baselines and MA4DIV on TREC web track datasets. The best result in each metric is bold and the top-3 results are shaded. ”*” indicates the difference between the baseline and M4DIV (ours) is statistically significant. Method |  $\alpha$-NDCG@5 |  $\alpha$-NDCG@10 | ERR-IA@5 | ERR-IA@10 | S-recall@5 | S-recall@10
---|---|---|---|---|---|---
MMR | 0.4273* | 0.5059* | 0.2015* | 0.2153* | 0.6058* | 0.7848*
xQuAD | 0.4451* | 0.5296* | 0.2108* | 0.2243* | 0.5994* | 0.7887*
MDP-DIV | 0.4987* | 0.5663* | 0.2662 | 0.2865 | 0.6310* | 0.7853*
$\mathrm{M^{2}Div}$ | 0.5144* | 0.5798* | 0.2338* | 0.2448* | 0.6593 | 0.8028
DALETOR | 0.5008 | 0.5703 | 0.2237* | 0.2355* | 0.6451* | 0.8012
MO4SRD | 0.5135* | 0.5815* | 0.2280* | 0.2396* | 0.6576 | 0.8074
MA4DIV (ours) | 0.5056 | 0.5724 | 0.2680 | 0.2882 | 0.6600 | 0.8070

We compare MA4DIV with several state-of-the-art baselines in search result
diversification, including the heuristic methods:

MMR (Carbonell and Goldstein, 1998): a heuristic approach which select
document according to maximal marginal relevance.

xQuAD (Santos et al., 2010): a representative approach that explicitly models
different aspects underlying the query in the form of subqueries.

MDP-DIV (Xia et al., 2017): a single-agent reinforcement learning approach
which model the diverse ranking process as MDP.

$\mathbf{M^{2}}$Div (Feng et al., 2018): a single-agent reinforcement learning
approach which utilizes Monte Carlo Tree Search to enhance ranking policy.

DALETOR (Yan et al., 2021): a method for approximating evaluation metrics that
optimizes an approximate and differentiable objective function.

MO4SRD (Yu, 2022): another method to make evaluation metrics differentiable
and optimize the approximating evaluation metrics.

We reproduce the code of DALETOR and MO4SRD, and ensure that these two
algorithms have the same parameter scale of MHSA structure as our MA4DIV in
Table 2, that is, the $L=1$ and $H=4$, $z$ is 64 and 256 respectively on two
datasets.

###  5.3. Experimental Results

Table 3 and 4 report the performances of all baselines and our MA4DIV in terms
of the six diversity performance metrics, including $\alpha$-NDCG@5,
$\alpha$-NDCG@10, ERR-IA@5, ERR-IA@10, S-recall@5, S-recall@10 on the TREC web
track datasets and the DU-DIV dataset respectively. We highlight the top three
algorithms on each metric by darkening the background color of the numbers.

####  5.3.1. TREC web track datasets

In Table 3, $\mathrm{M^{2}Div}$ and MO4SRD have the best performance in term
of $\alpha$-NDCG, our MA4DIV performs worse than these two algorithms but
better than the others. Moreover, MA4DIV takes the lead in both ERR-IA and
S-recall metrics, with MO4SRD also exhibiting strong performance in S-recall
metric. Considering multiple evaluation metrics comprehensively, MA4DIV,
$\mathrm{M^{2}Div}$ and MO4SRD are the best three algorithms on the TREC web
track datasets. (answer to RQ.1)

Table 4. Performance comparison of baselines and MA4DIV on DU-DIV dataset. The best result in each metric is bold and the top-3 results are shaded. ”*” indicates the difference between the baseline and M4DIV (ours) is statistically significant. Method |  $\alpha$-NDCG@5 |  $\alpha$-NDCG@10 | ERR-IA@5 | ERR-IA@10 | S-recall@5 | S-recall@10
---|---|---|---|---|---|---
MMR | 0.7416* | 0.8171* | 0.7583* | 0.8100* | 0.6062* | 0.8481*
xQuAD | 0.7075* | 0.8277* | 0.7745* | 0.8201* | 0.5670* | 0.8520*
MDP-DIV | 0.8101* | 0.8623 | 0.7694* | 0.8204* | 0.6389* | 0.8590*
$\mathrm{M^{2}Div}$ | 0.8089* | 0.8610* | 0.7633* | 0.8142* | 0.6468 | 0.8608*
DALETOR | 0.7981* | 0.8543* | 0.7450* | 0.7955* | 0.6447* | 0.8550*
MO4SRD | 0.7989* | 0.8553* | 0.7467* | 0.7969* | 0.6432* | 0.8556*
MA4DIV (ours) | 0.8187 | 0.8702 | 0.7836 | 0.8342 | 0.6534 | 0.8699

As mentioned in Section 5.1, TREC web track datasets have only 198 unique
queries, deep learning methods are prone to overfitting on this dataset.
Figure 2 shows the training curve of MA4DIV on the TREC web track datasets. We
can see, after about the 11 iterations, MA4DIV achieves the best performance
on the test data, and the subsequent iterations fall into overfitting the
relatively small training set. However, the evaluation metric $\alpha$-NDCG@10
on the training set grows to more than 0.8. These results indicate that:

  * •

Our MA4DIV is capable to effectively optimize the diversity metric
$\alpha$-NDCG@10.

  * •

However, it could easily overfit the relatively small training set of the TREC
web track dataset, which only contains 198 unique queries.

  * •

Therefore, MA4DIV has the potential to perform even better in the search
result diversification task when given a larger dataset.

Therefore, we further construct the DU-DIV dataset and conduct extensive
experiments on it.

Figure 2. Training curves of MA4DIV on TREC web track datasets.

####  5.3.2. DU-DIV dataset

Table 4 shows results in different evaluation metrics on the DU-DIV dataset.
Obviously, MA4DIV achieves state-of-the-art performances on all six evaluation
metrics. Heuristic algorithms, MMR and xQuAD, perform poorly on $\alpha$-NDCG.
Comparing to single-agent reinforcement learning methods, MDP-DIV and
$\mathrm{M^{2}Div}$, MA4DIV has a better performance on evaluation metrics
which demonstrate that MA4DIV can improve the diversity of search results. And
MA4DIV also outperforms DALETOR and MO4SRD which optimize the approximate
value of the evaluation metrics. This verifies that directly optimizing the
evaluation metrics is indeed better than optimizing the approximation of the
evaluation metrics. All these results demonstrate that the proposed MA4DIV
method outperforms existing search result diversification methods on an
industrial scale dataset (answering RQ.2).

Interestingly, we notice that MDP-DIV, which does not perform well on the TREC
web track datasets, is the second best performing algorithm on the DU-DIV
dataset, following our MA4DIV in terms of $\alpha$-NDCG@5 and
$\alpha$-NDCG@10. In MDP-DIV, the reward function is defined as:
$R(s_{t},a_{t})=\alpha\textrm{-}DCG[t+1]-\alpha\textrm{-}DCG[t]$, where
$\alpha\textrm{-}DCG[t]$ is the discounted cumulative gain at the $t$-th
ranking position. And the objective function of MDP-DIV is to maximize the
cumulative rewards in one episode, that is
$G_{t}=\sum_{k=0}^{n-1-t}\gamma^{k}R_{t+k+1}$. Consider that Xia et al. (2017)
sets $\gamma\textrm{=}1$ and $\alpha\textrm{-}DCG[t]\textrm{=}0$, the
objective function can be rewritten as $G_{t}=\alpha\textrm{-}DCG[n]$, which
is equal to $\alpha\textrm{-}DCG$ defined in Equation (2). In addition, the
objective function of our MA4DIV defined in Equation (10) is equal to
$\alpha\textrm{-}NDCG$. Essentially, the optimization objective of MDP-DIV is
basically the same as that of our MA4DIV. Therefore, due to the correctness of
its optimization objective, MDP-DIV can outperform all the other baselines.

###  5.4. Comparison and Analysis of Efficiency

Table 5. The comparison of the training time taken by different algorithms to achieve the optimal value of metrics. Method |  Training Time
---|---
MDP-DIV |  5$\sim$6 hours
MO4SRD |  6$\sim$7 hours
$\mathrm{M^{2}Div}$ |  1 day +
MA4DIV (ours) |  20$\sim$25 mins

####  5.4.1. Training Time on TREC web track datasets

To highlight the efficiency of our MA4DIV, we also compare several algorithms
from the perspective of training time. Table 5 shows the comparison of
training time taken by different algorithms to achieve their optimal
performance on the TREC web track datasets. To ensure a fair comparison, all
the algorithms in Table 5 run on the same machine. We can see that
$\mathrm{M^{2}Div}$ takes over a day to reach optimal performance. This is
because $\mathrm{M^{2}Div}$ utilizes Monte Carlo Tree Search for policy
enhancement, which is highly time-consuming. The time taken by MDP-DIV and
MO4SRD is close and significantly less than $\mathrm{M^{2}Div}$. The proposed
MA4DIV takes the shortest time, approximately only 20$\sim$25 minutes. This is
due to the efficient exploration ability of using a multi-agent to model the
ranking process, in which a permutation of the given documents set ($n$
documents) can be obtained at one time step. The single agent reinforcement
learning algorithm MDP-DIV can only explore a permutation of the given
documents after a whole episode which contains $n$ time steps. This is the
main reason why the training time of MA4DIV is significantly shorter than MDP-
DIV. In MO4SRD, the complexity of calculating all approximate ranking
positions $r_{i}$ in Equation (1) is $\mathcal{O}(n^{2})$ and the complexity
of calculating all $c_{li}$ approximations is $\mathcal{O}(n^{2}m)$, which are
time-consuming parts. While MA4DIV directly optimizes Equation (2) without
complex approximations, which takes significantly less time.

In summary, the training time of MA4DIV is significantly shorter than that of
other baselines, which demonstrate its training efficiency and answers RQ.3.

####  5.4.2. Iteration Times on DU-DIV dataset

As the optimization goals of MA4DIV and MDP-DIV are essentially the same as we
discussed in Section 5.3.2, we are interested in comparing the learning
efficiency of the proposed multi-agent RL approach and the existing single-
agent RL method.

Figure 3 shows the training curves of MA4DIV and MDP-DIV on the DU-DIV
dataset. We conduct the experiments of these two algorithms with the same
learning rate which is set to $1\times 10^{-5}$. From the curves, we can see
that, after 250 iterations, $\alpha$-NDCG of MA4DIV basically converges to
about 0.87. However, $\alpha$-NDCG of MDP-DIV still fails to reach the optimal
value at around 6000 iterations. This indicates that MA4DIV has higher
exploration and exploitation efficiency compared with MDP-DIV, which also
answers RQ.3.

The main reason for the results just mentioned is as follows: MDP-DIV adopts
an on-policy RL method to optimize the cumulative rewards. A feature of on-
policy RL is that the currently sampled data is discarded after it is
utilized. While MA4DIV is a off-policy RL method. From 9-th line and 12-th
line of Algorithm 2, we can see that the sampled data is stored in replay
buffer $\mathcal{M}$, then update the model multiple times in minibatch
approach. In addition, each data stored in replay buffer $\mathcal{M}$ may be
sampled multiple times to update the ranking model. Therefore, the data
utilization efficiency of MA4DIV is higher than that of MDP-DIV, which is the
main reason why MA4DIV converges significantly faster.

The shorter training time on the TREC web track datasets and the faster
convergence rate on the DU-DIV dataset jointly demonstrate that MA4DIV has
high efficiency in training, which answers RQ.3.

Figure 3. Training curves of MA4DIV and MDP-DIV on DU-DIV dataset.

##  6\. Conclusions and Future Work

In this paper we have proposed a new method for search result diversification,
referred to as MA4DIV. To alleviate the sub-optimal problem and improve the
efficiency of training, we consider each document as an agent and model the
diversity ranking process as a multi-agent cooperative task. We conduct
experiments on the TREC web track dataset to prove the effectiveness and
potential of our MA4DIV. Furthermore, we construct a large-scale dataset
called DU-DIV using the real data from Baidu search engine. And MA4DIV achieve
state-of-the-art performance and high learning efficiency on the DU-DIV
dataset.

A major contribution of this paper is to introduce a multi-agent reinforcement
learning framework for the ranking optimization task. We argue that modeling
ranking process in the multi-agent setting can be used not only to optimize
the diversity of search results, but also to optimize other ranking tasks,
such as relevance ranking and fairness ranking. Therefore, in future work, we
will try to propose a general ranking framework base on multi-agent
reinforcement learning and apply it to a variety of ranking tasks.

## References

  * (1)
  * Agrawal et al. (2009) Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong. 2009.  Diversifying search results. In _Proceedings of the second ACM international conference on web search and data mining_. 5–14.
  * Carbonell and Goldstein (1998) Jaime Carbonell and Jade Goldstein. 1998.  The use of MMR, diversity-based reranking for reordering documents and producing summaries. In _Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval_. 335–336.
  * Carterette (2011) Ben Carterette. 2011.  An analysis of NP-completeness in novelty and diversity ranking.  _Information Retrieval_ 14 (2011), 89–106.
  * Chapelle et al. (2011) Olivier Chapelle, Shihao Ji, Ciya Liao, Emre Velipasaoglu, Larry Lai, and Su-Lin Wu. 2011.  Intent-based diversification of web search results: metrics and algorithms.  _Information Retrieval_ 14 (2011), 572–592.
  * Chen et al. (2022a) Yiqun Chen, Hangyu Mao, Tianle Zhang, Shiguang Wu, Bin Zhang, Jianye Hao, Dong Li, Bin Wang, and Hongxing Chang. 2022a.  Ptde: Personalized training with distillated execution for multi-agent reinforcement learning.  _arXiv preprint arXiv:2210.08872_ (2022).
  * Chen et al. (2022b) Yiqun Chen, Wei Yang, Tianle Zhang, Shiguang Wu, and Hongxing Chang. 2022b.  Commander-Soldiers Reinforcement Learning for Cooperative Multi-Agent Systems. In _2022 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 1–7.
  * Clarke et al. (2008) Charles LA Clarke, Maheedhar Kolla, Gordon V Cormack, Olga Vechtomova, Azin Ashkan, Stefan Büttcher, and Ian MacKinnon. 2008.  Novelty and diversity in information retrieval evaluation. In _Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval_. 659–666.
  * Coulom (2006) Rémi Coulom. 2006.  Efficient selectivity and backup operators in Monte-Carlo tree search. In _International conference on computers and games_. Springer, 72–83.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * Feng et al. (2018) Yue Feng, Jun Xu, Yanyan Lan, Jiafeng Guo, Wei Zeng, and Xueqi Cheng. 2018.  From greedy selection to exploratory decision-making: Diverse ranking with policy-value networks. In _The 41st international ACM SIGIR conference on research & development in information retrieval_. 125–134.
  * Gollapudi and Sharma (2009) Sreenivas Gollapudi and Aneesh Sharma. 2009.  An axiomatic approach for result diversification. In _Proceedings of the 18th international conference on World wide web_. 381–390.
  * Guo and Sanner (2010) Shengbo Guo and Scott Sanner. 2010.  Probabilistic latent maximal marginal relevance. In _Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval_. 833–834.
  * He et al. (2012) Jiyin He, Vera Hollink, and Arjen de Vries. 2012.  Combining implicit and explicit topic representations for result diversification. In _Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval_. 851–860.
  * Hu et al. (2021) Jian Hu, Siyang Jiang, Seth Austin Harding, Haibin Wu, and Shih-wei Liao. 2021.  Rethinking the implementation tricks and monotonicity constraint in cooperative multi-agent reinforcement learning.  _arXiv e-prints_ (2021), arXiv–2102.
  * Hu et al. (2015) Sha Hu, Zhicheng Dou, Xiaojie Wang, Tetsuya Sakai, and Ji-Rong Wen. 2015.  Search result diversification based on hierarchical intents. In _Proceedings of the 24th ACM International on Conference on Information and Knowledge Management_. 63–72.
  * Le and Mikolov (2014) Quoc Le and Tomas Mikolov. 2014.  Distributed representations of sentences and documents. In _International conference on machine learning_. PMLR, 1188–1196.
  * Li et al. (2009) Liangda Li, Ke Zhou, Gui-Rong Xue, Hongyuan Zha, and Yong Yu. 2009.  Enhancing diversity, coverage and balance for summarization through structure learning. In _Proceedings of the 18th international conference on World wide web_. 71–80.
  * Lowe et al. (2017) Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. 2017.  Multi-agent actor-critic for mixed cooperative-competitive environments.  _Advances in neural information processing systems_ 30 (2017).
  * Mihalkova and Mooney (2009) Lilyana Mihalkova and Raymond Mooney. 2009.  Learning to disambiguate search queries from short sessions. In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 111–127.
  * Oliehoek and Amato (2016) Frans A Oliehoek and Christopher Amato. 2016.  _A concise introduction to decentralized POMDPs_.  Springer.
  * Pang et al. (2020) Liang Pang, Jun Xu, Qingyao Ai, Yanyan Lan, Xueqi Cheng, and Jirong Wen. 2020.  Setrank: Learning a permutation-invariant ranking model for information retrieval. In _Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval_. 499–508.
  * Puterman (2014) Martin L Puterman. 2014.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons.
  * Qin et al. (2023) Xubo Qin, Zhicheng Dou, Yutao Zhu, and Ji-Rong Wen. 2023.  GDESA: Greedy Diversity Encoder with Self-attention for Search Results Diversification.  _ACM Transactions on Information Systems_ 41, 2 (2023), 1–36.
  * Radlinski et al. (2008) Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. 2008.  Learning diverse rankings with multi-armed bandits. In _Proceedings of the 25th international conference on Machine learning_. 784–791.
  * Rashid et al. (2018) Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. 2018.  Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In _International conference on machine learning_. PMLR, 4295–4304.
  * Santos et al. (2010) Rodrygo LT Santos, Craig Macdonald, and Iadh Ounis. 2010.  Exploiting query reformulations for web search result diversification. In _Proceedings of the 19th international conference on World wide web_. 881–890.
  * Singh and Joachims (2019) Ashudeep Singh and Thorsten Joachims. 2019.  Policy learning for fairness in ranking.  _Advances in neural information processing systems_ 32 (2019).
  * Sunehag et al. (2017) Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. 2017\.  Value-decomposition networks for cooperative multi-agent learning.  _arXiv preprint arXiv:1706.05296_ (2017).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Wang et al. (2020b) Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. 2020b.  Qplex: Duplex dueling multi-agent q-learning.  _arXiv preprint arXiv:2008.01062_ (2020).
  * Wang et al. (2020a) Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. 2020a.  Rode: Learning roles to decompose multi-agent tasks.  _arXiv preprint arXiv:2010.01523_ (2020).
  * Wei et al. (2017) Zeng Wei, Jun Xu, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2017.  Reinforcement learning to rank with Markov decision process. In _Proceedings of the 40th international ACM SIGIR conference on research and development in information retrieval_. 945–948.
  * Williams (1992) Ronald J Williams. 1992.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ 8 (1992), 229–256.
  * Xia et al. (2015) Long Xia, Jun Xu, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2015.  Learning maximal marginal relevance model via directly optimizing diversity evaluation measures. In _Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval_. 113–122.
  * Xia et al. (2016) Long Xia, Jun Xu, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2016.  Modeling document novelty with neural tensor network for search result diversification. In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_. 395–404.
  * Xia et al. (2017) Long Xia, Jun Xu, Yanyan Lan, Jiafeng Guo, Wei Zeng, and Xueqi Cheng. 2017.  Adapting Markov decision process for search result diversification. In _Proceedings of the 40th international ACM SIGIR conference on research and development in information retrieval_. 535–544.
  * Xu et al. (2020) Jun Xu, Zeng Wei, Long Xia, Yanyan Lan, Dawei Yin, Xueqi Cheng, and Ji-Rong Wen. 2020.  Reinforcement learning to rank with pairwise policy gradient. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 509–518.
  * Xu et al. (2017) Jun Xu, Long Xia, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2017.  Directly optimize diversity evaluation measures: A new approach to search result diversification.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ 8, 3 (2017), 1–26.
  * Yan et al. (2021) Le Yan, Zhen Qin, Rama Kumar Pasumarthi, Xuanhui Wang, and Michael Bendersky. 2021.  Diversification-aware learning to rank using distributed representation. In _Proceedings of the Web Conference 2021_. 127–136.
  * Yao et al. (2020) Jing Yao, Zhicheng Dou, Jun Xu, and Ji-Rong Wen. 2020.  RLPer: A reinforcement learning model for personalized search. In _Proceedings of The Web Conference 2020_. 2298–2308.
  * Yu et al. (2022) Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. 2022.  The surprising effectiveness of ppo in cooperative multi-agent games.  _Advances in Neural Information Processing Systems_ 35 (2022), 24611–24624.
  * Yu (2022) Hai-Tao Yu. 2022.  Optimize What You Evaluate With: Search Result Diversification Based on Metric Optimization. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 10399–10407.
  * Zhai et al. (2015) ChengXiang Zhai, William W Cohen, and John Lafferty. 2015.  Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In _Acm sigir forum_ , Vol. 49. ACM New York, NY, USA, 2–9.
  * Zhang et al. (2022) Bin Zhang, Yunpeng Bai, Zhiwei Xu, Dapeng Li, and Guoliang Fan. 2022.  Efficient cooperation strategy generation in multi-agent video games via hypergraph neural network.  _arXiv preprint arXiv:2203.03265_ (2022).
  * Zhang et al. (2023a) Bin Zhang, Lijuan Li, Zhiwei Xu, Dapeng Li, and Guoliang Fan. 2023a.  Inducing stackelberg equilibrium through spatio-temporal sequential decision-making in multi-agent reinforcement learning. In _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence_. 353–361.
  * Zhang et al. (2023b) Bin Zhang, Hangyu Mao, Lijuan Li, Zhiwei Xu, Dapeng Li, Rui Zhao, and Guoliang Fan. 2023b.  Stackelberg decision transformer for asynchronous action coordination in multi-agent systems.  _arXiv preprint arXiv:2305.07856_ (2023).
  * Zhou and Agichtein (2020) Jianghong Zhou and Eugene Agichtein. 2020.  Rlirank: Learning to rank with reinforcement learning for dynamic search. In _Proceedings of The Web Conference 2020_. 2842–2848.
  * Zhu et al. (2014) Yadong Zhu, Yanyan Lan, Jiafeng Guo, Xueqi Cheng, and Shuzi Niu. 2014.  Learning for search result diversification. In _Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval_. 293–302.
  * Zou et al. (2019) Shihao Zou, Zhonghua Li, Mohammad Akbari, Jun Wang, and Peng Zhang. 2019.  MarlRank: Multi-agent reinforced learning to rank. In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_. 2073–2076.