Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
arXiv:2006.06613
Abstract
We investigate stochastic combinatorial multi-armed bandit with semi-bandit feedback (CMAB). In CMAB, the question of the existence of an efficient policy with an optimal asymptotic regret (up to a factor poly-logarithmic with the action size) is still open for many families of distributions, including mutually independent outcomes, and more generally the multivariate sub-Gaussian family. We propose to answer the above question for these two families by analyzing variants of the Combinatorial Thompson Sampling policy (CTS). For mutually independent outcomes in , we propose a tight analysis of CTS using Beta priors. We then look at the more general setting of multivariate sub-Gaussian outcomes and propose a tight analysis of CTS using Gaussian priors. This last result gives us an alternative to the Efficient Sampling for Combinatorial Bandit policy (ESCB), which, although optimal, is not computationally efficient.
arXiv commentaccepted to NeurIPS 2020
References in corpus (14)
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- Combinatorial Bandits Revisited
- Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
- Matroid Bandits: Fast Combinatorial Optimization with Learning
- Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays
- Efficient Learning in Large-Scale Combinatorial Semi-Bandits
- Thompson Sampling for Combinatorial Semi-Bandits
- Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
- Combinatorial semi-bandit with known covariance
- Thompson Sampling for the MNL-Bandit
- Thompson Sampling for Complex Bandit Problems
- Budgeted Online Influence Maximization
- Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits
- Finding the bandit in a graph: Sequential search-and-stop