# Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 59 references that are in the map.
- First posted on arXiv 20 Aug 2024.

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

- [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)
- [Off-policy evaluation for slate recommendation](https://mlsanity.com/paper/1605.04812/) (2016)
- [KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems](https://mlsanity.com/paper/2202.10842/) (2022)
- [Doubly robust off-policy evaluation with shrinkage](https://mlsanity.com/paper/1907.09623/) (2019)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off-Policy Evaluation](https://mlsanity.com/paper/2008.07146/) (2020)
- [Off-policy Bandits with Deficient Support](https://mlsanity.com/paper/2006.09438/) (2020)
- [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)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Counterfactual Evaluation of Slate Recommendations with Sequential Reward Interactions](https://mlsanity.com/paper/2007.12986/) (2020)
- [Off-Policy Evaluation for Large Action Spaces via Conjunct Effect Modeling](https://mlsanity.com/paper/2305.08062/) (2023)
- [Offline Evaluation of Ranking Policies with Click Models](https://mlsanity.com/paper/1804.10488/) (2018)
- [Evaluating the Robustness of Off-Policy Evaluation](https://mlsanity.com/paper/2108.13703/) (2021)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [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)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [Policy-Adaptive Estimator Selection for Off-Policy Evaluation](https://mlsanity.com/paper/2211.13904/) (2022)
- [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)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem](https://mlsanity.com/paper/1905.03125/) (2019)
- [Off-Policy Evaluation for Large Action Spaces via Policy Convolution](https://mlsanity.com/paper/2310.15433/) (2023)
- [Control Variates for Slate Off-Policy Evaluation](https://mlsanity.com/paper/2106.07914/) (2021)
- [Towards Assessing and Benchmarking Risk-Return Tradeoff of Off-Policy Evaluation](https://mlsanity.com/paper/2311.18207/) (2023)
- [POTEC: Off-Policy Learning for Large Action Spaces via Two-Stage Policy Decomposition](https://mlsanity.com/paper/2402.06151/) (2024)

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

- [Off-Policy Evaluation and Learning for Matching Markets](https://mlsanity.com/paper/2507.13608/) (2025)
- [Off-Policy Evaluation for Ranking Policies under Deterministic Logging Policies](https://mlsanity.com/paper/2603.21485/) (2026)
- [Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities](https://mlsanity.com/paper/2605.29500/) (2026)
- [Off-Policy Evaluation of Ranking Policies via Embedding-Space User Behavior Modeling](https://mlsanity.com/paper/2506.00446/) (2025)
- [Offline Contextual Bandits in the Presence of New Actions](https://mlsanity.com/paper/2605.18509/) (2026)
- [Diffusion-Based Data-Driven Assortment Optimization](https://mlsanity.com/paper/2608.11419/) (2026)
- [COVER: Identifiable Evaluation of Coalition Routing](https://mlsanity.com/paper/2608.28475/) (2026)
- [Adaptive Doubly Robust Off-Policy Evaluation for Ranking Policies under Diverse User Behavior](https://mlsanity.com/paper/2608.29600/) (2026)

## Abstract (arXiv)

We explore off-policy evaluation and learning (OPE/L) in contextual combinatorial bandits (CCB), where a policy selects a subset in the action space. For example, it might choose a set of furniture pieces (a bed and a drawer) from available items (bed, drawer, chair, etc.) for interior design sales. This setting is widespread in fields such as recommender systems and healthcare, yet OPE/L of CCB remains unexplored in the relevant literature. Typical OPE/L methods such as regression and importance sampling can be applied to the CCB problem, however, they face significant challenges due to high bias or variance, exacerbated by the exponential growth in the number of available subsets. To address these challenges, we introduce a concept of factored action space, which allows us to decompose each subset into binary indicators. This formulation allows us to distinguish between the ''main effect'' derived from the main actions, and the ''residual effect'', originating from the supplemental actions, facilitating more effective OPE. Specifically, our estimator, called OPCB, leverages an importance sampling-based approach to unbiasedly estimate the main effect, while employing regression-based approach to deal with the residual effect with low variance. OPCB achieves substantial variance reduction compared to conventional importance sampling methods and bias reduction relative to regression methods under certain conditions, as illustrated in our theoretical analysis. Experiments demonstrate OPCB's superior performance over typical methods in both OPE and OPL.