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

arXiv: https://arxiv.org/abs/2402.06151 · HTML: https://mlsanity.com/paper/2402.06151/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 30 of its 50 references that are in the map.
- First posted on arXiv 9 Feb 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 30)

- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Doubly Robust Policy Evaluation and Optimization](https://mlsanity.com/paper/1503.02834/) (2015)
- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1911.06854/) (2019)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes](https://mlsanity.com/paper/1908.08526/) (2019)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Doubly robust off-policy evaluation with shrinkage](https://mlsanity.com/paper/1907.09623/) (2019)
- [Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off-Policy Evaluation](https://mlsanity.com/paper/2008.07146/) (2020)
- [Learning Action Representations for Reinforcement Learning](https://mlsanity.com/paper/1902.00183/) (2019)
- [Off-Policy Evaluation for Large Action Spaces via Embeddings](https://mlsanity.com/paper/2202.06317/) (2022)
- [Adaptive Estimator Selection for Off-Policy Evaluation](https://mlsanity.com/paper/2002.07729/) (2020)
- [Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling](https://mlsanity.com/paper/1910.06508/) (2019)
- [Off-Policy Evaluation for Large Action Spaces via Conjunct Effect Modeling](https://mlsanity.com/paper/2305.08062/) (2023)
- [Evaluating the Robustness of Off-Policy Evaluation](https://mlsanity.com/paper/2108.13703/) (2021)
- [Optimal Off-Policy Evaluation from Multiple Logging Policies](https://mlsanity.com/paper/2010.11002/) (2020)
- [Doubly Robust Off-Policy Evaluation for Ranking Policies under the Cascade Behavior Model](https://mlsanity.com/paper/2202.01562/) (2022)
- [Bayesian Counterfactual Risk Minimization](https://mlsanity.com/paper/1806.11500/) (2018)
- [Using Experiments to Correct for Selection in Observational Studies](https://mlsanity.com/paper/2006.09676/) (2020)
- [Policy-Adaptive Estimator Selection for Off-Policy Evaluation](https://mlsanity.com/paper/2211.13904/) (2022)
- [Imitation-Regularized Offline Learning](https://mlsanity.com/paper/1901.04723/) (2019)
- [Learning from eXtreme Bandit Feedback](https://mlsanity.com/paper/2009.12947/) (2020)
- [Off-Policy Evaluation of Slate Bandit Policies via Optimizing Abstraction](https://mlsanity.com/paper/2402.02171/) (2024)
- [Off-Policy Evaluation of Ranking Policies under Diverse User Behavior](https://mlsanity.com/paper/2306.15098/) (2023)
- [Off-Policy Evaluation for Large Action Spaces via Policy Convolution](https://mlsanity.com/paper/2310.15433/) (2023)
- [Towards Assessing and Benchmarking Risk-Return Tradeoff of Off-Policy Evaluation](https://mlsanity.com/paper/2311.18207/) (2023)
- [Local Policy Improvement for Recommender Systems](https://mlsanity.com/paper/2212.11431/) (2022)
- [Off-Policy Evaluation in Embedded Spaces](https://mlsanity.com/paper/2203.02807/) (2022)

## Built on by (most cited first, 13 of 13)

- [Long-term Off-Policy Evaluation and Learning](https://mlsanity.com/paper/2404.15691/) (2024)
- [Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits](https://mlsanity.com/paper/2408.11202/) (2024)
- [Hyperparameter Optimization Can Even be Harmful in Off-Policy Learning and How to Deal with It](https://mlsanity.com/paper/2404.15084/) (2024)
- [Structured Learning of Compositional Sequential Interventions](https://mlsanity.com/paper/2406.05745/) (2024)
- [Prompt Optimization with Logged Bandit Data](https://mlsanity.com/paper/2504.02646/) (2025)
- [A General Framework for Off-Policy Learning with Partially-Observed Reward](https://mlsanity.com/paper/2506.14439/) (2025)
- [Off-Policy Learning with Limited Supply](https://mlsanity.com/paper/2603.18702/) (2026)
- [Off-Policy Evaluation for Semantic ID Recommenders: Does the Model's Own Code Hierarchy Help?](https://mlsanity.com/paper/2608.28905/) (2026)
- [DOLCE: Decomposing Off-Policy Evaluation/Learning into Lagged and Current Effects](https://mlsanity.com/paper/2505.00961/) (2025)
- [Your Offline Policy is Not Trustworthy: Bilevel Reinforcement Learning for Sequential Portfolio Optimization](https://mlsanity.com/paper/2505.12759/) (2025)
- [Off-Policy Evaluation of Ranking Policies via Embedding-Space User Behavior Modeling](https://mlsanity.com/paper/2506.00446/) (2025)
- [Off-Policy Evaluation and Learning for Survival Outcomes under Censoring](https://mlsanity.com/paper/2603.22900/) (2026)
- [Offline Contextual Bandits in the Presence of New Actions](https://mlsanity.com/paper/2605.18509/) (2026)

## Abstract (arXiv)

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.