Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 in 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 importance 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 (Schnabel 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 on 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-exploitation techniques including bandits and reinforcement learning (Auer et 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 of immediate satisfaction and revenue, even with the help of bandits or 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 a candidate hypothesis, even if DA or 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 a 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 extrapolation1 (Xu et al., 2021b).
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 we are about to make. For instance, the placement of a recommendation on the webpage proposed to the user directly influences the occurrence of clicks. Therefore, we alternatively consider optimizing recommendation as searching for an intervention that best transports the patterns it learns from the source domain to 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, intervention, and transportation, as depicted in Figure 1. 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 working 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-constraint risk minimization. We rigorously investigate for our objective:
• the consistency, generalization, and excessive risk bounds for the theoretical insights and guarantees; • equivalence to a two-player minimax game efficiently solved by gradient descent-ascent algorithm; • convergence to the standard IW-based solution for the ideal fully-overlapped bandit feedback;
We demonstrate the empirical performance of our method via comprehensive experiments via simulation, real-data analysis, as well as online experimentation and testing in a real-world IR system.

heading: 2 RELATED WORK
text: 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., 2020). Steck (2010) 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 et al., 2019; Xu et al., 2020). As mentioned in Section 1, they largely ignore the overlapping issue even when the recommendation is deterministic. 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 Urner, 2012). See Appendix D for further discussions.
Existing solutions for insufficient overlapping focus primarily on reducing or calibrating the variance, e.g., as discussed in Swaminathan and Joachims (2015b); Wang et al. (2020); Johansson et al.
1The presumption for this argument is that the underlying causal mechanism is unknown, which applies to the settings we discuss in the paper.
(2020). They do not account for the unique working mechanism of IR where the domain discrepancy can be actively controlled. We devise the domain-transportation constraint using the Wasserstein distance originated from the optimal transport theory (Courty et al., 2016; Redko et al., 2017). The idea of converting a Wasserstein-constraint 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 on the observed data. Finally, learning from bandit feedback and the associated counterfactual risk minimization can be viewed as a special case of our framework (Swaminathan and Joachims, 2015a). We will use it as a test bed to examine the guarantees of the proposed approach.

