# Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2014.

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

- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Fully Dynamic Online Selection through Online Contention Resolution Schemes](https://mlsanity.com/paper/2301.03099/) (2023)

## Abstract (arXiv)

A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we close the problem of computationally and sample efficient learning in stochastic combinatorial semi-bandits. In particular, we analyze a UCB-like algorithm for solving the problem, which is known to be computationally efficient; and prove O(K L (1 / Delta) log n) and O(√K L n log n) upper bounds on its n-step regret, where L is the number of ground items, K is the maximum number of chosen items, and Delta is the gap between the expected returns of the optimal and best suboptimal solutions. The gap-dependent bound is tight up to a constant factor and the gap-free bound is tight up to a polylogarithmic factor.