POTEC: Off-Policy Contextual Bandits for Large Action Spaces via Policy Decomposition

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

The paper did not discuss how the number of the cluster 'C' can affect the performance of the algorithm.

We have indeed discussed the effect of the cluster size $C$ from both methodological and empirical perspectives.

Firstly, in Section 3.3 on pages 7–8, we provide an interesting interpretation of our POTEC algorithm as a generalization of the policy-based and regression-based approaches. Here, the cluster size $C$ controls the extent to which POTEC relies on policy-based or regression-based components. Specifically, when $C$ is large, POTEC relies more on its policy-based component (i.e., the first stage). In contrast, using a small $C$ means that we rely more on the regression-based component (i.e., the second stage).

Secondly, we empirically evaluate the effect of $C$ on the performance of POTEC on Figure 5(ii). The figure suggests that POTEC is most sample-efficient with a moderate number of clusters, such as $|C| = 50$ or $100$. It is also noteworthy that POTEC does not underperform the baseline or logging policies even in the worst cases, such as when using overly small ($|C| = 10$) or large ($|C| = 1,000$) cluster spaces.

We are more than happy to discuss this point further if our response does not fully address the reviewer’s question.

1. How do you choose the number of cluster C?

This is indeed an important point to clarify. The number of clusters is a hyperparameter of POTEC, so we can tune it using the standard cross-validation procedure. However, it is important to perform careful off-policy evaluation (OPE) on validation data to evaluate the performance of each hyperparameter with low bias. To address the variance issue in large action spaces during validation, we recommend using OPE methods from:

• Noveen Sachdeva, Lequn Wang, Dawen Liang, Nathan Kallus, and Julian McAuley. Off-policy evaluation for large action spaces via policy convolution. WWW2024
• Jie Peng, Hao Zou, Jiashuo Liu, Shaoming Li, Yibao Jiang, Jian Pei, and Peng Cui. Offline policy evaluation in large action spaces via outcome-oriented action grouping. WWW2023.
• Yuta Saito, Ren Qingyang, and Thorsten Joachims. Off-policy evaluation for large action spaces via conjunct effect modeling. ICML2023.

These papers provide OPE estimators to deal with the variance issue in large action spaces. We will clarify how we can perform hyperparameter tuning for POTEC in the revised version of the paper.

2, how do you get the embedding of action a? Is it from the reward estimation? (more details of the clustering is beneficial)

Yes, in our experiments, we used the averaged estimated rewards for each action, $\hat{q}(a):=(1 / n) \sum_{i=1}^{n} \hat{q}\left(x_{i}, a\right)$, as the embedding of $a$ when performing action clustering.

This heuristic method for action clustering worked well and was sufficient to outperform existing OPE methods across a range of scenarios in both synthetic and real-world experiments. However, we believe a more principled and effective approach to action clustering for our method likely exists. As mentioned in Section 5, we consider the development of a clustering algorithm tailored to OPL as valuable future work.

3, do you assume the logging policy known? What if it is not known?

Thank you for the great question. We do not necessarily assume that the logging policy is known. In real-world applications, we encounter both known and unknown logging policies. In the relevant literature, it is standard to estimate the logging policy by predicting the action $a$ from the context $x$ on the logged data, when the logging policy is unknown. Similarly, we can estimate the cluster distribution under the logging policy $\pi_0(c|x)$ used in our method by predicting $c$ from $x$ on the logged data.

It is worth noting that, when we need to estimate the logging policy for our proposed method, we must also estimate it to implement existing methods such as IPS-PG and DR-PG, producing some bias in the gradient estimate. We will clarify this in the revision.

Thanks for the clarification. I raise my score to 8. And it would be beneficial to include more experiments about other logging policies.

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

The selection of the number of clusters is a crucial aspect of the proposed method, as illustrated in the numerical studies. The author could provide more details on how to select the number of clusters in the real-world applications.

This is indeed an important point to clarify. The number of clusters is a hyperparameter of POTEC, so we can tune it using the standard cross-validation procedure. However, it is important to perform careful off-policy evaluation (OPE) on validation data to evaluate the performance of each hyperparameter with low bias. To address the variance issue in large action spaces during validation, we recommend using OPE methods from:

• Noveen Sachdeva, Lequn Wang, Dawen Liang, Nathan Kallus, and Julian McAuley. Off-policy evaluation for large action spaces via policy convolution. WWW2024
• Jie Peng, Hao Zou, Jiashuo Liu, Shaoming Li, Yibao Jiang, Jian Pei, and Peng Cui. Offline policy evaluation in large action spaces via outcome-oriented action grouping. WWW2023.
• Yuta Saito, Ren Qingyang, and Thorsten Joachims. Off-policy evaluation for large action spaces via conjunct effect modeling. ICML2023.

