Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
This work provides tight theoretical guarantees for online learning in combinatorial settings, which is incremental but important for applications like recommendation systems and resource allocation.
The paper tackles the problem of computationally and sample efficient learning in stochastic combinatorial semi-bandits by analyzing a UCB-like algorithm, proving tight regret bounds of O(K L (1/Δ) log n) and O(√(K L n log n)).
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 / Δ) \log n)$ and $O(\sqrt{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 $Δ$ 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.