On component interactions in two-stage recommender systems
Year: 2022

Abstract:
Thanks to their scalability, two-stage recommenders are used by many of today’s largest online platforms, including YouTube, LinkedIn, and Pinterest. These systems produce recommendations in two steps: (i) multiple nominators—tuned for low prediction latency—preselect a small subset of candidates from the whole item pool; (ii) a slower but more accurate ranker further narrows down the nominated items, and serves to the user. Despite their popularity, the literature on two-stage recommenders is relatively scarce, and the algorithms are often treated as mere sums of their parts. Such treatment presupposes that the two-stage performance is explained by the behavior of the individual components in isolation. This is not the case: using synthetic and real-world data, we demonstrate that interactions between the ranker and the nominators substantially affect the overall performance. Motivated by these findings, we derive a generalization lower bound which shows that independent nominator training can lead to performance on par with uniformly random recommendations. We find that careful design of item pools, each assigned to a different nominator, alleviates these issues. As manual search for a good pool allocation is difficult, we propose to learn one instead using a Mixture-of-Experts based approach. This significantly improves both precision and recall at K.

text: Thanks to their scalability, two-stage recommenders are used by many of today’s largest online platforms, including YouTube, LinkedIn, and Pinterest. These systems produce recommendations in two steps: (i) multiple nominators—tuned for low prediction latency—preselect a small subset of candidates from the whole item pool; (ii) a slower but more accurate ranker further narrows down the nominated items, and serves to the user. Despite their popularity, the literature on two-stage recommenders is relatively scarce, and the algorithms are often treated as mere sums of their parts. Such treatment presupposes that the two-stage performance is explained by the behavior of the individual components in isolation. This is not the case: using synthetic and real-world data, we demonstrate that interactions between the ranker and the nominators substantially affect the overall performance. Motivated by these findings, we derive a generalization lower bound which shows that independent nominator training can lead to performance on par with uniformly random recommendations. We find that careful design of item pools, each assigned to a different nominator, alleviates these issues. As manual search for a good pool allocation is difficult, we propose to learn one instead using a Mixture-of-Experts based approach. This significantly improves both precision and recall at K.

heading: 1 Introduction
text: Recommender systems play a central role in online ecosystems, affecting what media we consume, which products we buy, or even with whom we interact. A key technical challenge is ensuring these systems can sift through billions of items to deliver a personalized experience to millions of users with low response latency. A widely adopted solution to this problem are two-stage recommender systems [12, 20, 28, 98, 101] where (i) a set of computationally efficient nominators (or candidate generators) preselects a small number of candidates, which are then (ii) further narrowed down, reranked, and served to the user by a slower but more statistically accurate ranker.
Nominators are often heterogeneous, ranging from associative rules to recurrent neural networks [18]. A popular choice are matrix factorization [56, 72] and two-tower [98] architectures which model user feedback by the dot product between user and item embeddings. While user embeddings often evolve with the changing context of user interactions, item embeddings can typically be precomputed before deployment. The cost of candidate generation is thus dominated by the (approximate) computation of the embedding dot products. In contrast, the ranker often takes both the user and item features as input, making the computational cost linear in the number of items even at deployment [20, 67].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
With few exceptions [44, 52, 67], two-stage specific literature is sparse compared to that on singlestage systems (i.e., recommenders which do not construct an explicit candidate set within a separate nominator stage [e.g., 17, 40, 46, 56, 72, 78, 84]). This is especially concerning given the considerable ethical challenges entailed by the enormous reach of two-stage systems: according to the recent systematic survey by Milano et al. [70], recommender systems have been (partially) responsible for unfair treatment of disadvantaged groups, privacy leaks, political polarization, spread of misinformation, and ‘filter bubble’ or ‘echo chamber’ effects. While many of these issues are primarily within the realm of ‘human–algorithm’ interactions, the additional layer of ‘algorithm–algorithm’ interactions introduced by the two-stage systems poses a further challenge to understanding and alleviating them.
The main aim of our work is thus to narrow the knowledge gap between single- and two-stage systems, particularly in the context of score-based algorithms. Our main contributions are:
1. We show two-stage recommenders are significantly affected by interactions between the ranker and the nominators over a variety of experimental settings (Section 3.1).
2. We investigate these interactions theoretically (Section 3.2), and find that while independent ranker training typically works well (Proposition 1), the same is not the case for the nominators where two popular training schemes can both result in performance no better than that of a uniformly random recommender (Proposition 2).
3. Responding to the highlighted issues with independent training, we identify specialization of nominators to smaller subsets of the item pool as a source of potentially large performance gains. We thus propose a joint Mixture-of-Experts [47, 49] style training which treats each nominator as the expert for its own item subset. The ability to learn the item pool division alleviates the issues caused by the typically lower modeling capacity of the nominators, and empirically leads to improved precision and recall at K (Section 4).

