Cross-Domain Off-Policy Evaluation and Learning for Contextual Bandits

We appreciate the valuable and thoughtful feedback from the reviewer. We respond to the concrete questions and comments in detail below.

Can the authors provide a theoretical comparison of COPE with the existing methods in the setting of deterministic logging policies?

This is a good point to clarify. Our current analysis already includes the scenario with deterministic logging as a special case. Specifically, Eq. (3) characterizes the bias of IPS when common support is violated, and when the logging policy is deterministic, nearly all actions are in the set $\mathcal{U}_0$, leading to an extremely large bias for IPS. (Note that it is straightforward to extend Eq. (3) to analyze the bias of DR.)

Even when the logging policy in the target domain is deterministic, it is still possible for Condition 3.1 to be satisfied, allowing the bias of our estimator to be characterized by Theorem 3.1. It is not straightforward to theoretically compare Eq. (3) and Theorem 3.1, so we conducted a comprehensive empirical analysis, demonstrating that our estimator reduces bias compared to IPS(T) and DR(T), particularly for cases with deterministic logging and entirely new actions. This bias reduction is one of the crucial factors to achieve much lower MSE by our estimator.

Can the authors provide a more detailed explanation of the clustering function, its practical implementation, and its impact on the performance of COPE? What guidelines can be offered for choosing appropriate clustering strategies in different domains?

Thank you for raising this important point for discussion. In our current experiments, we applied KMeans to the empirical average of the rewards in each domain to perform domain clustering, and this heuristic worked effectively and was sufficient to outperform existing methods across a range of experimental setups.

In practice, the number of clusters and the clustering function used can be considered hyperparameters of COPE. We can tune these hyperparameters rigorously by using estimator selection methods for OPE proposed in the following papers.

• Yi Su, Pavithra Srinath, and Akshay Krishnamurthy. Adaptive estimator selection for off-policy evaluation. ICML2020.
• Takuma Udagawa, Haruka Kiyohara, Yusuke Narita, Yuta Saito, and Kei Tateno. Policy-adaptive estimator selection for off-policy evaluation. AAAI2023.

We will clarify this point further in the revision.

How can these assumptions be verified in practice?

It appears that the reviewer is concerned about the satisfaction of the CPC condition. It is indeed almost impossible to verify this in practice, which is why we first analyze the bias of COPE when the condition is not satisfied in Theorem 3.1. It is also important to note that in challenging cases, such as deterministic logging and the presence of new actions, every existing estimator, including IPS and DR, produces much bias, but our estimator leverages source domain data and is much more robust to the bias arising due to those challenges. We conducted comprehensive experiments to compare the MSE, bias, and variance of the estimators across a range of challenging cases, and we demonstrated that our estimator performed best in most scenarios even with an estimated reward function ($\hat{q}$) that likely violates the condition.

Can the authors provide an analysis of the variance of the COPE estimator? How does the variance compare to existing methods? What is the bias of COPE when the conditions for unbiasedness are not met?

Thank you for suggesting interesting analyses. First, it is important to note that Theorem 3.1 already provides the bias of COPE when the CPC condition is not satisfied. It is also straightforward to analyze the bias of COPE under violations of Condition 3.1 in a manner similar to Eq. (3). Additionally, it is possible to analyze the variance of COPE. Intuitively, COPE has lower variance than IPS and DR due to the additional use of source domain data. Furthermore, COPE has lower variance than IPS-ALL and DR-ALL due to the use of multiple importance weighting techniques, as already shown in (Agarwal et al., 2017; Kallus et al., 2021). The variance reduction effect of COPE has also been empirically demonstrated in our experiments as well.

We appreciate the valuable and thoughtful feedback from the reviewer. We respond to the concrete questions and comments in detail below.

This paper does not compare with significant literature focused on the limited overlap problem. For instance, the assumptions in Condition 3.1 and the subsequent proof of unbiasedness are fundamentally similar to those in [1, 2], which also assume that while the original x may not satisfy the overlap assumption, there exists a score or representation that does.