heading: 3 PRELIMINARIES
text: We use upper-case letters to denote random variables and measures, and bold-font letters for vectors and matrices. We denote by ∥ · ∥2, ∥ · ∥∞ and ∥ · ∥L the ℓ2, ℓ∞ norm and the Lipschitz constant of a 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 U and I. To be concise, we denote the features (or pre-trained embeddings) for users and items by xu for u ∈ U and xi for i ∈ I . We study primarily the practical implicit-feedback setting with Yui ∈ {0, 1}, e.g., users express preferences implicitly via clicks. Let D be the population of all possible (xu,xi) or (u, i) depending on the context. The embeddings can also be free parameters under the representation mapping f from X or U ∪ I to Rd. We let P be any base probability measure supported on the subsets of D, and let Pn be the empirical versions according to the collected feedback of Dn 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 wui ∈ [0,M ] or weighting function w : U × I (or X × X )→ [0,M ], the reweighted measures are given by such as: Pw(u, i) ∝ w(u, i) · P (u, i). The candidate recommendation algorithm f ∈ 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 to the user. We denote this procedure by the function: reco(u, i; f) ∈ {0, 1}. Define the new measure onD induced by deploying f on D as: Pf (u, i) ∝ reco(u, i; f) · P (u, i). If we choose the base measure P as uniform, it is clear that Pf is a uniform measure on the (u, i) pairs that will be exposed: {(u, i) ∈ D : reco(u, i; f) = 1}. Finally, given a loss function ℓ for f , we define the corresponding risk under P : EPR(f) = E(u,i)∼P ℓ ( f(u, i), yui ) , the weighted risk under Pw: EPwR(f) = E(u,i)∼P ℓ ( f(u, i), yui ) · w(u, i). Our setting covers a wide range of recommendation problems from the classical collaborative filtering to sequential recommendation (when user embedding is a function of the item sequence), as well as those using bandits for exploration where f(u, i) becomes the exploration probability, and the base measure is given by the inverse propensities. We defer the detail of that setting to Appendix A.1.
Consequence of Insufficient Overlapping.
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, we 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 et 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 Q(u, i)/P (u, i) – where P and Q represent 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 inff∈F [EQR(f) + EPR(f)] small. For IW, we show the hardness of learning, i.e., the best target risk inff EQR(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. Proposition 1. Let P and Q be the training and target distribution supported on SP ,SQ ⊆ D, and w(u, i) = Q(u,i)P (u,i) , for (u, i) ∈ SP ∩ SQ. Dn consists of training instances sampled i.i.d from P .
Hardness of learning with IW: if SP = SQ, for any f ∈ F , with probability at least 1− δ, it holds:
EQR(f) ≲ EPn,wR(f) + M
( log 1δ + logN∞( 1 n ,F ) n + √ Md1(P∥Q) ( log 1δ + logN∞( 1 n ,F ) n ,
and P (∣∣EQR(f)− EPn,wR(f)∣∣ ≳ √(d1(P∥Q)− 1)/n) > 0 under mild condition, where M :=
max{w(u, i)}, N∞( 1n ,F ) := N ( 1n ,F , ℓ 2n ∞ ) is the 1 n -covering number for F in ∥ · ∥∞ based on
2n i.i.d samples from P , and d1(P∥Q) = ∫ SQ(dP/dQ)dP is a divergence measure. Further, if SP ̸= SQ, for any prior and posterior distributions π and τ on F , for risks associated with the 0-1 loss, it holds with probability at least 1− δ:
Ef∼τ,QR(f) ≲ Ef∼τ,Pn,wR(f) + dKL(π∥τ) + log d1(P∥Q)δ
n + Ef∼τ,SQ\SPR(f) +O(Dn(τ)),
where dKL is the Kullback-Leibler divergence, d1(P∥Q) is the same as above but defined only on the overlapped part, and Dn(τ) 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 algorithm, and Cu,i(P ), Cu,i(Q) be the co-occurrence statistics under P , Q, as mentioned in Xu et al. (2021a). Even if SP = SQ, it holds that:
inf f [EPR(f) + EQR(f)] ≥
1 |SP | ∑
(u,i)∈SP
dKL ( Cu,i(P )∥Cu,i(Q) ) + c,
where c takes some positive value and equals to inff EPR(f) + inff 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 d1 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. (2021a). 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, it nevertheless suggests the limitations of DA caused by insufficient overlapping in IR.

heading: 4 MODEL AND THEORY
text: 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 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 no longer perceive reweighting as a change-of-measure tool commonly implied in the causal inference and missing data solutions. Instead, we use reweighing as a mechanism to help identify a particular training domain to ensure certain transportation properties (which we explain next) to the deployment domain2, which may concern only a subpopulation of all the potential user-item instances.

heading: 4.1 TRANSPORTATION-CONSTRAINED RISK MINIMIZATION
text: 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 ℓ1(u) = up1 and ℓ−1(u) = u 1−p1 be the positive and negative loss under prediction score u, where p1 is the prior probability that a sample
2Suppose a candidate recommender f is deployed to D. According to Section 3, the domain of users and items who are affected by the recommendation is given by Pf 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 is conventionally intervention-free.
comes from P . Interestingly, the L-Wasserstein distance between P and Q admits3:
−dW (P,Q) = inf g:{∥g∥L≤L} p1 ∫ D ℓ1(g)dP + (1− p1) ∫ D ℓ−1(g)dQ, (1)
which is 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 transports to Q by any means necessary, as long as they are Lipschitz-bounded. Since the constant of L is simply a scaling factor, we simply continue with the 1-Wasserstein distance. Using dW to device the domain transportation contraint between Pf and the particular training domain Pw we seek to construct with our weighting mechanism, the learning objective is directly given by:
minimize f∈F,w∈H EPwR(f) s.t. D(w, f) ≤ ρ, (2)
where D(w, f) is a shorthand for dW (Pw, Pf ), and ρ can be treated as a hyper-parameter. As a sanity check, when ρ = 0, the feasible set is given by: f(u, i) = w(u, i) for all (u, i), 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 a small proportion of the feedback data will be considered and the result can be heavily biased toward the historical recommendation. Therefore, a suitable ρ will give us the opportunity to better explore the whole feedback data. Nevertheless, if ρ becomes too large, we are likely to overfit the feedback data due to the high capacity of f 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 effectiveness. 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, we show that jointly optimizing w leads to the sample-consistency guarantee. For clarity, we start with the feature-based learning where f(u, i) := f(xu,xi), and defer the extension with the representation mapping to the next section. Let Z := D × {0, 1}, and we denote by ℓf : Z → R+ the composition with the loss function such that for zui = (xu,xi, yui), we have ℓf (u, i) := ℓ ( f(u, i), yui ) . We use wui as a shorthand for the individual weight.
Theorem 1. Denote by Dn(w, f) = dW (Pn,w, Pn,f ). Suppose that ℓf is L-Lipschitz w.r.t ∥ · ∥2. Define SG = supg:∥g∥L≤1 ∑ (u,i)∈Dn g(u, i) and MG = sup∥g∥L≤1, (u,i)∈D g(u, i). Assume Z ∈ RdZ and w ∈ H. Given any f ∈ F and ρ > 0, it holds with probability at least 1− δ that:∣∣∣∣ minw:D(w,f)≤ρEPwR(f)− minw:Dn(w,f)≤ρEPn,wR(f) ∣∣∣∣ ≤ 9M(log 12δ )n +Bn(H, δ)L+ Cn(w̄, w̃, f, δ).
Here, w̃ = argminDn(w,f)≤δ−Bn(H,δ) EPwR(f), w̄ = argminDn(w,f)≤δ+Bn(H,δ) EPwR(f), Cn(w̄, w̃, f, δ) = n − 12 √ 18M max{Rw̄(f)2, Rw̃(f)2} log 12δ and Rw(f) 2 = 1n ∑ Dn w 2 uiℓf (u, i) 2.
Also, Bn(H, δ) is given by O (( SGn 1/(dZ+1) )−1 +MGn −1/2 √ log 12δ +N∞( 1 n ,H) ) .
We relegate the proof of this theorem to Appendix A.4. Crucially, other than showing that the sample-consistency result can still be achieved with the jointly-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 Rw̄(f)2 and Rw̃(f)2 presented by the Cn term. Given any f ∈ F , our result shows that both w̄ and w̃ are the minimizers of a weighted risk term, i.e. EPwR(f) ∝ ∑ D wuiℓf (u, i), under some constraint involving ρ. Therefore, thanks to the constraint of D(w, f) ≤ ρ and the joint optimization of w, Rw̄(f)2 and Rw̃(f)2 will have more controlled behaviors compared with the domain discrepancy terms in Proposition 1.
We now investigate the learning-theoretical guarantees of the proposed objective, particularly the generalization and excessive risk bounds. Suppose the underlying labeling function of yui with respect to (xu,xi) is deterministic. With a little abuse of notation, we use z ∼ Pn,f to denote sampling (xu,xi, yui) via (xu,xi) ∼ Pn,f and the deterministic labelling function. Theorem 2. Suppose inf z̃∈Z{ℓf (z̃) + λ∥z − z̃∥2} ≤ MF for all z ∈ Z and λ ≥ 0, f ∈ F . Let Rn(F) be the empirical Rademacher complexity: Rn(F) = Eσ supf∈F ∣∣ 1 n ∑ (u,i)∈Dn σu,if(u, i)
∣∣, and σ takes {−1, 1} with equal probability. We consider individual weights wui ∈ (0, 1) for brevity.
3In Appendix A.3, we provide a more thorough introduction to Wasserstein distance for interested readers.
Generalization Error: for any f ∈ F, it holds with probability at least 1− δ that:
min w:D(w,f)≤ρ EPwR(f) ≤ min λ≥0
{ − λρ+ Ez∼Pn,f [ inf z̃∈Z ℓf (z̃) + λ∥z− z̃∥2 ] +MF √ log 1/(2δ) n
+
√ log(λ+ 1) n + C ∫∞ 0 √ logN∞(ϵ,F)dϵ n1/2 } .
Excessive risk: define f̂ = argminf,Dn(w,f)≤ρ EPn,wR(f) as the empirical optimal and f ∗ = argminf,D(w,f)≤ρ EPwR(f) as the theoretical optimal. With probability at least 1− δ:∣∣∣∣ min w:D(w,f̂)≤ρ EPwR(f̂)− min w:D(w,f∗)≤ρ EPwR(f∗) ∣∣∣∣ ≤ 2Rn(ℓ ◦ F) +O(L+ M̃ √ log 1/δ n1/2 ) .
We defer both proofs to Appendix A.5. Theorem 2 establishes two critical learning guarantees for the proposed transportation-constraint risk minimization. In particular, the generalization error reveals how we resolve the previous drawback mentioned for using DA in IR system. Recall from Section 3 that the joint optimal risk might be uncontrolled for DA since it can depend on how different the training and target domains are. In this regard, withD(w, f) ≤ ρ explicitly constrains the discrepancy between the training and deployment domain, we have the additional −λρ 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 recommendation. Further, the excessive risk bound suggests that the transportation constraint does not cost the convergence rate comparing with the standard empirical risk minimization guarantee (Mohri et al., 2018).

heading: 4.2 TOWARDS TRANSPORTATION-REGULARIZED RISK MINIMIZATION
text: 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 A.6. Claim 1. Suppose that ℓ ◦ F is convex. It holds for any f ∈ F that:
min Pw: dW (Pw,Pf )≤ρ EPwR(f) = max λ≥0
{ − λρ+min
Pw
{ EPwR(f) + λ · dW (Pw, Pf ) }} .
The above duality result suggests we alternatively consider the regularized learning objective:
minimize f∈F,w∈H EPwR(f) + λ · dW (Pw, Pf ), (3)
where the relaxation on maxλ≥0 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 transportation-regularized 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, 2015a). Let the logging policy by given by π. It holds in the bandit off-policy learning setting that: Pf (u, i) ∝ f(u,i)π(u,i) , where f(u, i) ∈ (0, 1) now serves as the policy we try to optimize. The counterfactual risk is given by: EPfR(f) := ∑ (u,i)∈D f(u,i) π(u,i)ℓ(f(u, i), yui), and we prove that the solution of (3) is consistent with that of the counterfactual risk minimization. Theorem 3. Let f∗ = argminf∈F EPfR(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. λ ≥ O(L) ≥ 1, it holds with probability at least 1− δ that:∣∣∣EPf∗R(f∗)− (EPŵR(f̂) + λdW (Pŵ, Pf̂ ))∣∣∣ ≲ λn1/(d+1) + log 1/(2δ)n + λMG √ log 1/(2δ) n
+
√ M max{Rf∗/π(f∗)2, Rw̃(f̃)2} log 12δ
n ,
where MG, Rw(f)2 are defined as in Theorem 1, and π 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 Pw ultimately toward Pf and lead to the consistency result. We defer the proof of Theorem 3 to Appendix A.7. This example reveals the effectiveness of the proposed transportation-regularized risk minimization, which we show is a strict extension of the counterfactual risk minimization. For IR systems, the transportation-regularized 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. Inspired by how Wasserstein GAN transforms its objective to a two-player adversarial game (Gulrajani et al., 2017), we can also convert our objective to a minimax optimization problem discussed below.

heading: 4.3 MINIMAX OPTIMIZATION
text: Algorithm 1: Batch-wise GDA for Minimax Optimization Input: D̃(t): a batch of training sample of size m at step t. η: the learning rate for ascent step. γ: shrinking parameter for the learning rate of descent step. λ: the regularization parameter. for each step t = 0, 1, . . . do
Compute reco(u, i; fθ1) for (u, i) ∈ D̃(t) (see Section 5 for the computation detail); θ (t+1) 1 ← θ (t) 1 − η γ∇θ1Lλ ( [θ (t) 1 ,θ (t) 2 ],θ (t) 3 ) ; θ(t+1)2 ← θ (t) 2 − η γ∇θ2Lγ ( [θ (t) 1 ,θ (t) 2 ],θ (t) 3 ) ; θ (t+1) 3 ← θ (t) 3 + η∇θ3Lλ ( [θ (t) 1 ,θ (t) 2 ],θ (t) 3 ) .
end
The key to our implementation is again perceiving Wasserstein distance as a binary classification problem with Lipschitz-bounded classifier as we discussed in Section 4.1. Towards this end, we denote by g ∈ G any suitable classifier for computing dW according to (1). Without loss of generality, we letw, f and g be parameterized by θ1, θ2 and θ3. It is straightforward to verify that the regularized objective in (3) transforms exactly into: min[θ1,θ2] maxθ3 Lλ([θ1,θ2],θ3), where Lλ given by:∑
(u,i)∈D
wui(θ2)ℓui ( fθ1 ) + λ ( ∑ (u,i)∈D wui(θ2) · gui(θ3)− ∑ (u,i)∈D reco(u, i; fθ1) · gui(θ3) ) . (4)
In view of (4) as a 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 andw cannot simultaneously improve the empirical risk and the domain transportation between Pw and Pf . It suggests we have found the recommendation hypothesis that best transports the learnt patterns to its intervention domain. We propose using the two-time-scale gradient descent-ascent algorithm (GDA) to 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 1 to solve our objective.

heading: 5 EXPERIMENT AND RESULT
text: We present in this section the experiment settings, implementations, empirical results, as 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, 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|I|)} for the user u. This is expensive during training, so we refer to the widespread practice of downsampling. In particular, for each (u′, i′), we randomly sample m < |I| irrelevant items and see if i′ is 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-1M, 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) is generated from the exposure and relevance status via: P(Yui = 1) = P(Oui = 1) · P(Rui = 1), where Oui indicates the exposure and Rui 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 (e.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.1.1.
Models and baselines methods. The functions of f , w and g in the minimax objective (4) can be any recommendation algorithm that suits the context, such as matrix-factorization collaborative filtering (MCF), neural collaborative filtering (NCF) (He et al., 2017), and sequential recommendation 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 a broad range of combinations for f , w and g as we present in Appendix C.3. As for the baseline methods, other than the standard popularity-based recommendation (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 Saito et al. (2020), the user-exposure aware MF (ExpoMF) from Liang et al. (2016), and the adversarial-counterfactual MF method (AC-MF) from Xu et al. (2020). The model configurations and training details are deferred to Appendix C.2.
Training & evaluation. We use the two-timescale GDA as described in Algorithm 1 with a preselected 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-last interaction is used for validation, and the last interaction is used for testing. For evaluation, in addition to the regular Hit@10 and NDCG@10 as in Rendle et al. (2020), we further consider the relevance score of the top-10 recommendation, i.e. ∑ top-10 Rui, since it also reveals the quality of the recommendation and more closely resembles the deployment performance of EPfR(f). We have access to Rui during simulation, and on real-data analysis, we settle to the Yui in testing data as an approximation. The evaluation results are provided in Table 1.
Result analysis. From Table 1, we first observe that the proposed methods achieves the best performances in both the benchmark and simulated datasets on all metrics. In particular, the DTX 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 Figure 2c). It is clear that without the transportation regularization, the performances degenerate significantly in both the real data and simulation studies. Also, we find that the performance variation of the proposed approach is relatively steady under different λ.
Analysis on w. We specifically analyze the learnt weights since they play a critical role in our approach. On both MovieLens and GoodReads (Figure 2a), we find that: 1). the learnt weights are larger on the positive training instances; 2). for the (u, i) that are among Pf (the recommended), the weights wui 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 2b, we observe from the Movielens simulation study that the learnt weights correlate positively to the exposure on the negative training data, and are distributed more evenly on the positive data. It means that wui learns 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 C.3.
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-regularized solution, and the online A/B/C testing against the standard and IPW-based solutions for an item recommendation task. Due to the space limitation, we defer the details and analysis to Appendix C.6.

