Off-Policy Learning in Large Action Spaces: Optimization Matters More Than Estimation

Off-policy evaluation (OPE) and off-policy learning (OPL) are foundational for decision-making in offline contextual bandits. Recent advances in OPL primarily optimize OPE estimators with improved statistical properties, assuming that better estimators inherently yield superior policies. Although theoretically justified, this estimator-centric approach neglects a critical practical obstacle: challenging optimization landscapes. In this paper, we provide theoretical insights and empirical evidence showing that current OPL methods encounter severe optimization issues, particularly as the action space grows. We show that estimator-aware policy parametrization can mitigate, but not fully resolve, optimization challenges. Building on this, we explore simpler weighted log-likelihood objectives and demonstrate that they enjoy substantially better optimization properties and still recover competitive, often superior, learned policies. Our findings emphasize the necessity of explicitly addressing optimization considerations in the development of OPL algorithms for large action spaces.

Many important decisions, such as choosing which recommendation to show a user, must be learned from data that was collected in the past. This is challenging because the data only tells us what happened for the choices that were actually made, not what would have happened for all other possible choices. Most existing methods try to solve this by first building better ways to estimate how good a new decision-making strategy would be. The usual assumption is that a better estimate will lead to a better strategy. In this work, we show that this is not always enough: even when the estimate is statistically well designed, the resulting learning problem can be very hard to optimize, especially when there are many possible actions to choose from. We study why these optimization difficulties arise and show that changing how the strategy is represented can help, but does not fully fix the problem. We then explore simpler learning objectives that are easier to optimize and find that they often produce equally good or better strategies in practice. Our results suggest that future methods should consider not only statistical accuracy, but also whether the learning problem can be solved reliably.