Thank you for providing these valuable references; we will cite them in the revised version of the paper. It is important to note, however, that the problem setup and methods proposed in the papers suggested by the reviewer are substantially different from ours and are not directly comparable.

First, the papers suggested by the reviewer focus on causal effect estimation, while we study off-policy evaluation and learning of contextual bandit policies. In particular, the policy learning problem is not considered at all in those previous works.

Second, the papers suggested by the reviewer address limited overlap in $x$, whereas we deal with the limited overlap regarding the action $a$. We even tackle the problem of completely new actions, which is a distinct and unique aspect of our work.

Third, we address the issue of limited overlap in $a$ by leveraging structure across different domains, while the papers suggested by the reviewer leverage structure within a single domain. Indeed, we could not find the term “cross-domain” in the text of these papers, which indicates that our approach and the prognostic score approach in these works could potentially be combined. This suggests that our work and these previous works are orthogonal to each other.

As discussed here, our motivation, formulation, and approach are substantially different from those of previous work. We will clarify this distinction in the revision.

the absence of a real cross-domain experimental validation, relying instead on semi-simulated experiments, limits the contribution of this work.

Thank you for raising this important point. We agree that it would be ideal to conduct empirical evaluation on a real-world cross-domain dataset; however, there is currently no public dataset available that enables such an experiment in the off-policy bandit setup. It is indeed standard to perform fully synthetic or semi-synthetic experiments in most of the relevant papers we discussed in Section 1 on page 2, and this limitation applies not only to our work but also to most other related studies. We will clarify this point in the revision.

The reviewer thankfully shared a few papers in the initial review, but we are confident that their methods do not aim to address the specific challenges that our methods tackle (deterministic logging and new actions). It should be noted that the other reviewers explicitly reference “deterministic logging” and “new actions” in their reviews or discussion, while the reviewer states only:

This paper focuses on addressing the problem of OPE/L when the common support assumption is not met.

Thus, it is unclear if the reviewer is aware of the difference between the mere violation of common support and its harder scenarios of deterministic logging and new actions. It is crucial to ensure the reviewer fully understands our key motivations and contributions, as the other reviewers thankfully do.

We have revised our text to improve clarity regarding deterministic logging and new actions and to emphasize that these represent harder versions of the typical limited overlap or deficient support problem (the updates are highlighted in red in the text).

Regarding Real-world Data Validation: Consider examining multi-domain recommendation literature, which utilizes real-world datasets (e.g., MovieLens-1M, KuaiRand-Pure). Evaluation metrics can be diversified beyond semi-synthetic ground truth to include proxy indicators (e.g., total gains, AUC) that demonstrate real-world utility.

Thank you for suggesting the datasets and metrics. We have considered using them, however, it is unclear what specific value these datasets and metrics add to our research.

First, it is important to note that the MovieLens dataset does not provide a full-reward matrix, which is crucial for performing OPE/L without synthesizing the reward function, as described in [Gao et al. 2022]. Additionally, we looked at one of the latest papers on cross-domain recommendations [Yang et al. 2024]. The paper uses MovieLens and defines different domains based on user features (e.g., gender), which is essentially the same approach we use to produce domains in our experiments. Given that the MovieLens dataset lacks a full-reward matrix and thus we need to synthesize it, we are unclear how an additional experiment using MovieLens produces value compared to our current experiments.