These papers provide OPE estimators to deal with the variance issue in large action spaces. We will clarify how we can perform hyperparameter tuning for POTEC in the revised version of the paper.

Please provide more details on how to incorporate context-dependent clustering into the algorithm.

This is a good point. It is straightforward to incorporate context-dependent clustering into our algorithm. This can be achieved by applying a context-dependent clustering function, denoted as $c_{x,a}$, instead of the context-independent clustering $c_a$ in Eq. (7) and Eq. (10) when performing first- and second-stage policy learning for POTEC. We will clarify this in the revision.

The authors could compare the proposed method with Saito et al.,2023, highlighting performance differences and potential advantages/disadvantages.

We would like to clarify that Saito et al. (2023) focuses solely on the problem of off-policy evaluation, not off-policy learning as in our work, as described in Section 1 on page 2. Therefore, our method and that of Saito et al. (2023) are NOT comparable.

Please provide more details on data generating mechanism in the real-world experiment.

It is worth noting that the Kuairec dataset used in our real-world experiment is an actual real-world dataset, not a synthetically generated one. The dataset collection process is described in detail in the following paper, which we have already cited:

• Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, and Tat-Seng Chua. Kuairec: A fully-observed dataset and insights for evaluating recommender systems. CIKM 2022.

Additionally, the dataset schema is thoroughly described on their website: https://kuairec.com/

Using the dataset, we first randomly split the users into training (50%) and test (50%) groups. Then, we draw $n$ users ($x_i$) from the training set with replacement. For each context, we sample action $a_i$ from the logging policy and then sample the reward $r_i$ given $(x_i, a_i)$. This constructs the training logged dataset of the form $\mathcal{D} = \\{(x_i, a_i, r_i)\\}_{i=1}^n$. After training the policies on the train data, we evaluate their performance on the test set using the true reward function $q(x, a)$. This process is repeated 30 times with different draws in the training group.

We are more than happy to clarify our real-world experiment procedure further if the reviewer has additional clarification questions.

The authors could consider mentioning potential limitations of the proposed method.

Thank you for the valuable suggestion. There are indeed limitations to the proposed method, which we could not fully discuss in the main text due to space constraints. For example, using the averaged estimated rewards for each action to perform clustering was sufficient to outperform existing OPL methods, but is a heuristic approach. Thus, there remains room for improvement in the clustering method, as implied by the empirical comparison between POTEC w/ true clusters and w/ learned clusters performed in the synthetic experiment. We will clarify this point further in the revision.

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

Clustering the action space based on the scalar embedding of averaged marginal rewards seems somewhat surprising and not justified even informally -- can you comment on this? Have you considered a random bucketing strategy as a baseline for the first stage, and if so, how much better does proposed method do over this baseline?

This is an interesting point to discuss. The intuition behind the heuristic clustering used in our experiments is that by grouping (marginally) better and worse actions separately, the first-stage policy effectively removes most of the worse actions (note that the first-stage policy is context-dependent, so the cluster with the highest marginal reward may not necessarily be the best cluster for some contexts). It is important to remove those actions in the first stage, because the potential overestimation of worse actions by the regression model $\hat{q}(x,a)$ is often the main source of performance degradation in the second stage. This cannot be achieved by merely performing random clustering.

It is important to note that we acknowledge the current clustering method is heuristic. Indeed, in the synthetic experiment, POTEC with true clusters performed better than that with learned clusters, demonstrating the potential of POTEC with improved clustering methods. As discussed in Section 5, we believe that developing a more principled approach for action clustering is possible and is an intriguing future direction.

Following the reviewer’s interesting suggestion, we additionally compared POTEC with random clusters on synthetic data. The result is summarized in the following table, suggesting that heuristically learned clusters at least empirically outperform random clusters for a range of training data sizes, which is reasonable as discussed above.

(Note that the values indicate the test policy value relative to that of the logging policy, i.e., $V(\pi_{\theta})/V(\pi_0)$.)

Is there a typo in Equation (3)? should the third variance term on RHS be $\hat{q}(x,a)s_{\theta}(x,a)$

Thank you for pointing this out, but that is NOT a typo. We will provide the derivation in the revision, but as a quick reference, the following papers on off-policy evaluation (not learning, as in our work) derive the variance of the DR estimator. It can be observed that the term corresponding to the last term in our Eq. (3) depends on the true reward function, $q(x,a)$, rather than its estimate, $\hat{q}(x,a)$.

