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