POTEC: Off-Policy Learning for Large Action Spaces via Two-Stage Policy Decomposition

Yuta Saito, Jihan Yao, Thorsten Joachims

Abstract

Off-policy learning (OPL) in environments with massive action spaces—such as recommendation systems or large-scale classification—faces a fundamental bias-variance trade-off. Policy-based methods suffer from extreme variance as action spaces grow, while regression-based methods are prone to high bias from model misspecification. We present POTEC (Policy Optimization via Two-Stage Policy Decomposition), a framework that decomposes the policy into a policy-based cluster selection stage and a regression-based intra-cluster action selection stage. By requiring only "local correctness" of the reward model, POTEC achieves superior performance and stability in large-scale applications.

Introduction: The Bias-Variance Dilemma

In modern interactive systems, learning from historical logs (Off-Policy Learning) is essential for improving user experience without risky online exploration. However, when the number of possible actions reaches the thousands or millions, traditional OPL estimators fail:

  1. Policy-based methods (e.g., Inverse Propensity Scoring): These are theoretically unbiased but suffer from extreme variance. In large action spaces, the probability of the logging policy selecting a specific action becomes infinitesimal, leading to exploding importance weights and unstable learning.
  2. Regression-based methods: These are stable but suffer from high bias. They rely on a reward model to predict outcomes for all actions. If this model is even slightly misspecified—a common occurrence in complex real-world environments—the resulting policy will be suboptimal.

POTEC addresses this "bias-variance dilemma" by bridging the gap between these two paradigms.

The POTEC Framework

The core innovation of POTEC is the decomposition of the decision-making process into two distinct, manageable stages. This approach allows the system to leverage the strengths of both policy-based and regression-based methods while mitigating their respective weaknesses.

The POTEC two-stage framework: (1) Action Clustering, (2) 1st-Stage Policy for cluster selection, and (3) 2nd-Stage Policy for picking the best action within the chosen cluster.

Step 1: Cluster Selection (Policy-Based)

Instead of attempting to select a single action from a massive set, the first-stage policy $\pi_{\theta}^{1st}$ selects a cluster of actions $c$. Because the number of clusters is significantly smaller than the total number of actions, the importance weights remain stable. This stage effectively acts as a variance buffer.

Step 2: Intra-Cluster Action Selection (Regression-Based)

Once a cluster is selected, the second-stage policy $\pi_{\psi}^{2nd}$ identifies the best action $a$ within that specific cluster. This selection is guided by a reward regression model. By limiting the regression task to a small subset of actions, the impact of global model misspecification is minimized.

Theoretical Foundation: Local Correctness

A critical theoretical contribution of POTEC is the concept of Local Correctness. Traditional regression-based OPL requires a globally accurate reward model to ensure policy quality. In contrast, POTEC only requires the regression model to be "locally correct"—meaning it must accurately rank the relative differences between actions within the same cluster.

This insight makes POTEC far more resilient to model misspecification. Even if the reward model fails to accurately predict absolute rewards across the entire action space, it can still guide the second stage effectively as long as it identifies the best action within the chosen cluster.

Empirical Evaluation

The researchers evaluated POTEC against standard baselines like IPS-PG (Inverse Propensity Scoring Policy Gradient) and DR-PG (Doubly Robust Policy Gradient).

Datasets

  • Synthetic Data: Controlled environments with up to 4,000 actions and 30 clusters, used to test robustness against noise and data sparsity.
  • Extreme Classification: Real-world datasets EUR-Lex 4K (~4,000 actions) and Wiki10-31K (~31,000 actions), converted into contextual bandit problems.

Key Results

  • Sample Efficiency: In synthetic tests, POTEC demonstrated steady performance gains as data increased, whereas baseline methods often flatlined or collapsed due to high variance.
  • Robustness to Noise: POTEC maintained superior performance even when 30% of cluster assignments were intentionally corrupted, highlighting its practical reliability.
  • Real-World Performance: On the Wiki10-31K dataset, POTEC significantly outperformed traditional policy-gradient methods, which struggled to extract meaningful signals from the sparse, high-variance logs of 31,000 actions.

Conclusion

POTEC offers a unified framework for large-scale off-policy learning. By treating clustering as a tunable parameter, it allows practitioners to find the optimal balance between bias and variance. If a single cluster is used, POTEC behaves like a regression method; if every action is its own cluster, it behaves like a policy-based method. This flexibility, combined with the robustness provided by "local correctness," makes POTEC a powerful tool for modern interactive systems.

Summary updated

Abstract

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.
BibTeX
@inproceedings{saito2025potec,
  author = {Yuta Saito and Jihan Yao and Thorsten Joachims},
  title = {{POTEC: Off-Policy Learning for Large Action Spaces via Two-Stage Policy Decomposition}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=LXftdR11io},
}
Figure