• Eq.(6) of Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudık. Optimal and adaptive off-policy evaluation in contextual bandits. ICML2017.
• Lemma 5.2 of Audrey Huang, Liu Leqi, Zachary C. Lipton, and Kamyar Azizzadenesheli. Off-Policy Risk Assessment in Contextual Bandits. NeurIPS2021.

Is there a fundamental reason for the theory to only work with the policy at the base stage and value at the second stage? A footnote on page 4 is discussing this, but the implication is unclear for whether this is a fundamental difference...

The point about importance weights made in the footnote on page 4 is indeed the fundamental reason, and we will clarify it further here. First, it is important to understand that the POTEC gradient estimator for the first-stage policy relies on cluster importance weighting, not vanilla importance weighting as used in existing methods. This is the primary strength of our proposed gradient estimator and results in variance reduction shown in Proposition 3.5. This variance reduction is particularly advantageous for large action spaces, where vanilla importance weighting of existing methods produces extreme variance.

The footnote argues that we lose this crucial advantage of the two-stage OPL framework if we use regression for the first stage and importance weighting for the second stage, because in this case, vanilla importance weighting is required to make the second-stage policy gradient unbiased. Consequently, the two-stage method would suffer from the same variance issue as IPS-PG and DR-PG.

To fully grasp this point, it would be important to understand the distinction between cluster and vanilla importance weighting, as well as the role of cluster importance weighting to reduce variance in our method. We are more than happy to discuss this point further if our response above does not fully address the reviewer’s question.

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

The paper did not specify how different clustering algorithm could impact the performance of POTEC from both theoretical point of view and empirical study.

This is a great point. From a theoretical standpoint, our current analysis already provides valuable insights. Specifically, the bias analysis in Theorem 3.2 indicates that the bias in the first-stage policy gradient estimation decreases when the estimation error for the relative value differences, $\Delta_{q}(x,a,b)$, within each cluster is small. Therefore, an effective clustering algorithm should lead to a better estimation of relative value differences within each cluster by a given regression model $\hat{q}(x,a)$.

In the synthetic experiment, we have already compared POTEC with true clusters and with learned clusters, demonstrating the impact of clustering quality on POTEC’s performance and the potential of POTEC with improved clustering methods.

Another reviewer was interested in comparing POTEC with random clusters, and we performed such an additional ablution study on synthetic data. The result is summarized in the following table, suggesting that heuristically learned clusters empirically outperform random clusters for a range of training data sizes.

(Note that the values indicate the test policy value relative to that of the logging policy, i.e., $V(\pi_{\theta})/V(\pi_0)$.)

How test data is constructed in empirical study (both synthetic and real world experiment)? For example, is there overlap of context between test data and training data, if so how much overlap?

We are happy to clarify this point. In the synthetic experiment, both the training and testing data follow the same distribution (Gaussian), so there is no covariate shift and their context spaces completely overlap. Please note that we ensured the training and testing data are different samples to evaluate and compare the generalization performance of the OPL methods.

For the real-world experiment, we first randomly split the users into training (50%) and test (50%) groups. Then, we draw $n$ users ($x_i$) from the training set with replacement. For each context, we sample action $a_i$ from the logging policy and then sample the reward $r_i$ given $(x_i, a_i)$. This constructs the training logged dataset of the form $\mathcal{D} = \\{(x_i, a_i, r_i)\\}_{i=1}^n$. After training the policies, we evaluate their performance on the test set using the true reward function $q(x, a)$. This process is repeated 30 times with different draws in the training group. Since the user split and data sampling are random, the context distributions in the training and testing sets are, in expectation, identical. We will clarify these settings in the revision.

What will happen if full cluster support condition is not met in logging policy? In the real world, how do you check if this condition is met?

We are happy to clarify this as well. If the full cluster support condition is not met, the proposed estimator for the policy gradient in Eq.(7) will be biased. However, the full cluster support is weaker than the standard cluster support (Condition 2.1), and thus existing estimators would produce larger bias in this case.

It is straightforward to analyze the bias of the POTEC gradient estimator when the full cluster support condition is violated by following the relevant derivation in (Sachdeva et al. 2020). Similarly, it is straightforward to verify whether this condition is satisfied by following its definition. Specifically, we first calculate the marginalized logging distribution regarding the cluster space, i.e., $\pi_0(c|x) = \sum_a \mathbb{I} \\{c_a = c \\} \pi_0(a|x)$, and then check if the condition $\pi_0(c|x) > 0$ holds for all $c$ and $x$.

• (Sachdeva et al. 2020) Noveen Sachdeva, Yi Su, and Thorsten Joachims. Off-policy bandits with deficient support. KDD2020.