POTEC: Off-Policy Contextual Bandits for Large Action Spaces via Policy Decomposition
Off-Policy Learning;Contextual Bandits;Large Action Space;Importance Weighting;Clustering;Policy Gradient
Yes
No ethics review needed.
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?

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?
The paper introduces a novel two-stage approach to address the challenges of large action spaces in off-policy learning.

It demonstrates high quality through rigorous theoretical proof of the unbiasedness of the POTEC gradient estimator under local correctness condition, and shows how cluster-level importance weighting effectively reduces variance.

The paper provides clear theoretical justification for the two-stage decomposition and progresses logically from the problem formulation to the solution.

the paper addresses fundamental challenges in large-scale off-policy learning by providing a unified framework with theoretical guarantees for the joint optimization of two-stage policies.
This paper introduces POTEC, a novel off-policy learning (OPL) method designed to handle large action spaces, a common challenge in real-world recommendation systems. The algorithm decomposes the policy into two stages: a first-stage policy that selects promising action clusters, and a second-stage policy that chooses specific actions within the selected cluster. The paper provides theoretical analysis showing that POTEC achieves unbiased gradient estimation under a local correctness condition. It also shows its cluster-based importance weighting leads to substantially lower variance compared to traditional methods. The authors present a complete learning framework, including how to optimize both policies through a combination of policy-based and regression-based approaches. Through extensive experiments on both synthetic and real-world recommendation data, POTEC demonstrates superior performance compared to existing methods such as IPS-PG and DR-PG, particularly when dealing with sparse action observations in logged data and large action spaces.
The paper did not specify how different clustering algorithm could impact the performance of POTEC from both theoretical point of view and empirical study.

There could be more details provided on how the test data is constructed in empirical study.
Yes
No ethics review needed.
- 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?


- Is there a typo in Equation (3)? -- should the third variance term on RHS be $\hat{q} (x, a) s_\theta (x, a)$ ? For easier verification, please consider adding a quick derivation of this to the appendix.


- 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 the importance weights being an issue doesn't seem convincing since the same reasoning applies to the first stage in the current proposal.
- Novel general approach for combining policy and value based learning methods in a hierarchical fashion so as to avoid bias and variance simultaneously.
- The paper is very well written and a pleasure to read
- Good discussion of related literature and its context for the current work.
The authors derive a novel theoretical framework for off policy contextual bandits that strictly generalizes the complementary approaches of policy based and value based methods via a two stage decomposition involving both. It is argued that this provides a non-trivial advantage in large and structured action spaces. The two stage decomposition involves first using a policy based parametrization to identify an action cluster, followed by a regression based approach within each cluster to discriminate between the fine grained individual actions.
- A good bit of the technical novelty in the current paper is shared with  prior work [Saito et. al. 2023] which the authors duly point out. Having said, that the prior work applies a similar idea for off policy estimation while the current work deals with policy optimization.

- No satisfactory general recipe to perform the right kind of clustering that can best exploit such a two stage decomposition.

- The main issue with a regression based approach is non-zero bias due to model capacity as the authors point out,  and in practice this error seems more plausible to have its source in an inability to fit within cluster, if at all, rather than across clusters. However, this is precisely what is assumed for a good performance in the second stage. If it is assumed to do sufficiently well in the second stage, wouldn't this somehow make the problem more likely to achieve a low error for a simple supervised learning global fit?
Yes
No ethics review needed.
1.	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.
2.	Please provide more details on how to incorporate context-dependent clustering into the algorithm.
3.	The authors could compare the proposed method with Saito et al.,2023, highlighting performance differences and potential advantages/disadvantages.
4.	Please provide more details on data generating mechanism in the real-world experiment.
5.	The authors could consider mentioning potential limitations of the proposed method.
1. The authors study an important problem of off-policy learning for contextual bandit policies in large discrete action spaces.
2. The theoretical analysis of the bias and variance for policy gradient estimator makes the work more solid and convincing.
3. The authors perform comprehensive numerical studies to demonstrate the performance of the proposed algorithm
This work studies the problem of off-policy learning for contextual bandit policies in large discrete action spaces. The authors propose an approach that decomposes the overall policy into two components: a cluster-selection policy and a conditional action-selection policy. To optimize the cluster-selection policy, they derive a policy gradient, while a pairwise regression procedure is used to learn the conditional action-selection policy. The authors provide a thorough analysis of the bias and variance of the proposed policy gradient estimator, which makes the work more solid and convincing. The authors perform comprehensive numerical studies to demonstrate the performance of the proposed algorithm compared to several baselines.
The clarity of the writing could be further improved by providing more details on certain aspects, such as practicability of the algorithm and experiment settings. See Questions section.
Yes
No ethics review needed.
1, How do you choose the number of cluster C? 

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

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

