From Intervention to Domain Transportation: A Novel Perspective to Optimize Recommendation
Authors: Da Xu
Yuting Ye
Chuanwei Ruan
Evren Korpeoglu
Sushant Kumar
Kannan Achan
Venue: ICLR 2022 Poster (2022)
Keywords: Information retrieval
Learning theory
Causal inference
Missing data
Overlapping
Reweighting
Optimal transport

Abstract: The interventional nature of recommendation has attracted increasing attention in recent years. It particularly motivates researchers to formulate learning and evaluating recommendation as causal inference and data missing-not-at-random problems. However, few take seriously the consequence of violating the critical assumption of overlapping, which we prove can significantly threaten the validity and interpretation of the outcome. We find a critical piece missing in the current understanding of information retrieval (IR) systems: as interventions, recommendation not only affects the already observed data, but it also interferes with the target domain (distribution) of interest. We then rephrase optimizing recommendation as finding an intervention that best transports the patterns it learns from the observed domain to its intervention domain. Towards this end, we use domain transportation to characterize the learning-intervention mechanism of recommendation. We design a principled transportation-constraint risk minimization objective and convert it to a two-player minimax game.
We prove the consistency, generalization, and excessive risk bounds for the proposed objective, and elaborate how they compare to the current results. Finally, we carry out extensive real-data and semi-synthetic experiments to demonstrate the advantage of our approach, and launch online testing with a real-world IR system.

Published as a conference paper at ICLR 2022
FROM INTERVENTION TO DOMAIN TRANSPORTATION: A NOVEL PERSPECTIVE TO OPTIMIZE RECOMMENDA-
TION
Da Xu
Walmart Labs
Sunnyvale, CA 94086, USA DaXu518 8 gmail com
Yuting Ye
Division of Biostatistics University of California, Berkeley Berkeley, CA 94720, USA yeykeberkeley. edu
Chuanwei Ruan
Instacart
San Francisco, CA 94107, USA Ruanchuanwei gma com
ABSTRACT
The interventional nature of recommendation has attracted increasing attention in recent years. It particularly motivates researchers to formulate learning and evaluating recommendation as causal inference and data missing-not-at-randde problems. However, few take seriously the consequence of violating the critical assumption of overlapping, which we prove can significantly threaten the validity and interpretation of the outcome. We find critical piece missing in the current understanding of information retrieval (IR) systems: as interventions, recommen- dation not only affects the already observed data, but it also interferes with the target domain (distribution) of interest. We then rephrase optimizing recommen- dation finding an intervention that best transports the patterns it learns from the observed domain to its intervention domain. Towards this end, we use do- main transportation to characterize the Graming-interventtnn mechanism of rec- ommendation. We design principled transportation-ccnntraann risk minimization objective and convert it to two-player minimax game. We prove the consistency, generalization, and excessive risk bounds for the proposed objective, and elaborate how they compare to the current results. Finally, we carry out extensive real real-data and semi-synthetic experiments to demonstrate the advantage of our approach, and launch online testing with a real-world IR system.
INTRODUCTION
For information retrieval (IR) systems, the users' willingness to interact is often intervened by the content we show. Recommendations not only impact the potential response of the users, but also change the nature of the data collected for training machine learning models (Bottou et al.) 2013). The interventional nature of recommendation, as well as the fact that many questions IR are counterfactual, e.g., "what the response would have been if we recommended something else". makes it natural to rephrase recommendation in the context of causal inference or missing data problems (Rubin 2005| Little et al., 2002). Among the two disciplines, technical tools of impor- tance weighting (IW) and domain adaptation (DA) have been commonly applied. Recently, there has been widespread interest in adapting those tools for learning the best recommendation (Schn-

---

Published as a conference paper at ICLR 2022
abel et al. 2016 Bonner and Vasile, 2018), but we find a critical discussion missing from most existing literature in this direction. In many scientific disciplines, the effectiveness of IW and DA relies heavily overlapping between source and target domain (Austin and Stuart 2015 David et al., 2010). The underlying reason also happens to be the motivation of exploration-exploiaae
techniques including bandits and reinforcement learning (Auer al. 2002] (Sutton and Barto 1998): in the less-explored regions where few observations are collected, the confidence of selecting any hypothesis is discounted.
Unfortunately, modern IR systems are often cautious about exposing users to less relevant content for the sake immediate satisfaction and revenue, even with the help of bandits RL (Bonner and Vasile, 2018). In particular, many real-world recommenders are deterministic, e.g., an item is shown with probability either zero or one, which further limits the exploration and thus the coverage of collected data. In Section 3 we rigorously prove for both IW- and DA-based learning the hardness or impossibility results caused by insufficient overlap. Intuitively, when a less-explored instance is passed to candidate hypothesis, even if DA IW can improve the accuracy of the prediction, they inevitably increase the uncertainty of that prediction as a consequence of the bias-variance tradeoff. To certain point, the increased uncertainty from having too many instances in the weakly overlapped regions will fundamentally limit what any learning procedure can achieve. Further, if the instance lies in the non-overlapped region, we can barely exceed regular extrapolation Xu al. 2021b
Intervention
Exposure
Feedback
Learning pattern
By recommendation
Exposure
Feedback
User intent
Source
User intent
Target
domain
The pracess domain transportation
domain
Figure 1: A realistic working mechanism of IR systems that emphasize domain transportation.
We resolve the fundamental limitation of insufficient overlapping in IR with the key insight that the interventional impact of recommendation is not exclusive to observed data, but also interferes with the target domain of interest - the instances that will be affected by the recommendations about to make. For instance, the placement user directly influences the occurrence of clicks. Therefore, alternatively consider optimizing recommendation as searching for an intervention that best transports the patterns it learns from the source domain its intervention domain. The procedure is best described by transport instead of transfer because it will interfere with how the learnt patterns are carried to the target domain. This change of view describes a complex but realistic working mechanism that involves learning, inter- vention, and transportation, as depicted in Figure [ On the one hand, we wish to learn patterns that can be transported to the target domain of interest. On the other hand, the patterns we identify lead to the intervention (in the form of recommendation) that generates the target domain. Following this working mechanism, we impose constraints on the domain transportation between the (reweighted) source domain and the future intervention domain. We point out that reweighting is essential for learning from interventional feedback data (Rosenbaum and Rubin 1983). especially for the work- ing mechanism we identify here because the relationship between the source and target domain is more involved. Towards this end, we propose a novel solution via transportation-come constrrinn risk minimization. We rigorously investigate for our objective:
recommendation on the webpage proposed to the
the consistency, generalization, and excessive risk bounds that provide theoretical insights and guarantees;
the equivalence to a two-player minimax game that can be efficiently solved by gradient descent-
ascent algorithm;
convergence to the standard IW-based solution for the ideal oully-overlapped bandit feedback;
We demonstrate the empirical performance our method via comprehensive experiments via sim- ulation, real-data analysis, well as online experimentation and testing in real-world IR system.
'The presumption for this argument is that the underlying causal mechanism is unknown, which applies to the settings we discuss in the paper.
2

---

Published as a conference paper at ICLR 2022
2 RELATED WORK
Bottou et al. (2013) first reveals the importance of characterizing the working mechanism of IR systems. However, they study specifically the advertising systems where the underlying causal structures are assumed given. Our work significantly extends their discussion by moving beyond causal mechanisms. Issues caused by ignoring the interventional nature of recommendation have been pointed out for numerous scenarios (Chen et al. (220). |Steck (2110) and Liang et al. (2016) address optimizing recommendation in the context of missing data and causal inference, and the majority of recent follow-up work investigate particularly inverse propensity weighting (IPW) and learning domain invariant representation methods (Chen et al. 2020 Saito 2020 Yang et al. 2018 Joachims et al. 2017 Bonner and Vasile 2018 Agarwal al. 2019 Xu al. 2020). As mentioned in Section I they largely ignore the overlapping issue even when the recommendation is determin- istic. Our theoretical results on the interplay between overlapping and learning performance are novel and add to the current venue of revealing the tradeoff for IW- and DA-based learning (Byrd and Lipton 2019; Johansson et al., 2019; (Ben-David and Umer 2012). See Appendix for further discussions on related work.
Existing solutions for insufficient overlapping focus primarily on reducing or calibrating the vari- ance, c.g., discussed in SSamiinthhan and Joachims (2015b); Wang et al. (2020); JJohansonn et al.. (2020). They do not account for the unique working mechanism of IR where the domain discrepancy can be actively controlled. We devise the domain traninntttasootttiion constraint using the Wasserstein dis- tance originated from the optimal transport theory (Courty et al. 2016 Redko et al. 2017). The idea of converting Wasserstein -ensssrrteinncossraanttt objective to two-player minimax game is similar to that of the generative adversarial network (Gulrajani et al., 2017). however, we do not make any generative assumption the observed data. Finally, learning from bandit feedback and the associated coun- terfactual risk minimization can be viewed as a special case of our framework (Swaminathan and Joachims 2015a We will use test bed to examine the guarantees of the proposed approach.
3 PRELIMINARIES
We use upper-case letters to denote random variables and measures, bold-font letters for vectors and matrices. We denote by ||- I12. Iloo I1 the Eg. fo norm and the Lipschitz constant of function.
For clarity, we borrow the item recommendation setting to illustrate the IR system we discuss next. The set of all users and items are given by 24 and I. To be concise, we denote the features (or pre-trained embeddings) for users and items by x., for E U and x; for i E I. We study primarily the practical implicit- feedbackk setting with Yui E {0, 1). e.g., users express preferences implicitly via clicks. Let D be the population of all possible (X,, or (u, i) depending on the context. The embeddings can also be free parameters under the representation mapping / from X' or UUI to Rdd We let P be any base probability measure supported on the subsets of D, and let Ps, be the empirical versions according to the collected feedback of D,, where n is the sample size. We assume the weight of a user-item is positive and bounded by a constant M. Equipped with either individual weights wai E [0, M) or weighting function w : 2 x I (or X' x X)) + [0, M). the reweighted measures are given by such as: (u, i) x w(u, i)- i(u,
The candidate recommendation algorithm f E F outputs a score or probability for each user-item pair. Top-k recommender often ranks the output and then renders the top-k items the user. We denote this procedure by the function: reco(u, J) E {0, 13. Define the new measure on D induced by deploying f on DD as: P, i) x reco(u, f) ) P(u, i). If we choose the base measure P as uniform, it is clear that Py is a uniform measure
the (u,i) pairs that will be exposed: {(u,i) i) E D reco(u, f) = 1}. Finally, given a loss function for f. we define the corresponding risk under P: R(f) = E(us)=l(ff (u, i), yus). the weighted risk under Pw: R(f) = (( i), yu:) ww. i).
Our setting covers wide range of recommendation problems from classical collaborative filtering to sequential recommendation (when user embedding is a function of the item sequence). including those using bandits for exploration where fu, i) becomes the exploration probability, and the base measure is given by the inverse propensities. We defer the detail of that setting to Appendix
Consequence of Insufficient Overlapping.
3

---