heading: 6 CONCLUSION AND DISCUSSION
text: In this paper, we study from the critical intervention perspective of recommendation and summarize a domain transportation view supported by the realistic working mechanism of IR systems. We propose a principled transportation-constraint risk minimization for optimizing recommendation, and illustrate by both theories and experiments how we find it more favorable than directly importing the causal inference and missing data solutions. However, we point out that our work does not aim to replace those solutions since we 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. It 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-constraint 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 of 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.

heading: A APPENDIX ON BACKGROUND AND MAIN THEORETICAL RESULTS
text: We provide the supplementary background introduction, proofs for the claim, proposition and theorem, as well as the detailed experiment settings and complete numerical results in this part of the paper.

heading: A.1 RECOMMENDER WITH EXPLORATION POLICY, AND LEARNING FROM BANDIT FEEDBACK DATA
text: Using multi-armed bandits for exploration has attracted increasing attention from the recommendation 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 our paper is that an item is exposed to the user with randomness, and the exploration policy controls the randomness in the exposure.
Mathematically, we continue with X as the context (feature) space, I = {1, . . . , k} be the action (item) space. The exploration-exploitation 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 to the exploration policy π(u, i) := π(i |xu), which is a mapping between the item space and the probability space, and expose it to the user. Then the user, whose feature is xu, reveal the regret (or reward) action i ∈ I, which corresponds to the Yu,i in our setting. In the context of delivering recommendation, clearly we have: P(reco(u, i; f) = 1) = π(u, i) during exploration, and in the context of learning from the logged feedback data, we have P(Oui = 1) = π(u, i) since it characterizes the probability of exposure.
Similar to the deterministic recommender, the challenge in bandit offline learning is largely due to its partial-observation nature as 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 an 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)
π(u, i) Yui = EPfYui.
Swaminathan and Joachims (2015a) refers to the IPW-reweighted risk, which essentially replace the regret Yui by the corresponding risk under f , as the counterfactual risk for learning from the logged bandit feedback data. It exactly corresponds to setting the base measure P with PIPW, so it holds: EPfR(f) = ∑ (u,i)∈D f(u,i) π(u,i)ℓ(f(u, i), yui).

heading: A.2 PROOF AND BACKGROUND FOR THE IW AND DA BOUNDS IN PROPOSITION 1
text: 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⃗ = [z1, . . . , zn] to denote the observed samples, and z⃗′ = [z′1, . . . , z ′ n] to denote an i.i.d copy of z⃗. We first define by:
UB1(f, z⃗, t) = 1
n n∑ i=1 wiℓf (zi) + 3Mt n +
√ 2d(P∥Q)t
n ,
and
UB2(f, z⃗, t) = 1
n n∑ i=1 wiℓf (zi) + 9Mt n +
√ 18d(P∥Q)t
n .
Given f ∈ F , let A := EQR(f) + 6Mtn + √ 8d(P∥Q)t n it holds:
P ( UB2(f, z⃗ ′, t) ≤ UB1(f, z⃗, t) ) ≤ P ( UB2(f, z⃗ ′, t) ≤ A ) + P ( UB1(f, z⃗, t) ≥ A ) ≤ 2P (∣∣EQR(f)− 1 n ∑ wiℓf (zi) ∣∣ ≥ 3Mt n + √ 2d(P∥Q)t n
) ≤ 4e−t,
where the last line follows from Lemma A.2. Next, we define C(ϵ, ℓ ◦ F , ℓ1(Pn,w)) be the ϵ-cover of ℓ ◦ F with the empirical ℓ1 norm under Pn,w such that for any f ∈ ℓ ◦ F , there exists f̃ in C(ϵ, ℓ ◦ F , ℓn1 ): ∣∣ 1 n ∑ wif(zi)− 1n ∑ wif̃(zi) ∣∣ ≤ ϵ, for (z1, . . . , zn) sampled i.i.d from P . It then holds:
P ( ∃f ∈ F : EQR(f) ≥ UB2(f, z⃗, t) + ϵ ) = Ez⃗ sup
f∈F I[EQR(f) ≥ UB2(f, z⃗, t) + ϵ]
(a) ≤ Ez⃗ sup f∈F I[EQR(f) ≥ UB2(f, z⃗, t) + ϵ] · 2Ez⃗′I[UB1(f, z⃗′, t) ≥ EQR(f)]
≤ 2Ez⃗,⃗z′ sup f∈F I[UB1(f, z⃗ ′, t) ≥ UB2(f, z⃗, t) + ϵ]
(b) ≤ 2Pσ(⃗z,⃗z′) ( ∃f̃ ∈ C(ϵ, ℓ ◦ F , ℓ1(Pn,w)) : UB1(f, σ(⃗z, z⃗′), t) ≥ UB2(f, σ(⃗z, z⃗′), t) ) ≤ 8N (ϵ, ℓ ◦ F , ℓ1(Pn,w)) · e−t,
where (a) follows from the fact that Ez⃗′I[UB1(f, z⃗′, t) ≥ EQR(f)] ≥ 12 as suggested by Lemma A.2, and in step (b) we let σ(⃗z, z⃗′)i takes the value of zi, z′i with equal probability, and the inequality follows from the definition of the ϵ cover. Notice that N (ϵ, ℓ ◦ F , ℓ1(Pn,w)) ≤ N (ϵ/M, ℓ ◦ F , ℓn∞). We take ϵ = 1n , which solves for t = c log 1 δ + logN (ϵ/M, ℓ ◦ F , ℓ n ∞) for some constant c and leads to the desired result after arranging terms.
The corresponding lower bound follows directly from Lemma A.4, where we make a mild assumption that there exists a hypothesis f ∈ F such that EPnR(f) = 1, so it holds that EPn,wR(f) = d(P∥Q)− 1 suggested by Lemma 1 of 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 as in Germain et al. (2015).
Proof. We use ℓ to denote the 0− 1 loss for brevity. The PAC-Bayesian approach concerns with the Gibbs risk of Ef∼τE(u,i)∼Qℓ(f(u, i), yui), where τ is some posterior distribution on the hypothesis space F . Clearly, when there are mismatch in the supports of SP and SQ, the Gibbs risk for the mismatched part is given by Ef∼τE(u,i)∈SQ/SPR(f). We now focus on the overlapped part. Using the classical decomposition result from Germain et al. (2015), which states that:
Ef∼τEQR(f) = 1
2 dQ(τ) + eQ(τ),
where dD(τ) = Ef,f ′∼τEQℓ(f(u, i), f ′(u, i)) is a discrepancy term, and eQ(τ) = 2Ef,f ′∼τEQℓ(f(u, i), yui)ℓ(f ′(u, i), yui) is the Gibbs risk for the joint hypothesis. Therefore, we have:
Ef∼τEQR(f)− Ef∼τEPwR(f) = (1 2 dQ(τ)− 1 2 dPw(τ) ) + ( eQ(τ)− eP (τ) ) ≤ 1
2 ∣∣dQ(τ)− dPw(τ)∣∣+ ∣∣eQ(τ)− ePw(τ)∣∣︸ ︷︷ ︸ D(τ) ,
where D(τ) essentially characterizes the disagreement of Q and Pw in terms of the posterior τ on F . Therefore, for any posterior distribution τ , we have: Ef∼τEQR(f) ≤ Ef∼τEPwR(f) +D(τ), so the next step is to bound the Gibbs risk of Ef∼τEPwR(f). Our strategy follows that of Germain et al. (2015), that we employ the convex function ∆ : [0,M ]× [0,M ]→ R. It then holds that:
n ·∆ ( Ef∼τEPn,wR(f),Ef∼τEPwR(f) ) ≤ nEf∼τ∆ ( EPn,wR(f),EPwR(f)
) ≤ dKL(τ∥π) + lnEf∼π exp ( n∆ ( EPn,wR(f),EPwR(f) )) by Lemma A.7
w.p. 1−δ ≤ dKL(τ∥π) + ln 1
δ Ef∼πEz1,...,zn∼P exp
( n∆ ( 1 n ∑ k w(zk)ℓf (zk),Ez∼Pw(z)ℓf (z) )) ,
where the last line comes from the Markov inequality, and w(zk) is a shorthand for w(u, i) for zk = (u, i, yui). We then focus on bounding: Ef∼πEzk∼P exp ( n∆ ( 1 n ∑ k w(zk)ℓf (zk),Ez∼Pw(z)ℓf (z) )) . Since ℓf is the 0 − 1 loss,
the term inside ∆ (setting aside w(zi)) are essentially binomial variable of n trials with a success rate of EPR(f). Since ∆ is convex in both arguments and w(u, i) is given by Q(u, i)/P (u, i), it is easy to verify that:
Ezk∼P exp ( n∆ ( 1 n ∑ k w(zk)ℓf (zk),Ez∼Pw(z)ℓf (z) ))
≤ d(P,Q) · Ezk∼P exp ( n∆ ( 1 n ∑ k ℓf (zk),EPR(f) )) ,
where d(P,Q) = ∫ SQ(dP/dQ)dP as we mentioned in the statement. It is then obvious that:
Ezk∼P exp ( n∆ ( 1 n ∑ k ℓf (zk),EPR(f) )) ≤ sup r∈[0,1] { n∑ k=0 Bin(k;n; r) exp ( n∆( k n , r) )} ,
where we use r ∈ [0, 1] to replace the role of EPR(f), since the prior π is arbitrary, and Bin(k;n; r) is probability of having k success in n 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 ∆, so we obtain the desired result by putting together the above arguments.
Now we briefly introduce the skip-gram negative sampling algorithm and prove its associated rersults in Proposition 1. 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 objective function is given by:
P(Oui = 1|u, i) = σ ( Φ(i)⊺Φ(u) ) =
1 1 + exp ( − Φ(i)⊺Φ(u) ) , P(Oui = 0|u, i) = σ ( − Φ(i)⊺Φ(u) ) = 1
1 + exp ( Φ(i)⊺Φ(u) ) , ℓu,i = − logP(Oui = 1|u, i) + k · Ek∼Neg(I) [ logP(Oui = 0|u, i) ] ,
(A.1)
where Φ(u), Φ(i) are the embeddings for the user u and item i, k is the number of negative samples, and Neg(I) is the uniform negative-sampling distribution on the item set. The risk objective is thus give by: EPR(Φ) = ∑ (u,i)∈D ℓu,i. 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 statistics 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.e. Y ⊥ X | f(X) or p(Y |X) and p ( Y |f(X) ) are the same, then f(X) is a sufficient dimension reduction (SDR). According to Globerson and Tishby (2003), finding the SDR f(X) is equivalent to solving a optimization problem:
min q(y,f(x))
dKL ( p(Y,X) ∥ q(Y, f(X)) ) , (A.2)
where dKL is the Kullback-Leibler divergence.
Proof. Let Rui := NuiNuNi be the relatedness measure defined in Xu et al. (2021a), where Nui is the co-count of (u, i), and Nu, Ni are the individual counts of u and i. The co-occurrence statistics is given by Cui := Oui |Rui, which is exposure Oui condition on the relatedness measure. It is shown in the Claim 1 of Xu et al. (2021a) that:
min Φ(u),Φ(i)∈Rd EPR(Φ) = min Φ(u),Φ(i)∈Rd
1 |D| ∑
(u,i)∈D
dKL ( p(Oui |Φ(u),Φ(i)) ∥∥ p(Oui |Rui)), (A.3) so Φ gives the SDR of Cui in Rd, 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: dKL(a∥c) + dKL(c∥b) ≥ dKL(a∥b) + (c − a) log c(1−b)(1−c)b . Recall that Cui(P ) and Cui(Q) are the co-occurrence statistics under P and Q, respectively. Therefore, if we let Φ(P ) and Φ(Q) be the solution to (A.3) under P and Q, by assuming SP = SQ, it holds that:
inf Φ
( EPR(Φ) + EQR(Φ) ) ≥ inf
Φ EPR(Φ) + inf Φ EPR(Φ)
≥ 1 |SP | ∑ (u,i)∈SP dKL ( p(Oui |Φ(P )(u),Φ(P )(i)) ∥∥Cui(P )))+ dKL ( p(Oui |Φ(Q)(u),Φ(Q)(i))
∥∥Cui(Q)) = 1
|SP | ∑
(u,i)∈SP
dKL(Cui(P ) ∥Cui(Q)) + C,
and C = infΦ ( EPR(Φ) + EQR(Φ) ) when P = Q a.s.

