On Component Interactions in Two-Stage Recommender Systems
Authors: Jiri Hron
Karl Krauth
Michael Jordan
Niki Kilbertus
Venue: NeurIPS 2021 Poster (2021)
Keywords: recommender systems
mixture of experts
bandits
scalability

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$.

On component interactions in two-stage recommender systems
Jiri Hron
Karl Krauth UC Berkeley
Michael I. Jordan UC Berkeley
University of Cambridge
Niki Kilbertus
Technical University of Munich Helmholtz AI, Munich
Abstract
Thanks to their scalability, two-stage recommenders used by many of today's largest online platforms, including YouTube, Linkedln, and Pinterest. These systems produce recommendations in two steps: (i) multiple nominators- 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 sums of their parts. Such treatment presupposes that the two-stage performance is explained by the behavior of the individual components isolation. This 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 performance on par with uniformly random recommendations. We find that careful design of item pools, each assigned a different nominator, alleviates these issues. manual search for good pool allocation is difficult, we propose to learn one instead using Mixture-of-Expee -fxpees based approach. This significantly improves both precision and recall K.
Introduction
Recommender systems play central role 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 deliver a personalized experience millions users with low response latency. A widely adopted solution to this problem are two-stage recommender systems [12, 20, 28, 98, 101] where (i) of computationally efficient nominators (or candidate generators) preselects small number of candidates, which are then (ii) further narrowed down, reranked, and served to the user by a slower but more statistically accurate runker.
Nominators are often heterogeneous, ranging from associative rules to recurrent neural networks [18]. 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. 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 (NcurIPS 2021).

---

With few exceptions [44, 52, 67], two-stage specific literature is sparse compared to that on single- stage systems (i.e., recommenders which do not construct an explicit candidate set within 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 misinforma- tion, and 'filter bubble' or "echo chamber' effects. While many of these issues are primarily within the realm of alman-algorithmi interactions, the additional layer of "algorthn-algoriimmm interactions introduced by the two-stage systems poses a further challenge 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 nomina- tors where two popular training schemes can both result in performance no better than that of uniformly random recommender (Proposition 2).
3. Responding to the highlighted issues with independent training, we identify specialization of nominators smaller subsets of the item pool source of potentially large performance gains. We thus propose a joint Mixture-of- -f--exerts [47, 49] style training which treats each nominator 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 K (Section 4).
2 Two-stage recommender systems
The goal of recommender systems is to learn policy which maps contexts E X' to distributions (2)) over a finite set of items (or actions) a E A, such that the expected reward E,, Ea--(<)) [ra a æ*] 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 (e.g.. rating, clickthrough, watch-time). We assume that r. Jx has well-defined fixed mean I f* a) = E(ra ax] for all the (z, a) pairs. To simplify, we further assume only one item O₂ is to be recommended for each given context Tr, where E [7] with [7] == (I....,7] T) for T N.
Two-stage systems differ from the single-stage ones by the two-step strategy of selecting a. First, each nominator E [N] picks single candidate a,,t from its assigned pool An, C A (AA, # Ø, A, = A). Second, the ranker chooses an item a, from the candidate pool C, = {a1.e...., and observes the reward recommendation quality can be measured by instantaneous regret rī - r2 where rī = Tta; is the reward associated with an optimal arm oj argmax f*(,,, a). This leads us an important identity for the (cumulative) regret in two-stage systems which is going to be used throughout:
Tta, associated with a,. Since the goal is expected reward maximization,
R
(ri Σ
rta.) + Σ (ria, r2),
t=l
with ā, E argmax, f* a). In words, Ry is the nominator regret, quantifying the difference between the best action presented to the ranker and the best overall action aj, and R.. is the ranker regret which measures the gap between the choice of the ranker a, and the best action in the candidate set C.. The two-stage recommendation process is summarized in Figure 2 (left).
While Equation (1) is typical for the bandit literature (data collected interactively, only Tta, revealed for each !), we also consider the supervised learning case (a dataset with all (rra)to revealed is given). In particular, Section 3 presents an empirical comparison of single- and two-stage systems in the bandit setting, followed by theoretical analysis with implications for both the learning setups.

---

round:
arms A.
35
contexts: X
nominators
frequency
25
ranker
20
age
5
0.02
0.04
0.06
0.08
0.10
positivity rate
Figure 2: Left: The two-stage recommendation setup. Right: Amazon reward histogram. The top arms are responsible for 19.22% whereas the bottom 50 only for 19.85% of the positive rewards.
3 Comparing single- and two-stage systems
Since the ranker and nominators could each be deployed independently, one may wonder whether the performance of two-stage system is significantly affected by factors beyond the hypothetical single- stage performance of its components. This question 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 non-trivial interaction between the nominator training objective and the item pool allocations {AAn )
3.1 Empirical observations
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 fe a) = (0,, r.)) (xa differs for each a). Abbreviating zy Tto, the estimates are converted into policy via either:
UCB (U) [6, 64] which computes the ridge-regression estimate with regularizer
: :2
ΣS =
Al +
x
(2)
and selects actions with exploration bonus a 0: ag E argmaxx, (0,, Dta) + a / Extra
2. Greedy (G) [8, 53] which can be viewed as a special case of UCB with a
The argmax is restricted to An (resp. C,) in two-stage systems, with pool allocation (An }n designed 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.
use one synthetic and one real-world dataset. The synthetic dataset generated using linear for each time step E [T] and action .A. The vector 0* is drawn uniformly from the d-dimensional unit sphere the beginning and then kept fixed, the contexts Ite sampled independently from (N00, 1), and Eta (0, 0.01) is independent observation noise.
model = (0* :taa)