Published as a conference paper at ICLR 2022
We now rigorously justify our previous intuition that insufficient overlapping causes uncertainty that fundamentally limits what IW- and DA-based learning can achieve. While the results we show for IW are universal, i.e., it applies to any hypothesis class, discuss particularly for DA the skip- gram negative sampling (SGNS) algorithm (Mikolov et al. 2013). The reason is that SGNS is a widespread technique for learning user or item embedding in IR systems (Xu al., 2021a), and its more straightforward formulation will allow us to present concise theoretical results to the readers.
As a gentle introduction, IW-based learning uses the ratio i(u, resent the source and target domain - to reweigh the loss of each instance in order to correct the distribution shift. On the other hand, DA-based learning assumes there exists some hypothesis that makes the optimal joint risk of se [B R(f) + EpR(f)) small. For IW, we show the hardness of learning, i.e., the best target risk inf l2 R(f) can be uncontrolled for any F due to insufficient overlapping. For DA, we show the impossibility of learning. i.e., there does not exist a solution of SGNS that can make the optimal joint risk small when P and Q are not aligned.
where P and Q rep-
Proposition 1. Let P and Q be the training and target distribution supported on Sr,Sq C DD and w(u, i) = Q(u.)) for (u, i) E Sp n Sq. Dn consists of training instances sampled i.i.d from P. P(u.))
Hardness of learning with IW: Sp SQ. any f E F, with probability at least 1 - 8, it holds:
M M(log 1/2 + log log (
Md (log 1/4 log Noo (
EQ &
+
n
n
-1/mn 1)/m) > O under mild condition, where M == and P (EQ EP R(f) 2 (PP(() -
max maxx(w(u, (H, == F, is the 2,- -cooering number for F in || 1loo based on 2n i.dd samples from P. and (P(I)) = Iss (dP)dQ)dP is divergence measure. Further, if for any prior and posterior distributions and T on F, for risks associated with the 0-1
Sp F for
loss, it holds with probability at least 1 1-66 5:
E (iv..R(f) S ESSTT, R(f) + (T|[T + log (P(() + (5,.
n
where dxi is the Kullback-Leible divergence, di (PIIQ) is the same as above but defined only on the overlapped part, and (T) consists of disagreement terms detailed in Appendix A.2
Impossibility of learning for DA with SGNS: let R(f) be the associated risk for the SGNS algo- rithm, and (P), Cu.((Q (Q) be the co-occurrence statistics under P. Q, as mentioned in Xu et al. (2021a). Even if Sp -Sq, it holds that:
inf Ep(f) + EQR(f)I [Sp] f
1
dKL (C.(CC.(P))ICC..O0)) tc, (u,))ESr
Σ
where e takes some positive value and equals to inf EpR(f) + inf EqR(f) when P= Q a.s.
We defer all the proofs to Appendix A.2 For IW, we reveal the generalization bounds for both the frequentist setting (the first set of bounds) and the PAC-Bayesian setting (the second bound). While they emphasize conceptually on different learning guarantees (Germain et al., 2009), and while the latter can handle the existence of non-overlap (Sp * SQ), we find them both showing insufficient overlapping (characterized by the discrepancy terms di and dKL.) can cause arbitrarily large gaps leading to poor generalizations to the target domain. For DA with SGNS, our lower bound reveals the impact of insufficient overlapping indirectly via a notion of co-occurrence statistics defined in Xu et al. 12) In particular, if the source and target domains are well-aligned in terms of the co-occurrence statistics, the increased divergence term can make it impossible to find a hypothesis that simultaneously performs well in both domains. Although this result holds only for SGNS, nevertheless suggests the limitations of DA caused by insufficient overlapping in IR.
4 MODEL AND THEORY
As much as we would like to continue investigating the consequence of insufficient overlapping, for the purpose of this paper, we have shown the drawbacks of directly applying such as IW and
4

---

Published as a conference paper at ICLR 2022
DA to optimizing recommendation without accounting for the working mechanism of IR systems. In what follows, we describe a principled solution motivated by our domain transportation view, which requires actively identifying the suitable training domain via reweighting. Notably, we longer perceive reweighting as a change-of- meeasur tool commonly implied in the causal inference mechanism to help identify particular
and missing data solutions. Instead, we use reweighing training domain to ensure certain transportation properties (which we explain next) to the deploy- ment domain which may concern only subpopulation of all the potential user-item instances.
4.1 TRANSPORTATION CON.OONNNNSSTTIINNN CONNOODRAATIONNCCONOTNNIIEE RISK MINIMIZATION
Throughout our discussion, we emphasize the transportability of patterns across domains, which can be difficult to define precisely. However, if we make a a mild assumption that all patterns can be recovered by Lipschitz-bound functions, it immediately becomes clear that the Wasserstein distance can characterize our notion of transportability. To show this point, we first describe an imbalanced binary classification problem with two domains P and Q. Let (u( = Pi and f-1(u) = 1-p1
be the positive and negative loss under prediction score u, where p1 is the prior probability that sample comes from P. Interestingly, the I.- T-Wasserstein distance between P and Q admit
inf P1 ((())dP+ (1 ph) l (-100))0. dw (P,Q) = 9: I.
(1)
which exactly the optimal risk of the binary classification problem described in the first place! Therefore, Wasserstein distance can be perceived as how well the classification patterns on P trans- ports to Q by any means necessary, as long as they are hipschitzz-ounnder Since the constant of L is simply a scaling factor, we simply continue with the 1- 1-Wasserstein distance. Using dw to device the domain transportation contraint between Py and the particular training domain P.. we seek to construct with our weighting mechanism, the learning objective is directly given by:
minimize Ep,, R(f) s.t. D(w, f) P: JEF,EER
(2)
where D(w, f) is shorthand for dw (Pa, and p can be treated as a hyper-parameter. As san- ity check, when p = the feasible set is given by: f(u, i) = w(u, i) for all (u, so we are directly optimizing the associated risk of the deployment domain. However, this is a suboptimal practice for deterministic recommenders because in that case, only small proportion of the feedback data will be considered and the result can be heavily biased toward the historical recommendation. Therefore, a suitable P will give us the opportunity to better explore the whole feedback data. Nevertheless, o becomes too large, we are likely to overfit the feedback data due to the high capacity of ʃ and w combined while the transportation constraint is too loose.
The proposed objective is tailored specifically to the working mechanism of IR systems, and it is natural to question the validity and effectivvness. In what follows, we rigorously prove a series of guarantees associated with our novel learning objective, and discuss how it connect and compare to the existing results.
To begin with, show that jointly optimizing leads to the sample-consisteng guarantee. For clarity, we start with the feature-based learning where fu, i) = s(xa, x;), and defer the extension with the representation mapping to the next section. Let 2 = D x (0, 1), and we denote by l 2 > R the composition with the loss function such that for Zesi = (Xux X,, Vus). we have (y(u, i) = (f i), Mus). We use wui as a shorthand for the individual weight.
Theorem 1. Denote by Du(w, f) = dw (Pn,w, Mha, Pa,y)- Suppose that E is L-Lipschitz w.r. || l|2.
Define So supp:llail SS E(u,)ED, g(u, and MG supitalla (M,3)D g(u,i). Assume Z Rd and w E H. Given any f E F and p > 0, it holds with probability at least 1 - 8 that:
min Er,,, R(n) S 9M 1.) (".
min BP... DSS
+ Ba, CC (..
n
SSuposs a candidate recommender f is deployed to D. According Section the domain of users and items who are affected by the recommendation is given by Py defined on {(u, i) D reco(u, i; f) = 1}. We refer to it as the deployment domain to differentiate from the notion of target domain which conventionally intervention-free.
In Appendix
A.3 we provide a more thorough introduction Wasserstein distance for interested readers.
5

---

Published as a conference paper at ICLR 2022
Here, i D. Bp, R(f), v0 arg arg Dr (w. (w Ep Ep, R(f),
Cn(w, $,
n= 18M max Rio (f)? Ra log 26 and Rio =
1 Er. wi (u
Also, Bn(H, is given by (((ontVidaet))
+
Mcn 1/2 1/2 VoVVlog log 28 + (,,
We relegate the proof of this theorem Appendix A..4 Crucially, other than showing that the sample-consistency result can still be achieved with the jointy-optimized weights, we point out that this bound is completely independent of distribution discrepancy terms that troubled IW and DA. Notice that the bound depends on the weights only through Re (f)² and Rg (f) presented by the Cn term. Given any f E F. our result shows that both and ú are the minimizers of a weighted risk term, i.e. P.,, R(J) x Ed Wnily(u, i), under some constraint involving p. Therefore, thanks
to the constraint of D(w, f) I and the joint optimization of w, (f) and R. (f) will have more controlled behaviors compared with the domain discrepancy terms Proposition]] T
We now investigate the learning- nuuming-theoretica theoretical guarantees of the proposed objective, particularly the generalization and excessive risk bounds. Suppose the underlying labeling function of yus with respect to (x,; x;) is deterministic. With little abuse of notation, we use ~ Pa. to denote sampling (Xu; X1, Mus) via (Xu, x;) ~ fa. and the deterministic labelling function.
Theorem 2. Suppose infzez (2) + \|z 2||2] S My for all Z and X 0,5 E F. Let (F) be the empirical Rademacher complexity: (F) E, ser | (a,iEE, ousf(u,i), and a takes {-1.1} with equal probability. We consider individual weights was E (0, for brevity.
Generalization Error: for any f E F, it holds with probability at least 1 - that:
min un: DSp
Ep R(J) S mmn { X20
Ap + E P..s
inf tT(2) + A112 - 2112] + MM 22E
log 1/
log(A+1) C
VlogNa (E, F)
n/2
Excessive risk: define f == arg
Bp... R() the empirical optimal and f
arg m pis Brg R(f) the theoretical optimal. With probability at least 1 - 8:
T T.+ M MMMnn /og 1/5
min Ep, R(f) on: DSp
Ep, (PF) DS
min
< (2)
n-/2
We defer both proofs to Appendix A.3 Theorem 2 establishes two critical learning guarantees for the proposed transportation-consttae
risk minimization. In particular, the generalization error veals how we resolve the previous drawback mentioned for using DA in IR system. Recall from Section Bl that the joint optimal risk might be uncontrolled for DA since it can depend on how dif- ferent the training and target domains are. In this regard, with D(w, f) < explicitly constrains the discrepancy between the training and deployment domain, we have the additional -Ap term in the generalization error bound where the second term on the RHS can be think of as the empirical "transported" risk. In other words, the constraint ensures that the deployment risk will not deviate far from the training risk, and thus creates the possibility of learning transportable recommenda- tion. Further, the excessive risk bound suggests that the transportation constraint does cost the convergence rate comparing with the standard empirical risk minimization guarantee (Mohri et al. 2018).
4.2 TOWARDS TRANSPORTATIONS AANNRLLARATIONRRRELLLAAAZZZZZ RISK MINIMIZATION
To render the proposed objective computationally feasible, we apply a strong duality argument to show that there exists a regularized counterpart for (2). where we defer the proof to Appendix
Claim 1. Suppose that E F is convex. It holds for any f E F FF that:
min Pw: dw (P..
R(f) = max { X
Ap + min
{
+ X -dw(Pu. P/)]
Pa

---

Published as a conference paper at ICLR 2022
The above duality result suggests we alternatively consider the regularized learning objective:
minimize Ep,, R(f) + A dw (P),
fEJ,EE
where the relaxation on m has been made. Here. À is the tuning parameter that regularizes the domain transportation between the reweighted training domain and the deployment domain. To give some insight for the transporaation-regulaiizz objective, we use learning from bandit feedback data as a test bed and examine how the optimal solution of (3) compares to the solution of the standard counterfactual risk minimization with complete overlapping (Swaminathan and Joachims) 201 Let the logging policy by given by я. It holds in the bandit off-policy learning setting [a..) where f(,, i) E (0, 1) now serves as the policy we try to optimize. The
that: (y(u,)) & *(u.3)
v(u,3) counterfactual risk is given by: R(f) := (u,ijED Mudd ((f(u, i). Mus), and we prove that the
solution of (3) is consistent with that of the counterfactual risk minimization.
Theorem 3. Let f arg min fer Ep, R(f) be the solution of the counterfactual risk minimization,
and f, w be the solution of the proposed objective in (3.. For suitably large s.t. X 2 O(L) 2 1, it
holds with probability at least 8 that:
Ep, R((*) (Erg R() Adw (Por, py))
A
log 1/(20)
log 1/(2))
+ XMay
n 1//d+1)
n M max m /
n
Rud (f)2) log 24
where MG. RI) are defined as in Theorem and a is the logging policy.
Intuitively, since both f and π are probability distributions with the same support in the idea bandit feedback setting, a suitably large À will drive P' ultimately toward Py and lead the consistency result. We defer the proof of Theorem 3 to Appendix|e AA. This example reveals the effectiveness of the proposed mnnssooraationrrgulaaiii
risk minimization, which we show is a strict extension of the counterfactual risk minimization. For IR systems, the transportation-regllaae
risk minimization applies to a much broader setting including deterministic recommendation. Nonetheless, directly solving (3) is still challenging due to the complications in computing the Wasserstein distance. In- spired by how Wasserstein GAN transforms its objective to a two-player adversarial game (Gulrajani al. 2017). can also convert objective to minimax optimization problem discussed below.
4.3
MINIMAX OPTIMIZATION
Algorithm 1: Batch-wise GDA for Minimax Optimization
Input: D(t): batch of training sample of size at step 1y: the learning rate for ascent step. 7: shrinking parameter for the learning rate of descent step. X: the regularization parameter.
for each step t = 0, 1... do
Compute reco(u, i; fo.) for (u, i) E D(t) (see Section for the computation detail);
((++1) ((t) Ve, Cx (10( 00)) (f))):) 0h ((++)) g VVe 0/' 0 o!));
0 (++1) - (t) Cs
end
The key to our implementation is again perceiving Wasserstein distance binary classification problem with Lipschitz-bounded classifier as we discussed in Section 4.1 Towards this end, we denote by g E G any suitable classifier for computing dw according to (I.. Without loss of gener- ality, we let w, f and g be parameterized by 0,, O₂ and 0z. It is straightforward to verify that the regularized objective in (3) transforms exactly into: min .2] maxe, (x((,,, 02), Oz), where Lx given by:
Wiel (.n(0))).. (Jo.) X( (D
Σ
Wui (02) (mx(Os) (M,))D
Σ
reco(u, é; So,) gmn(0s)) (4) (u,))ED
Σ
7

---

Published as a conference paper at ICLR 2022
In view of 4 as two-player game, the first player optimizes f and w to minimize both the training risk and domain transportation, while the second player tries to increase the gap between the two domains. The global equilibrium is reached when neither player can change the objective without knowing each other's strategy, which means f and w cannot simultaneously improve the empirical risk and the domain transportation between P.. and Py. It suggests we have found the recommenda- tion hypothesis that best transports the learnt patterns to its intervention domain. We propose using the two-time-scale gradient descent-ascent algorithm (GDA) solve the minimax optimization.
GDA is very efficient for solving objectives like 4 with both empirical and theoretical evidence (Lin et al. 2020), and it has been widely applied to optimize generative adversarial networks. Since our solution will be deployed to real-world systems, we pay more attention to the convergence and stability of GDA. In appendix [A.8] we rigorously prove that for the bounded Lipschitz functions we consider, GDA will converge to the global Nash equilibrium with a proper learning-rate schedule. Further, it is unlikely to bouncing around near the optimum. Now that we have the performance guarantee, we apply the batch-wise GDA described in Algorithm I to solve our objective.
5 EXPERIMENT AND RESULT
We present in this section the experiment settings, implementations, empirical results, well as the analysis. The complete experimental results and the real-world online testing performance are deferred to Appendix C
All the implementation codes are provided in the supplement material.
Computing the reco(u, (u, i: f) function. For the deterministic top-K recommendation, reco(u, i; f) requires computing and sorting the scores of (f(u,, i1),...,., f(u, i for the user u. This is expen- sive during training, so we refer to the widespread practice of downsampling. In particular, for each (u',²), we randomly sample m < [Z] irrelevant items and see if i' among the top-K (Krichene) and Rendle 2020). While the sampled outcome may have certain bias, it significantly speeds up the training process while maintaining a decent accuracy under moderate m, e.g. m 100.
Benchmark datasets. We refer to the MovieLens- IM, LastFM, and GoodReads datasets that are extensively employed by the IR literature. We treat them as implicit feedback data, and the detailed description and processing are deferred to Appendix C.1
Simulation studies.. For implicit feedback, the response (click) generated from the exposure and relevance status via: P(Y.: = 1) = P(O.. 1)- -P = 1). where Ou: indicates the exposure and Ru is the relevance. The relevance score is critical for unbiased offline evaluation, but it is unknown for real-world datasets. We thus conduct simulation so we know what the ground truth relevance is. To make sure the distribution of the simulated data conforms to the real-world feedback data, we first extract the exposure and relevance signals from public datasets (c.g. the three datasets described above) via models such as matrix factorization, and then generate the new feedback data by adding noise to the extracted relevance signal. The detailed mechanisms are provided in Appendix C.I.I
a. Weight analysis on Movielans and Goodreads for DT-MCF Goodreads
b. Weight analysis on simulation
c. Ablation sensitivity analysis
NoviaLars
Moxtel were Syrttetic
7pe
Prqquency
Deta Sea
-00
64
-190
-055
-C20 -.00
-115
Weigets
Methed
DT-
42-
431 Loarmt (eegles
Learn: Wagles
LeaITE WiN g7ts
Figure 2: (a). Weight analysis on MovieLens and GoodReads. Upper: distribution of Wus on the positive and negative feedback data. Lower: relation between Vni and fus under Py (the recommended (u, i) under f) and others; (b). Weight analysis on MovieLens simulation: the relations between wa: and P(O 1) the positive and negative synthetic feedback data for MCF (upper) and NCF (lower); (c). Ablation study for the transportation regularization and sensitivity analysis on X for Movieeeens and its synthetic data.
8

---

Published as a conference paper at ICLR 2022
Table 1: Real-data and semi syntheeit experiment testing testing results for the MovieLens- IM, LaftFM and GoodReads dataset. All the results are computed via ten runs and the Hit and NDCG metrics are multiplied by 100 for presentation. The results for the LastFM and GoodReads datasets, and sequential recommendation (Arm) are deferred to Appendix D.3. The metric of Rel@ 10, Hit 10 and NDCG @ 10 are short for the top- 10 relevance score, hitting rate and normalized discounted cumulative gain. The metrics synthetic data are computed by using the true relevance model. We highlight the best and second best results. Attn is not experimented on simulation because the ordering of the generated data is random.
Pop
IPW-MF
EspoCT
AC-MF
MCF
DT-MCF
NCF
DE-NCE
DT-Aft
MowiLLms-IM
Relg 10
9.05 (.02)
14.00 (005
(.004(008)
14.05 (.07)
14,02 (.03)
14.65 (007)
13.77 (.04)
13.98 (.06
14,26
16.32 (.09)
Hir@:10
43.67 (.10)
60.48 (.12)
60.21 (14)
(1119(11)
60.27 (115)
(.12)
(.395
61.17 (11)
(212
74.82 (.24)
NDCCO
(.033
(10)
(.10)
31.72(.11)
30,91 (11)
32.83 (08)
31.07 (.10)
32.27 (10))
42,48 (10)
43,09 (:14)
MovicLens-Jh IM Simmlation
Rele 10"
(,02)
3.77 (00)
3.73 (.03)
(07)
3,75 (.02)
1.98 (02)
(12)
4.11 (03)
Hiv 10
56.12(007)
75.02 (.11)
(09)
(.13)
(,.61(.09)
(.12)
75.69 (.09)
(11)
NDCG@10 10
29.71 (.05)
37.79 (.06)
(7.86.(07)
(.07)
(.05)
38.57 (.88
38.43 (.05)
38.72 (107)
LastFM
ReNR 10
(,61
6.41 (.04
6,44 (.03)
(.03)
6.38 (003)
(02)
(.05)
6.56 (04)
5.71 (004
5.82 (.05)
Hile 10
25,22 (.0))
79:21 (.31)
79.62 (:27)
79 64 (.22)
79.02 (222)
81.81 (20)
77.20 (:35)
80.83 (338)
67.48 (35)
68:74 (.57)
NDC068810 10
15.35 (.DI
50.63 (.19)
(.276
51.05 (.19)
60.066.131
52.96 (.14)
50.55 (.18)
52.03 (.26)
56,12 (223)
56.601 (.19)
GoodReads
10
(:01)
5:94 (.08)
(.10)
5.97 (.07)
5,90 (.0)
(.07)
(.02)
6.07 (.09)
(.04)
4.68 (.10)
Hir@
43.37 (.06)
59.04 (.10)
59.28 (.14)
(p.33.(.12)
58.32 (.12)
60.95 (.11)
58.07 (.04)
59.7% (.34)
48.97 (.26)
49: 30 (.25)
NDCG@ 10
(.03)
38.19 (007)
(.08)
(.1I)
34,69 (.10)
36.45 (.09)
34.90
36.27 (.15)
(.17
26.04 (.13)
Models and baselines methods. The functions of f. w and 9 in the minimax objective can be any recommendation algorithm that suits the context, such as filtering (MCF), neural collaborative filtering (NCF) (He et al.| (017), and sequential recommen- dation model with the prevalent attention mechanism (Attn) as in Kang and McAuley (2018). We index our domain domain transportation approach by such as DT-X, with X stands for the models of f, w and g. We will experiment with broad range of combinations for f, w and g as we present recommen- in Appendix C As for the baseline methods, other than the standard popularity- dation (Pop) and MCF, we select particularly the approaches that adapts causal inference or missing data techniques, including the IPW-debaised MF method (IPW-MF) from [aato et al. (2020), the MF method (AC-MF) from Xu et al. 2020). The model configurations and training details are deferred to Appendix
collaborative
user-exposure aware MF (ExpoMF) from Liang et al. (2016), and the
Training & evaluation. We use the two-timescale GDA as described in Algorithm I with pre- selected shrinkage parameter, and we will conduct its sensitivity analysis in Appendix C.4 The configurations for both our model and the baselines are described in Appendix C.2 We adopt the convention where the second-to- for testing. For evaluation, in addition to the regular Hir@ 10 and NDCG@ 10 as in Rendle et al. (020), we further consider the relevance score of the top-10 recommendation, i.e. Lup- Rui. since it also reveals the quality of the recommendation and more closely resembles the deployment performance of Ep, R(f). We have access to Rus during simulation, and on real-data analysis, we settle to the Yuu in testing data as an approximation. The evaluation results are provided in Table
interaction is used for validation, and the last interaction is used
Result analysis. From Table 1. first observe that the proposed methods achieves the best perfor- mances in both the benchmark and simulated datasets on all metrics. In particular, the DT-X method significantly improves the performance of the original model X. Also, our solution outperforms all the baselines, including those adapted from causal inference or missing data methods. The rest simulation studies are provided in Appendix C.3 and their results admit similar patterns. Finally, we conduct ablation studies on the transportation regularizer and the sensitivity analysis on À (see FigureZ)). It is clear that without the transportation regularization, the performances degenerate sig- nificantly in both the real data and simulation studies. Also, we find that the performance variation of the proposed approach is relatively steady under different X.
Analysis on w. We specifically analyze the learnt weights since they play a critical role in our approach. On both MovieLenss and GoodReads (Figure we find that: 1). the learnt weights are larger the positive training instances; 2). for the (u, that are among Py (the recommended), the weights Wai are higher and relates positively with f(u, i), while there is no such pattern for the non-recommended. They both suggest the weights are indeed learnt to balance the domains of the positive feedback data and the instances recommended under f. In Figure PDb, we observe from the Movielens simulation study that the learnt weights correlate positively to the exposure on the

---

Published as a conference paper at ICLR 2022
negative training data, and are distributed more evenly the positive data. It means that was lears to emphasize the instances that were more likely to be exposed but not clicked, which usually have strong negative signals, and the positive instances. It is valuable for training under implicit feedback because the algorithm learns to locate the strong negative instances. The remaining weight analysis, ablation studies, and sensitivty analysis are provided in Appendix
Real-world IR system. We deploy our solution to a real-world IR system held by a major e- commerce platform in the U.S. We deploy our transportation-regulliiia A/B/C testing against the standard and IPW-based solutions for an item recommendation task. Due the space limitation, defer the details and analysis Appendix C.6
solution, and the online
CONCLUSION AND DISCUSSION
In this paper, we study from the critical intervention perspective of recommendation and summarize domain transportation view supported by the realistic working mechanism of IR systems. We propose a principled transportation-consee constraint risk minimization for optimizing recommendation, and illustrate by both theories and experiments how find it more favorable than directly importing the causal inference and missing data solutions. However, we point out that our work does not aim replace those solutions since focus exclusively on optimizing recommendation. For instance, we do not readily incorporate the known causal mechanisms (which might be available for certain applications) to answer questions that are relevant to the decision making in IR. will be interesting to explore how the presumed or discovered causal structures can interact with domain transportation and improve our solution. Towards this end, our transportation-cone conntttaaiinnnnnssaaanttt risk minimization can be viewed as a modular toolkit that allows researchers to apply further insights to solve more complex IR problems. Finally, we hope our work raises the awareness developing IR-oriented solutions with a proper understanding of the system's mechanism. The novel perspectives, solutions, and theoretical results in our paper may also open the door to future research.
REFERENCES
A. Agarwal, K. Takatsu, I. Zaitsev, and T. Joachims. A general framework for counterfactual Borning-to-ranke In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 5-14, 2019.
M. Anthony and P. L. Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 2009.
Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
C. Austin and E. A. Stuart. Moving towards best practice when using inverse probability of treatment weighting (iptw) using the propensity score to estimate causal treatment effects in ob- servational studies. Statistics in medicine, 54(28):3661-3679) 2015.
S. Ben-David and R. Urner. On the hardness of domain adaptation and the utility of unlabeled target samples. In International Conference on Algorithmic Learning Theory, pages 139-153. Springer, 2012.
S. Bonner and F. Vasile. Causal embeddings for recommendation. conference on recommender systems, pages 104-112, 2018.
I Proceedings of the 12th ACM
L. Bottou, Peters, J. Quinonero-Candela, D. X. Charles, D. M. Chickering, E. Portugaly, D. Ray, P. Simard, and E. Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
J. Byrd and Z. Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning, pages 872-881. PMLR, 2019.
J. Chen, H. Dong, X. Wang, F. Feng, M. Wang, and X. He. Bias and debias in recommender system: A survey and future directions. arXiv preprint 10.02200 2020.
10

---

Published as a conference paper at ICLR 2022
H.TT. Cheng, L. Koc, J. Harmsen, T. Shaked, T. Chandra, H. Aradhye. G. Anderson, G. Corrado, W. Chai, M. Ispir, et al. Wide deep learning for recommender systems. In Proceedings of the 1st workshop on deep learning for recommender systems, pages 7-10, 2016.
C. Cortes, Y. Mansour, and M. Mohri. Learning bounds for importance weighting. In Nips, vol- ume 10, pages 442-450. Citeseer, 2010.
N. Courty, R. Flamary, D. Tuia, and A. Rakotomamonjy. Optimal transport for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 39(9):1853 1865, 2016.
C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent in min-max opti-
mization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, page 9256-9266, 2018.
S. B. David, T. Lu, T. Luu, and D. Pál. Impossibility theorems for domain adaptation. Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, pages 129- 136. JMLR Workshop and Conference Proceedings, 2010.
R. M. Dudley. Real analysis and probability. CRC Press, 2018.
L. Faury, U. Tanielian, E. Dohmatob, E. Smirnova, and F. Vasile. Distributionally robust coun- terfactual risk minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3850-3857, 2020.
M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32:1 18:11427-11438 2019.
R. Gao and A. J. Kleywegt. Distributionally robust stochastic optimization with wasserstein dis- tance. arXiv preprint 1rXiv:160..02199 2016.
P. Germain, A. Lacasse, F. Laviolette, and M. Marchand. Pac-bayesian learning of linear classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 353- 360, 2009.
P. Germain, A. Lacasse, F. Laviolette, M. March, and J.-F. Roy. Risk bounds for the majority vote: From a bay-saan analysis to a learning algorithm. Journal of Machine Learning Research, 16 (26):787-860, 2015,
A. Globerson and N. Tishby. Sufficient dimensionality reduction. Journal of Machine Learning Research, 3(Mar): 2003.
I. Guirajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. Courville. Improved training of wasser- stein gans. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 5769-57777 5779, 2017.
X. He, L. Liao, H. Zhang, L. Nie, X. Hu, and T.-S. Chua. Neural collaborative filtering. In Proceed- ings of the 26th international conference on world wide web, pages 173-182, 2017.
C. Jin, P. Netrapalli, and M. Jordan. What local optimality in nonconvex- concoonneex-ooccccvvve minimax optimization? In International Conference Machine Learning, pages 4880-4889. PMLR, 2020.
T. Joachims, A. Swaminathan, and T. Schnabel. Unbiased Searning-to-rant with biased feedback. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 781-789 2017.
F. D. Johansson, D. Sontag, and R. Ranganath. Support and invertibility in domain-invariant repre- sentations. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 527-536. PMLR, 2019.
F. D. Johansson, U. Shalit, N. Kallus, and D. Sontag. Generalization bounds and repre- sentation learning for estimation of potential outcomes and causal effects. arXiv preprint arXiv:2001.07426, 2020.

---

Published as a conference paper at ICLR 2022
W.-C. Kang and J. McAuley. Self-attentive sequential recommendation. In 2018 IEEE International Conference on Data Mining (ICDM), pages 197-206. IEEE, 2018.
V. Koltchinskii, D. Panchenko, et al. Empirical margin distributions and bounding the generalization error of combined classifiers. Annals statistics, 30(1):1-50 2002.
W. Krichene and S. Rendle. On sampled metrics for item recommendation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1748-1757, 2020.
D. Kuhn, P. M. Esfahani, V. A. Nguyen, and S. Shafieeradeh-Abadeh Wasserstein distributionally robust optimization: Theory and applications in machine learning. In Operations Research & Management Science in the Age of Analytics, pages 130-166. INFORMS, 2019.
D. Liang. L. Charlin, and D. M. Blei. Causal inference for recommendation. In Causation: Foun- dation to Application, Workshop at UAL AUAI, 2016.
T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-come minimax problems. In International Conference on Machine Learning, pages 6083-6093 6093. PMLR, 2020.
R. Little, D. B. Rubin, and D. B. Rubin. Statistical analysis with missing data: Wiley series in probability and statistics. 2002.
D. Liu, P. Cheng, Z. Dong, X. He, W. Pan, and Z. Ming. A general knowledge distillation framework for counterfactual recommendation via uniform data. Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 831-840, 2020.
D. G. Luenberger. Optimization by vector space methods. John Wiley & Sons, 1997.
A. Maurer and M. Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint ar XxXxx:0007.37400 2009.
T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. arXiv preprint 1rxXiv:/3013311 2013.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
S. T. Rachev. The monge -anto-kantooo mass transference problem and its stochastic applications. Theory of Probability Its Applications, 29(4):647-676, 1985.
I. Redko, A. Habrard, and M. Sebban. Theoretical analysis of domain adaptation with optimal transport. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 737-753. Springer, 2017.
Rendle, W. Krichene, Zhang, and Anderson. Neural collaborative filtering vs. matrix fac- torization revisited. In Fourteenth ACM Conference on Recommender Systems, pages 240-248, 2020.
R. T. Rockafellar and R. J.-B. Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
P. R. Rosenbaum and D. B. Rubin. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41-55, 1983.
D. B. Rubin. Causal inference using potential outcomes: Design, modeling, decisions. Journal of the American Statistical Association, 100(469):32--331, 2005.
N. Sachdeva, Y. Su, and T. Joachims. Off-policy bandits with deficient support. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 965-975, 2020.
Y. Saito. Asymmetric tri-training for debiasing missing- random- explicit feedback. In Pro- ceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 309-318, 2020.
12

---

Published as a conference paper at ICLR 2022
Y. Saito, S. Yaginuma, Y. Nishino, H. Sakata, and K. Nakata. Unbiased recommender learning from bessingnoo-att-andoo implicit feedback. In Proceedings of the 13th International Conference Web Search and Data Mining, pages 501-509, 2020.
T. Schnabel, A. Swaminathan, A. Singh, N. Chandak, and T. Joachims. Recommendations treat- ments: Debiasing learning and evaluation. In international conference on machine learning, pages 1670-1679. PMLR, 2016.
U. Shalit, F. D. Johansson, and D. Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In International Conference on Machine Learning, pages 3076-3085. PMLR, 2017.
N. Si, F. Zhang, Z. Zhou, and Blanchet. Distributionally robust policy evaluation and learning in offline contextual bandits. In International Conference on Machine Learning, pages 8884-8894. PMLR, 2020.
B. K. Sriperumbudur, Fukumizu, A. Gretton, Schölkopf, and G. R. Lanckriet. On integral probability metrics, Aphi-divergences and binary classification. arXiv preprint arXiv:0901.2698, 2009.
H. Steck. Training and testing recommender systems on data missing not at random. In Pro- ceedings of the 16th ACM SIGKDD international conference Knowledge discovery and data mining, pages 713-722, 2010.
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. 1998.
A. Swaminathan and T. Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference Machine Learning, pages 814 823. PMLR, 2015a.
A. Swaminathan and T. Joachims. The self-normalized estimator for counterfactual learning. ad- vances in neural information processing systems, 28, 2015b.
X. Wang, R. Zhang, Y. Sun, and J. Qi. Doubly robust joint learning for recommendation on data missing not random. In International Conference Machine Learning, pages (688-6647. PMLR, 2019.
X. Wang, M. Long, J. Wang, and M. I. Jordan. Transferable calibration with lower bias and vari- ance in domain adaptation. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020. NeurlPS 2020, December 6-12, 2020, virtual, 2020.
T. Xiao and Wang. A general offline reinforcement learning framework for interactive recom- mendation. In The Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, 2021.
D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan. Adversarial counterfactual learning and evaluation for recommender system. Advances in Neural Information Processing Systems, 33, 2020.
D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan. Theoretical understandings of product embedding for e-commerce machine learning. In Proceedings of the 14th ACM International Conference Web Search and Data Mining, pages 256-264, 2021a.
K. Xu, M. Zhang, J. Li, S. S. Du, K. Kawarabayashi, and S. Jegelka. How neural networks extrap- olate: From feedforward to graph neural networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.nest 2021b.
L. Yang, Y. Cui, Y. Xuan, C. Wang, S. Belongie, and D. Estrin. Unbiased offline recommender eval- uation for missing-not maasing-not--t--aaddo implicit feedback. In Proceedings of the 12th ACM Conference Recommender Systems, pages 279-287, 2018.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX ON BACKGROUND AND MAIN THEORETICAL RESULTS
We provide the supplementary background introduction, proofs for the claim, proposition and the- orem, as well as the detailed experiment settings and complete numerical results in this part of the paper.
A.1 RECOMMENDER WITH EXPLORATION POLICY, AND LEARNING FROM BANDIT FEEDBACK DATA
Using multi-armed bandits for exploration has attracted increasing attention from the recommen- dation literature in recent years. The major advantage is that the interactive process between users and recommender is explicitly characterized in an online fashion. Exploration also helps alleviate the exposure bias, popularity bias, position bias, etc, via more efficient exploitation of the feedback data. A critical difference between the bandit recommender and the deterministic recommender we referred to in paper is that item is exposed the user with randomness, and the exploration policy controls the randomness the exposure.
Mathematically, continue with X' as the context (feature) space, I (1....,kk) (item) space. The exploration-exploittiii strategy can be viewed as a sequential game between the user and recommender. For notation simplicity, we introduce the stationary bandit setting where the exploration policy does not depend on the history. In each round, an item is sampled according mapping between the item space and
kt) be the action
to the exploration policy I (u, i) : Ti xw), which the probability space, and expose it to the user. Then the user, whose feature is Xu, reveal the regret (or reward) action E I, which corresponds to the Yu,; in our setting. delivering recommendation, clearly we have: P(reco(u, (u, f) 1) x(u, i) during exploration, and in the context of learning from the logged feedback data, we have P(O.. = 1) = (u, i) since it characterizes the probability of exposure.
the context of
Similar to the deterninistic recommender, the challenge bandit offline learning largely due its partial-obe oottiallobsevattion nature we do not observe the complete reward for all items. However, unlike the deterministic recommender, the random exposure mechanism allows efficient estimation of the counterfactual regret, i.e. what the regret would have become if alternative exploration policy was used. The IPW estimator fits particularly well to this purpose, since it provides the unbiased estimation of the counterfactual regret:
EP f(u, i) Yus = Ep, Yui. n (u,
Swaminathan and Joachims 2015 refers to the IPW-reweighted risk, which essentially replace the regret Y.. by the corresponding risk under f. as the counterfactual risk for learning from the logged bandit feedback data. It exactly corresponds setting the base measure P with Piew, it holds: Ep, R(f) = E(UN)ED f(u.a) ((f(u, i), Vus).
*(M,))
A.2 PROOF AND BACKGROUND FOR THE IW AND DA BOUNDS IN PROPOSITION
We first prove the upper bound for importance weighting under weak overlap.
Proof. Our proof leverages the classical "double sampling" technique from Anthony and Bartlett (2009). We use [z .2...... zn] to denote the observed samples, and z' z to denote an
...d copy of z. We first define by:
2d Q)t wily +
3Mt n
Uf,(f n
n
and
U U22ff,Zt) = Σ wol wglg(Zi)) +
9Mt +
18d(PI[Q)t
14

---

Published as a conference paper at ICLR 2022
6MC 8d( it holds:
Given f F. =
P SUUBBLU S A) +P(UBI(J,Z,)) 2 A)
1 n E w,
Pd( 3M1
s 2P EQ [QQ
+
n
n
- 4
where the last line follows from Lemma A.2 Next, we define Cie, l F, (P,.))n)))) be the c-cover of l with the empirical & norm under Pn, such that for any f l o F, there exists f in Cle, Eo F.F: Σ w:f(2;) # Σ u:, ((x)) S for (ZI.... 2n) sampled i.i from P. It then holds:
P(3f E F: EQ 2 (f +c)
= Eg sup
(E 2 UB, +e] JEF
(0)
I Eg sup ( + (UBUUUUU BgR(S)
JEF
< 2Eg, sup (f, (1) fel
(
- (ZZ (3f E F.G(PP.. of o(,E)) (
I FN .e
where (a) follows from the fact that Eg [U 2 E&R( 2 1/2 as suggested by Lemma
A.2 and in step (b) we let o [Z, z'), takes the value of z, with equal probability, and the inequality follows from the definition of the cover. Notice that F,
M, F, e ) I &N(e/M,&
We take e = J. which solves for = clog 1 + to the desired result after arranging terms.
(x)) for some constant c and leads
The corresponding lower bound follows directly from Lemma A.4 where we make a mild assump- tion that there exists hypothesis f FF such that Ep R(f) 1. so it holds that Ep,, R(f) Q( - suggested by Lemma Cortes et al. (2010).
We then show the PAC-Bayesian result that stated for the partial-overlap case. Our proof relies on the existing results in the PAC-Bayesian literature in Germain al. (2015).
Proof. We use E to denote the 0 - loss for brevity. The PAC- PaC-Baaesian approach concerns with the Gibbs risk of E Eo
i), yus). where 7 is some posterior distribution on the hypothesis space F. Clearly, when there mismatch in the supports of Sp and Sq. the Gibbs risk for the mismatched part is given by E De..// R(f). We now focus on the overlapped part. Using the classical decomposition result from Germain et al. (2015), which states that:
BoR() 2 do( +eQ()))Q(T))))))))
where dr((T) = Sx.r,Bollf(C 1). f(u, 1)) is a discrepancy term, and cQ(() i), Mui) is the Gibbs risk for the joint hypothesis. Therefore, we (), en)) Erll:
have:
1 E E R(J) E P. R(S) (g((()) dp. (7)) + (EQ(T)- -p((T)
1
2
1
< 2 (do(T) - dp, (7) (eo(T) Ep (T)
D(F))
where D(T) essentially characterizes the disagreement of Q and P.p in terms of the posterior 7 on
F. Therefore, for any posterior distribution 7, we have: EE R(J) & Ey,TEr R(J) D(7),
15

---

Published as a conference paper at ICLR 2022
so the next step is to bound the Gibbs risk of E,, R(f). Our strategy follows that of Germain ct al. (2015), that we employ the convex function A [0, x [0, M] + R. then holds that:
A B R(S) By R(())
y A Bp (Pr... R(f). Ep, R(f))
ddxl(T|m [T)) In yor exp nd Ep R(f), Ep, B(.f)))
by Lemma
1 1-.1-6 dRI(T|T) + In EgraaBalnnn exp nn ( Σ ((zz)ez(Zz)) Ex
where the last line comes from the Markov inequality, and w(zs) is a short- (u,i, Bui). We then focus on bounding:
hand for w(u,i) for Zk Ef EE exp nA Ex (aa. (2)))))))) the term inside A (setting aside w(2)) are essentially binomial variable of n trials with a success rate EpR(f). Since A is convex in both arguments and w(u, i) is given by Quu, P(u, i), is easy to verify that:
Since ly is the 0 1 loss,
EP2rP exp (nL -
Σ
( E2 pw(z)e
$ d().Q) ExppPexp (nA 1
Ee((
where d(P,Q) Isa (dP/dQ)dP we mentioned in the statement. It is then obvious that:
Exp exp nn n [e((a)).
S sup
Σ Bin(k;;;)) exp (nA( k rE(o.1]
r))
where we use r E [0. 1] to replace the role of RpR(f), since the prior æ arbitrary, and Bin(k; n; r) probability of having i success in rounds of Bernoulli trail where the success rate is r. It is shown by Germain et al. (2009) that the RHS is O(1) by choose a particular A, so we obtain the desired result by putting together the above arguments.
Now we briefly introduce the skip-gran negative sampling algorithm and prove its associated rersults Proposition [T It have been shown by the recent work of Xu et al. (2021a) that the user/item embeddings optimized via the skip-gram negative sampling (SGNS) algorithm are the sufficient dimension reduction of a specific co-occurrence statistics. In particular, the SGNS objec- tive function is given by:
1
P(O,. 1/u, t) = a ( = 1 exp (())
P(O = 0/u, i) = a( -i ( = 1 1 exp (())))
(A.1)
eu log P(O 1/u, k- Eg~Nog(2) llog IPO... 0lu, 1)
where (uu), (t) are the embeddings for the user u and item i, A is the number of negative samples, and Neg(T) the uniform negative-ammpling distribution on the item set. The risk objective is thus give by: Ep )) = (u,))e lu,; The SGNS algorithm has been widely applied to train user and item embeddings for various recommendation tasks.
The sufficient dimension reduction (SDR), on the other hand, is inspired by the sufficient statisties of exponential family. Broadly speaking, when predicting Y with X, if all the information in X about Y can be compressed into a dimension reduction f(X). i.. Y fxx) or X and pYYI(XX) are the same, then f(X) is sufficient dimension reduction (SDR). According
16

---

Published as a conference paper at ICLR 2022
to Globerson and Tishby (2003), finding the SDR f(X) is equivalent to solving optimization problem:
min dxl (()f())
(A.2)
where dxL is the Kullback-Leibler divergence.
Proof. Let Rui := Nut be the relatedness measure defined in Xu et al. 2021a), where Nui is the co-count of 2), and Nu. .N are the individual counts of and i. The co-occurrence statistics is given by Cui = Oui Rui, which exposure Ous condition on the relatedness measure. is shown in the Claim 1 of Xu et al. (2021a) that:
N.N;
min (1)
Bp
mim (E)
Σ (u,))DD
dkl (p(O @ (()) p(Ous Rus));
(A.3)
so 4 gives the SDR of Cui in R according to the definition of A.2 Note that the terms in the RHS of (A.3) are all binary KL divergence, and it easy to verify that binary KL divergence satisfies: dxz(al + dxL(cll6) 2 dkI(allb) + (c - a) log اQا- co-occurrence statistics under P and Q, respectively. Therefore, if we let ((P) and (QQ) be the solution to (A.3) under P and Q. by assuming Sp Sq. it holds that:
(1-cjh- Recall that Cui(P) and Cu.(Q) are the
inf (EpR(T) + EQR(T)) 2 inf R(((()) + +inf ip(()(()))
Σ
(pl(p(Owl 1 (P))) Ca(P)))
Spl
(a.i)ESp
dx (p((O(Oui ( (19)(1)) Cn((Q))
Σ
dKL(Cunf Cui + +C,
= SSPl
(u,i)
and C infa (EpR(Ø) + EqR(Φ)) when P Q a.s.
A.3 BACKGROUND ON THE WASSERSTEIN DISTANCE
Perhaps the two most common discrepancy measures on probabilities are şi-divergence and integral probability metric (IPM). Obviously, é-divergence does not satisfy our need of characterizing do- main transportation because it requires Sp C Sq (weak overlap) to hold in practice. IPM, on the other hand, provides the flexibility and is defined
SOaP fada)
dg Q) sup gEg
where G is class of real-valued bounded measurable function. In this direction, find the Wasser- stein distance from the optimal transportation (OT) theory [Rachey| (1985) a good fit to our goal. Although the maximum mean discrepancy distance is also valid, its computation and related theo- retical results rely on the specification of reproducing kernel Hilbert space, whose usage is less common in the IR literature.
The origin of the Wasserstein distance is to give the optimal cost of transporting mass from one marginal distribution another:
/ c(z, 2z) PQQ),
du,e (P.Q) arg min
where II(P, Q) is the set of all joint probability measure whose marginals are and Q, and c(.. ) is the cost function. Clearly, du.c(P, (P, Q) relies the geometry of P and Q if the cost function is well- chosen. For recommender system, z is often given by (x,, ) or (#(u), (())). ) so is natural to use the la distance: c(z, z') Iz z' 2/ We denote by dw for this particular cost function, which
17

---

Published as a conference paper at ICLR 2022
is also referred to the 1-Wasserstein distance. The classical Seterovvicc-Rbiinsternn theorem Dudley (0188) connects the dw to IPM by proving the duality result of.
I gdP gdQ. s:lllgll
dw sup
(A.4)
In the above formulation, the constant of under sup less critical since we can always rescale The class of Lipschitz-bounded function covers wide selection of models including neural networks discussed in Fazlyab et (2019)
A.4 PROOF FOR THEOREM 1
We first state proposition for the following proofs.
Proposition A.I. Suppose l is semi-continuous for all f E F, P is any distribution supported on Z, and c(z, z') Iz z/112. It holds:
min (Q.P)P
RQf(f) suu { 1- EgpP RE2
inf (2)((()) + A xx(2,,)]]]]
A20
Proof. is shown by Gao and Kleywegt 2016) that:
max Q:dw (Q.P)SP
Eq R(f)
inf {Ap + Ex-p (u) A 2(z,))}} 2
aEZ
Following the above result, we immediately have:
min (Q
Eq
max Q:dw (Q,P)sP
R())
inf {Xp Exnr
sup (f)(()) X c((z, }]}}}
A20
26
sup { Ap-
ExnP P
ssupf (l (2) À d.c(z, 2)
A20
BE2
sup { - Ap + E
inf (l, (ž) + A ol }
X20
RE2
Now we prove the result in Theorem 1.
Proof. We first define Hi (w E H dw Pς) S p}, and Hi {w H dw (Pws Pς) S
log z ), where cw is the constant stated in Lemma A.5
8M
We then omit the w H. in the following proofs for brevity. By Lemma A.5 for any > 0. it holds with probability at least 8 that 74 S H2, which suggests that for any given f E F:
min wiD.
Ep. R(J) 2
min
BP..R(]
(HDD
log
with probability at least 1 - 8, where B 1T/(+1
8MM
Now we define ã arg min wi. A15BBB E., R(J). Then using the result in Lemma A.1 for any given f F, holds with probability at least that:
min w: w:DD(tt.f)$6+B
Er. R()) Er. R(F)
7M log
2R (f) (f)²
Ep,.s R())
3n
n
7M log
2Ra log 1
min w:D., (5
EP.... R(f)
3n
n1.
where the last line follows from the definition of w.
18

---

Published as a conference paper at ICLR 2022
Using Proposition A.1 we have:
min
E. R(S) sup
M(p + B) + Ean.a inf (E + X d(2 xE2
w:D. w:DD(w.f)$B+
A20
2 sup
Ap + Eg Pa inf (Lf(2) + X c(z, 2)}|} B 8E2
X20
min wu
Ep.. R(f) - L. B,
where the second line the result in LemmalA.66 which bounds the X that achieves the supremum with the Lipscitize constant L. Combining the above results, it holds with probability at least that:
7M Togog 3
2R log
Ep., P(f) D(.ff).
min
E P R(f) w: (w)
min
L B.
3n
n
The upper bound can shown the same manner, by using w arg min D., (6- Ep, R() replace Combining the upper and lower bounds, obtain the result stated in Theorem 1.
A.5 PROOF FOR THEOREM 2
Suppose is some bounded loss function, then My stated Theorem must finite for E [o, f1.
otherwise can be shown from Proposition A. and Lemma A.6 A.6 that:
min RO)()) = sup { Ap + Ex inf (y(ø) + A x(2(22 2(2, X
PSP
2E2
unbounded for finite p. which contradicts that is bounded.
We first prove the generalization error bound.
Proof. We use the shorthand (z) := Eg- jinfz (z) + Ac(ž, z)]. Since we do not make any parametric assumption on the weighting function here (as the consequence using w H has been stated in Theorem 1), we have:
min BqR(f) sup Ap Ee- 0/,((2)) By Proposition A.I
dw (PP. PSP
A20
sup
Ap+ Ee-P, (z))(z) + E Ez 0z) Ez- (z)(
A20
sup
Ap EewPan + sup (Ep ,z) (,,,) } FEF
A20
Using the standard symmetrization argument, supJer [Ep, - (z,) with the empirical Rademarcher complexity:
can upper-bound
Σ (Z;)) /EF 1=1
Eva < 2E sup
where the expectation on LHS is taken with respect to the random variables of 21...., 2n Clearly, (A) is bounded by M,F that we illustrated the beginning, so from McDiarmid's inequality we have:
P(((A) > (v(() + Mt.
f S eex((22t))
(A.5)
19

---

Published as a conference paper at ICLR 2022
Also, note that / / ( (z,) is zero-mean and I-subgaussian with respect to the || lo norm on F, so for any f1, f2 F, it holds that:
a
exp
(((oni((2)) - (222)
t inf (fi(z) + Ad(z), 2)) + sup(-f2(2) Ac(z1, 2)]))]" 2E2
[8 exp
Vn
#C2
(A.6)
$
cxp
exp
sup
(fi ff(2))))
vn
zE2
1/ S2ll
exp
2
Using the entropy integral bound on the empirical Rademarcher complexity term, we have:
C. Vn. I
EA(A)
S
since is Lipscitz (and absorb the Lipscitz constant into Combining the above results, for any given À 2 0, holds with probability at least 1 - that:
P P(3f e F min
RQf(f) 2 Ap + Ez-Pan Pa., inf ( 2)]
(P..P.
So No, F, E de
Myty S 2 22xxp(-1 -xx)(-21²).
n
n
Then we apply the same union-bound argument from Theorem Koltchinski et al. (0022) to extend the above result to any À > 0. In particular, we pick the sequence of À and
+
Vlog k k = 1, ..... By simple calculations and the sum of infinite series arguments, we reach the conclusino that for any f F, holds with probability at least ô that:
EqR(f) 2 min { Ap + BawPn.s inf (Z) + Ac(z, [0(z, ZEZ
min dw (Po.P)))) P/iSp
X
Jo VlogN(c,FFF En de de
Mr v log 28
log ( + 1)
n
Now we prove the excessive risk bound.
Proof. We start by defining: f argminfes min (...ff Ep... R(f), and f
arg men min Ep... R(f). Using the definition of f. we have:
min Ep. R(f) min Ep. R(f") D(w.))pp
DS
< min Ep, R()) D(w,fisp
min
Ep, R(f) + min Ep, R(S))
min Ep, R(()).
D. (w,
D.(wF-))sp
D(w.f")P
Let = arg max - Ap - Exe linfaez f + X. c(z, 2)]} and from Lemma A.6 we know
that Â < L. holds that:
min Ep. R(f) min Ep. R(f) D(w.)sp
- Sp -Ap
EawPy
inf l (2) + + A.c(z, (2), - max X20
Ap + Ez-p, iin (,(2) + A c(z, 2)1}
ZE2
2e2
/ (inf& + 7e(z, d() -Pnn)
sup / (inf ( + Ac(z, 2)) d(p -P Pn.f)
20

---

Published as a conference paper at ICLR 2022
Again applying the standard symmetrization argument and McDiarmid's inequality to the last line (similar to what we have shown in proving the generalization bound), the following bound holds with probability at least 6/2:
log 3 min Ep R(f)- min Ep, R(f) 2Rad, (10, 0 (l.F) MF D(w
n
Similarly, we let X = arg maxx20 { - Ap + Py linlzez ey. (2) + X c(z, }. and using the
same arguments, we also have the following bound that holds with probability at least - 8/2:
2 log 2
min EP SSp
min Du(w
EP, & 2Rad, (1,
Mr
n
Combining the above two bounds, we obtain the desired result.
A.6 PROOF FOR CLAIM
Proof. Given f E F, the mapping of Pw to dw (Pw, Pу) is convex in the space of probability measures. Since dw (Pw. Py) 0 can be achieved by taking Pw Py a.e, using the generalized Lagrange duality result in Lemma A.3 it holds that:
/ (f(2)dP + X dw (.)) J (z(2) suu inf { (-2p dw (Pw. WwW(P.PPyyyn Py
inf
X20 dw (pu,
Notice that for any π E II(Pwr. Py), where II(P,,, Py) is the set of all joint distributions whose marginals are given by Pw and Py. we have: Jz 2 (2)dP Se ( dd 22). Therefore, we have:
J (z(2) inf / TEI((w.:P)) 122 c(z1, 22 (2), (21, = inf 1 1f _22 (z + b2));
=EII(P..PP) using the definition of the Wasserstein distance introduced Appendix A.3 As a consequence, holds that:
/ (z(2) = sup
{- Ap {-xp+ / (f(21) + A +x)d(z)z2)}
inf (P) We first point out that:
inf X20 S.
2x2
inf { { w,TEI(PP.PP) J2Zz (z(Z)) c(21, x2)}
inf {ef(2)) + (x).((z,22))llll (2))) (A.7) 2i
and in the following proof we show that the other direction also holds, the above inequality becomes equality. Also, if we consider M as the space of all the regular conditional probabilities from Z2 21, it is evident that:
inf w.xeTI(Pu..P) P1) { { 1 (g(2)) + +A-c(zi, 22)
(A.8)
{ 1/ ()(2)) A c(z1, z2) (22)dP
I inf MEM
Furthermore, using Lemma to Z, then it holds:
A.8 if we consider X' as the space of all measurable mappings from Z
inf ([lr(a(2)2) + Ac(x(z2), (2)12))22))PP((( (2)d)) = ff inf (z)(2)) + À c(z), (P) xEx:
Consequently, if let X be the mapping that achieves e-close to the above infimum (which requires certain continuity condition for E and M (-Izz) be defined by i(zz):
/ (z(2)) + Ac(z), (d)) = (f((2)) + do 22 (2))/(22)
inf x (22 +c
2 mi
inf W. P2) { 1/ (x(z)) + x. clz) ((21, te
(A.9)
21

---

Published as a conference paper at ICLR 2022
Since >> 0 is arbitrary, combining A.7
A.8 and A.9 have:
//2 (z(21) À c(2), 22 (2)d))(2))
inf W.TTEI(P.:.P))
inf (Ez(z)) A c(2), 22) (d)
and using the result in Proposition A.1 we obtain the final that for any f F:F:
min dw (Pw. PS) PS)SP
Ep, R(f)
max { X20
Ap min (in(EE. R(f) + X dw (P Pj))}
P
A.7 PROOF FOR THEOREM 3
Proof. We first let / arg miF Ep, R(J), and define w² = f" (suppose F C H) such that Pa iu, = Fn.r-(u, i) and Pa- (u, i) = Py- (u, i). Since F is the class of valid exploration
policies in the bandit setting, we have [u, i) E (0, 1) for f E F. Note that by the definition of f and w
min EP R() - x- --d dw(Pn, P).s) S Ep.... R(f*) + x (wwnnwww Pn.f.). SEF
Combining the results in Lemma A.l and Lemma A.5 it holds with probability at least - 6/2 for any f F and w E H. that:
E R(f*) Ep... R(ft) S dw (Panor Pa.s-) सा/बT 8MM V
log z 3n
2R... (1-)² log +
n
log 1
"
Hence, the following inequality holds with probability at least 1 6:
min SEF
Ep. R(F) + x dw (Pn,w Pa,s)
(A.10)
7 7log 26
2R (f+)2 log 26
Cue 1/(+11
log
< min EpinEp,R(f] +
+
+ 8MG
3n
7
n
On the other hand, with ス 2 and w E H. it holds that:
where L is the Lipschitz constant for Jo , for any given f F
Ep, R(f) = R(,) / [)(z)
(z) Py(z)
+
dz
T(z)
(z)
$ Er. R(f)+ + sup Ep, vizz) Epy (z)
SEtof
S Ep., R(S) L dw (Pw, Pf):
where in the first line we use the background of learning from bandit feedback data where the logging policy (e.g. (2) = (), for (x.. X;, Mni) )); and the last line we use the definition of Wasserstein distance under the Sestorovvcc-Rubinstee theorem (Appendix A..).. Again, by comb- further bound the last line with probability at least 1 8/2
ing Lemma A.I and Lemma A.5
with:
EP,,.. L. d. Pn
7 log 1
+
2R, (J)² log 1
48
+
!/(++1) + &8Ma
Cu
log 3 n
3n
n
slack Lerms
Now let j, arg migg Ep.... R() dw (Pr,w Pa.)) for X 2 L 2 1. Then holds that:
min E, R() < Rp, R()) fEF
(A.11)
< EP, R(F) + X dw P. Pn,,)) slack terms,
where the slack terms are stated above. Combining A..1 and A.11) we obtain the desired result.
22

---

Published as a conference paper at ICLR 2022
A.8 ANALYSIS ON THE GDA ALGORITHM.
By using bounded Lipschitz functions for wa,, Le.. we will show below that the gradient of Lx is L-Lipschitz. It is indicated by Daskalakis and Panageas (2018) that GDA with y S 1/L avoids
unstable critical points for almost all initialization, which means that (0 02 0g) (2)) is unlikely to cycle & grows. Furthermore, any stationary point yielded by GDA with large 7 is basically local minimax point except degenerated case (Jin et al., 2020), and thus the convergence guarantee of Algorithm [] Here, a solution (0T, 07 0%) is local minimax if there exits dg > 0 and a function h satisfying lims-o (()6) - 0 such that vS E (0,do), and any (01, 02, 03) satisfying ||[01, 02) [0 eilll2 I 5 and ||0g 0% l2 s fu()), it holds that:
(1 02], 03) < Lx (101, 02) 03) < max 0, 03 (1))
Lx (10), O2]. 03).
In other words, by using the two-time-scale GDA algorithm with a small 77 and large y our re- sulting solution has similar role as a local binimum//maximun in minimization/maxiiizatiii problem - the global Nash equilibrium, any, must be one of the solutions yielded by the GDA in Algorithm
Proof. Here, we show that if we,, fe, are bounded Lipschitz functions and ge, is a Lipschitz func- tion, the gradient of the minimax objective is also Lipschitz.
Recall the objective function in (6), i.e.,
Cx [2][ 02),
Σ wwi (m) (u,))D
+
Σ wwi(O2) (0s
Σ
reco i; fe.) (0s)
(u,i)D
(u,))D
straightforward to show that:
aLx
Ie Hem
@reco i; fo,)
Σ
weil (02)
(02)
- Σ gui(Oz)
001
001
00,
(u,jeD
(u,i)ED
OL,
@wni (02)
Owai (02)
Σ
lue(fo,)
A Σ
(O))
002
002
002
(u.))D
(u,))D
0Lx
Og
Ogai (0a)
00,
=
Σ (L.))D
Wus( (02)
00,
reco (u, i; fo,)
00
(M,))D
We impose few assumptions on fo, Wms (0)) and Jui (fz). First, we assume they are bounded and their gradients are Lipschitz functions, which are standard assumptions for neural or factorization models. Then, with a careful selection the loss function E (e.g..logistic loss, exp-loss, probit loss) and the reco function (e.g., top-K), we can ensure (ni(fe, and reco i; fo, to have Lipschitz gradients. Finally. by employing clipping tricks on the gradients to ensure they will not explode, which is also common practice, we have universally bounded and Lipschitz functions that include:
fe. War (2), qui (Q))
(Je,) re),( (w.,(02) 00,
gui (g)
00,
00,
00:
Therefore, the products and summations of these function a I- Lisshiitt function for some positive constant L.
B LEMMAS AND PROOFS
In this part of the appendix, we state the important lemmas that we used in our proofs.
Lemma A.1 (Empirical Bernstein bound). Suppose that E Z > [o, 1] without loss of generality.
Q(u.i) and Z ....... ... Zn sampled i.i.d from P. for any 8 > 0, it holds with probability With w u, i) P(a.))
23

---

Published as a conference paper at ICLR 2022
at least 8 that:
7M log
2 ( lo)
RQ S Ep....
g
3n
n
where = u (z.))
The result is modified from Corollary of Maurer and Pontil (2009).
Lemma A.2. Let P and Q be the training and target distribution supported on Sp, SQ S DD and Q(a.3) w(u, i) P(u.aj. P(a for (u, i) E Sp n nSq. D, consists of training instances sampled i.id from Given single hypothesis f F, suppose Wui y. any 8 > 0, it holds with probability at least 1- that:
2M log EQ I EP.... R(f)
1
2d(P)I log
+1
3n
n
where d(PllQ) = -so (dP/dQ)dP.
The above result for importance weighting of single hypothesis stated in the Theorem I Cortes al. (2010).
Lemma A.3, be real-valued convex functional defined on a convex subset Q of a vector space X, and let G be convex mupping of X into a normed space Z. Suppose there exists X1 such that G(x1) < p and that inf {f(x) :G(x) p; x E 21} is finite, then it holds that:
inf G(x)SpXER
max inf (f(x) + (G(x),z")}
x 2P. xei
The above Lagrange duality result is stated in Theorem 8.1 of Luenberger 1997).
Lemma A.4 (Lower bound based maximum variance). Suppose f E F takes values in [0. 1] without loss of generality, and the variance of f denoted by o² Let o(F) supsEF (f),
and assume I o² (g) < +00. holds that:
Epf Ep.f
TP sup JEF o(F)
2c>0.
2/ml
The result is stated in Theorem 9 Cortes al. (2010)
Lemma A.S (Finite sample bound for I-Wasserstein distance). Suppose and Q are supported on (perhaps non-overlapping subsets of) 2 where 2 E RRd and is bounded. Let MG
supg:lallag1 supzez Oz)). For all > 0, it holds with probability at least 1 - 8 that:
Cw dw (P,Q) dw (Pn, Qn) n1/(d+1)
log
+ 8Ma
n
Proof. The first part of the proof follows from the result on integral probability metric stated in Theorem of Sriperumbbuurr et al. 22099). that for G {g: I|gllz S 1}. we have:
223 log 1
gdP / gdQ] sup /f gd.,. gdQ..] s 61 gEg
sup gEG
(9),
with probability at least - 8, and (g) is the empirical Rademarcher complexity of Using the entropy integral bound on the empirical Rademarcher complexity, we have:
Rn( S 2c 4 I
Vn Je/1
Note that Rdd implies: N(u, 2. .1 |1x) = O(u-)) Using the fact that log(æ + 1) S x + 1, we
have: log (u, G, (P.)) < log Nuu, 9. /1,0) I ciu -d++1) + czu-d. Since is bounded, the entropy integral bound becomes:
4/2
4diam(2 2)
RT) < inf 2c
V (d+t) ddu
<0
Vn
Je/4
which directly leads the desired bound where co is the corresponding constant.
24

---

Published as a conference paper at ICLR 2022
Lemma A.6. Let c(z, 11 2.12. Define:
f" = arg min
min JEF (Q.((Q.P)5
EQ and X = arg max (Ap Ee-pl inf py. + A c(z, o(z, REZ
A=0
1(())1((() c(2,z')
all is i.e. supz,x'
S L, then it holds: X S L.
Proof. Using the Lipsehitz property, we have:
X'p X Egrp inf l (2) +x* c(z, Eg. (z)
always
2 -Xp + BeNP inf f (2) + X czz 2) ey- (z)
(by the definition of X
1EZ
2 -Ap + Ex ExNP P
c(z, 2) + c(2,
2 -Xp inf Lt At}
10
2 Lp ( (by choosing X = L),
which gives X S L.
Lemma A.7 (Change of measure inequality). For any and Q on X, and for any measurable function f X + R, it holds that:
Er~Q S dxL(Pl))) + in (Bx-pe)(a)).
This is standard result that has been included in many textbooks for probability.
Lemma A.8 (Interchange of integration and minimization). Let X be space of measurable functions from TR" with respect to u, a a o-finite measure on the underlying space. Let Z Z R + R be normal integrand, then it holds:
inf / f(2,2(2))ll2 REX
inf x(txx))(d2)
xER"
The result is simplied from Theorem 14.60 of Rockafellar and Wets 2009).
C COMPLETE EXPERIMENT SETTINGS, NUMERICAL RESULTS, AND REAL-WORLD DEPLOYMENT AND TESTING ANALYSIS
We provide the complete experiment settings (real-data and simulation experiments), including the data description and preprocessing, experiment setups, model configurations and training details. The complete numerical results and analysis are also presented in this part of the appendix. Finally, we discuss the real-world online experiments by deploying our solution to a e-commerce platform.
The implementation code for the real-data and simulation experiments provided in the supple- ment material. All the reported results are averaged over ten independent runs.
C.I DATASET DESCRIPTION, PREPROCESSING AND EXPERIMENT SETUP
The detailed descriptions for the three real-world benchmark datasets given below.
The dataset provides the users' ratings for movies that they watched, which consists of around million ratings collected from 60,40 users on 3,952 movies. The movie ratings are ranged from I to 5, where higher rating indicates more positive feodback. Hence. the original Movielens-IM dataset possesses explicit feedback. The traditional way of converting the dataset to implicit feedback is to set the rating cut-off at 3, as suggested by He et al. (201)). We use the explicit feedback for semi-synthetic experiments, and use the converted explicit feedback for the real-data experiments.
Movielens-IN 1M
25

---

Published as a conference paper at ICLR 2022
La
The context of the LastFM dataset is music recommendation: each of the 1,892 listeners (recorded in the dataset) tags the artists they may find fond of overtime. Since the tag is a binary indicator, the LastFM is implicit feedback dataset. There is a total of 186,479 tagging events, where 12,523 artists have been tagged.
GoodReads The book recommendation dataset is obtained from the users' public shelves on Goodread.com. We use the user review data on the history and biography sections for their richness. There are in total 238,450 users, 302,346 unique books, and 2,066, 193 ratings in these sections. The rating range is also from to 5, and a higher rating indicates more positive feedback. We concert the dataset to implicit feedback in the same way as the Movielens- IM dataset for the real-data experiments.
|
Data preprocessing. As for preprocessing, we point out that the Moviclens- IM dataset has been filtered by the publisher, where each user has rated at least 20 movies. For the LastFM and Goodread datasets, we first filter the infrequent items and users who have less than 20 total interactions as well.
C.I.1 SIMULATION SETTING
We generate the implicit feedback (clicks) according to the click model of: P(Y 1) P( 1) P(O..; = 1), where R., and On: indicates the relevance and exposure. We refer to P(R.. 1) as the relevance score. To carry over the inductive bias of the benchmark dataset to the generated data, we first learn PR... 1) and P(Ouus 1) from the explicit feedback data of Movielens- IM and GoodReads. Our simulation approach does not apply to the LastFM data because it lacks the explicit feedback.
Since the ratings are explicit indicators for relevance, we directly conduct the matrix factorization collaborative filtering (MCF) using the ratings the response. We then estimate Pi (Rui 1) via (R.,, - u)P. where (-) the sigmoid function, and and p are the two hyperparameters that help us control the overall relevance distribution between the original and generated data. For both Movielens- M and GoodReads, we find we inherit the inductive bias for the relevance to the simulated data.
and p = 2 gives decent approximation. In this way,
As for the exposure, we first assume all the exposed movies/books are rated by the user, so we have Ou = 1 if and only if Yui > O. We then conduct another MCF using the converted O., as response, and obtain the user and item embedding: +(u), (t). We further design the exposure model by Psim (Oni 1) (MLP(( ((i))), where MIP(-)) is three-layer feed-forwart neural network with ReLU activation and no bias terms, whose parameters are given by the random normal initialization.
In the sequel, the simulated click probability is given by: Pism(aa.. = 1) = Pam (Rus = 1)
Fsim (Ous 1), from which we generated the click data by picking the cutoff probability that ensures the click v.s. non-click proportion of the generated data matches that of the original data.
C.1.2 TRAIN-VALIDATION-.
SPLIT
We adopt the widely-ackkowlleded approach for splitting the dataset to training, validation and test- ing as He et al. (2017) and et al. (2020). In particular, we leverage the ordering information and use the last interaction of each user for testing, the second-to-lass interaction for validation, and the previous interactions for training. All three datasets are provided with the ordering information, so we use the same splitting mechanism. For the semi-synthetic dataset, since the simulation does not account for the ordering information, we treat the ordering random and conduct the splitting in the same fashion. We point out here that using sequential recommendation models is not reasonable in this case, we do not experiment with the attention models (Attn) in the simulation experiments.
C.1.3 EVALUATION
As we discussed in Section 6, the three metrics that we use for both the real-data and semi-synthetic experiments are Rel @ K. NDCG@N @ and Recall @ K. We also adopt the widely-acknowledee. for-
mulation of NDCG@K K and Recall K as from He et al. (2017) and Rendle et al. (2020): for
26

---

Published as a conference paper at ICLR 2022
each positive instance (clicked data) of (u', f', Yu' 1). we randomly sample 100 negative items fii...., } and compute NDCG@K and Recall K. according to where i' is ranked among the total of 101 items. We point out that the recent work by Krichene and Rendle (2020) points out the potential bias issue of using the sampled metries; however, it is still the mainstream approach that is used in the majority of existing literature. We apply them here our results can be directly compared with the results in the relevant literature. To make up for the bias issue of using sam- pled metric, we further consider the Rel@K metric, which ranks all the items {ii..... | and see where i' is placed for each u'. In this way, we eliminate the bias of using sampled metric. Essen- tially, Rel@ K equals Recall @ K with no sampling when each user interacts with only one item in the testing data (which happens in our experiments by the way we conduct the rein-validation-tess split).
The only difference in computing the three metries for the real-data and semi-synthetic experiments is that we replace Yu'r by the underlying relevance score of F. (Ra'r 1). In this way, we obtain a more accurate characterization of the actual testing performance. Finally, for the MovieLens and
Goodreads datasets, we adopt the tradition that the sreviously-interaete items are not considered during the evaluation for each user. This is because in practice, the same movie or book should not be exposed to the user repeatedly.
C.2 MODEL CONFIGURATION AND TRAINING
We provide the model configurations, training and computation details in this part of the appendix.
C.2.1 MODEL CONFIGURATIONS
To achieve a fair comparison, we fix all the user and item embedding dimensions to 32 for the CF models and sequential recommendation model. For all the baseline models, we select the initial learning rate from (0.001, 0.005, 0.01, 0.05, 0.1). and the lg regularization parameter from {0, 0.01, 0.05, 0.1, 0.2, 0. The tuning parameters are selected separately to avoid excessive computations.
The other hyperparameters are identified according to the original papers as for the model-specific configurations, other than the embedding dimension, learning rate, and & regularization. For in- stance, NCF considers the hidden dimensions of the feed-forward neural network as the hyperpa- rameters, IPW-CF considers the IPW threshold, Atnn considers the hidden dimension and number of attention blocks, AC-MF considers the adversarial strength of the IPW component. We use the same range as provided in their published implementations, which we discuss later in Appendix C.2.2 When implemented with our aamsporraaiinn-rgulaiize using the same "base model" for f. w and g. c.g. with MCF, NCF Attn. In fact, we can pick any combinations for f. w and g. but we find the performances comparable to using the same "base model", so we randomly pick some of the configurations to report, instead of exhausting all the possibilities. Finally, the hyperparameters of the "base models" persist to our setting, in addition to the penalization parameter (in eq. (4), which we select from (0.005, 0.1, 0.3, 0.5).
risk minimization, we focus primarily on
C.2.2 TRAINING DETAILS
For both the proposed approach and the baseline methods, we adopt the widely-applied negative- sampling-bast training schema according to He et al.] (2017) and Rendle et al. (202)). for both the real-data and simulation experiments. In particular, for each positive instance (Yui 1), we randomly sample three pairs of user-item tuple and treat them as the negative instances. We point out that in many existing literature, the number of negative samples per positive instance treated as a tuning parameter. Here, we treat it as a fixed quantity and focus on tuning the model-specific configurations.
For all the experiments, use the binary cross-entropy loss function for classification, and apply early stopping during training when the Rel@ K metric does not improve for more than five epochs. We record the model parameters after each epoch, and select the one that achieves the best validation performance for testing.
Transportation-rrgulaiiie risk minimization. When training with the proposed approach, the discount of learning rate (in Algorithm| [ is critical for the two-time-scale GDA. In a sense it re- sembles the number of gradient updates under the same learning rate, and we focus on their relative
27

---

Published as a conference paper at ICLR 2022
ratios. In practice, allow the model of t in the minimization step to have learning rate different from that of f. We denote the ratio for f. w and g as step,, step,. and step,. In practice, we select
the ratio among {1 : 10, :: 10, 1 : 10: 10, 1 : 10: 5) for our experiments, and the sensitivity analysis is provided in Appendix C.3.1
Baseline models. The popularity (Pop) baseline is implemented with off offthhe-hheff code, the MCF and NCF models are implemented according to their original implementation published on Githut f the IPW-debaised MF (IPW-MF) and user-exposure aware MF (ExpoMF) models are implemented using their published code with necessary modifications. The aaterssaria--couneeffttuulll MF (AC-
MF) method is also implemented using the published codo [9] which we apply directly to our datasets. The sequential recommendation model with attention mechanism is also implemented according to the original code [0] We point out that most of the implementation provided by the authors include the set of hyper parameters they found optimal in their experiments. We re-select those hyper parameters in each of our settings.
As for the doubly robust joint learning (DR-MF) approach (Wang et al. 2019), the method was originally proposed for the bandit feedback setting or when the feedback data is explicit and the propensity scores can be effectively estimated. Since we focus on the implicit feedback setting, we use the clicks to estimate the propensities, and plug it to the DR approach. The causal embedding approach (CE-MF), on the other hand, assumes the access to a uniform exposure dataset. The authors propose workaround to construct such data from non- uniform-expoosseeeee (Bonner and Vasile, 2201)) however, they take advantage of the explicit feedback (rating). Since we only have implicit feedback, we random subsample the click data and treat them as if they are from the uniform exposure.
feedback data
Computation. All the models are implemented with the auto-differentiatiion framework of Py- The computations are conducted on a Linux cluster with 2 Nvidia V100 GPU machines (each with 32 Gb memory) and 32 CPU with a total memory of 100 Gb. We use the sparse Adam [2 optimizer to update the hidden factors (user and item embeddings), and the usual Adam optimizer to update the remaining parameters. This is because both the user and item embeddings are rela- tively sparse in the datasets. Therefore, the Adam algorithm, which leverages the momentum of the gradients from the previous batch, may not be ideal for updating the item and user embedding in the current batch. The sparse Adam optimizer address the above issue.
Torch [1]
C.3 COMPLETE NUMERICAL RESULTS
Table A.I: Additional testing results MovieLens- IM. The settings of this table follow from Table DTT((M/M/N), for instance, indicates using the proposed method with f and MCF, w as NCF and g as NCF. We highlight the best results.
DT-NN/
(M/MN))))
DT-(N/M/M)
DR-MF
CE-MF
MovieLens-IM
Rel@10 10
(.I1)
14.63 (.10)
14.52 (.08)
14.28 (.12)
14.17 (.08)
@it@ 10
62.34 (.20)
63.02 (.21)
62.18 (.19)
61.03 (.16)
61.22 (.18)
NDCG@ 10
32.75 (.11)
33.21 (.23)
32,90 (.16)
31.97 (.08)
32.04 (.07)
Moviel Lens Simulation
Rel@ 10*
4.62 (.03)
4.67 (.02)
4.84 (.04)
3.89 (.03)
3.91 (.02)
@it@ 10
79.89 (.17)
79.80 (.15)
79.83 (.20)
75.99 (.10)
75.69 (.12)
NDCG@10 10
39.98 (.10)
39.94 (.11)
40.57 (.11)
38.38 (.07)
38.21 (.06)
We present the complete numerical results in this part of the appendix. We start with the testing performance with respect to the methods for MovieLens- 1M that are not shown in the main paper due to the space limitation.
wttettiiieeeiieieeeeeeeeeeeeeeee filtering for IPW-MF and https:
htsthh/.ccm/aaaee//////miii///// ExpoME
ht
https://pvtorch.org/
28

---

Published as a conference paper at ICLR 2022
Table A.2:
Simulation experiment results for the Goodreads simulation. The settings and interpre- tations are the same as T I
We highlight the best results.
Pup
IPW-MI
ExpoCT
AC-MI
MCF
DT-MCT
NCF
DT-NCI
GoodReads Synthetc
Rc
4.34 (.02)
4.62 (,09)
4.57 (,04)
4.68 (.10)
4.56 (.06)
4.78 (.06)
4.99 (.05)
5.13 (.07)
@it@ 10
42.75 (.04)
49.22 ((34)
48.97 (.26)
49.30 (.25)
48.06 (.25)
49,94 (.21)
52.47 (118)
52.96 (.21)
NDCG@10 10
23,20 (.02)
25,91 (.15)
25.76 (.17)
26.04 (.13)
25.25 (.15)
26.72 (.12)
28.17 (11))
29.78 (.13)
Table A.3: Additional numeric results for the variations of the proposed domain transportation meth- ods with different combinations of the f. g and w models).
DT-MNNNN) DT-(N/M/M)
DT-(M/NN) DT-(N/MM)
DT-(M/N/N) DT-NNMMM
GoodReads
GoodReads Simulation
LasIFM
@el@ 10
5,92 (.04)
6.28 (.05)
4.65 (.04)
4.95 (.06)
6.53 (.06)
6,38 (.07)
@ 10
58.48 (.22)
61.64 (.30)
48.97 (.26)
49.30 (.25)
81.09 (.33)
78.96 (.31)
NDCG@ 10
30.32 (.17)
36.32 (.22)
25,88 (.14)
28.61 (.13)
52.05 (.18)
51.37 (.20)
Additional results for MovieL_en-IIM and its synthetic data. In Table A. we show the addi- tional results for the MovieLens experiments, including using the proposed domain-tranp transooratttooooionnnno approach with different configurations of f. w and g (denoted by DTT((Fw/g)), Note that Attn does not apply to the synthetic data, because the ordering in the synthetic data is randomly generated as we mentioned previously. For notation, we use the short hand DT-(M/N/N), where in the parenthesis the assignments for f. and g, and M is short for MCF, N is short for NCF. Also, exper- iment with the doubly-robust joint learning approach on MCF (denoted by DR-MF) as proposed by Wang et al. (2019), and the causal embedding approach on MCF (denoted by CE-MF) proposed in Bonner and Vasile (211)). The two methods were proposed for the explicit feedback data, and we observe that while they are still able to improve the performance of MCF in our implict feed- back setting, their improvements are much less significant compared with the proposed approach. Also, it appears that the causal embedding approach suffers from high variances, which is due the workaround when constructing the "uniform exposure" dataset from implicit feedback data.
Complete results for the LastFM data. In Table A.3] we show the complete results for the LastFM experiments. We do not conduct the synthetic experiments on the LastFM data, because unlike the other two datasets, the original dataset consists only of implicit feedback. Therefore, neither the relevance nor the exposure and notations for our approach are the same as above.
be efficiently estimated from the data. The settings, interpretations
Complete results for the Goodreads simulation experiment. In Table A.2 and Table A.3 show the complete results for the Goodreads experiments. Similarly, Aun does not apply to the synthetic data for the same reason discussed above.
We then present the complete results in correspondence to Figure of the learnt weights on the Goodreads data and its simulation. In Figure A.2 show the same
In Figure A. we the analysis
set of analysis for the LastFM dataset. Finally, in Figure A.3 we provide the ablation study and sensitivity analysis on X, for both Goodreads and LastFM dataset.
C.3.1 SENSITIVITY ANALYSIS ON THE OPTIMIZATION SETTING AND OVERLAPPING
To ensure the convergence of the minimax optimization without being trapped in a cycle, it is standard practice to use the two-time-scale GDA algorithm. Our situation even more involved since we not only have minimax game, but there are two minimization players.
Intuitively, f moved only when Pu has approximated Py sufficiently well. means that w. has converged in the sense that dw(Pj, P..) is sufficiently small. Since we use the Monge and Kantorovich formulation to represent the 1-Wasserstein distance dw, i.e., (w sup 1 gdP Jp gdQ, we need to ensure g to converge every time w moves so that the integral difference is approximately equal dw (P,,Pw), In other words, this is lhyee-layer loops: when if moves one step. we need w to move step,., steps until convergence; when w moves one step, need g move step,, steps until convergence.
29

---

Published as a conference paper at ICLR 2022
Tyge
True Exposure Score
Frequency
Reco Score
225
-05
Recommended
-0.3
Poultive Nlgattive
-1.00
Learnt Weights
-030 -0.55
Learnt Weights
Learnt Weights
-622
a.0
DT-NCF
DT-NCF
.TF
Tyge Nog
0.50
Frequency
Roco Scote
-025
Thue Recommended
+0.00
Data Type Rootiiv
Nagaat ve
-1.33 -005
-2.00
Leamt Weights
-0.4 Learne Weights
-12
Learnt Weights
Figure A.I: Analysis on the learnt weights for the Goodreads dataset. The setting and interpretation of the figure follows from Fig. and Db in Section 5
DT-MCF
DT-MCF
Type Pas
-0.2
Frequency
Neg
Reco Score
-0.4
Type
Recommended Others
0.75
0.60
Learnt Weights DT-NCF
0.55
0.50
0.5
1.00
-1.0
0.0
Learnt Weights
29
DT-NCF
Type
-0.2
Reco Score
-0.4
-0.6
Type
Recommended
0.7
1.0
Leart Weights
0.70
675
abs 0.00
640
Learnt Weights
Figure A.2: Analysis on the learnt weights for the LastFM dataset. Note that the cemi-synthetic experiments are not conducted on the LastFM dataset. The setting and interpretation of the figure follows from Fig. and Th Section
Figure A.4h shows that as the step,,, increases when step, is fixed, the overall performance of our method Is boosted, which aligns with the above claim that w should converge before f moves. We observe similar phenomenon when step,, increases step,, is fixed, which corroborates the claim that y should converge before we moves. These results suggest that we might want to use large step,, and a large step,- However, can be computationally expensive. From our experience, we can use relatively large step, and slightly smaller step to achieve a good performance. In addition, appropriate choices of learning rates ir,, Irw, and Ir, can expedite the convergence of w and g so that we can use less steps.
C.4 ANALYSIS FOR THE COMPLETE RESULTS
We first observe from Table A.I that the sequential recommendation methods achieve overall better performances than the others. dataset is usually substantial, as point out by Kang and McAuley (2018). Similar to the previous experiments, DT-Attn improves the performance of the regular Attn model. As for the variations of methods, they all improve the performance of the corresponding model, and even outperforms
expected because the sequential signal in the MovieLens- 1M
30

---

Published as a conference paper at ICLR 2022
Goodreads
Goodroads Synthotic
LastFM
with rog Reg
with rop
Reg
Relig
Reli
(Wil) Rlag
MCT
MC7
Method
Method
Method
Goodreads
LastFM
VKCT
1.29
NCP
Re
Reigi1
6:50
5.55
0.2
lambda
0.3
04
65
lambda
2.3
Figure A.3: The ablation study the regularization component, and the sensitivity analysis on X, for both the Goodreads and LastFM datset. The setting and interpretation of the figure follows from Fig. T in Section 5
(a)
(b)
NOCO010
16.5
Pe
Valuo
16.5
16.54
Hetic Aewiigto
0..5
62.7
valuo
02.3
D DI000O
Matic gto
$2.75
Value
080060 006002
1:10
210
6.10
10:10
19.5
102
W_step : Stop
Propensity cutoff
Figure A.4: (a). Performacee of minimax optimization with different number of optimization steps for updating and g. The analysis is conducted the Moviel dataset. (b). Sensitivity analysis on the threshold of propensity score for IPW-MF. In the orignial paper (Saito et al.) 2020), the authors apply a threshold on the smallest possible propensity score as if there was sufficient overlap. Here, we vary the threshold to hypothetically generate the different overlapping scenarios.
the DT methods where f. and g the same "base model". This is phenomenon that worth future investigation, since the results might indicate the DT-(f/w/g) methods combine the strengths of the base models.
The results for the Goodreads and its simulation experiments in Table A.2 and Table A.3 show the similar patterns. Firstly, using the proposed transportation-rrggllaaaae approach improves the performances of the baseline methods, and the best results are achieved by our DT-X methods. Secondly, while the other enhanced MF/CF methods also improve upon the baseline MCF model, but their improvements are much less significant than the DT approach. Thirdly, the DT-(f/w/gg methods also achieve more significant improvements compared with the DT-f methods. We point out that the sequential recommendation method (Atin) does not particularly suit the dataset, since it is outperformed by the non-sequential methods. Still, DT-Att achieves better performances than Attn Finally, the additional results for the LastFM dataset in Table A.3 have the similar patterns.
As for the analysis on the learnt weights, we observe from Figure A. and Figure A.2 that the patterns discussed in Section 6 for the MovieLens dataset and its simulation holds almost the same for the Goodreads and LastFM datasets. Firstly, the learnt weights for the instances among the feedback data can be distinguished by whether the instance is positive negative. We observe that the positive instance tends to have larger weights than the negative instances, which means the weighting model is learnt to emphasise the "higher-quality" positive implicit feedback. Secondly,
31

---

Published as a conference paper at ICLR 2022
the learnt weights also get larger for the instances that will be recommended under f. and the larger the score of f, the higher the weights. means the weighting function works harder on balancing Pj with Par. which conforms to our design. Lastly, for the simulation, the learnt weights tend to be larger for the negative instances with higher exposure probability, which can be considered the strong negative instances. This is because they are more likely to be exposed but not clicked.
C.5 EFFICIENCY ANALYSIS
Recallgg0,
Relg Movielens
medell DT-MV
44154
OTMF NCF
030
Thaining Times (nwcod)
Traiing Time (second)
Taining Time (eecad))
Figure A.5: Analysis on the efficiency of the proposed approach. We report the training time (on the x-axis) and the per-epoch evaluation results (on the y-axis), using the Movielens-IM data as examples. We compare between the original MCF and the DT-MF approach, and when training both models, all the model and data configurations are kept exactly the same.
In terms of the space complexity, it is evident that our approach need to store the parameters and gradients of the f, w, and g models (if no parameter sharing is considered). For the time complexity, however, the proposed approach is highly efficient due to the following reasons.
1. As it is shown in Figure A.5, although the DT-MF approach has a larger per-epoch training time, it makes training progress much faster than the original MCF thanks to the rewieghting and DT regularization. For the Movielens dataset, DT-X catches up and outperforms X couple of training epochs even before the X model converges.
The update of w, and g can be efficiently parallelized.
3. Our approach does not change the inference time since only the f component will be used for evaluation and testing. just like when using / alone.
C.6 DEPLOYMENT TO HEAL-WORLD IR SYSTEM AND ONLINE TESTING
An important motivation of our work is to solve the practical challenges of industrial IR systems, and the working mechanism we described in Section | applies to most settings. In particular, many deterministic, and to the customers due to the limited slots and business requirements. For many industrial tasks, the revenue is directly related to the performance of recommender since unqualified recommendations may hurt customer satisfaction severely. Therefore, the feedback data often covers extremely limited support of the product space. It causes realistic dilemma:
real-world recommenders
only expose tiny proportion of the catalog
if the candidate recommender / recommends products very differently from the previous exposure, then the feedback data may not provide enough evidence assert the perfor- mance of f:
if the candidate recommender / recommends products highly similar to the previous expo- sure, then f will inevitably inherit the various data bias.
From this realistic perspective, our approach aims to find the right balance between the two extremes: the weighting model helps to reshape the feedback data domain (to better fit the objective risk), and the regularizer enforces to be sufficiently close to the reshaped feedback data domain. To test the competence of approach for industrial tasks, apply the proposed domain transportation approach to an industrial recommendation task, and conduct online A/B/C testing to examine the real-world performance.
The context of our task is to recommend items that are similar to the current webpage's 's product for major e-commerce platform in the U.S. The platform hosts more than hundred million products
32

---

Published as a conference paper at ICLR 2022
Recall
NDCG@2 20
CTR
D& W (control) +0.0
+0.0
+0.0
IWW-D&W (variationl) +0.23%
+0.06%
+0.05%
DT-D&&W (variation2) +0.56%
+0.09%
+0.07%
Table A.4: Offline evaluation of the three models used in the online A//C testing, Due to pri- vacy reasons, we are only able to report the relative lift percentage with respect to the baseline. We use D&W to represent the original deep&wide control model, IW-D&W to represent the approxi- mate poopensity-weightee approach when coupled with the wide& model. * the CTR is computed using the history ex- posure log and the past estimated CTR, similar how computed the relevance score Rel in the benchmark and simulation experiments.
version, and DT-D&W to represent the proposed domain transportation
Figure A.6: Online A/B/C testing results for the similar-item model under direct training (control), IPW-adjusted training (variation 1) and the proposed paasportation-constaiiee risk minimization (variation2). The first plot shows the daily gross merchandise value (GMV) lift, and the second plot shows the overall lift of GMV, number of units per checkout (UNITS), number of orders per visit (ORDERS), and the total number converted visitors (CONVERTED VISITOR).
ranging from high-end electronics daily grocery. Each item has its contextual features, including rating, price, taxonomy, etc. The pre-trained embeddings are also available for the items obtained from modified version of the SGNS algorithm. When applying the item embedding the model, we use the pre-trained embeddings initialization and update the parameters with lower learning rate than the other model parameters. We employ an architecture that is similar the classical Deep- and-wide model, initially proposed by Chenng al. (2016) for recommending YouTube videos, with the difference that we do not use the real-time features here.
We trained three versions of the deep-and-wide model offline:
control: directly training f using the implicit feedback data;
variation1: first training an exposure model using the past exposure log, apply its normal- ized version (for controlling the variance) as the weighting function w, and then train f in way similar to the baseline IPW-MF mentioned in Section
variation2: train using the proposed transporiation-reeullriie risk minimization, where w and are neural CF models that take the item embeddings input.
All three versions are trained under the same setting. We deploy online A/B/C testing to examine the real-world performances, and the monitored metrics and testing results are provided in Figure A.6 We see that our causportation-regulaiiin the original model (control) and the IW-adjusted model (variation in term of the gross merchan- dise value (GMV), which is the most critical metrie for industrial recommender system. Also, the proposed approach improves the other monitored metrics (lower panel of Figure A.6) more signif-
risk minimization (variation2) consistently outperforms
33

---

Published as a conference paper at ICLR 2022
icantly than the IW-adjusted model. Our deployment results further suggest the capability of the proposed approach for improving the performance industrial IR systems.
D EXTENDED LITERATURE REVIEW
When viewing our solution from the causal inference perspective, our objective resembles the coun- terfactual loss proposed by Shalit et al. (2017) focusing individual treatment effect, which was also discussed in the following work (Johansson et al. 2019; 2020). Further, JJohansson et al. (2019) studies from the domain adaptation perspective the issues of insufficient overlapping. Unlike these works where the target domain of interest is fixed in advance, IR systems get to choose the counter- factual world in which they want act. leads the main difference between our work and that line of research: we can control the domain in which the counterfactual risk is computed.
Recently, there has been fruitful research progress in off-py learning and data missing-not- -ot-at- random. Again, most existing methods treat the uniform-exposet domain as the target, while we aim at the deployment domain formed by the IR system. Further, most them require either suff- ciently randomized logging policy or explicit ratings in the feedback, while our approach is primar- ily designed for implicit feedback under deterministic policy. For instance, (Sachdeva (Sachece,Saccdeva et al. (2020) studied the overlapping issue for learning from bandit feedback. Similarly, the causal embedding approach (Bonner and Vasile 2018) requires access to a subset of randomly exposed feedback, and many others rely the explicit ratings to estimate the historical propensities (Wang et al. 2019 Saito 2020 Liu et al.] (2220). On the other hand, the interventional nature of IR systems is also discussed in Xiao and Wang 2021 but their solution is devised from the reinforcement learning setting.
The Wasserstein distance has also been employed by distribution-robuse optimization (DRO) (Kuhn eet al. 2019). For instance, Si et al. (2020) uses Wasserstein distance to assert certain robustness to the contextual feature distribution during bandit off-policy learning, and Faury et al.) (2020) proposes a robust counterfactual learning framework to handle the various uncertainties in bandit feedback data. Our work differs fundamentally from that research venue we use Wasserstein distance to regularize learnt policy (via constraining its deployment domain) rather than assert its robustness. Further, DRO methods often have a min-max formulation, while our initial objective tackle min-min problem.
2 and
34


Reviews:
[{"review_id": "td5FGU78LE", "reviewer": "Reviewer_n8vS", "summary": "", "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": "The paper is well written and easy to follow. Generally, the overall framework is novel. The authors give some theoretical analyses to the proposed transportation-constraint risk minimization. Extensive experiments are conducted to show the effectiveness of the proposed methods. \n\nMy major concerns and questions are as follows:\n\n(1) The motivation is not clear to me. One of the claims of the paper is that the proposed algorithm can address the insufficient overlapping problem. However, the authors do not give a clear motivation of why this problem is important in real-world RL systems and why the proposed methods can address this problem.\n\n(2) The theoretical analyses are not clear and lack interpretations.  Proposition 1 is good to show that IW and DA can not address the insufficient overlapping problem. However, Theorem 1 & 2, Claim 1 and Theorem 3 are not clear.  Specifically,  Theorem 1 and Theorem 2 are only the finite sample bounds under $P$ but not the transfer generalization bound w.r.t the target distribution $Q$ like Proposition 1. It is unclear to me why  Theorem 1 and  Theorem 2 can resolve the insufficient overlapping problem mentioned for using DA in the IR system. For Claim 1, I think the left part in the equation is $\\min_{d_{W}(P_{w}, P_{f}) \\leq\\rho}\\mathbb{E}_{P_w} R(f)$ \n\nnot the risk  $\\min_{d_{W}(P_{w}, ~P_{f}) \\leq \\rho}\\mathbb{E}_{Q} R(f)$ under the target $Q$. Thus the Claim 1 is also irrelevant to the target risk.  Theorem 3 indeed gives the generalization bound under the target domain, but it does not clearly show the proposed method can address the insufficient overlapping problem of IW and DA in Proposition 1.  Given above, I think the theoretical part is not well written and it would be great if the authors can provide some interpretations of the theoretical results. The presentation in these parts of the paper could be improved. \n\n\n(3) The literature review is not very good, and the context is missing about how the research work stands in the agenda of each subfield such as Wasserstein Robust Optimization, Unbiased Recommendation, Off-policy Learning and Causal Inference with Missing data. For instance, the authors miss some important related works [1-7] with deficient support in logging policy and unbiased learning in recommendation. The authors also need to discuss the differences between this paper and other Distributionally robust optimization papers with Wasserstein distance in terms of the generalization bounds. This paper does not make a clear connection with the presented theoretical results and contextualize this work in the existing literature. It is difficult to figure out what's new and what's already a part of the existing literature. \n\n(4) The experimental comparison is also not sufficient. This paper lacks some baselines and results on benchmark datasets.  The comparison should also be done with some DA [8] and advanced IW methods [2]. The authors also need to evaluate their methods on Yahoo and Coat datasets which are the benchmark datasets for counterfactual learning in the recommendation.  A more detailed analysis of the time complexity would be desirable.\n\n[1] Off-policy bandits with deficient support. KDD 2020.\n\n[2] Doubly Robust Joint Learning for Recommendation on Data Missing Not at Random. ICML 2019.\n\n[3] A General Offline Reinforcement Learning Framework for Interactive Recommendation. AAAI 2021.\n\n[4] Distributionally Robust Counterfactual Risk Minimization. AAAI 2020.\n\n[5] Asymmetric Tri-training for Debiasing Missing-Not-At-Random Explicit Feedback. SIGIR 2020.\n\n[6] Distributionally Robust Policy Evaluation and Learning in Offline Contextual Bandits. ICML 2020.\n\n[7] A General Knowledge Distillation Framework for Counterfactual Recommendation via Uniform Data. SIGIR 2020.\n\n[8] Causal Embeddings for Recommendation. RecSys 2018.\n", "summary_of_the_paper": "In this paper, the authors study the domain transportation issue in information retrieval (IR) systems. The main challenge is the insufficient overlapping problem. The authors propose a new adversarial learning method based on transportation-constraint risk minimization to address this challenge. The main insight behind this proposed method is that the interventional impact of recommendation is not exclusive to observed data, but also interferes with the target domain of interest. The authors first analyze the generalization bound of IW and DA methods, and then further give the consistency, generalization, and excessive risk bounds of the transportation-constraint risk minimization. The simulation, real-data analysis, and online experimentation show the effectiveness of the proposed method.", "summary_of_the_review": " I think this paper is potential. The proposed domain transportation strategy for the recommendation is quite interesting. I suggest the authors focus on this part and give more discussions about the motivation, interpretations, and related works. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hg0fdY41_aj", "reviewer": "Reviewer_Lm9j", "summary": "", "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": "Pros: \n\t1. This paper identifies and tries to tackle an important problem in recommender systems - insufficient overlapping. The theoretical proof is given to show the uncertainty of the results.  \n\t2. Generally speaking, the paper is well-written and well-presented. Though many mathematical theorems are contained in this paper, it is easy to follow for readers.\n\t3. The proposed method is novel and can inspire future research in recommender systems. \n\t4. The experiments are sufficient to validate the claims.\n\nCons:\n\t1. There are some small typos that should be fixed before publication. \n\t\t1. In claim 1, E_Q R(f) should be E_Pw R(f).\n\t\t2. In Table 1, the Hit@10 of DT-MCF on LastFM is 81.81(20). I am confused as 20 is pretty high, and maybe here is (0.20) or (.02).\n\t\t3. In Section 5, we randomly sample m < |I| items and see if i' is among the top-K of these m items. items should be unrelated items. Also, the same questions occurred in other parts. I suggest to double-check that.\n\n\t2. \\mu is also an important hyperparameter, and authors also mentioned that a suitable \\mu will give us the opportunity to better explore the whole feedback data. I recommend that the parameter sensitivity of \\mu should be conducted. \n\t3. The main contribution is to address the insufficient overlapping problem that causes the uncertainty of IW and DA-based methods. However, in the experiment part, IW and DA-based methods are not compared with. I recommend that DT-IW and DT-WA should be included.\n\t4. The motivation is somehow unclear and the presentation of introduction could be further improved. A more detailed explanation about the relationships between intervention and domain adaption, intervention and the proposed method, why the proposed method can address insufficient overlapping problems, etc should be introduced. \n", "summary_of_the_paper": "In this paper, the authors first point out that the requirement of efficiency of IW- and DA-based methods is the overlapping between the source domain and target domain. Meanwhile, theoretical analysis also shows that insufficient overlapping problems can cause the hardness or impossibility of IW- and DA-based learning methods. In light of this, this paper aims to propose a novel method to optimize recommendation results by solving such insufficient overlapping problems. Specifically, a principled transportation-constraint risk minimization objective function is devised to optimize the recommendation results, which is able to transport the learned patterns from the source domain to the intervention domain better. Then a two-layer adversarial model (GDA) is deployed to optimize the transportation-constraint risk minimization objective function, and sufficient analysis of the GDA is provided. Extensive experiments were conducted on both real datasets and semi-synthetic datasets to show the superiority of the proposed method.    ", "summary_of_the_review": "The novelty of this paper is high.  However, the motivation is not quite clear, and  more IW- and DA-based methods are expected to compare in the experiment.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "chyjwblC5aS", "reviewer": "Reviewer_j5tz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* The subject of the paper is quite relevant and the identified issue of non-overlapping support for RW recommendations serious\n* The application of existing methods from causal inference to deterministic recommendation policies is valuable and the empirical section is well-developed and the results significant \n\nWeaknesses:\n* The motivation for the particular approach is not extremely clear. The authors build the argument around “transportability of patterns”, but I feel the point is never fully explained. If an action is never taken under a certain context in the past, (meaning is in the non-overlapping set), the algorithm will have to extrapolate the outcome. In order for the extrapolation to hold some assumptions need to be made about the reward model, and I find the authors do not really spend time on this.\n* The resulting objective is closely resembling the counterfactual loss proposed in [1], eq. 3. I think the authors should expand on this approach in the related work, and highlight that unlike in the cited work, they can choose the counterfactual world in which they want to act. Furthermore, I think borrowing either the counterfactual notation or the policy learning notation and vocabulary would help quite a lot in explaining the approach.\n\n\n\n", "summary_of_the_paper": "The authors propose a novel way to learn new recommendation deterministic policies from feedback collected under different recommendation policies.\nThe authors start by pointing out that the majority of current approaches, either Counterfactual (Inverse Propensity Weighting) either Domain Adaptation-based, \ndo not work well when the support of the current and future recommendation policies do not fully overlap (one of the main causes being that the current recommendation is deterministic and therefore not exploring all actions).\nTo this end, the authors propose a novel way of re-weighting and regularizing empirical risk that encourages the search for policies that have better reward (lower risk) and are still overlapping in evidence with the current policy.\nTo escape the support issue that is present in the existing approaches, the authors switch the regularization parameter to an IPM metric (WASSERSTEIN) that can handle non-overlapping supports.\n The authors provide both theoretical and empirical evidence that the resulting algorithm outperforms existing SOTA methods.", "summary_of_the_review": "Overall, I liked the paper and I found the approach interesting. I think the authors should link their approach a lot more to the work presented in [1] and also covered in two of their references [2,3].\nI think by doing so, it clarifies that the main difference in the problem domain is that we are in control of which of the counterfactual worlds we want to compute the risk in. \nOtherwise, all of the vocabulary and the core explanations of the soundness of the approach remain the same.\n\n[1] @inproceedings{shalit2017estimating,\n  title={Estimating individual treatment effect: generalization bounds and algorithms},\n  author={Shalit, Uri and Johansson, Fredrik D and Sontag, David},\n  booktitle={International Conference on Machine Learning},\n  pages={3076--3085},\n  year={2017},\n  organization={PMLR}\n}\n\n[2] F. D. Johansson, D. Sontag, and R. Ranganath. Support and invertibility in domain-invariant representations. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 527–536. PMLR, 2019. \n[3] F. D. Johansson, U. Shalit, N. Kallus, and D. Sontag. Generalization bounds and representation learning for estimation of potential outcomes and causal effects. arXiv preprint arXiv:2001.07426, 2020. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YAn9tTBsAXZ", "reviewer": "Reviewer_ozid", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper views recommender systems from a new perspective, which is similar but different to existing works in causal collaborative filtering. The theoretical analyses are comprehensive. The experimental studies are conducted in synthetic data, offline data and online data, which can well demonstrate the effectiveness of the proposed method.\n\nI have the following questions/concerns about this paper:\n1.\tIt seems to me that the proposed method can outperform IW methods when the overlap between the source and target domains are insufficient. However, there is no measurement about the insufficiency. It will be better to have some theoretical or empirical analysis about how the overlap between different domains can affect the performance.\n2.\tIt is hard to directly compare the bounds derived by the paper, e.g., between Theorem 3 and Proposition 1. This will be important to intuitively understand the advances of the proposed method.\n3.\tThe online evaluation used the Deep and Wide method. But the same method is not evaluated in the offline setting, which seems unreasonable.\n4.\tThe proposed method tries to optimize recommendation algorithms via a minimax game, which could be much more complicated than other baselines. Thus, it would be necessary to analyze the efficiency of the proposed method in the experiments.\n", "summary_of_the_paper": "This paper proposed a new perspective for recommender systems: rephrase optimizing recommendation as finding an intervention that best transports the patterns it learns from the observed domain to its intervention domain. To optimize the recommendation algorithms in this setting, the authors proposed a transportation-constraint risk minimization objective and convert it to a two-player minimax game. Theoretical and empirical studies demonstrated the effectiveness of the proposed method. ", "summary_of_the_review": "In summary, this paper targets at an interesting problem and shows promising theoretical and empirical results, which could be helpful for the community of recommender systems. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presented a domain transportation perspective on optimizing recommender systems. The basic motivation is to view recommendation as applying some form of intervention, implying a distributional shift after the recommendation/intervention. Distribution shift brings tremendous difficulty to traditional causal inference or missing data theory perspective of recommender systems as it violates the distributional overlapping assumption: in simple terms, if the model recommends radically different set of items, there isn't much you can say about its generalization ability; on the other hand, if the model only recommends items that it already observed during training (no distribution shift at all), it would inherent all the biases which already exist in the data. To that end, this paper proposed a domain transportation perspective by introducing a Wasserstein distance constrained risk minimization to find interventions that can best transport the patterns it learns from the observed domain to the post-intervention domain.

The paper received overall borderline scores. All the reviewers acknowledged that the proposed perspective is novel and has the potential to spark a new direction for future work. The reviewers raised concerns, ranging from the bounds in the paper, sensitivity of the optimization w.r.t. the hyperparameter, to some relevant but missing baselines. The authors provided very detailed response and revised the paper quite substantially to address most of the feedback. I also read the paper myself given the borderline scores, and I think the authors did a reasonably good job improving the paper and I agree this paper provides an interesting and novel perspective on viewing recommendation, though I also agree with one reviewer that the idea of "partially extrapolation" can be further explored. 

My major complaint is around experimental evaluation. It seems to me that only the semi-synthetic experiment actually makes sense in this context (where the measure is based on the unobserved relevance as opposed to observed click), as the traditional random-split-on-clicks evaluation would inevitably favor models with little distributional shift (the training and test data essentially come from the same distribution, maybe not so with a sequential setting but still close). Furthermore, the inclusion of Yahoo R3 and Coat dataset is even more confusing, as the associated test set implies random exposure which is certainly not what this paper aims to address, unless I am missing something in which case more clarification would be nice. 

My overall assessment of the paper is still leaning towards positive but I also wouldn't be too upset if this paper doesn't end up making it. However, if accepted, I do want the authors to carefully revise the presentation of the experimental results for the final version.
Decision: Accept (Poster)