heading: 2 Two-stage recommender systems
text: The goal of recommender systems is to learn a policy π which maps contexts x ∈ X to distributions π(x) over a finite set of items (or actions) a ∈ A , such that the expected reward Ex Ea∼π(x)[ra |x] is maximized. The context x represents information about the user and items (e.g., interaction history, demographic data), and ra is the user feedback associated with item a (e.g., rating, clickthrough, watch-time). We assume that ra|x has a well-defined fixed mean f?(x, a) := E[ra |x] for all the (x, a) pairs. To simplify, we further assume only one item at is to be recommended for each given context xt, where t ∈ [T ] with [T ] := {1, . . . , T} for T ∈ N. Two-stage systems differ from the single-stage ones by the two-step strategy of selecting at. First, each nominator n ∈ [N ] picks a single candidate an,t from its assigned pool An ⊆ A (An 6= ∅,⋃ nAn = A). Second, the ranker chooses an item at from the candidate pool Ct := {a1,t , . . . , aN,t}, and observes the reward rt = rtat associated with at. Since the goal is expected reward maximization, recommendation quality can be measured by instantaneous regret r?t − rt where r?t = rta?t is the reward associated with an optimal arm a?t ∈ argmaxa∈A f?(xt, a). This leads us to an important identity for the (cumulative) regret in two-stage systems which is going to be used throughout:
R2sT = T∑ t=1 r?t − rt = T∑ t=1
(r?t − rtãt)︸ ︷︷ ︸ =:RNT +
T∑ t=1
(rtãt − rt)︸ ︷︷ ︸ =:RRT , (1)
with ãt ∈ argmaxa∈Ct f ?(xt, a). In words, RNT is the nominator regret, quantifying the difference between the best action presented to the ranker ãt and the best overall action a?t , and R R T is the ranker regret which measures the gap between the choice of the ranker at and the best action in the candidate set Ct. The two-stage recommendation process is summarized in Figure 2 (left). While Equation (1) is typical for the bandit literature (data collected interactively, only rtat revealed for each t), we also consider the supervised learning case (a dataset with all {rta}ta revealed is given). In particular, Section 3 presents an empirical comparison of single- and two-stage systems in the bandit setting, followed by a theoretical analysis with implications for both the learning setups.

heading: 3 Comparing single- and two-stage systems
text: Since the ranker and nominators could each be deployed independently, one may wonder whether the performance of a two-stage system is significantly affected by factors beyond the hypothetical singlestage performance of its components. This question is both theoretically (new developments needed?) and practically interesting (e.g., training components independently, as common, assumes targeting single-stage behavior is optimal). In Section 3.1, we empirically show that while factors known from the single-stage literature also affect two-stage systems, there are two-stage specific properties which can be even more important. Section 3.2 then investigates these properties theoretically, revealing a non-trivial interaction between the nominator training objective and the item pool allocations {An}n.

heading: 3.1 Empirical observations
text: Setup
We study the effects of item pool size, dimensionality, misspecification, nominator count, and the choice of ranker and nominator algorithms in the bandit setting. We compare single- and two-stage systems where each (component) models the expected reward as a linear function ft(x, a) = 〈θ̂t, xa〉 (xa differs for each a). Abbreviating xt = xtat , the estimates are converted into a policy via either:
1. UCB (U) [6, 64] which computes the ridge-regression estimate with regularizer λ > 0
θ̂t := Σt t−1∑ i=1 xiri , Σt := ( λI + t−1∑ i=1 xix > i )−1 , (2)
and selects actions with exploration bonus α > 0: at ∈ argmaxa 〈θ̂t, xta〉+ α √ x>taΣtxta .
2. Greedy (G) [8, 53] which can be viewed as a special case of UCB with α = 0.
The argmax is restricted toAn (resp. Ct) in two-stage systems, with pool allocation {An}n designed to minimize overlaps and approximately equalize the number of items in each pool (see Appendix B).
We chose to make the above restrictions of our experimental setup to limit the large number of design choices two-stage recommenders entail (architecture and hyperparameters of each nominator and the ranker, item pool allocation, number of nominators, etc.), and with that isolate the variation in performance to only a few factors of immediate interest.
We use one synthetic and one real-world dataset. The synthetic dataset is generated using a linear model rta = 〈θ?, xta〉 + εta for each time step t ∈ [T ] and action a ∈ A. The vector θ? is drawn uniformly from the d-dimensional unit sphere at the beginning and then kept fixed, the contexts xta are sampled independently from N (0, I), and εta ∼ N (0, 0.01) is independent observation noise.
The real-world dataset ‘AmazonCat–13K’ contains Amazon reviews and the associated product category labels [10, 69].1 Since ‘AmazonCat–13K’ is a multi-label classification dataset, we convert it into a bandit one by assigning a reward of one for correctly predicting any one of the categories to which the product belongs, and zero otherwise. An |A|–armed linear bandit is then created by sampling |A| reviews uniformly from the whole dataset, and treating the associated features as the contexts {xta}a∈A. This method of conversion is standard in the literature [27, 35, 66, 67]. We use only the raw text features, and convert them to 768-dimensional embeddings using the HuggingFace pretrained model ‘bert-base-uncased’ [24, 97];2 we further subset to the first d = 400 dimensions of the embeddings, which does not substantially affect the results. Because we are running thousands of different experiment configurations (counting the varying seeds), we further reduce the computational complexity by subsetting from the overall 13K to only 100 categories. Since most of the products belong to 1–3 categories, we take the categories with 3rd to 102nd highest occurrence frequency. This ensures less than 5% of the data points belong to none of the preserved categories, and overall 10.73% reward positivity rate with strong power law decay (Figure 2, right).
While the ranker can always access all d features, the usual lower flexibility of the nominators (misspecification) is modelled by restricting each to a different random subset of s out of the total d features on both datasets. This is equivalent to forcing the corresponding regression parameters to be zero. Both UCB and Greedy are then run with xt replaced by the s-dimensional xn,t = xn,tat everywhere. The same restriction is applied to the single-stage systems for comparison. In all rounds, each nominator is updated with (xn,t, at, rt), regardless of whether at ∈ An (this assumption is revisited in Section 3.2). Thirty independent random seeds were used to produce the (often barely visible) two-sigma standard error regions in Figures 3 and 4. More details—including the hyperparameter tuning protocol and additional results—can be found in Appendices B and C.
Results
Starting with the synthetic results in Figure 3, we see that the number of arms and the feature dimension d are both correlated with increased regret in single- and two-stage systems. Another similarity between all the algorithms is that misspecification—as measured by d/s—also has a significant effect on performance.3 This is also the case for the Amazon dataset in Figure 4.
1We did not use ‘MovieLens’ [38] since it contains little useful contextual information as evidenced by its absence even from the state-of-the-art models [79]. Two-stage recommenders are only used when context matters as otherwise all recommendations could be precomputed and retrieved from a database at deployment.
2Encoded dataset: https://twostage.s3-us-west-2.amazonaws.com/amazoncat-13k-bert.zip. 3Misspecification error typically translates into a linear regret term T [21, 25, 31, 32, 36, 58, 61]. We can thus gain some intuition for the concavity of d/s 7→ RT from the L2 error = minθn(E[(ra − 〈θn, xn,a〉)2])1/2 where a ∼ Unif(A) [58]. Using xta ∼ N (0, I), the minimum is achieved by (E[xn,ax>n,a])−1 E[xn,ara] = θ?n,
The influence of the number of arms, dimensionality, and misspecification on single-stage systems is well known [60]. Figures 3 and 4 suggest similar effects also exist for two-stage systems. On the other hand, while the directions of change in regret agree, the magnitudes do not. In particular, two-stage systems perform significantly better than their single-stage counterparts. This is possible because the ranker can exploit its access to all d features to improve upon even the best of the nominators (recall that nominators and single-stage systems share the same model architecture). In other words, the single-stage performance of individual components does not fully explain the two-stage behavior.
To develop further intuition about the differences between single- and two-stage systems, we turn our attention to the Amazon experiments in Figure 4. The top row suggests the performance of two-stage systems improves as the number of nominators grows. Strikingly, the accompanying UCB ranker + nominator plots in the bottom row show the nominator regret RNT dominates when there are few nominators, but gives way to the ranker regret RRT as their number increases.
To explain why, first note that the single-stage performance of the ranker can be read off from the bottom left corner of each plot where d = s (because all the components are identical at initialization, and then updated with the same data). Since the size of the candidate set Ct increases with the number of nominators, the two-stage performance in the d > s case eventually approaches that of the single-stage UCB ranker as well, even if the nominators are no better than random guessing. In fact, because ≈ 10% of the items yield optimal reward, the probability that a set of ten uniformly random nominators with non-overlapping item pools nominates at least one optimal arm is on average 1− ( 910 )
10 ≈ 0.65, i.e., the instantaneous nominator regret would be zero 65% of the time. To summarize, we have seen evidence that properties known to affect single-stage performance— number of arms, feature dimensionality, misspecification—have similar qualitative effects on twostage systems. However, two-stage recommenders perform significantly better than any of the nominators alone, especially as the nominator count and the size of the candidate pool increase. Complementary to the evidence from offline learning [67], and the effect of ranker pretraining [44], these observations add to the case that two-stage systems should not be treated as just the sum of their parts. We add theoretical support to this argument in the next section.

heading: 3.2 Theoretical observations
text: The focus of Section 3.1 was on linear models in the bandit setting. We lift the bandit assumption later in this section, and relax the class of studied models to least-squares regression oracle (LSO) based algorithms, which estimate the expected reward by minimizing the sum of squared errors and a
with θ?n the s entries of θ? corresponding to the dimensions available to n. The L2 error is thus a concave function of d/s by symmetry: = √ E[E[(rta − 〈θ?n, xn,ta〉)2 | θ?]] = √ E[‖θ?‖22 − ‖θ?n‖22] = √ 1− s/d.
regularizer ‖ · ‖F over a given model class F ft ∈ argminf∈F { ‖f‖F + t−1∑ i=1 (ri − f(xi, ai))2 } . (3)
These estimates are then converted into a policy either greedily, πt(x) = Unif(argmaxa ft(x, a)), or by incorporating an exploration bonus as in LinUCB [6, 19, 22, 64, 82], or the more recent class of black-box reductions from bandit to online or offline regression [30–32, 58, 86]. The resulting algorithms are often minimax optimal, and (some) also perform well on real-world data [11].
We choose LSO based algorithms because they (i) include the Greedy and (Lin)UCB models studied in the previous section, and (ii) allow for an easier exposition than the similarly popular cost-sensitive classification approaches [e.g., 2, 18, 20, 26, 59]. The following proposition is an application of the fact that algorithms like LinUCB or SquareCB [1, 30, 32] provide regret guarantees robust to contexts chosen by an adaptive adversary, and thus also to those chosen by the nominators.
Proposition 1 Assume the ranker achieves a single-stage regret guarantee RT ≤ BRT for some constant BRT ∈ R (either in expectation or with high probability), even if the contexts {xt}Tt=1 are chosen by an adaptive adversary. The ranker regret then satisfies
RRT = T∑ t=1 rtãt − rt ≤ BRT ,
in the sense of the original bound (i.e., in expectation, or with high probability).
While proving Proposition 1 is straightforward, its consequences are not. First, if BRT is in some sense optimal, then Equation (1) implies the two-stage regret R2sT will be dominated by the nominator regret RNT (unless it satisfies a similar guarantee). Second, R R T ≤ BRT holds exactly when the ranker is trained in the ‘single-stage mode’, i.e., the tuples (xt, at, rt) are fed to the algorithm without any adjustment for the fact Ct is selected by a set of adaptive nominators from the whole item pool A. The above however does not mean that the ranker has no substantial effect on the overall behavior of the two-stage system. In particular, the feedback observed by the ranker also becomes the feedback observed by the nominators, which has the primary effect of influencing the nominator regret RNT , and the secondary effect of influencing the candidate pools Ct (which creates a feedback loop). The rest of this section focuses on the primary effect, and in particular its dependence on how the nominators are trained and the item pools {An}n allocated.
Pitfalls in designing the nominator training objective
The primary effect above stems from a key property of two-stage systems: unlike the ranker, nominators do not observe feedback for all items they choose. While importance weighting can be used to adjust the nominator training objective [67], it does not tell us what adjustment would be optimal.
We thus study two major types of updating strategies: (i) ‘training-on-all,’ and (ii) ‘training-on-own.’ Both can be characterized in terms of the following weighted oracle objective for the nth nominator
fn,t ∈ argminfn∈Fn { ‖fn‖Fn + t−1∑ i=1 wn,i(ri − fn(xn,i , ai))2 } , (4)
where Fn is the class of functions the nominator can fit, ‖ ·‖Fn the regularizer, and wn,t = wn,at ≥ 0 the weight. ‘Training-on-all’—used in Section 3.1—takes wn,a = 1 for all (n, a), which means all data points are valued equally regardless of whether a particular at belongs to the nominator’s pool An. ‘Training-on-all’ may potentially waste the already limited modelling capacity of the nominators if the pools An are not identical. The ‘training-on-own’ alternative therefore uses wn,a = 1{a ∈ An} so that only the data points for which at ∈ An influence the objective.4
While ‘training-on-all’ and ‘training-on-own’ are not the only options we could consider, they are representative of two very common strategies. In particular, ‘training-on-all’ is the default easy-toimplement option which sometimes performs surprisingly well [11, 81]. In contrast, ‘training-on-own’
4There are two possible definitions of ‘training-on-own’: (i)wn,t = 1{at ∈ An}; (ii)wn,t = 1{at = an,t}. While the main text considers the former, Proposition 2 can be extended to the latter with minor modifications.
approximates the (on-policy) ‘single-stage mode’ where the nominator observes feedback only for the items it selects (in particular, at ∈ An only if at = an,t when the pools are non-overlapping). Proposition 2 below shows that neither ‘training-on-all’ nor ‘training-on-all’ is guaranteed to perform better than random guessing in the infinite data limit (T → ∞). We consider the linear setting f?(xt, a) = 〈θ?, xta〉 for all (xt, a), θ? fixed, with nominators using ridge regression oracles fn,t(xn,t, a) = 〈θ̂n,t, xn,ta〉 as defined in Equation (2), λ ≥ 0 fixed, and xn,ta again a subset of the full feature vector xta. We also assume the nominators take the predicted best action with non-vanishing probability (Assumption 1), which holds for all the cited LSO based algorithms.
Assumption 1 Let fn,t be as in Equation (4), and denote AGn,t := argmaxa∈An fn,t(xn,t, a). We assume there is a universal constant δ > 0 such that for all n ∈ [N ] and a ∈ An with lim supT−1 ∑ 1≤t≤T P(a?t = a) > 0, we have lim supT−1 ∑ 1≤1≤T P(an,t ∈ AGn,t | a?t = a) ≥ δ.
Proposition 2 In both the supervised and the bandit learning setup, there exist two distinct context distributions with pool allocations {An}n, and ra ∈ [0, 1] almost surely (a.s.) for all a ∈ A, such that ‘training-on-own’ (resp. ‘training-on-all’) leads to asymptotically linear two-stage regret
lim sup T→∞ E[R2sT ] T > 0 .
Moreover, the asymptotic regret of ‘training-on-all’ is sublinear under the context distribution and pool allocation where ‘training-on-own’ suffers linear regret, and vice versa.
Proof 1 Throughout, we use θ̂n,t → (E[xn,ax>n,a])−1 E[xn,ara] =: θ?n (a.s.) by Lemma 1 (Appendix A), assuming invertibility and that at is i.i.d.; note θ?n = argminθn E[(ra − 〈θn, xn,a〉)
2]. We allow any zero mean reward noise which satisfies ra ∈ [0, 1] (a.s.) for all a ∈ A. (I) Supervised setup. Take two nominators, A1 = {a(1)}, A2 = {a(2), a(3)}, a single context
X :=  xa(1)xa(2) xa(3)
 = [1 0 −10 1 0 0 0 1 ] , (5)
