# Oracle-Efficient Combinatorial Semi-Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 24 Oct 2025.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [An efficient algorithm for learning with semi-bandit feedback](https://mlsanity.com/paper/1305.2732/) (2013)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity](https://mlsanity.com/paper/1808.06932/) (2018)
- [Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits](https://mlsanity.com/paper/2002.07258/) (2020)
- [Multinomial Logit Bandit with Low Switching Cost](https://mlsanity.com/paper/2007.04876/) (2020)
- [Parallelizing greedy for submodular set function maximization in matroids and beyond](https://mlsanity.com/paper/1811.12568/) (2018)
- [Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits](https://mlsanity.com/paper/2110.08057/) (2021)
- [Robust Dynamic Assortment Optimization in the Presence of Outlier Customers](https://mlsanity.com/paper/1910.04183/) (2019)
- [Best-of-K Bandits](https://mlsanity.com/paper/1603.02752/) (2016)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback](https://mlsanity.com/paper/2305.16074/) (2023)
- [Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2402.15171/) (2024)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Optimal and Practical Batched Linear Bandit Algorithm](https://mlsanity.com/paper/2507.08438/) (2025)

## Abstract (arXiv)

We study the combinatorial semi-bandit problem where an agent selects a subset of base arms and receives individual feedback. While this generalizes the classical multi-armed bandit and has broad applicability, its scalability is limited by the high cost of combinatorial optimization, requiring oracle queries at every round. To tackle this, we propose oracle-efficient frameworks that significantly reduce oracle calls while maintaining tight regret guarantees. For the worst-case linear reward setting, our algorithms achieve tildeO(√T) regret using only O(loglog T) oracle queries. We also propose covariance-adaptive algorithms that leverage noise structure for improved regret, and extend our approach to general (non-linear) rewards. Overall, our methods reduce oracle usage from linear to (doubly) logarithmic in time, with strong theoretical guarantees.