heading: A.3 BACKGROUND ON THE WASSERSTEIN DISTANCE
text: Perhaps the two most common discrepancy measures on probabilities are ϕ-divergence and integral probability metric (IPM). Obviously, ϕ-divergence does not satisfy our need of characterizing domain transportation because it requires SP ⊆ SQ (weak overlap) to hold in practice. IPM, on the other hand, provides the flexibility and is defined as
dG(P,Q) = sup g∈G
∣∣ ∫ gdP − ∫ gdQ∣∣,
where G is a class of real-valued bounded measurable function. In this direction, we find the Wasserstein distance from the optimal transportation (OT) theory Rachev (1985) a good fit to our goal. Although the maximum mean discrepancy distance is also valid, its computation and related theoretical results rely on the specification of a 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 to another:
dw,c(P,Q) = argmin π∈Π(P,Q) ∫ D×D c(z, z′)dπ(P,Q),
where Π(P,Q) is the set of all joint probability measure whose marginals are P and Q, and c(·, ·) is the cost function. Clearly, dw,c(P,Q) relies on the geometry of P and Q if the cost function is well-chosen. For recommender system, z is often given by (xu,xi) or (Φ(u),Φ(i)), so it is natural to use the ∥ · ∥2 distance: c(z, z′) = ∥z− z′∥2. We denote by dW for this particular cost function, which is also referred to as the 1-Wasserstein distance. The classical Kantorovich-Rubinstein theorem Dudley (2018) connects the dW to IPM by proving the duality result of:
dW = sup g:{∥g∥L≤1} ∫ D gdP − ∫ D gdQ. (A.4)
In the above formulation, the constant of 1 under sup is less critical since we can always rescale g. The class of Lipschitz-bounded function covers a wide selection of models including neural networks as discussed in Fazlyab et al. (2019).

heading: A.4 PROOF FOR THEOREM 1
text: We first state a proposition for the following proofs. Proposition A.1. Suppose ℓf is semi-continuous for all f ∈ F , P is any distribution supported on Z , and c(z, z′) = ∥z− z′∥2. It holds:
min Q:dW (Q,P )≤ρ EQR(f) = sup λ≥0
{ − λρ+ Ez∼P [ inf z̃∈Z {ℓf (z̃) + λ · c(z, z̃)} ]} .
Proof. It is shown by Gao and Kleywegt (2016) that:
max Q:dW (Q,P )≤ρ EQR(f) = inf λ≥0
{ λρ+ Ez∼P [ sup z̃∈Z {ℓf (z̃)− λ · c(z, z̃)} ]} .
Following the above result, we immediately have:
min Q:dW (Q,P )≤ρ EQR(f) = − max Q:dW (Q,P )≤ρ −EQR(f)
= − inf λ≥0
{ λρ+ Ez∼P [ sup z̃∈Z {−ℓf (z̃)− λ · c(z, z̃)} ]} = sup
λ≥0
{ − λρ− Ez∼P [ sup z̃∈Z {−ℓf (z̃)− λ · c(z, z̃)} ]} = sup
λ≥0
{ − λρ+ Ez∼P [ inf z̃∈Z {ℓf (z̃) + λ · c(z, z̃)} ]} .
Now we prove the result in Theorem 1.
Proof. We first define H1 = {w ∈ H : dW (Pw, Pf ) ≤ ρ}, and H1 = {w ∈ H : dW (Pw, Pf ) ≤
ρ+ cw n1/(d+1) + 8M √ log 4δ n }, where cw is the constant stated in Lemma A.5.
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 1− δ thatH1 ⊆ H2, which suggests that for any given f ∈ F :
min w:D(w,f)≤ρ EPwR(f) ≥ min w:Dn(w,f)≤δ+B EPwR(f)
with probability at least 1− δ, where B = cw n1/(d+1) + 8M √ log 4δ n .
Now we define w̃ = argminw:Dn(w,f)≤δ+B EPwR(f). Then using the result in Lemma A.1, for any given f ∈ F , it holds with probability at least 1− δ4 that:
min w:Dn(w,f)≤δ+B EPwR(f) = EPw̃R(f)
≥ EPn,w̃R(f)− 7M log 1δ
3n −
√ 2Rw̃(f)2 log 1 δ
n
≥ min w:Dn(w,f)≤δ+B
EPn,wR(f)− 7M log 1δ
3n −
√ 2Rw̃(f)2 log 1 δ
n ,
where the last line follows from the definition of w̃.
Using Proposition A.1, we have: min
w:Dn(w,f)≤δ+B EPm,wR(f) = sup λ≥0
{ − λ(ρ+B) + Ez∼Pn,w [ inf z̃∈Z {ℓf (z̃) + λ · c(z, z̃)} ]} ≥ sup
λ≥0
{ − λρ+ Ez∼Pn,w [ inf z̃∈Z {ℓf (z̃) + λ · c(z, z̃)} ]} − L ·B
= min w:Dn(w,f)≤δ EPn,wR(f)− L ·B,
where the second line uses the result in Lemma A.6 which bounds the λ∗ that achieves the supremum with the Lipscitize constant L. Combining the above results, it holds with probability at least 1− δ2 that:
min w:D(w,f)≤ρ EPwR(f) ≥ min w:Dn(w,f)≤δ
EPn,wR(f)− 7M log 1δ
3n −
√ 2Rw̃(f)2 log 1 δ
n − L ·B.
The upper bound can be shown in the same manner, by using w̄ = argminw:Dn(w,f)≤δ−B EPwR(f) to replace w̃. Combining the upper and lower bounds, we obtain the result stated in Theorem 1.

heading: A.5 PROOF FOR THEOREM 2
text: Suppose ℓ is some bounded loss function, then MF stated in Theorem 2 must be finite for λ ∈ [0, Lρ ], otherwise it can be shown from Proposition A.1 and Lemma A.6 that:
min dW (Q,P )≤ρ EQR(f) = sup λ≥0
{ − λρ+ Ez∼P [ inf
z̃∈Z ℓf (z̃) + λ · c(z, z̃)] } is unbounded for finite ρ, which contradicts that ℓ is bounded.
We first prove the generalization error bound.
Proof. We use the shorthand ϕf,λ(z) := Ez∼Pf [inf z̃ ℓf (z̃) + λc(z̃, z)]. Since we do not make any parametric assumption on the weighting function w here (as the consequence of using w ∈ H has been stated in Theorem 1), we have:
min dW (Pw,Pf )≤ρ EQR(f) = sup λ≥0
{ − λρ+ Ez∼Pfϕf,λ(z) } By Proposition A.1
= sup λ≥0
{ − λρ+ Ez∼Pn,fϕf,λ(z) + Ez∼Pfϕf,λ(z)− Ez∼Pn,fϕf,λ(z) } ≤ sup
λ≥0
{ − λρ+ Ez∼Pn,f + sup
f∈F
{ EPfϕf,λ(z)− EPn,fϕf,λ(z) } ︸ ︷︷ ︸
ψλ
}
Using the standard symmetrization argument, we can upper-bound Eψλ = 1n supf∈F { EPfϕf,λ(z)−
ϕf,λ(zi) } with the empirical Rademarcher complexity:
Eψλ ≤ 2E sup f∈F
1
n n∑ i=1 ϵiϕf,λ(zi),
where the expectation on LHS is taken with respect to the random variables of z1, . . . , zn. Clearly, ψ(λ) is bounded by MF that we illustrated in the beginning, so from McDiarmid’s inequality we have:
P ( ψ(λ) ≥ Eψ(λ) + Mt√
n
) ≤ exp(−2t2). (A.5)
Also, note that √
1 nϵiϕf,λ(zi) is zero-mean and 1-subgaussian with respect to the ∥ · ∥∞ norm on F ,
so for any f1, f2 ∈ F , it holds that:
E [ exp ( t n n∑ i=1 ϵi(ϕf1,λ(zi)− ϕf2,λ(zi)) )]
≤ E [ exp ( t√ n ϵ · ( inf z̄∈Z {f1(z̄) + λc(z1, z̄)}+ sup z̃∈Z {−f2(z̃)− λc(z1, z̃)} ))]n ≤ E [ exp
( t√ n ϵ sup z∈Z {f1(z)− f2(z)} )]n ≤ exp ( t2∥f1 − f2∥∞ 2 ) .
(A.6)
Using the entropy integral bound on the empirical Rademarcher complexity term, we have:
Eψ(λ) ≤ c√ n ∫ ∞ 0 √ logN (ϵ,F , ℓ∞(Pn))dϵ,
since ℓ is Lipscitz (and we absorb the Lipscitz constant into c). Combining the above results, for any given λ ≥ 0, it holds with probability at least 1− δ that:
P ( ∃f ∈ F : min
dW (Pw,Pf )≤ρ EQR(f) ≥ −λρ+ Ez∼Pn,f [ inf z̃∈Z ℓf (z̃) + λc(z, z̃) ] +
c ∫∞ 0 √ logN (ϵ,F , ℓn∞)dϵ
n + MF t n
) ≤ 2 exp(−2t2).
Then we apply the same union-bound argument from Theorem 1 Koltchinskii et al. (2002) to extend the above result to any λ > 0. In particular, we pick the sequence of λk = k and tk = t+ √ log k, k = 1, 2, . . .. By simple calculations and the sum of infinite series arguments, we reach the conclusino that for any f ∈ F , it holds with probability at least 1− δ that:
min dW (Pw,Pf )≤ρ EQR(f) ≥ min λ≥0
{ − λρ+ Ez∼Pn,f [ inf z̃∈Z ℓf (z̃) + λc(z, z̃) ] +
c ∫∞ 0 √ logN (ϵ,F , ℓn∞)dϵ
n + MF
√ log 12δ
n +
√ log(λ+ 1)
n
}
Now we prove the excessive risk bound.
Proof. We start by defining: f̂ = argminf∈F minDn(w,f)≤ρ EPn,wR(f), and f∗ = argminf∈F minD(w,f)≤ρ EPn,wR(f). Using the definition of f̂ , we have:
min D(w,f̂)≤ρ EPwR(f̂)− min D(w,f∗)≤ρ EPwR(f∗)
≤ min D(w,f̂)≤ρ EPwR(f̂)− min Dn(w,f̂)≤ρ EPwR(f̂) + min Dn(w,f∗)≤ρ EPwR(f∗)− min D(w,f∗)≤ρ EPwR(f∗).
Let λ̂ =λ≥0 { − λρ + Ez∼Pf̂ [inf z̃∈Z ℓf̂ (z̃) + λ · c(z, z̃)] } , and from Lemma A.6 we know that λ̂ ≤ L. It holds that:
min D(w,f̂)≤ρ EPwR(f̂)− min Dn(w,f̂)≤ρ EPwR(f̂)
= ( − λ̂ρ+ Ez∼Pf [ inf
z̃∈Z ℓf̂ (z̃) + λ̂ · c(z, z̃)]
) −max
λ≥0
{ − λρ+ Ez∼Pf [ inf
z̃∈Z ℓf̂ (z̃) + λ · c(z, z̃)] } ≤
∫ Z ( inf z̃ ℓf̂ (z̃) + λ̂c(z, z̃) ) d ( Pf̂ − Pn,f̂ ) ≤ sup λ∈[0,L],ψ∈ℓ◦F ∫ Z ( inf z̃ ℓf̂ (z̃) + λc(z, z̃) ) d ( Pf̂ − Pn,f̂ ) .
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 1− δ/2:
min D(w,f̂)≤ρ EPwR(f̂)− min Dn(w,f̂)≤ρ
EPwR(f̂) ≤ 2Radn ( [0, L]⊗ ℓ ◦ F ) +MF √ 2 log 2δ n .
Similarly, we let λ∗ =λ≥0 { − λρ + Ez∼Pf∗ [inf z̃∈Z ℓf∗(z̃) + λ · c(z, z̃)] } , and using the same arguments, we also have the following bound that holds with probability at least 1− δ/2:
min D(w,f∗)≤ρ EPwR(f∗)− min Dn(w,f∗)≤ρ
EPwR(f∗) ≤ 2Radn ( [0, L]⊗ ℓ ◦ F ) +MF √ 2 log 2δ n .
Combining the above two bounds, we obtain the desired result.

heading: A.6 PROOF FOR CLAIM 1
text: Proof. Given f ∈ F , the mapping of Pw to dW (Pw, Pf ) is convex in the space of probability measures. Since dW (Pw, Pf ) = 0 can be achieved by taking Pw = Pf a.e, using the generalized Lagrange duality result in Lemma A.3, it holds that:
inf dW (Pw,Pf )≤ρ ∫ Z ℓf (z)dPw = sup λ≥0 inf dW (Pw,Pf )≤ρ { − λρ+ ∫ Z ℓf (z)dPw + λ · dW (Pw, Pf ) } .
Notice that for any π ∈ Π(Pw, Pf ), where Π(Pw, Pf ) is the set of all joint distributions whose marginals are given by Pw and Pf , we have: ∫ Z ℓf (z)dPw = ∫ Z ∫ Z ℓf (z1)dπ(z1, z2). Therefore,
we have:∫ Z ℓf (z)dPw+ inf π∈Π(Pw,Pf ) ∫ Z×Z c(z1, z2)dπ(z1, z2) = inf π∈Π(Pw,Pf ) {∫ Z×Z ℓf (z1)+λ·c(z1, z2) } ,
using the definition of the Wasserstein distance introduced in Appendix A.3. As a consequence, it holds that:
inf dW (Pw,Pf )≤ρ ∫ Z ℓf (z)dPw = sup λ≥0 inf w,π∈Π(Pw,Pf ) { − λρ+ ∫ Z×Z ℓf (z1) + λ · c(z1, z2) } .
We first point out that:
inf w,π∈Π(Pw,Pf ) {∫ Z×Z ℓf (z1) + λ · c(z1, z2) } ≥ ∫ Z inf z1 { ℓf (z1) + λ · c(z1, z2) } dPf (z2), (A.7)
and in the following proof we show that the other direction also holds, so the above inequality becomes equality. Also, if we consider as the space of all the regular conditional probabilities from z2 to z1, it is evident that:
inf w,π∈Π(Pw,Pf ) {∫ Z ℓf (z1) + λ · c(z1, z2)dPf (z2) } ≤ inf M∈ {∫ Z ℓf (z1) + λ · c(z1, z2)dM(z1|z2)dPf (z2) } .
(A.8)
Furthermore, using Lemma A.8, if we consider X as the space of all measurable mappings from Z to Z , then it holds:
inf x∈X {∫ Z ℓf (x(z)2)) + λc(x(z2), z2)dPf (z2) } = ∫ Z inf z1 { ℓf (z1) + λ · c(z1, z2) } dPf (z2).
Consequently, if we let x̃ ∈ X be the mapping that achieves ϵ-close to the above infimum (which requires certain continuity condition for ℓf ) and M(·|z2) be defined by x̃(z2):∫ Z ℓf (z1) + λc(z1, z2)dM(z1|z2)dPf (z2) = ∫ Z ℓf (x̃(z2)) + λc(z̃2, z2)dPf (z2)
≤ ∫ Z inf z1 { ℓf (z1) + λ · c(z1, z2) } dPf (z2) + ϵ
≤ inf w,π∈Π(Pw,Pf ) {∫ Z ℓf (z1) + λ · c(z1, z2)dPf (z2) } + ϵ
(A.9)
Since ϵ > 0 is arbitrary, combining (A.7), (A.8) and (A.9), we have:
inf w,π∈Π(Pw,Pf ) {∫ Z ℓf (z1) + λ · c(z1, z2)dPf (z2) } = ∫ Z inf z1 { ℓf (z1) + λ · c(z1, z2) } dPf (z2),
and using the result in Proposition A.1, we obtain the final that for any f ∈ F : min
dW (Pw,Pf )≤ρ EPwR(f) = max λ≥0
{ − λρ+min
Pw {EPwR(f) + λ · dW (Pw, Pf )}
} .