and restrict the nominators to the last two columns of X . As |A1| = 1, the first nominator always proposes a(1), disregards of its fitted model. Since all rewards are revealed and used to update the model in the supervised setting, ‘training-on-all’ t→∞ limit for the second nominator’s θ̂2,t is
θ?2 = argminβ∈R2 Ea∼Unif(A)[(ra − 〈β, x2,a〉)2] = argminβ∈R2 { (r̄1 + β2) 2 + (r̄2 − β1)2 + (r̄3 − β2)2 } = [r̄2, r̄3−r̄1 2 ] > ,
where r̄ is the mean reward vector for the single context (θ? is then X−1r̄). If we take, e.g., r̄ = [ 14 , 1 2 , 1] >, then a(3) 6= argmaxa∈A2〈θ ? 2 , x2,a〉 = a(2). On the other hand, ‘training-on-own’ would yield θ?2 = [r̄2, r̄3] >, and thus correctly identify a(3) via argmaxa∈A2〈θ ? 2 , x2,a〉.
In contrast, consider the modified setup A1 = {a(1)}, A2 = {a(2), a(3), a(4)}
X :=  xa(1) xa(2) xa(3) xa(4)
 = 1 0 0 −10 1 0 −10 0 1 0
0 0 0 1  . (6) Restricting nominators to the last two columns ofX , ‘training-on-own’ would yield θ?2 = [r̄3, r̄4−r̄2 2 ] > under full feedback access, whereas ‘training-on-all’ would converge to θ?2 = [r̄3, r̄4−r̄2−r̄1 3 ] >. Hence with, e.g., r̄ = [ 34 , 1, 1 6 , 7 8 ] >, ‘training-on-own’ would make the second nominator pick a(3) via argmax, but ‘training-on-all’ would successfully identify the optimal a(2).
(II) Bandit setup. Take X from Equation (6), but use r̄ = [ 34 , 7 8 , 1 6 , 1] > and the associated θ? = X−1r̄. For each j ∈ [4], let X(j) be a deterministic context matrix which is the same as X except all but the jth row are replaced by zeros. Observe that for each j, the mean reward vector X(j)θ? has exactly one strictly positive component, and thus a?t = a(j) when X(j) is drawn.
Let Unif({X(j)}j) be the context distribution, A1 = {a(1)}, A2 = {a(2), a(3), a(4)}, and restrict nominators to the last two columns of each sampledX(j). We employ a proof by contradiction. Assume lim supT−1 E[R2sT ]→ 0. Then θ̂2,t → θ?2 in probability by Lemma 2 (Appendix A), with θ?2 as stated right after Equation (6) for both the update rules. Since θ?2,2 = 1 16 > 0 under ‘training-on-own’, resp. θ?2,2 = − 524 < 0 under ‘training-on-all’, argmaxa∈A2〈θ ? 2 , x2,ta〉 would fail to select a?t when X(2), resp. X(4), is sampled (see Equation (6)). This would translate into an expected instantaneous regret of at least ∆ := mini r̄i = 16 > 0. Hence by Equation (1) and P(a ? t = a) = |A|−1
E[R2sT ] ≥ E[RNT ] ≥ ∆ |A| ∑ a∈A2 P(a2,t 6= a | a2,t ∈ AG2,t, a?t = a)P(a2,t ∈ AG2,t | a?t = a) . (7)
For ‘training-on-own’, P(a2,t 6= a(2) | a2,t ∈ AG2,t, a?t = a(2)) = P(θ̂2,t2 · (−1) < 0) → 1 by the above established θ̂2,t → θ?2 in probability, and the continuous mapping theorem. Analogously for
‘training-on-all’. Hence lim supT−1 E[R2sT ] ≥ |A|−1∆δ > 0 by Assumption 1, a contradiction, meaning both modes of training fail, but for a different item (a(3) is picked out correctly by both again by the convergence in probability). To make lim supT−1 E[RNT ] → 0 for exactly one of the two setups, add a third nominator with A3 = {a(2)}, resp. A3 = {a(4)}, so that P(a?t ∈ Ct)→ 1.
Proposition 2 shows that the nominator training objective can be all the difference between poor and optimal two-stage recommender.5 Moreover, neither ‘training-on-own’ nor ‘training-on-all’ guarantees sublinear regret, and one can fail exactly when the other works. The main culprit is the difference between context distribution in and outside of each pool: combined with the misspecification, either one can result in more favorable optima from the overall two-stage performance perspective. This is the case both in the supervised and the bandit setting.
Proposition 2 can be trivially extended to higher number of arms and nominators (add embedding dimensions, let the new arms have non-zero embedding entries only in the new dimensions, and the expected rewards to be lower than the ones we used above). We think that the difference between the in- and out-pool distributions could be exploited to derive analogous results to Proposition 2 for non-linear (e.g., factorization based) models, although the proof complexity may increase.
To summarize, beyond the actual number of nominators identified in the previous section, we have found that the combination of training objective and pool allocation can heavily influence the overall performance. We use these insights to improve two-stage systems in the next section.