Second, the reviewer suggested using the KuaiRand dataset. We are similarly confused with this suggestion, because KuaiRand is a dataset targeted for the task of sequential recommendation collected on the Kuaishou app. We have already used the KuaiRec dataset (https://kuairec.com/) that was collected on exactly the same app, and is more suitable for our setup of OPE/L in contextual bandits. We agree that KuaiRand is more suitable if we are focusing on a sequential problem such as reinforcement learning, but this is indeed not the case for our work. In addition, KuaiRand does not provide multiple domains, meaning we would need to generate domains ourselves, as we have already done in our experiments or as done in [Yang et al. 2024]. Therefore, we are not yet sure why using the KuaiRand dataset would add value to our research, given that we have already used the KuaiRec dataset from the same platform.

If the reviewer has more specific experimental designs for using these datasets to produce more advantageous and insightful experiments for the specific problem of cross-domain OPE/OPL compared to what we have provided, we would need to understand those designs in detail to have a more constructive discussion.

Additionally, the reviewer suggested a few proxy indicators, but it is unclear what is meant by “total gains.” We would appreciate a rigorous definition to discuss if it would be meaningful to add it as a reward in our experiments. We are also confused by the suggestion of using AUC, as it is a ranking or classification metric. Given that the reviewer is proposing a metric that is irrelevant to our off-policy learning setup with a single action, there may be a misunderstanding that we are addressing a ranking/classification problem and aiming to maximize an AUC-type metric, which does not align with our formulation. Regarding this context, we think it is important to note that the issues we are tackling are agnostic to how we define the reward. Therefore, we would need to understand why the reviewer thinks it is important to test various reward definitions, even though it is a more general problem and is not directly relevant to our focuses such as deterministic logging, new actions, and the cross-domain formulation.

Here are the references we used in the response:

[1] Hansen B B. The prognostic analogue of the propensity score[J]. Biometrika, 2008, 95(2): 481-488.

[2] Wu P, Fukumizu K. beta-Intact-VAE: Identifying and Estimating Causal Effects under Limited Overlap[J]. arXiv preprint arXiv:2110.05225, 2021.

[Sachdeva et al. 2020]: Noveen Sachdeva, Yi Su, Thorsten Joachims. Off-policy Bandits with Deficient Support. KDD2020.

[Gao et al. 2022]: Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, Tat-Seng Chua. KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems. CIKM2022.

[Yang et al. 2024] Zhiming Yang, Haining Gao, Dehong Gao, Luwei Yang, Libin Yang, Xiaoyan Cai, Wei Ning, Guannan Zhang. MLoRA: Multi-Domain Low-Rank Adaptive Network for CTR Prediction. RecSys2024.

We appreciate the valuable and thoughtful feedback from the reviewer. We respond to the concrete questions and comments in detail below.

What are the challenges that make the cross-domain application more difficult/particular compared to the large action space scenario?

We would like to address a potential critical misunderstanding by the reviewer. Our motivation is substantially different from that of OPE/L for large action spaces; our main focus is on addressing issues such as extremely small sample sizes, deterministic logging, and new actions in the target domain, rather than to address the variance issue of importance weighting in large action spaces. Moreover, in our setup, we do not assume access to action features or embeddings, making methods developed for OPE/L in large action spaces infeasible. Our work demonstrates that we can still handle these challenging cases by leveraging both target and source domain data in a principled way. If action embeddings are available, our method can even be combined with methods developed for large action spaces, indicating that our formulation and OPE/L for large action spaces are orthogonal to each other.

If it is just deterministic policies/deficient support, then it is not different than the case of large action spaces.

We respectfully disagree with the reviewer on this point. Our problem setup for cross-domain OPE/L is substantially different from that of OPE/L for large action spaces. First, we do not assume access to action embeddings. We also consider cases with completely new actions in the target domain, making it infeasible to perform representation learning of actions to obtain such embeddings. In addition, as we described above, if multiple domains and action embeddings are both available, it is possible to combine our estimator with approaches developed for large action space problems. This suggests that our approach is orthogonal to methods designed for large action spaces. It seems important for the reviewer to understand that methods developed for large action spaces are simply infeasible in our problem setup.

What is the originality of the bias/variance study of the COPE estimator?

Our analysis is original because we are the first to analyze the statistical properties of an estimator specific to OPE for the cross-domain setup. If the reviewer is aware of any existing paper that improves and analyzes OPE in the cross-domain setup, we would be more than happy to discuss it. If no such paper exists, this would mean that we are the first to propose and analyze a principled approach for leveraging cross-domain data to expand the applicability of OPE/L.

While it is true that our analysis is inspired by existing methods for large action spaces (as we have already mentioned in our paper), no one previously demonstrated that cross-domain data could be leveraged through the high-level decomposition approach. It might seem straightforward after seeing the formulation that we developed, but it is not at all straightforward to come up with it from scratch. This is why it is worth writing a whole new paper to formulate this problem setup and to demonstrate the effectiveness of our approach to leverage cross-domain data from both theoretical and empirical perspectives.

How can you be sure that your OPL method will converge to the right policy?

We are not certain what the reviewer means by “the right policy” in the question.

If this refers to the “optimal” policy, no methods converge to it in scenarios with deterministic logging and new actions due to severe bias in policy gradient estimation. This is why we empirically compare the effectiveness of off-policy learning methods under those challenging (but prevalent) cases comprehensively. Our experiments demonstrate that our OPL method outperforms existing methods under the challenging scenarios, by leveraging source domain data to reduce bias and variance in estimating the policy gradient for the target domain and for new actions.

Is there a reason why you omit the whole OPL literature based on pessimism?

This is simply because we did not aim to study the effectiveness of the pessimism approach in our work. It is important to understand that our main motivation is to provide an approach that leverages both source and target domain data to perform OPE/L more effectively, even when the target data is extremely limited, involves deterministic logging, or includes new actions. Pessimism is irrelevant in this context because it does not address the specific challenges we tackle. However, it is straightforward to incorporate pessimism with our OPL method if one wants to do so in practice. We will clarify this point in the revision.

Actually, the same decomposition was used multiple times in a multitude of applications [4, 5, 6], because all these applications present the same underlying challenges.

These are indeed very interesting references! The fact that these papers ([4, 5, 6]) have been accepted by top-tier conferences demonstrates that formulating and solving a new problem using a (seemingly) similar decomposition approach, along with providing relevant empirical demonstrations, is indeed considered a valuable and non-trivial contribution.

It seems the reviewer believes it is trivial to apply the decomposition approach to a different problem setup. If it is indeed true that the reviewer immediately came up with the cross-domain setup upon learning about the decomposition approach, it would be truly impressive and extraordinary. However, this is not the case for many other potential readers, which is one of the reasons why the previous conferences evaluate papers like [4, 5, 6] as worth sharing with the relevant audience. If the reviewer believes that only our contribution is not worth presenting, despite the existence of those multiple similar “types” of contributions that have been accepted as the reviewer mentioned, we would be really eager to learn the reviewer’s reasoning behind this. Such feedback would be valuable in improving our approach to research in general.

But the analysis does not tell us anything about the difficulty of the cross-domain setup, as it is purely based on a decomposition technique used in other applications.

As we have demonstrated above, in the presence of deterministic logging and new actions, the existing decomposition approach of OffCEM cannot be unbiased or address the residual effect in the off-policy setup. Our bias analysis indicates that the residual effect can be addressed depending on the pairwise accuracy of $\hat{q}$ and that it can be unbiased under Condition 3.2. This is in contrast to OffCEM, which cannot achieve unbiasedness under any additional conditions in the presence of deterministic logging and new actions. Therefore, our analysis provides new insights that did not appear in the previous papers, and thus we do not think that our analysis “purely” relies on previous results.

It is also important to clarify that we do not necessarily aim to highlight the “difficulty” of the cross-domain setup. Instead, we regard source domain data as "additional" information that can potentially be leveraged to address the already challenging issues. Nevertheless, we can still discuss the difficulty of the cross-domain setup, particularly as it relates to the varying distributions across domains, as we will elaborate on in the following section.

For example, what is the bias of IPS-ALL/DR-ALL in this setup? and how can we be sure that COPE improves it?

We can derive the bias of IPS-ALL as follows (we will include the detailed derivation and the bias of DR-ALL, which is a straightforward extension, in the revision).

$Bias (\hat{V}\_{\mathrm{IPS}} (\pi ; \mathcal{D})) = | \mathbb{E}_{p_T(x)\pi(a|x)}[q^T(x,a)] - \sum\_k \frac{n^k}{N} \mathbb{E}\_{p_k(x)\pi(a|x)}[q^k(x,a)] |$

We observe that it is no longer guaranteed to remain unbiased in our setup. This bias becomes significant when the reward distributions across domains differ substantially because the expectation of IPS-ALL is characterized by the weighted sum of the policy values of all the domains involved. In contrast, the bias becomes zero when the reward distributions across all domains are identical (which is no longer a cross-domain setup).

Based on this derivation and Theorem 3.1, we can compare the bias of COPE and that of IPS/DR-ALL as follows:

• COPE performs better when the distributions across domains are substantially different and also when the pairwise estimation by $\hat{q}$ is accurate.

• IPS/DR-ALL performs better when the distributions across domains are similar, i.e., when the cross-domain setup is close to the typical single-domain setup.

When the setup is close to the typical single-domain scenario, effective estimators such as DR and its extensions are already well-known. Therefore, we focused more on novel and challenging scenarios where the distributions across domains are not necessarily similar, as baseline methods tend to fail in these cases as shown above and in our experiments.

In practice, we do not precisely know which of COPE and baselines are better. This is not the case only for our setup, but also for the other OPE problems. A typical example is that we never know which of IPS and DM is better, because the comparison depends on many (potentially unknown) parameters such as the reward noise. This is why there exists an orthogonal line of work around estimator selection in OPE [7, 8, 9, 10], and we can use those methods to identify the appropriate estimator tailored to the specific problem when we use OPE in general and in the cross-domain setup.

I thank the authors for their thorough answer, It really helped me understand the work more. I will try to keep my response brief.

• Thank you for clarifying the differences between OffCEM and COPE. Indeed, even if the decomposition is similar, and that OffCEM can deal with some challenges in the one domain application (variance issues and deficient support), COPE uses this decomposition differently (with clustering on the domain) and tackles more severe challenges (deterministic logging policy on the target domain).

• Limitations of the approach should be discussed openly, for instance, these severe challenges (deterministic logging policy on the target domain) can only be tackled in the presence of nice data from other domains (stochastic policies in other domains for instance). It should also be highlighted that clustering the average reward will not always work if the average reward on all domains is the same, but the distribution of $r(a,x)$ is different in all domains. Another limitation that was not raised before, is the estimation of $p^{\phi(T)}(x, a)$ that involves ratios of covariate densities $p^k(x)$. The synthetic experiments conducted assume access to $p^k(x)$, which is far from practice. Indeed, these densities are hard to model in real world scenarios and estimating them will bias the approach, meaning that adopting this method in practice will require substantial effort and will always suffer from additional modelling bias.

• Pointing to [4, 5, 6] was to show that a lot of works are adopting these techniques and novelty comes from the application more than the technique itself, actually, [4, 5, 6] were all published in applied conferences. If the paper is positioned as applied work, it is fine, but I deem that the paper needs more challenging experiments than the synthetic ones to properly validate the approach.

• Thank you for the developed bias discussion, it may be added to the appendix. I think it can be of benefit to readers. A rigorous theoretical comparison between estimators in the cross domain setting will require another paper.

• Questions :

  • Did you try harder experiments where you do not have access to $p^k(x)$, and experiments with really difficult $p^k(x)$ to model?

Furthermore, we can extend the definition of the user distribution as:

$p^{k}(u):=\frac{\exp (\lambda \bar{q}(u) + (1-\lambda) f^k(u))}{\sum_{u^{\prime} \in \mathcal{U}} \exp (\lambda \bar{q}(u’) + (1-\lambda) f^k(u')))}$

where $\lambda$ controls the degree to which the user distribution depends on $\bar{q}(u)$. When $\lambda = 1$, the setup reduces to our original experiment. The following reports the OPL experiment with varying $\lambda$ within $\\{ 0, 0.2, 0.4, 0.6, 0.8, 1.0 \\}$.

Test (Relative) Policy Value in OPL for varying $\lambda$ values (values are larger the better)

We should mention here that the difference between the proposed method and the baselines decreases when $\lambda$ is small, which validates the reviewer’s comment. These additional observations, however, demonstrate the robustness of COPE to varying user distributions, even with a simple clustering procedure. Nevertheless, we believe a more principled and effective approach to domain clustering for our method likely exists. As mentioned in Section 5, we consider the development of a clustering algorithm tailored to Cross-Domain OPE and OPL to be a valuable direction for future research.

As a side note, we have updated our draft to include clarifications on points discussed with the reviewers, such as data-driven tuning of cluster numbers, bias comparisons against IPS/DR-ALL, density ratio estimation, and the convergence properties of COPE-PG under the CPC condition. We have also clarified that “deterministic logging” and “new actions” can be interpreted as harder versions of the common support violation to avoid confusion. These updates are highlighted in red in the text. We would greatly appreciate it if the reviewer could confirm whether the additional results address their main concern or if there are any remaining issues that require further discussion.

[Yang et al. 2024] Zhiming Yang, Haining Gao, Dehong Gao, Luwei Yang, Libin Yang, Xiaoyan Cai, Wei Ning, Guannan Zhang. MLoRA: Multi-Domain Low-Rank Adaptive Network for CTR Prediction. RecSys2024.

We appreciate the valuable and thoughtful feedback from the reviewer. We respond to the concrete questions and comments in detail below.

1a I am curious about the condition 3.2, is this a common and reasonable assumption? It is better to provide more insightful comments on when this assumption will hold in practice.

We would like to clarify that we do not expect Condition 3.2 to hold in practice. It is simply a condition that helps to understand when COPE can be unbiased. This is why we first present Theorem 3.1, which characterizes the bias of COPE without assuming Condition 3.2. It is also important to note that in challenging cases, such as deterministic logging and the presence of new actions, every existing estimator, including IPS and DR, produces much bias, but our estimator leverages source domain data and is much more robust to the bias arising due to those challenges. We conducted comprehensive experiments to compare the MSE, bias, and variance of the estimators across a range of challenging cases, and we demonstrated that our estimator performed best in most of such scenarios. This empirically demonstrates the effectiveness of leveraging cross-domain data through our approach even with an estimated reward function ($\hat{q}$) that likely violates Condition 3.2.

1b It is hard for me to understand the paragraph in line 314-320. Why is the estimator unbiased when its cluster size is equal to 1?

We are happy to clarify this point. When the cluster size is 1, the CPC condition becomes less stringent, resulting in COPE producing a smaller bias. The CPC condition requires that a regression model $\hat{q}(x,a)$ preserve the relative reward differences between different domains within the target cluster (as described in L291–299). When there is only one domain in the target cluster, CPC holds by definition, as the relative reward difference is always zero within a single cluster. In contrast, when there are many domains in the target cluster, the regression model must accurately estimate the relative reward differences for numerous domain pairs, making it more challenging to satisfy this condition, thereby producing some bias.

1c I also feel curious about using the off-the-shelf clustering algorithm based on empirical average. How does it work in your theoretical analysis? If the rewards are not very symmetrically distributed, i.e. heavy-tailed distributed, then the empirical mean will lead to terrible estimation, so how to deal with this issue in practice?

It is important to note that our theoretical analysis, including Theorem 3.1, is agnostic to the clustering method; the analysis applies to any given clustering function. Theorem 3.1 suggests that when the relative reward differences between different domains within the target cluster are accurately estimated by $\hat{q}$, the bias of COPE becomes small. Therefore, an effective clustering method is the one that leads to a better estimation of the relative reward differences within the target cluster for a given $\hat{q}$.

In our current experiments, we applied KMeans to the empirical average of the rewards in each domain to perform clustering, and this heuristic worked effectively and was sufficient to outperform the existing methods across a range of experimental setups. In practice, the number of clusters and the clustering function used can be considered hyperparameters of COPE. We can tune these hyperparameters rigorously by using estimator selection methods for OPE proposed in the following papers.

• Yi Su, Pavithra Srinath, and Akshay Krishnamurthy. Adaptive estimator selection for off-policy evaluation. ICML2020.
• Takuma Udagawa, Haruka Kiyohara, Yusuke Narita, Yuta Saito, and Kei Tateno. Policy-adaptive estimator selection for off-policy evaluation. AAAI2023.

We will clarify this point further in the revision.

1d is there a final regret bound in this paper in terms of the magnitude of $T$ like other bandit works.

We would like to address a potential critical misunderstanding by the reviewer. Our formulation is for an offline contextual bandit, not an online bandit, so regret bound analysis is indeed irrelevant to our work.