heading: A.7 PROOF FOR THEOREM 3
text: Proof. We first let f∗ = argminf∈F EPfR(f), and define w∗ = f∗ (suppose F ⊂ H) such that Pn,w∗(u, i) = Pn,f∗(u, i) and Pw∗(u, i) = Pf∗(u, i). Since F is the class of valid exploration policies in the bandit setting, we have f(u, i) ∈ (0, 1) for all f ∈ F . Note that by the definition of f∗ and w∗:
min f∈F,h∈H
EPn,wR(f) + λ · dW (Pn,w, Pn,f ) ≤ EPn,w∗R(f ∗) + λ · dW (Pn,w∗ , Pn,f∗).
Combining the results in Lemma A.1 and Lemma A.5, it holds with probability at least 1− δ/2 for any f ∈ F and w ∈ H that: EPn,w∗R(f∗)− EPw∗R(f∗) ≤ 7 log 14δ 3n + √ 2Rw∗ (f∗)2 log 1 4δ n ,
dW (Pn,w∗ , Pn,f∗) ≤ cwn1/(d+1) + 8MG √ log 1δ n
Hence, the following inequality holds with probability at least 1− δ: min
f∈F,h∈H EPn,wR(f) + λ · dW (Pn,w, Pn,f )
≤ min f∈F
EPfR(f) + 7 log 12δ
3n +
√ 2Rw∗(f∗)2 log 1 2δ
n + cw n1/(d+1) + 8MG √ log 2δ n .
(A.10)
On the other hand, with λ ≳ L ≥ 1 where L is the Lipschitz constant for ℓ ◦ F , for any given f ∈ F and w ∈ H, it holds that:
EPfR(f) = EPwR(f) + ∫ Z ℓf (z) ( − Pw(z) π(z) + Pf (z) π(z) ) dz
≲ EPwR(f) + sup ψ∈ℓ◦F EPwψ(z)− EPfψ(z)
≤ EPwR(f) + L · dW (Pw, Pf ), where in the first line we use the background of learning from bandit feedback data where π is the logging policy (e.g. π(z) = π(u, i) for z = (xu,xi, yui)); and the last line we use the definition of
Wasserstein distance under the Kantorovich-Rubinstein theorem (Appendix A.3). Again, by combing Lemma A.1 and Lemma A.5, we can further bound the last line with probability at least 1− δ/2 with: EPn,wR(f)+L·dW (Pn,w, Pn,f )+λ (7 log 14δ
3n +
√ 2Rw(f)2 log 1 4δ
n + cw n1/(d+1) + 8MG √ log 1δ n ) ︸ ︷︷ ︸
slack terms
.
Now we let f̃ , w̃ = argminf∈F,w∈H EPn,wR(f) + λ · dW (Pn,w, Pn,f ) for λ ≳ L ≥ 1. Then it holds that:
min f∈F EPfR(f) ≤ EPf̃R(f̃)
≤ EPn,w̃R(f̃) + λ · dW (Pn,w̃, Pn,f̃ ) + slack terms, (A.11)
where the slack terms are stated above. Combining (A.10) and (A.11), we obtain the desired result.