heading: 4 Learning pool allocations with Mixture-of-Experts
text: Revisiting the proof of Proposition 2, we see the employed pool allocations are essentially adversarial with respect to the context distributions. However, we are typically free to design the pools ourselves, with the only constraints imposed by computational and statistical performance requirements. Proposition 2 thus hints at a positive result: a good pool allocation can help us achieve an (asymptotically) optimal performance even in cases where this is not possible using any one of the nominators alone.
Crafting a good pool allocation manually may be difficult, and could lead to very bad performance if not done carefully (Proposition 2). We thus propose to learn the pool allocation using a Mixtures-ofExperts (MoE) [47, 49, 50, 99] based approach instead. A MoE computes predictions by weighting the individual expert (nominator) outputs using a trainable gating mechanism. The weights can be thought of as a soft pool allocation which allows each expert to specialize on a different subset of the input space. This makes the MoE more flexible than any one of the experts alone, alleviating the lower modeling flexibility of the nominators due to the latency constraints.
We focus on the Gaussian MoE [47], trained by likelihood maximization (Equation (8)). We employ gradient ascent which—despite its occasional failure to find a good local optimum [68]—is easy to scale to large datasets using a stochastic approximation of gradients
1
T T∑ t=1 log N∑ n=1 pn,t exp { − (rt − r̂n,t) 2 2σ2 } ≈ 1 B B∑ t=1 log N∑ n=1 pn,t exp { − (rt − r̂n,t) 2 2σ2 } , (8)
5Covington et al. [20] reported empirically observing that the the training objective choice has an outsized influence on the performance of two-stage recommender systems. Proposition 2 can be seen as a theoretical complement which shows that the range of important choices goes beyond the selection of the objective.
with pn,t ≥ 0 ( ∑ n pn,t = 1) the gating weight assigned to expert n on example t, r̂n,t the matching expert prediction, σ > 0 a hyperparameter approximating reward variance, and B ∈ N the batch size. MoE provides a compelling alternative to a policy gradient style approach applied to the joint twostage policy π2s(a |x) = ∑ a1,...,aN πR(a |x, C) ∏N n=1 π N n(an |x) as done in [67]. In particular, a significant advantage of the MoE approach is that the sum over the exponentially many candidate sets C = {a1, . . . , aN} is replaced by a sum over only N experts, which can be either computed exactly or estimated with dramatically smaller variance than in the candidate set case.
There are (at least) two ways of incorporating MoE into existing two-stage recommender deployments:
1. Use a provisional gating mechanism, and then distill the pool allocations from the learned weights, e.g., by thresholding the per arm average weight assigned to each nominator, or by restricting the gating network only to the item features. Once pools are divided, nominators and the ranker may be finetuned and deployed using any existing infrastructure.
2. Make the gating mechanism permanent, either as (i) a replacement for the ranker, or (ii) part of the nominator stage, reweighting the predictions before the candidate pool is generated. This necessitates change of the existing infrastructure but can yield better recommendations.
Unusually for MoEs, we may want to use a different input subset for the gating mechanism and each expert depending on which of the above options is selected. We would like to emphasize that the MoE approach can be used with any score-based nominator architecture including but not limited to the linear models of the previous section. If some of the nominators are not trainable by gradient descent but are score-based, they can be pretrained and then plugged in during the MoE optimization, allowing the other experts to specialize on different items.
We use the ‘AmazonCat-13K’ dataset [10, 69] to investigate the setup with a logistic gating mechanism as a part of the nominator stage. We employ the same preprocessing as in Section 3.1. Due to the success of greedy methods in Section 3.1, and the existence of black-box reductions from bandit to offline learning [31, 86], we simplify by focusing only on offline evaluation. We compare the MoE against the same model except with the gating replaced by a random pool allocation fixed at the start.
The experts in both models use a simple two-tower architecture, where de-dimensional dense embeddings are learned for each item, the s-dimensional subset of the BERT embeddings is mapped to Rde by another trained matrix, and the final prediction is computed as the dot product on Rde . To enable low latency computation of recommendations, the gating mechanism models the logits {log pn}n as a sum of learned user and item embeddings. Further details are described in Appendix B.
Figure 5 shows that MoEs are able to outperform random pool allocation for most combinations of model architecture and training set size. The improved results in recall suggest that the specialization allows nominators to produce a more diverse candidate set. Since the gating mechanism can learn to exactly recover any fixed pool allocation, the MoE can perform worse only when the optimizer fails or the model overfits. This seems to be happening for the smallest training set size (c = 100 samples per arm), and also when the item embedding dimension de is high. In practice, these effects can be counteracted by tuning hyperparameters for the specific setting, regularization, or alternative training approaches based on expectation–maximization or tensor decomposition [50, 68, 99].