4, Is the logging dataset sampled based on the ground-truth cluster? If I understand correctly when creating the logging dataset, you first cluster the action based on the reward of $(x,a_i)$, and then you have a reward for both cluster r(x,c_a) and r(x,a|c). What if the reward is not in this hierarchy way? For example, if the reward function is just defined as r(x,a) instead of the reward of cluster + reward of the action. Or, in other words, what if the logging policy is not defined as Eq.(11)? I believe that this algorithm might benefit from the logging policy and reward definition while it might not work that well in a more general logging policy. Because the logging policy itself is somehow a two-stage policy.

I am willing to further raise my score if these questions are addressed.
1, propose a novel new two-stage policy for OPL for bandits with large action space and the intuition/motivation is well-justified.

2, provide a variance and bias analysis of the gradient of the proposed algorithm and connect with the algorithm. Also, the proposed gradient has a smaller variance than the IPS method. 

3, the paper is well-written, solid, easy to follow.
This paper provides a solution to off-policy learning for large action spaces through a two-stage policy. The action space is first clustered with action embedding (reward). Then, the first-stage policy selects an action cluster, and the second-stage policy selects an action within the cluster. The two-stage policy is updated with the policy gradient method, providing a bias and variance analysis of the gradient. They show that the bias of the gradient is controlled by the relative difference in the reward estimation and can be further reduced with a pairwise regression if possible. Also, they show that the variance of the gradient is significantly smaller than the gradient of the original action space (which is straightforward). Empirical studies demonstrate its effectiveness.
1, The paper did not provide very detailed description of the clustering algorithm. More details will be preferred. 

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

3, They did not experiment with other logging policy settings. 

4, Others, see questions.
We propose a new two-stage off-policy learning algorithm called POTEC, which unifies regression- and policy-based approaches via a policy decomposition and is particularly effective in large action spaces.
@inproceedings{
anonymous2024potec,
title={{POTEC}: Off-Policy Contextual Bandits for Large Action Spaces via Policy Decomposition},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=LXftdR11io},
note={under review}
}
We study off-policy learning (OPL) of contextual bandit policies in large discrete action spaces where existing methods -- most of which rely crucially on reward-regression models or importance-weighted policy gradients -- fail due to excessive bias or variance. To overcome these issues in OPL, we propose a novel two-stage algorithm, called Policy Optimization via Two-Stage Policy Decomposition (POTEC). It leverages clustering in the action space and learns two different policies via policy- and regression-based approaches, respectively. In particular, we derive a novel low-variance gradient estimator that enables to learn a first-stage policy for cluster selection efficiently via a policy-based approach. To select a specific action within the cluster sampled by the first-stage policy, POTEC uses a second-stage policy derived from a regression-based approach within each cluster. We show that a local correctness condition, which only requires that the regression model preserves the relative expected reward differences of the actions within each cluster, ensures that our policy-gradient estimator is unbiased and the second-stage policy is optimal. We also show that POTEC provides a strict generalization of policy- and regression-based approaches and their associated assumptions. Comprehensive experiments demonstrate that POTEC provides substantial improvements in OPL effectiveness particularly in large and structured action spaces.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Off-Policy Learning Contextual Bandits Large Action Space Importance Weighting Clustering Policy Gradient
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/b5072aa3d24d394edb31507673623b0219b0d6df.pdf
reinforcement learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/74103807ec502ce33e01beee72048395d4bd6a84.zip
POTEC: Off-Policy Contextual Bandits for Large Action Spaces via Policy Decomposition
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission