Covariance-Adaptive Least-Squares Algorithm for Stochastic Combinatorial Semi-Bandits

Julien Zhou (1, 2, 3) , Pierre Gaillard (2) , Thibaud Rahier (1) , Houssam Zenati (4, 5) , Julyan Arbel (3)

1 Criteo AI Lab
2 Thoth - Apprentissage de modèles à partir de données massives
3 STATIFY - Modèles statistiques bayésiens et des valeurs extrêmes pour données structurées et de grande dimension
4 SODA - Méthodes computationnelles et mathématiques pour comprendre la société et la santé à partir de données
5 MIND - Modèles et inférence pour les données de Neuroimagerie

We address the problem of stochastic combinatorial semi-bandits, where a player can select from P subsets of a set containing d base items. Most existing algorithms (e.g. CUCB, ESCB, OLS-UCB) require prior knowledge on the reward distribution, like an upper bound on a sub-Gaussian proxy-variance, which is hard to estimate tightly. In this work, we design a variance-adaptive version of OLS-UCB, relying on an online estimation of the covariance structure. Estimating the coefficients of a covariance matrix is much more manageable in practical settings and results in improved regret upper bounds compared to proxy variance-based algorithms. When covariance coefficients are all non-negative, we show that our approach efficiently leverages the semi-bandit feedback and provably outperforms bandit feedback approaches, not only in exponential regimes where P ≫ d but also when P ≤ d, which is not straightforward from most existing analyses.

Mots clés: Covariance-Adaptive; Bandits; Stochastic Combinatorial Semi-Bandit; Confidence Ellipsoid

Domaines: Machine Learning [stat.ML]; Apprentissage [cs.LG]; Statistiques [math.ST]

Julien Zhou, Pierre Gaillard, Thibaud Rahier, Houssam Zenati, Julyan Arbel. Covariance-Adaptive Least-Squares Algorithm for Stochastic Combinatorial Semi-Bandits. 2024. ⟨hal-04470568⟩