Skip to Main content Skip to Navigation
Conference papers

Combinatorial semi-bandit with known covariance

Abstract : The combinatorial stochastic semi-bandit problem is an extension of the classical multi-armed bandit problem in which an algorithm pulls more than one arm at each stage and the rewards of all pulled arms are revealed. One difference with the single arm variant is that the dependency structure of the arms is crucial. Previous works on this setting either used a worst-case approach or imposed independence of the arms. We introduce a way to quantify the dependency structure of the problem and design an algorithm that adapts to it. The algorithm is based on linear regression and the analysis develops techniques from the linear bandit literature. By comparing its performance to a new lower bound, we prove that it is optimal, up to a poly-logarithmic factor in the number of pulled arms.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01408534
Contributor : Vianney Perchet <>
Submitted on : Monday, December 5, 2016 - 9:55:11 AM
Last modification on : Thursday, April 15, 2021 - 3:31:51 AM
Long-term archiving on: : Tuesday, March 21, 2017 - 6:47:57 AM

Files

ols_ucb_ArXiv.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01408534, version 1
  • ARXIV : 1612.01859

Collections

Citation

Rémy Degenne, Vianney Perchet. Combinatorial semi-bandit with known covariance. NIPS 2016 (Conference on Neural Information Processing Systems), Dec 2016, Barcelona, Spain. ⟨hal-01408534⟩

Share

Metrics

Record views

58

Files downloads

292