heading: A.8 ANALYSIS ON THE GDA ALGORITHM.
text: By using bounded Lipschitz functions for wθ1 , fθ2 , we will show below that the gradient of Lλ is L−Lipschitz. It is indicated by Daskalakis and Panageas (2018) that GDA with η ≤ 1/L avoids unstable critical points for almost all initialization, which means that ( θ (t 1 ,θ (t) 2 ,θ (t) 3 ) is unlikely to cycle as t grows. Furthermore, any stationary point yielded by GDA with large γ is basically a local minimax point except degenerated case (Jin et al., 2020), and thus the convergence guarantee of Algorithm 1. Here, a solution (θ∗1 ,θ ∗ 2 ,θ ∗ 3) is local minimax if there exits δ0 > 0 and
a function h satisfying limδ→0 h(δ) → 0 such that ∀δ ∈ (0, δ0], and any (θ1,θ2,θ3) satisfying∥∥[θ1,θ2]− [θ∗1 ,θ∗2 ]∥∥2 ≤ δ and ∥θ3 − θ∗3∥2 ≤ h(δ), it holds that: Lλ ( [θ∗1 ,θ ∗ 2 ],θ3 ) ≤ Lλ ( [θ∗1 ,θ ∗ 2 ],θ ∗ 3 ) ≤ max
θ′3:∥θ′3−θ∗3∥2≤h(δ) Lλ
( [θ1,θ2],θ ′ 3 ) .
In other words, by using the two-time-scale GDA algorithm with a small η and a large γ, our resulting solution has a similar role as a local minimum/maximum in a minimization/maximization problem — the global Nash equilibrium, if any, must be one of the solutions yielded by the GDA in Algorithm 1.
Proof. Here, we show that ifwθ1 , fθ2 are bounded Lipschitz functions and gθ3 is a Lipschitz function, the gradient of the minimax objective is also Lipschitz.
Recall the objective function in (6), i.e., Lλ([θ1,θ2],θ3) := ∑
(u,i)∈D
wui(θ2)ℓui(fθ1)
+ λ  ∑ (u,i)∈D wui(θ2) · gui(θ3)− ∑ (u,i)∈D reco(u, i; fθi) · gui(θ3)  . It is straightforward to show that:
∂Lλ ∂θ1
= ∑
(u,i)∈D
wui(θ2) ∂ℓui(fθ1)
∂θ1 − λ ∑ (u,i)∈D gui(θ3) · ∂reco(u, i; fθ1) ∂θ1
∂Lλ ∂θ2
= ∑
(u,i)∈D
ℓui(fθ1) ∂wui(θ2)
∂θ2 + λ ∑ (u,i)∈D gui(θ3) · ∂wui(θ2) ∂θ2
∂Lλ ∂θ3 = λ  ∑ (u,i)∈D wui(θ2) · ∂gui(θ3) ∂θ3 − ∑ (u,i)∈D reco(u, i; fθ1) · ∂gui(θ3) ∂θ3  . We impose a few assumptions on fθ1 , wui(θ2) and gui(θ3). 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 of the loss function ℓ (e.g., logistic loss, exp-loss, probit loss) and the reco function (e.g., top-K), we can ensure ℓui(fθ1) and reco(u, i; fθ1) to have Lipschitz gradients. Finally, by employing clipping tricks on the gradients to ensure they will not explode, which is also a common practice, we have universally bounded and Lipschitz functions that include:
fθ1 , wui(θ2), gui(θ3), ∂ℓui(fθ1 ) ∂θ1 , reco(u,i;fθ1 )∂θ1 , ∂wui(θ2) ∂θ2 , gui(θ3)∂θ3 .
Therefore, the products and summations of these function is a L-Lipschitz function for some positive constant L.

heading: B LEMMAS AND PROOFS
text: 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 ℓf : Z → [0, 1] without loss of generality. With w(u, i) = Q(u,i)P (u,i) and z1, . . . , zn sampled i.i.d from P , for any δ > 0, it holds with probability at least 1− δ that:
EQR(f) ≤ EPn,w + 7M log 1δ
3n +
√ 2Rw(f)2 log 1 δ
n ,
where Rw(f)2 = 1n ∑ w2i ℓf (zi) 2.
The result is modified from Corollary 5 of Maurer and Pontil (2009). Lemma A.2. Let P and Q be the training and target distribution supported on SP ,SQ ⊆ D, and w(u, i) = Q(u,i)P (u,i) , for (u, i) ∈ SP ∩ SQ. Dn consists of training instances sampled i.i.d from P . Given a single hypothesis f ∈ F , suppose wui ∈ (0,M), for any δ > 0, it holds with probability at least 1− δ that:
EQR(f) ≤ EPn,wR(f) + 2M log 1δ
3n +
√ 2d(P∥Q) log 1δ
n ,
where d(P∥Q) = ∫ SQ(dP/dQ)dP .
The above result for importance weighting of a single hypothesis is stated in the Theorem 1 of Cortes et al. (2010). Lemma A.3. Let f be a real-valued convex functional defined on a convex subset Ω of a vector space X , and let G be a convex mapping of X into a normed space Z . Suppose there exists x1 such that G(x1) < ρ and that inf{f(x) : G(x) ≤ ρ,x ∈ Ω} is finite, then it holds that:
inf G(x)≤ρ,x∈Ω = max z∗≥ρ,z∈Z inf x∈Ω {f(x) + ⟨G(x), z∗⟩}.
The above Lagrange duality result is stated in Theorem 8.1 of Luenberger (1997). Lemma A.4 (Lower bound based on maximum variance). Suppose f ∈ F takes values in [0, 1] without loss of generality, and the variance of f is denoted by σ2(f). Let σ(F) = supf∈F σ(f), and assume 1n ≤ σ 2(g) < +∞. It holds that:
P ( sup f∈F EP f − EPnf σ(F) ≥ 1 2 √ m ) ≥ c > 0.
The result is stated in Theorem 9 of Cortes et al. (2010) Lemma A.5 (Finite sample bound for 1-Wasserstein distance). Suppose P and Q are supported on (perhaps non-overlapping subsets of) Z where Z ∈ Rd and is bounded. Let MG := supg:∥g∥L≤1 supz∈Z g(z). For all δ > 0, it holds with probability at least 1− δ that:
∣∣dW (P,Q)− dW (Pn, Qn)∣∣ ≤ cw n1/(d+1) + 8MG √ log 4δ n .
Proof. The first part of the proof follows from the result on integral probability metric stated in Theorem 11 of Sriperumbudur et al. (2009), that for G = {g : ∥g∥L ≤ 1}, we have:
∣∣∣ sup g∈G [ ∫ Z gdP − ∫ Z gdQ ] − sup g∈G [ ∫ Z gdPn − ∫ Z gdQn ]∣∣∣ ≤ 6 √ 2M2G log 4 δ n + 4Rn(G),
with probability at least 1− δ, andRn(G) is the empirical Rademarcher complexity of G. Using the entropy integral bound on the empirical Rademarcher complexity, we have:
Rn(G) ≤ 2ϵ+ 4 √ 2√ n ∫ ∞ ϵ/4 √ logN (u,G, ℓ2(Pn))du.
Note that Z ∈ Rd implies: N (u,Z, ∥ · ∥∞) = O(u−d). Using the fact that log(x+ 1) ≤ x+ 1, we have: logN (u,G, ℓ2(Pn)) ≤ logN (u,G, ∥ · ∥∞) ≤ c1u−(d+1) + c2u−d. Since Z is bounded, the entropy integral bound becomes:
Rn(G) ≤ inf ϵ>0 2ϵ+ 4 √ 2√ n ∫ 4diam(Z) ϵ/4 √ c1u−(d+1) + c2u−ddu,
which directly leads to the desired bound where cw is the corresponding constant.
Lemma A.6. Let c(z, z̃) := ∥z− z̃∥2. Define:
f∗ = argmin f∈F min Q:dW (Q,P )≤ρ
EQR(f), and λ∗ =λ≥0 { λρ+ Ez∼P [ inf z̃∈Z ℓf∗(z̃) + λ · c(z, z̃) ]} .
If all f ∈ F is L-Lipschitz, i.e. supz,z′ |f(z)−f(z′)| c(z,z′) ≤ L, then it holds: λ ∗ ≤ L.
Proof. Using the Lipschitz property, we have: λ∗ρ ≥ λ∗ρ+ Ez∼P [ inf z̃∈Z ℓf∗(z̃) + λ ∗ · c(z, z̃)− ℓf∗(z) ] ︸ ︷︷ ︸
always ≤0,because = 0 when z=z̃ ≥ −λρ+ Ez∼P [ inf z̃∈Z ℓf∗(z̃) + λ ∗ · c(z, z̃)− ℓf∗(z) ] ( by the definition of λ∗)
≥ −λρ+ Ez∼P [ − L · c(z, z̃) + λ · c(z, z̃) ] ≥ −λρ+ inf
t≥0 {−Lt+ λt}
≥ −Lρ ( by choosing λ = L),
which gives λ∗ ≤ L.
Lemma A.7 (Change of measure inequality). For any P and Q on X , and for any measurable function f : X → R, it holds that:
Ex∼Q ≤ dKL(P∥Q) + ln ( Ex∼P ef(x) ) .
This is a standard result that has been included in many textbooks for probability.
Lemma A.8 (Interchange of integration and minimization). LetX be a space of measurable functions from Z to Rn with respect to u, a σ-finite measure on the underlying space. Let f : Z × Rn → R be a normal integrand, then it holds:
inf x∈X ∫ Z f(z, x(z))u(dz) = ∫ Z inf x∈Rn f(t,x)u(dz)
The result is simplied from Theorem 14.60 of Rockafellar and Wets (2009).

heading: C COMPLETE EXPERIMENT SETTINGS, NUMERICAL RESULTS, AND REAL-WORLD DEPLOYMENT AND TESTING ANALYSIS
text: 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 are provided in the supplement material. All the reported results are averaged over ten independent runs.

heading: C.1 DATASET DESCRIPTION, PREPROCESSING AND EXPERIMENT SETUP
text: The detailed descriptions for the three real-world benchmark datasets are given as below.
• Movielens-1M 4. The dataset provides the users’ ratings for movies that they watched, which consists of around 1 million ratings collected from 60,40 users on 3,952 movies. The movie ratings are ranged from 1 to 5, where a higher rating indicates more positive feedback. Hence, the original Movielens-1M 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. (2017). We use the explicit feedback for semi-synthetic experiments, and use the converted explicit feedback for the real-data experiments.
• LastFM 5. 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 an implicit feedback dataset. There is a total of 186,479 tagging events, where 12,523 artists have been tagged.
• GoodReads 6. 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 1 to 5, and a higher rating indicates more positive feedback. We concert the dataset to implicit feedback in the same way as the Movielens-1M dataset for the real-data experiments.
• Yahoo!R3 Music. The dataset contains five-scale user ratings on the songs, with approximately 1,000 songs and 15,400 users. The dataset has been pre-splitted by the publisher into training and testing, with a total of ∼300 thousand ratings in the training data. The training set is often regarded as missing not at random, and the testing set is missing completely at random (e.g. under uniform exposure).
• Coat. The Coat dataset is collected from 290 Amazon Mechanical Turk workers on a catalog of 300 coats. Each worker is asked to rate 16 self-selected coats, which is used as the training data. They then rate coats drawn completely at random (which can be considered as uniform exposure), which consists of the testing data.
Data preprocessing. As for preprocessing, we point out that the Movielens-1M 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.
The Yahoo!R3 and Coat datasets have been splitted by the publisher, and neither dataset have sequential information. Similar to the MovieLens dataset, we covert them to the implicit setting by treating those interactions whose rating>=3 as positive feedback (click). For the Yahoo!R3 dataset, we also filter out songs with less than 5 ratings.

heading: C.1.1 SIMULATION SETTING
text: We generate the implicit feedback (clicks) according to the click model of: P(Yui = 1) = P(Rui = 1) · P(Oui = 1), where Rui and Oui indicates the relevance and exposure. We refer to P(Rui = 1)
4http://files.grouplens.org/datasets/movielens/ml-1m.zip 5http://files.grouplens.org/datasets/hetrec2011/hetrec2011-lastfm-2k.zip 6https://sites.google.com/eng.ucsd.edu/ucsdbookgraph/home
as the relevance score. To carry over the inductive bias of the benchmark dataset to the generated data, we first learn P(Rui = 1) and P(Oui = 1) from the explicit feedback data of Movielens-1M 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 as the response. We then estimate Psim(Rui = 1) via σ(R̂ui − u)p, where σ(·) is the sigmoid function, and u and p are the two hyperparameters that help us control the overall relevance distribution between the original and generated data. For both Movielens-1M and GoodReads, we find u = 3 and p = 2 gives a decent approximation. In this way, we inherit the inductive bias for the relevance to the simulated data.
As for the exposure, we first assume all the exposed movies/books are rated by the user, so we have Oui = 1 if and only if Yui > 0. We then conduct another MCF using the converted Oui as response, and obtain the user and item embedding: Φ(u), Φ(i). We further design the exposure model by Psim(Oui = 1) = σ(MLP([Φ(u),Φ(i)])), where MLP(·) is a three-layer feed-forward 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: Psim(Yui = 1) = Psim(Rui = 1) · Psim(Oui = 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.

heading: C.1.2 TRAIN-VALIDATION-TEST SPLIT
text: We adopt the widely-acknowledged approach for splitting the dataset to training, validation and testing as in He et al. (2017) and Rendle et al. (2020). In particular, we leverage the ordering information and use the last interaction of each user for testing, the second-to-last 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 as random and conduct the splitting in the same fashion. We point out here that using sequential recommendation models is not reasonable in this case, so we do not experiment with the attention models (Attn) in the simulation experiments.
The Yahoo!R3 and Coat datasets have been splitted by the publisher, and both datasets do not have timestamps. We therefore split them by 80-20 into training and validation data. Note that Attn model cannot be experimented here since there is no sequential information.

heading: C.1.3 EVALUATION
text: 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@K and Recall@K. We also adopt the widely-acknowledged formulation of NDCG@K and Recall@K as from He et al. (2017) and Rendle et al. (2020): for each positive instance (clicked data) of (u′, i′, Yu′i′ = 1), we randomly sample 100 negative items {i1, . . . , i100} 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 metrics; however, it is still the mainstream approach that is used in the majority of existing literature. We apply them here so our results can be directly compared with the results in the relevant literature. To make up for the bias issue of using sampled metric, we further consider the Rel@K metric, which ranks all the items {i1, . . . , i|I|} and see where i′ is placed for each u′. In this way, we eliminate the bias of using sampled metric. Essentially, 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 train-validation-test split).
The only difference in computing the three metrics for the real-data and semi-synthetic experiments is that we replace Yu′i′ by the underlying relevance score of Psim(Ru′i′ = 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 previously-interacted 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.

heading: C.2 MODEL CONFIGURATION AND TRAINING
text: We provide the model configurations, training and computation details in this part of the appendix.

heading: C.2.1 MODEL CONFIGURATIONS
text: To achieve a fair comparison, we fix all the user and item embedding dimensions to d = 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 ℓ2 regularization parameter from {0, 0.01, 0.05, 0.1, 0.2, 0.3}. 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 ℓ2 regularization. For instance, NCF considers the hidden dimensions of the feed-forward neural network as the hyperparameters, IPW-CF considers the IPW threshold, Attn 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 transportation-regularized risk minimization, we focus primarily on using the same "base model" for f , w and g, e.g. with MCF, NCF or 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}.

heading: C.2.2 TRAINING DETAILS
text: For both the proposed approach and the baseline methods, we adopt the widely-applied negativesampling-based training schema according to He et al. (2017) and Rendle et al. (2020), 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 is 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, we 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-regularized risk minimization. When training with the proposed approach, the discount of learning rate (in Algorithm 1) is critical for the two-time-scale GDA. In a sense it resembles the number of gradient updates under the same learning rate, and we focus on their relative ratios. In practice, we allow the model of w in the minimization step to have a learning rate different from that of f . We denote the ratio for f , w and g as stepf , stepw and stepg. In practice, we select the ratio among {1 : 1 : 10, 1 : 5 : 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-the-shelf code, the MCF and NCF models are implemented according to their original implementation published on Github7, the IPW-debaised MF (IPW-MF) and user-exposure aware MF (ExpoMF) models are implemented using their published code8 with necessary modifications. The adversarial-counterfactual MF (AC-MF) method is also implemented using the published code9, which we apply directly to our datasets. The sequential recommendation model with attention mechanism is also implemented according to the original code10. 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
7https://github.com/hexiangnan/neural_collaborative_filtering 8https://github.com/usaito/unbiased-implicit-rec-real for IPW-MF and https:
//github.com/dawenl/expo-mf for ExpoMF. 9https://github.com/StatsDLMathsRecomSys/Adversarial-Counterfactual-

heading: Learning-and-Evaluation-for-Recommender-System
text: 10https://github.com/kang205/SASRec
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 a workaround to construct such data from non-uniform-exposure feedback data (Bonner and Vasile, 2018), 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.
Computation. All the models are implemented with the auto-differentiation framework of PyTorch11. 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 Adam12 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 relatively 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.

heading: C.3 COMPLETE NUMERICAL RESULTS

heading: MovieLens Simulation
text: 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.
Additional results for MovieLens-1M and its synthetic data. In Table A.2, we show the additional results for the MovieLens experiments, including using the proposed domain-transportation approach
11https://pytorch.org/ 12https://agi.io/2019/02/28/optimization-using-adam-on-sparse-tensors/
with different configurations of f , w and g (denoted by DT-(f/w/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 are the assignments for f , w and g, and M is short for MCF, N is short for NCF. Also, we experiment 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 (2018). 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 feedback 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 to the workaround when constructing the "uniform exposure" dataset from implicit feedback data.
Complete results for the LastFM data. In Table A.4, 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 can be efficiently estimated from the data. The settings, interpretations and notations for our approach are the same as above.
Complete results for the Yahoo, Yahoo Simulation, and Coat dataset. We focus on the various variants of MCF for these three datasets (IPW-MF, ExpoMF, AC-MF, DR-MF, CE-MF and our DT-MF). The Yahoo simulation dataset is generated in the same fashion as described above. We observe similar comparisons of those methods as for the other datasets, where the modified methods all improves the orginal MCF. Among them DT-MF leads to the most significant improvement, followed by DR-MF. The CE-MF method, on the other hand, suffers from a large variance since it relies on a "uniform exposure" dataset that is hard to obtain from implicit feedback data.
Complete results for the Goodreads simulation experiment. In Table A.3 and Table A.4, we show the complete results for the Goodreads experiments. Similarly, Attn does not apply to the synthetic data for the same reason discussed above.
We then present the complete results in correspondence to Figure 2. In Figure A.1, we the analysis of the learnt weights on the Goodreads data and its simulation. In Figure A.2, we show the same set of analysis for the LastFM dataset. Finally, in Figure A.3, we provide the ablation study and sensitivity analysis on λ, for both Goodreads and LastFM dataset.

heading: C.3.1 SENSITIVITY ANALYSIS ON THE OPTIMIZATION SETTING AND OVERLAPPING
text: To ensure the convergence of the minimax optimization without being trapped in a cycle, it is a standard practice to use the two-time-scale GDA algorithm. Our situation is even more involved since we not only have a minimax game, but there are two minimization players.
Intuitively, f is moved only when Pw has approximated Pf sufficiently well. It means that w has converged in the sense that dW (Pf , Pw) is sufficiently small. Since we use the Monge
and Kantorovich formulation to represent the 1-Wasserstein distance dW , i.e., dW (P,Q) = supg:∥g∥L≤1 ∫ D gdP − ∫ D gdQ, we need to ensure g to converge every time w moves so that the integral difference is approximately equal to dW (Pf , Pw). In other words, this is a three-layer loops: when f moves one step, we need w to move stepw steps until convergence; when w moves one step, we need g to move stepg steps until convergence.
Figure A.4a shows that as the stepw increases when stepg 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 stepg increases as stepw is fixed, which corroborates the claim that g should converge before w moves. These results suggest that we might want to use a large stepw and a large stepg . However, it can be computationally expensive. From our experience, we can use a relatively large stepg and a slightly smaller stepw to achieve a good performance. In addition, appropriate choices of learning rates lrf , lrw and lrg can expedite the convergence of w and g so that we can use less steps.

heading: C.4 ANALYSIS FOR THE COMPLETE RESULTS
text: We first observe from Table A.2 that the sequential recommendation methods achieve overall better performances than the others. It is expected because the sequential signal in the MovieLens-1M 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 our methods, they all improve the performance of the corresponding f model, and even outperforms the DT methods where f , w and g use the same "base model". This is a 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.3 and Table A.4 show the similar patterns. Firstly, using the proposed transportation-regularized 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/g) methods also achieve more significant improvements compared with the DT-f methods. We point out that the sequential recommendation method (Attn) does not particularly suit the dataset, since it is outperformed by the non-sequential methods. Still, DT-Attn achieves better performances than Attn. Finally, the additional results for the LastFM dataset in Table A.4 have the similar patterns.
As for the analysis on the learnt weights, we observe from Figure A.1 and Figure A.2 that the patterns we 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 or 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, 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. It means the weighting function works harder on balancing Pf with Pw, 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 are not clicked.

heading: C.5 EFFICIENCY ANALYSIS
text: 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 both the Movielens and Yahoo Music dataset, DT-X catches up and outperforms X in a couple of training epochs even before the X model converges.
2. The update of f, 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 f alone.

heading: C.6 DEPLOYMENT TO REAL-WORLD IR SYSTEM AND ONLINE TESTING
text: An important motivation of our work is to solve the practical challenges of industrial IR systems, and the working mechanism we described in Section 1 applies to most settings. In particular, many real-world recommenders are deterministic, and we can only expose a tiny proportion of the catalog 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 a realistic dilemma:
• if the candidate recommender f recommends products very differently from the previous exposure, then the feedback data may not provide enough evidence to assert the performance of f ;
• if the candidate recommender f recommends products highly similar to the previous exposure, 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 f to be sufficiently close to the reshaped feedback data domain. To test the competence of our approach for industrial tasks, we 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 product for a major e-commerce platform in the U.S. The platform hosts more than a hundred million products ranging from high-end electronics to 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 a modified version of the SGNS algorithm. When applying the item embedding to the model, we use the pre-trained embeddings as initialization and update the parameters with a lower learning rate than the other model parameters. We employ an architecture that is similar to the classical Deep-and-wide model, initially proposed by Cheng et 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 normalized
version (for controlling the variance) as the weighting function w, and then train f in a way similar to the baseline IPW-MF mentioned in Section 5;
• variation2: train f using the proposed transportation-regularized risk minimization, where w and f are neural CF models that take the item embeddings as 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 transportation-regularized risk minimization (variation2) consistently outperforms the original model (control) and the IW-adjusted model (variation1) in term of the gross merchandise value (GMV), which is the most critical metric for industrial recommender system. Also, the proposed approach improves the other monitored metrics (lower panel of Figure A.6) more significantly than the IW-adjusted model. Our deployment results further suggest the capability of the proposed approach for improving the performance of industrial IR systems.

heading: D EXTENDED LITERATURE REVIEW
text: When viewing our solution from the causal inference perspective, our objective resembles the counterfactual loss proposed by Shalit et al. (2017) focusing on individual treatment effect, which was also discussed in the following work (Johansson et al., 2019; 2020). Further, Johansson 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 counterfactual world in which they want to act. It leads to 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-policy learning and data missing-not-atrandom. Again, most existing methods treat the uniform-exposed domain as the target, while we aim at the deployment domain formed by the IR system. Further, most of them require either a sufficiently randomized logging policy or explicit ratings in the feedback, while our approach is primarily designed for implicit feedback under a deterministic policy. For instance, Sachdeva 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 on the explicit ratings to estimate the historical propensities (Wang et al., 2019; Saito, 2020; Liu et al., 2020). 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-robust optimization (DRO) (Kuhn et 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 as 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 in (2) and (3) tackle a min-min problem.

Review summaries:
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.    

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. 

The authors propose a novel way to learn new recommendation deterministic policies from feedback collected under different recommendation policies. The authors start by pointing out that the majority of current approaches, either Counterfactual (Inverse Propensity Weighting) either Domain Adaptation-based,  do 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). To 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. To 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.  The authors provide both theoretical and empirical evidence that the resulting algorithm outperforms existing SOTA methods.

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.