mlsanityData to 14 Oct 2026

Oracle-Efficient Combinatorial Semi-Bandits

arXiv 2510.21431 ↗First posted 24 Oct 2025stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

20 of 33 references.

References · 20

  1. 2019Introduction to Multi-Armed Banditscited by 481
  2. 2019Batched Multi-armed Bandits Problemcited by 98
  3. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  4. 2020Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networkingcited by 70
  5. 2016Combinatorial Multi-Armed Bandit with General Reward Functionscited by 56
  6. 2016Combinatorial semi-bandit with known covariancecited by 24
  7. 2013An efficient algorithm for learning with semi-bandit feedbackcited by 21
  8. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  9. 2018Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexitycited by 14
  10. 2020Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Banditscited by 11
  11. 2020Multinomial Logit Bandit with Low Switching Costcited by 10
  12. 2018Parallelizing greedy for submodular set function maximization in matroids and beyondcited by 9
8 more
  1. 2021Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Banditscited by 9
  2. 2019Robust Dynamic Assortment Optimization in the Presence of Outlier Customerscited by 8
  3. 2016Best-of-K Banditscited by 7
  4. 2024Optimal Batched Linear Banditscited by 7
  5. 2023Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedbackcited by 3
  6. 2024Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Banditscited by 3
  7. 2024Matroid Semi-Bandits in Sublinear Timecited by 3
  8. 2025Optimal and Practical Batched Linear Bandit Algorithmcited by 2

Built on by

Not cited yet.