Oracle-Efficient Combinatorial Semi-Bandits

Min-hwan Oh (Seoul National University) · Jung-hun Kim (CREST, ENSAE Paris, FairPlay team) · Milan Vojnovic (London School of Economics (LSE))

$\tilde{o}(\sqrt{t})$ regret$o(\log\log t)$ oracle queriescombinatorial optimizationcombinatorial semi-banditcovariance-adaptive algorithmsindividual feedbackmulti-armed banditnoise structurenon-linear rewardsoracle usage reductionoracle-efficient frameworksscalability theoretical guaranteestight regret guaranteesworst-case linear rewards

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 worst-case linear rewards, our algorithms achieve $\tilde{O}(\sqrt{T})$ regret using only $O(\log\log 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.