---

d
d
nominators
nominators
nominators
100 arms
1000
1000
100
10,000 arms
10,000 arms
2000
d/s
A/s
d/s
d/s
4/s
d/s
(a)
G+G U+U
U+G
U
(b)
G+G
U+U
U+G
G
U
Figure 3: Synthetic data results. The x-axis is the ratio between the true feature dimension and the size of the subset available to the nominators and the single-stage systems s. The y-axis shows the expected regret T 1000. plot (a), N total number of features d. In plot (b), d = 40 features are used, and columns show the number of nominators N. The legend describes model architectures, where two-stage systems are labeled by [[ranker] + [nominator] (e.g., 'U+G* is a UCB ranker with Greedy nominators).
nominators are used, and columns represent the
The real-world dataset 'AmazonCat-133 contains Amazon reviews and the associated product category labels [10, 69].' Since 'AmazonCal-13K
multi-label classification dataset, we convert it into 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 (Ztalae.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 76S-dimensional embeddings using the [24, 97];2 we further subset to the first
HuggingFace pretrained model 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 right).
While the ranker can always access all d features, the usual lower flexibility of the nominators (mixspecifccation) is modelled by restricting each different random subset of 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 H, replaced by the s-dimensional In,: 2n, everywhere. The same restriction is applied to the single-stage systems for comparison. In all rounds, each nominator is updated with (In,,: Gr, Tt), regardless of whether a, 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 More details Cetails-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 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/ d/s-also has significant effect on performance." This is also the case for the Amazon dataset Figure
'We did not use 'MovieLenns' [38] since contains little useful contextual information evidenced by its absence even from state-of-ther 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. 2 EEcoded dataset: https: hopp:://wwwttatt s3 us-west-2 amazonaws com/ amwzoncat-- 13k- bert zip. Misspecificatiin error typically translates into linear regret term e' [21, 31, 36, 58, 61J. We can thus gain some intuition for the concavity of d/s + Rr from the 2 error = mine,, (Bl(r.. Un,,)) 1) 4/2 where Unif(AA [58]. Using Zte ~ ( 1). the minimum achieved by (B(In,,R))a)) E[xn,aFa] 0

---

100 arms nominators
1000 arms nominators
nominators
10 nominators
2 nominators
10 nominators
negnet
regret
R5
0.5
0.5
0.7
50
30
30
mggret
01
0000
rogpet
0003-
0C3
10225
10000
00000
90
90
d/s
d/s
4/a
4/a
d/s
a/s
(a)
U-U
ranker
Figure 4: Amazon data results. The axes are the same as in Figure 3, except the y-axis is plotted at T = 5000 with the regret divided by that of uniformly random agent. The feature dimension is fixed to d = 400, and the number of arms to 100 in plot (a), and to 1000 in plot (b). The columns represent varying number of nominators N. The legend is shared, where the one in (a) corresponds to the top row plots and has the same interpretation as in Figure 3, and the one in (b) belongs to the bottom plots which show the proportion of ranker and nominator regret (see Equation (1)) for the 'U+U? two-stage system as representative example (all two-stage systems perform similarly here).
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 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 R dominates when there are few nominators, but gives way to the ranker regret R 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 = (because all the components are identical at initialization, and then updated with the same data). Since the size of the candidate set C, 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 random nominators with non-overlapping item pools nominates at least one optimal arm is on average 1 ( 0.65, i... the instantaneous nominator regret would be zero 65% of the time.
of ten uniformly
To summarize, we have seen evidence that propertics known to affect single-stage performance- number of arms, feature dimensionality, misspecification have similar qualitative effects two- stage 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 ranker pretraining [44], these observations add the case that two-stage systems should not be treated just the sum of their parts. We add theoretical support to this argument in the next section.
3.2 Theoretical observations
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 0 the entries of 0* corresponding to the dimensions available to n. The L error is thus a concave
function of d/ by symmetry: / EEEE (0% In, )² [ EEl 1 |0: [ VI //-s/d.
5

---

regularizer
|| over a given model class FF
f-1 || + -mn- ax);
St E argmii
These estimates are then converted into policy either greedily, ny (x) Unif(argmax, (a, a)), or by incorporating an exploration bonus 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 single-stage regret guarantee Rr B. for some constant By The (either in expectation with high probability), even if the contexts {xx (a)) are chosen by an adaptive adversary. The ranker regret then satisfies
R
Σ
Tea Pt S B
the sense of the original bound (i.e., in expectation, or with high probability).
While proving Proposition is straightforward, its consequences are not. First, if BA is in some sense optimal, then Equation (I) implies the two-stage regret R3 will be dominated by the nominator regret Ry (unless it satisfies a similar guarantee). Second, R < B holds exactly when the ranker trained in the 'single-stage mode', i.c., the tuples (Ie, ae. rt) are fed to the algorithm without any adjustment for the fact C, 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 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 Rý, and the secondary effect of inftuencing the candidate pools C, (which creates a feedback loop). The rest of this section focuses on the primary effect, and in particular its dependence how the nominators are trained and the item pools (An), allocated.
Pitfalls in designing the nominator training objective
The primary effect above stems from key property of two-stage systems: unlike the ranker, nomina- tors 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 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 1hth nominator
Sn,t E argmin S.EF 11 + Σ Wn,o(r: - (anns "a)n),,;;)))" 0:))2
(4)
where F, is the class of functions the nominator can fit, |1. the regularizer, and Wa.t Wn.ae 2 0 the weight. "Training-on-lll--un all data points are valued equally regardless of whether particular a, belongs to the nominator's pool A,, 'Training-on-all may potentially waste the already limited modelling capacity of the nominators if the pools An not identical. The "training-on-owe
in Section 3.k- Wn.a = for all (n, a), which means
alternative therefore uses Wn.a = 1aa E ),, so that only the data points for which a, E A,, influence the objective.*
While 'training- an-all' and 'training-on-onn on-own' are not the only options we could consider, they are representative of two very common strategies. In particular, 'training-on -n-all is the default easy-to- implement option which sometimes performs surprisingly well [11, 81]. In contrast, srining--o-own
'There are two possible definitions of 'training-on own': (i) W..,. = L(a E A..): (ii) Wn., = 1(er = a...). 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, o, E A., only a, an,t when the pools are non-overlappingg.
Proposition below shows that neither "training-on-al" nor "training-on-all guaranteed to perform better than random guessing in the infinite data limit (7 oc). We consider the linear setting (* a) = {
Tru) for all (or, a), l fixed, with nominators using ridge regression oracles fna(ITn,t ( as defined in Equation (2), À 0 fixed, and In,ta again subset of the full feature vector Zta. We also assume the nominators take the predicted best action with con-vanishing probability (Assumption 1), which holds for all the cited LSO based algorithms.
Let faz be as in Equation (4), and denote A = argmaa,EA, fn,e(Tn,esa) a). We assume there is universal constant 5 > O such that for all n E [N] and E An with lim sup T Eisist P(a; = a) > we have lim sup T Eigigr Pa An, l = a) 2 6.
Assumption
In both the supervised and the bandit learning setup, there exist two distinct context distributions with pool allocations { and Ta E [0, 1] almost surely (a.s.) for all A, such that 'raining-on-own' (resp. 'rraiing-oon-ll") leads to asympiotically linear two-stage regret
Proposition 2
R
lim sup
>0
T
T-+00
Moreover, the asymptotic regret of training-on-da is sublinear under the context distribution and pool allocation where 'training-on-one suffers linear regret, and vice versa.
E[zn,ero] =: 0% (a.s.) by Lemma I (Ap- pendix A), assuming invertibility and that a₁ is i.i.d;; note t%, = argming I[( (0,, In.))) We allow any zero mean reward noise which satisfies ra E [0, 1] (a.s.) all a E
Proof Throughout, we use 6n,t (B(
(I) Supervised setup. Take two nominators, A = =fa()) }. A = fa(2), a(a) ). a single context
Ta(t)
[ 11
X =
Ta(2)
= 0 0
Ta(s)
1
and restrict the nominators to the last two columns of X. As |Aal 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 co limit for the second nominator's ss 02,1 is
0 argmin A)l - -B,
argmingext (F1 32)² (F2 --)- (Fz B2) [22, " "T=
where F is the mean reward vector for the single context (0- is then X-) If we take, e.g., [4 2: _]" then a(3) + argmax (02, x2.a) = Q(2)- On the other hand, 'training-on on-own' would yield 82 [F2. F3] and thus correctly identify ((3) via argmax,EA. (02,22,0)
In contrast, consider the modified setup A1 {a())) A2 (a(2), ((3), ((4))
Ta())
1
0
0
-
Fa(2)
0
1
0
1
X
(6)
Ta(s)
0
0
1
0
Ta(a)
0
0
1
Restricting nominators to the last two columns of X, "training-on-own' would yield 03
= [r Fa f2
under full feedback access, whereas 'training-on on-all' would converge to 0 [Fa,
Fa F
3
Hence with, e.g., f= 1, Z1T, 'training on-own' would make the second nominator pick a via argmax, but 'Iruining-on--ll" would successfully identify the optimal 0(2)-
(II) Bandit setup. Take X from Equation (6), but use F = -[3 X-1f. For each j E [4), let XG) be deterministic context matrix which is the same X except all but the jth row are replaced by zeros. Observe that for each j, the mean reward vector k0 has exactly strictly positive component, and thus ot a(j) when X(3) is drawn.
1]T and the associated 6*
7

---

Let (n))((X(0)t))) be the context distribution. A1 {a()), A2 = {a(2). 4(3), ((4)), and restrict nominators to the last two columns of each sampled X()) We employ a proof by contradiction. Assume lim sup T ][ + O. Then 02.t + 05 in probability by Lemma (Appendix A), with 02 as stated right after Equation (6) for both the update rules. Since ,2 = To > 0 under 'training-on caaiiing-o-owwt resp. 02. = 5 < O under conining-on-alee argmax aE,A (0) x2,aa would fail to select of when
24
X(2). resp. X (4). is sampled (see Equation (6)) This would translate into an expected instantaneous
regret of at least A min; F; t > 0. Hence by Equation (1) and P(a = =a) = -|AI-1
A
E E 2 E
P(az2 # a a2, E A2 oj = a) P(a2, A2, aj = =a). (7)
A
A2
For 'raining-on-own'' oon-ow'', P(az. F a(2) 02,t E AA a = a(2)) P( (-1) <) () - by the above established 02, + 02 in probability, and the continuous mapping theorem. Analogously for "raining-on-all'. Hence lir sup E 2 |A|-118 > 0 by Assumption 1, contradiction, meaning both modes of training fail, but for different item (a(3) is picked out correctly by both again by the convergence in probability). To make lim sup T E[R + 0 for exactly one of the two setups, add a third nominator with A₁ = { resp. As = {a(4)) J. so that P(a; E C,) + 1.
Proposition 2 shows that the nominator training objective can be all the difference between poor and nor 'training-on-a guaran-
optimal two-stage recommender:" Moreover, neither 'training-on-oww tees 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.
4 Learning pool allocations with Mixture-of-Experls
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. Propo- sition 2 thus hints at positive result: good pool allocation help achieve (asymptotically) optimal performance even in cases where this is not possible using any one of the nominators alone.
Crafting 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-of- Experts (MoE) [47, 49, 50, 99] based approach instead. A MoF. 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 good local optimum [68] is easy to scale to large datasets using a stochastic approximation of gradients
1 log Pu.t exp T
(r: fn,e)" )
B
N log
Pa, exp{ (r. fn,t)²
(8)
20
20²
$ 'Covington 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 theoretical complement which shows that the range of important choices goes beyond the selection of the objective.
8

---

10 nominators
20 nominators
500
730
750
03
pre-65
14
000
0.38
0.15
recallo5
82
0.30
0.5
010
113
5 25 30 100
160
75
55
1140
25
50 10
5
(a)
Mol
random d,
10 4,
50
(b)
MMol
random
0,
10 10
Figure 5: Mixture-of-Expere results on the 100-item Amazon dataset. The x-axis is the size of the BERT embedding dimension subset. The y-axis shows the average precision (top row) and recall05 (bottom row) over 50,000 entries from an independent test set (both set to zero for entries with no positive labels-abol 5.5% of the test set). The columns in both plots (a) and (b) correspond to the number of examples per arm in the training set. Ten (resp. twenty) nominators were used in (a) (resp. (b)). The legend shows whether pool allocations were learned (MoE) or randomly assigned (random), and the dimension of item embeddings de employed by both model types.
with P.. 2 E,,,, Pn,t = 1) the gating weight assigned to expert n on example f, f... the matching expert prediction, > 0 hyperparameter approximating reward variance, and B E N the batch size.
MoE provides compelling alternative to a policy gradient style approach applied to the joint two- stage policy (a 1)) = Eas..... _ai....ar (a ær, C') II T. (a, x)) as done in [67]. In particular, a significant advantage of the MoE approach that the sum over the exponentially many candidate sets C {ai,.... .aN) } is replaced by 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 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 divided, nominators and the ranker may be finetuned and deployed using any existing infrastructure.
2. Make the gating mechanism permanent, either (i) 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 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 nor 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-Ie 13K' dataset [10, 69] to investigate the setup with a logistic gating mechanism as part of the nominator stage. We employ the same preprocessing in Section 3.1. Due to the success of greedy methods in Section 3. 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 simple two-tower architecture, where de di-mennsioa dense embed- dings are learned for each item, the s-dimensional subset of the BERT embeddings mapped to Rd by another trained matrix, and the final prediction is computed as the dot product on RR.., To enable low latency computation of recommendations, the gating mechanism models the logits (logPn) Pnhn as 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 more diverse candidate set. Since the gating mechanism can learn to exactly recover any fixed pool allocation, the Moł 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, alternative training approaches based on pnnectaaion-maximizaa or tensor decomposition [50, 68, 99].
5 Other related work
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 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] 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 recent survey).
Discussion
We used combination of empirical and theoretical tools to investigate the differences between single- and 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 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 way of lowering latency, but can also be used to improve recommendation quality.
Due to the the lack of access, major limitation of our work is not evaluating on 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/recal! 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 aagorithm-algorithe interactions between independently trained and deployed learning algorithms more broadly.
10

---

Acknowledgments and Disclosure of Funding
The authors thank Matej Balog, Mateo on early versions of this manuscript. Jiri Hron is supported by an EPSRC and Nokia PhD fellowship.
and Richard Turner for their useful feedback
References
[1] Naoki Abe and Philip M Longg Associative reinforcement learning using linear probabilistic concepts. In ICML, 1999.
[2] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In ICML, 2014.
[3] Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling band of bandit algorithms. COLT, 2017.
[4] Aman Agarwal, Ivan Zaitsev, Xuanhui Wang, Cheng Li, Mare Najork, and Thorsten Joachims. Estimating position bias without intrusive interventions. In ACM WSDM, 2019.
[5] Nima Asadi and Jimmy Lin. Fast candidate generation for two-phase document ranking: Postings list intersection with bloom filters. In ACM CIKM. 2012.
[6] Peter Auer. Using confidence bounds for exploiatiion-eploraiio tradc-offs. JMLR, 2002.
[7] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SICOMP, 2002.
[8] Hamsa Bastami, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-fee frree algorithms for contextual bandits. Management Science, 2021.
[9] Joeran Beel and Stefan Langer. A comparison of offiine evaluations, online evaluations, and user studies the context of research paper recommender systems. TPDL, 2015.
[10] Kush Bhatia, Kunal Dahiya, Himanshu Jain, Purushottam Kar, Anshul Mittal, Yashoteja Prabhu, and Manik Varma. The extreme classification repository: Multi-label datasets and code, 2016.
[11] Alberto Bietti, Alckh Agarwal, and John Langford. A contextual bandit bake-off. arXiv preprint, 2018.
[12] Fedor Borisyuk, Krishnaram Kenthapadi, David Stein, and Bo Zhao. Casmos: A framework for learning candidate selection models over structured queries and documents. In ACM SIGKDD, 2016.
[13] James Bradbury, Roy Frostig, Peter Hawkins, Matthew Johnson, Chris Leary. Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne and Qiao Zhang. JAX: Composable transformations of Python+NumPy programs, 2018.
[14] Lco Breiman. Bagging predictors. Machine Learning, 1996.
[15] Leo Breiman. Arcing classifiers. Annals of Statistics, 1998.
[16] Erion Çano and Maurizio Morisio. Hybrid recommender systems: A systematic litcrature review. Intelligent Data Analyxis. 2017.
[17] Jingyuan Chen, Hanwang Zhang, Xiangnan He, Liqiang Nie, Wei Liu, and Tat-Seng Chua. Attentive collaborative filtering: Multimedia recommendation with item-and component- attention. ACM SIGIR, 2017.
[18] Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-K off off-policy correction for REINFORCE recommender system. In ACM WSDM, 2019.
[19] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In AISTATS, 2011.
[20] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for YouTube recommendations. In ACM RecSys, 2016.
[21] Koby Crammer and Claudio Gentile. Multiclass classification with bandit feedback using adaptive regularization. Machine Learning, 2013.
[22] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In COLT, 2008
[23] Sarah Dean, Sarah Rich, and Benjamin Recht. Recommendations and user agency; the reachability of collaboratively-fileee -iittere information. In ACM FAceT, 2020.
[24] Jacob Devlin, Ming-We Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding, In NAACL-HLT, 2019.
[25] Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is a good representation sufficient for sample efficient reinforcement learning? In ICLR, 2020.

---

[26] Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang, Efficient optimal learning for contextual bandits. In UAI, 2011.
[27] Miroslav Dudik, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In JCML, 2011.
[28] Chantat Eksombatchai, Pranav Jindal, Jerry Zitao Liu, Yuchen Liu, Rahul Sharma, Charles Sugnet, Mark Ulrich, and Jure Leskovec. Pixie: A system for recommending 3+ hillion items to 200+ million users in real-time. In ACM WWW, 2018.
[29] William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint, 2021.
[30] Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In ICML, 2020.
[31] Dylan Foster, Alekh Agarwal, Miroslav Dudik, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In ICML, 2018.
[32] Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. In NeurlPS, 2020.
[33] Jerome H Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics, 2001.
[34] Jerome Friedman. Stochastic gradient boosting. Computational Statistics and Data Analysis, 2002.
[35] Claudio Gentile and Francesco Orabona. On multilabel classification and ranking with bandit feedback. JMLR, 2014.
[36] Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits. In AAAI, 2017.
[37] Prem Gopalan, Jake M Hofman, and David M Blei. Scalable recommendation with hierarchical poisson factorization. In UAI, 2015.
[38] Maxwell Harper and Joseph Konstan. The Movielens datasets: History and context. ACM TüS. 2015.
[39] Charles R Harris, K Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, Robert Ker, Matti Picus, Stephan Hoyer, Marten Н van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río. Mark Wiebe, Pearu Peterson, Pierre (érrard-Marcham Kevin Sheppard, Tyler Reddy, Warren Weekesser, Hameer Abbasi, Christoph Gohlke, and Travis E Oliphant. Array programming with NumPy. Nature, 2020.
[40] Xiangnan He, Lizi Liao. Hanwang Zhang. Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In ACM WWW, 2017.
[41] Jonathan Herlocker, Joseph Konstan, Loren G Terveen, and John Riedl. Evaluating collaborative filtering recommender systems. TOIS, 2004.
[42] Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning, (lecture
6): Overview of mini-batch gradient descent, 2012.
[43] Tin Kam Ho. Random decision forests. In ICDAR, 1995.
[44] Jiri Hron, Karl Krauth, Michael Jordan, and Niki Kilbertus. Exploration in two-stage recommender systems. REVEAL (ACM RecSys workshop), 2020.
[45] John Hunter. Matplotlib: A 2D graphics environment. Computing Science & Engineering. 2007.
[46] Eugene Ie, Vihan Jain, Jing Wang. Sanmit Narvekar, Ritesh Agarwal, Rui Wu, Heng-Tze Cheng, Tushar Chandra, and Craig Boutilier. SlateQ: A tractable decomposition for reinforcement. learning with recommendation sets. In IJCAI, 2019.
[47] Robert A Jacobs, Michael Jordan, Steven J Nowlan, and Geoffrey E Hinton. Adaptive mixtures of local experts. Neural Computation, 1991.
[48] Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. Unbiased lcarning-to- to-rank with biased feedback. In ACM WSDM, 2017.
[49] Michael 1 Jordan and Robert A Jacobs. Hierarchies of adaptive experts. In NeurlPS, 1992.
[50] Michacl I Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the EM algorithm. In JEEE IJCNN, 1993.
[51] Marius Kaminskas and Derek Bridge. Diversity, serendipity, novelty, and coverage: survey and empirical analysis of beyond-accuracy objectives in recommender systems. ThS, 2016.
[52] Wang-Cheng Kang and Julian McAuley. Candidate generation with binary codes for large-scale top-N recommendation. In ACM CIKM, 2019.
12

---

[53] Sampath Kannan, Jamie И Morgenstem. Aaron Roth, Bo Waggoner. and Zhiwei Steven Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In NeurlPS, 2018.
[54]
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In /CLR, 2015.
[55] Thomas Kluyver, Benjamin Kagan-Kelley Femando Pérez, Brian Granger, Matthias Bussonnier, Jonathan Frederie, Kyle Kelley, Jessica Hamrick, Jason Grout, Sylvain Corlay, Paul Ivanov, Damián Avila, Safia Abdalla, Carol Willing, and Jupyter development team. Jupyter notebooks a publishing format for reproducible computational workflows. In Positioning and Power in Academic Publishing: Players. Agents and Agendas, 2016.
[56] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 2009.
[57] Karl Krauth, Sarah Dean, Alex Zhao, Wenshuo Guo, Mihaela Curmei, Benjamin Recht, and Michael I Jordan. Do offline metrics predict online performance in recommender systems? arXiv preprint, 2020.
[58] Sanath K Krishnamurthy, Vitor Hadad, and Susan Athey. Tractable contextual bandits beyond realizability. AISTATS, 2021.
[59] John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side informa- tion. In NeurlPS, 2008.
[60] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[61] Tor Lattimore, Csaba Szepesvári, and Gellert Weisz. Learning with good feature representations in bandits and RL with a generative model. ICML, 2020.
[62] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems, arXiv preprint, 2020.
[63] Chao Li, Zhiyuan Liu, Mengmeng Wu, Yuchi Xu, Huan Zhao, Pipei Huang, Guoliang Kang, Qiwei Chen, Wei Li. and Dik Lun Lee. Multi-interest network with dynamic routing for recommendation Tmall. In ACM CIKM, 2019.
[64] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- bandut approach to personalized news article recommendation. In ACM wwW, 2010.
[65] Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. UC Santa Cruz, Computer Research Laboratory, 1989.
[66] Romain Lopez, Inderjit Dhillon, and Michael Jordan. Learning from extreme bandit feedback. In AAAI, 2021.
[67] Jiaqi Ma, Zhe Zhao, Xinyang Yi. Ji Yang, Minmin Chen, Jiaxi Tang, Lichan Hong, and Ed II Chi. Off-policy learning two-stage recommender systems. In ACM wWW. 2020.
[68] Ashok Makkuva, Pramod Viswanath, Sreeram Kannan, and Sewoong Oh. Breaking the gridlock in Mixture-of Experts: Consistent and efficient algorithms. In ICML, 2019.
[69] Julian McAuley and Jure Leskovec. Hidden factors and hidden topics: Understanding rating dimensions with review text. In ACM RecSys, 2013.
[70] Silvia Milano, Mariarosaria Taddeo, and Luciano Floridi. Recommender systems and their ethical challenges. Al & Society, 2020.
[71] Smitha Milli, Luca Belli, and Moritz Hardt. From optimizing engagement measuring value. In ACM FAccT, 2021.
[72] Andriy Mnih and Ruslan Salakhutdinov. Probabilistic matrix factorization. NeurIPS, 2007.
[73] Remi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforeement lcarning. In NewrIPS, 2016.
[74] The pandas development team. pandas-de devepadde Pandas, 2020.
[75] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen. Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejami, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In NeurlPS, 2019.
[76] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jak Vanderplas, Alexandre Passos, David Coumapeau, Matthieu Brucher, Matthicu Perrot, and Édouard Duchesnay. Seikit-leam: Machine learning Python. JMLR, 2011.
[77] Carl Edward Rasmussen and Zoubin Ghahramani. Infinite mixtures of Gaussian process experts. In NewrIPS, 2001.
13

---

[78] Steffen Rendle. Factorization machines. In JEEE ICDM. 2010.
[79]
Steffen Rendle, Li Zhang, and Ychuda Koren. On the difficulty of evaluating baselines: A study on recommender systems. arXiv preprint, 2019.
[80] Marco Rossetti, Fahio Stella, and Markus 7anker. Contrasting offline and online results when evaluating recommendation algorithms. In ACM RecSys, 2016.
[81] Mark Rowland, Will Dabney, and Remi Munos. Adaptive tradc-off's in off off-policy learning. In AISTATS, 2020.
[82] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 2010.
[83] Badrul M Sarwar, George Karypis, Joseph Konstan, and John Riedl. Recommender systems for large-scale e-commeree: Scalable neighborhood formation using clustering. In JEEE ICCIT, 2002.
[84] Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. Recom- mendations as treatments: Debiasing learning and evaluation. In ICML, 2016.
[85] Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gate gated Mixture-of- -f-eefftss layer. In ICLR, 2017.
[86] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizabiliity. SSRN, 2020.
[87] Adish Singla, Hamed Hassani, and Andreas Krause. Learning to interact with learning agents. In AAAI, 2018.
[88] Alexander L Strehl, John Langford, Lihong Li, and Sham M Kakade. Learning from logged implicit exploration data. In NeurlPS, 2010.
[89] Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. JMLR, 2015.
[90] Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miroslav Dudík, John Langford. Damien Jose, and Imed Zitouni. Off-policy evaluation for slate recommendation. In NeurlPS, 2017.
[91] Gábor Takács, István Pilászy, Bottyán Németh, and Domonkos Tikk. Scalable collaborative filtering approaches for large recommender systems. JML.R, 2009.
[92] Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In ICML, 2016.
[93] Guido van Rossum and Fred L Drake. Python 3 Reference Manual. CreateSpace, 2009.
[94] Pauli Virtanen, Ralf Gommers, Travis Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson. Warren Weckesser, Jonathan Bright. Stéfan van der Walt, Matthew Brett, Joshua Wilson. K Jarrod Millman, Nikolay Mayorov, Andrew R Nelson, Eric Jones. Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E A Quintero, Charles R Harris, Anne M Archibald, Antônio Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 2020.
[95] Michael I. Waskom. seaborn: statistical data visualization. Journal of Open Source Software, 2021.
[96]
Wes McKinney. Data structures for statistical computing in Python. In Python in Science, 2010.
[97] Thomas Wolf, Lysandre Dehut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the natural language processing, In EMNLP. 2020.
[98] Xinyang Yi, Ji Yang, Lichan Hong. Derek Zhiyuan Cheng, Lukasz Heldt, Aditce Kumthekar, Zhe Zhao, Wei, and Ed Chi. Sampling- biaiing--bis--orrctted neural modeling for large corpus item recommendations. In ACM RecSys, 2019.
[99] Seniha Esen Yuksel, Joseph N. Wilson, and Paul D. Gader. Twenty years of mixture of experts. IEEE Transactions on Neural Networks and Learning Systems, 2012.
[100] Longkai Zhang, Houfeng Wang, and Xu Sun. Coarse-grained candidate generation and fine- fme-grained re-ranking for Chinese abbreviation prediction. In EMNLP, 2014.
[101] Zhe Zhao, Lichan Hong, Li Wei, Jilin Chen, Aniruddh Nath, Shawn Andrews, Aditee Kumthekar, Maheswaran Sathiamoorthy, Xinyang Yi, and Ed Chi. Recommending what video to watch next: a multitask ranking system. In ACM RecSys, 2019.
[102] Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li. Jie He, Han Li, and Kun Gai. Learning bree-based deep model for recommender systems. In ACM SIGKDD, 2018
14


Reviews:
[{"review_id": "yIRfYAwuK6t", "reviewer": "Reviewer_GChu", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. This paper studies on the properties of the two-stage recommendation architecture. It is an interesting and under-explored topic.\n2. Both empirical and theoretical analyses are conducted to validate the importance of pool allocation on recommendation performance.\n3. The authors further propose to learn pool allocation with MOE strategy, which yields empirical improvement over the random pool allocation.\n\nWeaknesses:\n\n1. The analyses are based on some strong assumptions, which may not be consistent with the setting of real-world two-stage recommendation system.\n\nFor example, in real-world RS, we usually use complex model (e.g. MF, FM, DeepFM) instead of simple linear model; Also, each nominator may return a list of items rather than single item; What’s more serious, the assigned pool of nominators in real-world RS usually covers all items (ie. A_n=A). I do not understand why we need pool allocation in this scenario. \n\n2. The proof of Proposition 2 is not complete. \nThe proof is on the specific case with two nominators and three items, which lacks generalization.\n\n3. Some important concepts lack clear interpretation, making the paper hard to follow. \nFor example, what does “context distribution” mean? Does it mean \\pi(x), or mean the distribution of x over the items in the pool? Also, in figure 2, what does “ G” or “U” mean? Does it mean one-stage recommender?\n\n4. Insufficient motivation of using MOE.\n\nWe do agree that learning pool allocation is promising. But whether MOE can learn a proper allocation is questionable. More concretely, we do not understand why the weights returned by the MOE is a useful signal for pool allocation. The authors should give more deep analyses on MOE and explain why MOE is so special for pool allocation.\n \n\nIn summary, although this paper studies an interesting and important problem, it has some serious limitations in terms of presentation and theoretical soundness. As such, I think this paper is potential but this version is not touch the bar of NIPS.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4hours"}, "extra_text": {}}, {"review_id": "cDw_zAHTqs8", "reviewer": "Reviewer_hgnQ", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I totally agree with the authors that there's a lack of research devoted to two-stage recommenders. Indeed, there are many reports from different companies on the use-cases where such systems provide more advantages over standalone monolithic solutions. This observation is also supported by various recsys challenges where two-stage solutions are also demonstrated to provide highly competitive results. Hence, attempts to better understand their internals and working mechanics are more than welcomed. The work provides good theoretical grounds for the considered cases within the specified constraints and nicely connects it to experimental part.\n\nIt should be noted though, the focus is made specifically on bandits-based solutions, which is not the only possible setup. It would be great to see (at least at high level) some connections to other approaches, e.g. when ranker is based on Decision Trees and nominator is based on matrix factorization, which is a very popular setup. Surely, this may lead to many difficulties with analysis and may not even give a way for proper theoretical investigation, but it would be helpful to at least specify the limitations. Nevertheless, the lack of such analysis doesn't decrease the value of the provided results.\n\nRelated to the previous comment, an abstract creates an impression of a general solution, while only the case of bandits is considered. I'd suggest to modify the abstract and the introductory part of the text to more clearly position the work and define its boundaries.\n\nI also have a few concerns regarding the experimental part and the assumptions made there. In Section 3.1, the synthetic dataset is generated under the assumption that context follows normal distribution. However, in almost all practical cases, items in recommender systems follow power law or zipf-like distributions, which, I believe, would contradict to the described assumption. It's not clear how this would affect further derivations and provided intuitions. Describing how different assumptions on the nature of contexts may affect the theoretical and/or experimental results of this work would help to better understand its practicality.\n\nThe data preprocessing part also seems to deviate form real scenarios. E.g., in Section 4 (lines 273-275): why sampling based on label frequency is performed? How does it affect distribution of data? How it relates to the assumptions on data used in theoretical part?  What is the connection to real world datasets? Please, add more details on the reasons for the described preprocessing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly mention connections of recommender systems to some of the issues like biases, fairness, etc. and do not explore it further. However, even for single-stage recommenders this is a very challenging topic. Given that the problem of two-stage recommender systems is underexplored, I believe that putting too much focus on societal and ethical concerns in the presented work wouldn't be helpful. The demonstrated awareness of the problem is enough in this case.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Hcs0lVTkZJK", "reviewer": "Reviewer_Q3hM", "summary": "In this paper, the authors are trying to optimize two stage recommendation systems (first stage to generate candidates and second stage to rank the candidates for a given context).", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of being able to do combined optimization on the rankers and candidate generators together is extremely useful. The authors proposed solution to use MOE model to create multiple candidate/item pool (nominators) specialized on different sub-tasks and final ranker to select the best candidate can find a lot of applications. \n\nThe authors have given extensive explanation with solid theoretical proof for their proposed solution. They have presented a thorough study of different components in their system and how it effects the final stage performance of the ranker.\n\nThe evaluations presented in the paper support the author’s claims and observations. However, the paper is not extremely easy to read especially the experimental setup could have been better explained, and I have listed down some opportunities the authors could have presented better.\n\nOpportunities:\n1.\tThere is no evaluation against any Learning to rank models, extremely popular with the two stage recommendation systems. Their main performance comparison is against single stage performance, but the setup for that evaluation/theoretical justification remains the same (EE based system).\n2.\tThe related work section can be better explored.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have identified no limitations or  potential negative impact.\n\nPotential Limitation :\nOne of the main reasons for popularity of 2 stage recommendations is the scalability & flexibility they provide for large scale recommender systems (independence of creating a candidate set and a separate ranker). Increasing the number of nominators & MOE model adds more complexity and increases computational cost for the proposed 2-stage recommender system by the authors.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "C6w-ZXzG9g", "reviewer": "Reviewer_jFPh", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n\n1.This work targets at looking for two-stage specific properties, an interesting topic for the audience in the area of online large scale information system.\n\n2.Empirical and theoretical observations well motivate its research problem.\n\n3.Literature review is well embedded in the body of this submission.\n\nWeak:\n\n1.Since this work focus on recommender system. My main concern is what are the differences between RS and others. The mentioned ranker and nominator are also existed in some information systems like Q&A, Web search, sentence matching, and so on.\n\n2.Without clearly addressing those differences, readers may feel that the current version can be applied mechanically to other IS.\n\n3.Back to RS, there are various benchmark datasets. The reason of selecting “AmazonCat-13K” is not known. Experiments are conducted on review texts, so if only using rating scores, does it have different effects on the current findings?\n\n4.The way to define two-stage RS is based on the bandit based approach. The reason and its advantages should be further addressed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two-stage recommenders are critically important in production recommender systems, yet as the authors and reviewers point out, there has been very little theoretical analysis of this problem.  While the reviewers do reasonably question whether bandit-based analysis is really the right theoretical framework, the author response rightfully points out that their analysis captures generic characteristics of some deployed two-stage recommenders.  Post-rebuttal, the majority of reviewers agreed with a decision to accept and believe this work can inspire follow-on research in this potentially high impact area.  The authors are strongly encouraged to address review concerns (e.g., on power law and zipf-like distributions) and integrate their insightful rebuttal discussion into the paper (or Appendix), even when it may be self-critical of the present work.
Decision: Accept (Poster)