heading: 5 Other related work
text: Scalable recommender systems. Interest in scalable recommenders has been driven by the continual growth of available datasets [37, 63, 83, 91]. The two-stage architectures examined in this paper have seen widespread adoption in recommendation [12, 20, 28, 101, 102], and beyond [5, 100]. Our paper is specifically focused on recommender systems which means our insights may not transfer to application areas like information retrieval without adaptation.
Off-policy learning and evaluation. Updating the recommendation policy online, without human oversight, runs the risk of compromising the service quality, and introducing unwanted behavior. Offline learning from logged data [27, 73, 89, 92] is an increasingly popular alternative [18, 48, 67, 90]. It has also found applications in search engines, advertising, robotics, and more [4, 48, 62, 88].
Ensembling and expert advice. The goal of ‘learning with expert advice’ [3, 7, 65, 87] is to achieve performance comparable with the best expert if deployed on its own. This is not a good alternative to our MoE approach since two-stage systems typically outperform any one of the nominators alone (Section 3). A better alternative may possibly be found in the literature on ‘aggregation of weak learners’ [14, 15, 33, 34, 43], or recommender ensembling (see [16] for a recent survey).

heading: 6 Discussion
text: We used a combination of empirical and theoretical tools to investigate the differences between singleand two-stage recommenders. Our first major contribution is demonstrating that besides common factors like item pool size and model misspecification, the nominator count and training objective can have even larger impact on performance in the two-stage setup. As a consequence, two-stage systems cannot be fully understood by studying their components in isolation, and we have shown that the common practice of training each component independently may lead to suboptimal results. The importance of the nominator training inspired our second major contribution: identification of a link between two-stage recommenders and Mixture-of-Experts models. Allowing each nominator to specialize on a different subset of the item pool, we were able to significantly improve the two-stage performance. Consequently, splitting items into pools within the nominator stage is not just a way of lowering latency, but can also be used to improve recommendation quality.
Due to the the lack of access, a major limitation of our work is not evaluating on a production system. This may be problematic due to the notorious difficulty of offline evaluation [9, 57, 80]. We further assumed that recommendation performance is captured by a few measurements like regret or precision/recall at K, even though design of meaningful evaluation criteria remains a challenge [23, 41, 51, 71]; we caution against deployment without careful analysis of downstream effects and broader impact assessment. Several topics were left to future work: (i) extension of the linear regret proof to non-linear models such as those used in the MoE experiments; (ii) slate (multi-item) recommendation; (iii) theoretical understanding of how much can the ranker reduce the regret compared to the best of the (misspecified) nominators; (iv) alternative ways of integrating MoEs, including explicit distillation of pool allocations from the learned gating weights, learning the optimal number of nominators [77], using categorical likelihood [99], and sparse gating [29, 85].
Overall, we believe better understanding how two-stage recommenders work matters due to the enormous reach of the platforms which employ them. We hope our work inspires further inquiry into two-stage systems in particular, and the increasingly more common ‘algorithm-algorithm’ interactions between independently trained and deployed learning algorithms more broadly.
Acknowledgments and Disclosure of Funding
The authors thank Matej Balog, Mateo Rojas-Carulla, and Richard Turner for their useful feedback on early versions of this manuscript. Jiri Hron is supported by an EPSRC and Nokia PhD fellowship.

Review summaries:
The work focuses on a very practical problem of designing a good a two-stage recommender systems. The authors shed light on interaction between the two stages (called nominator and ranker) and its effects on an overall performance of the solution. They theoretically prove that the way nominators are trained may significantly affect the end quality and provide an empirical evidence for their findings as well. The authors also provide a recipe for designing a better first stage based on a mixture-of-experts approach that turns out to advantageous over naïve approach in certain cases. 

This paper studies on the properties of two-stage recommendation architecture. Both empirical and theoretical analyses have been conducted to reveal the impact of pool allocation on recommendation performance. The authors further propose a MOE-based learning strategy for pool allocation, which yields empirical improvement over the random pool allocation.

This work compares one-stage and two-stage systems from both of empirical and theoretical observations, which finds that interactions between the ranker and the nominators substantially affect the overall system performance. A Mixture-of-Experts approach is adopted to train the nominators to specialize on different subsets of the item pool. This improves the performance conducted on a Amazon review dataset. Overall, this submission is well presented and easy to follow.