Skip to Main content Skip to Navigation
Conference papers

Statistical efficiency of Thompson sampling for combinatorial semi-bandits

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 $[0,1]$, 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.
Complete list of metadata

https://hal.inria.fr/hal-03288983
Contributor : Michal Valko Connect in order to contact the contributor
Submitted on : Friday, July 16, 2021 - 3:55:03 PM
Last modification on : Tuesday, January 18, 2022 - 2:26:08 PM
Long-term archiving on: : Sunday, October 17, 2021 - 7:04:54 PM

File

richemond2020byol.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03288983, version 1
  • ARXIV : 2006.06613

Collections

Citation

Pierre H Richemond, Jean-Bastien Grill, Florent Altché, Corentin Tallec, Florian Strub, et al.. Statistical efficiency of Thompson sampling for combinatorial semi-bandits. Neural Information Processing Systems Conference, Dec 2020, Virtual, France. ⟨hal-03288983⟩

Share

Metrics

Record views

33

Files downloads

39