Profitable Bandits

Mastane Achab (1, 2) , Stéphan Clémençon (1, 2) , Aurélien Garivier (3, 4)

1 S2A - Signal, Statistique et Apprentissage
2 IDS - Département Images, Données, Signal
3 UMPA-ENSL - Unité de Mathématiques Pures et Appliquées
4 MC2 - Modèles de calcul, Complexité, Combinatoire

Originally motivated by default risk management applications, this paper investigates a novel problem, referred to as the profitable bandit problem here. At each step, an agent chooses a subset of the K ≥ 1 possible actions. For each action chosen, she then respectively pays and receives the sum of a random number of costs and rewards. Her objective is to maximize her cumulated profit. We adapt and study three well-known strategies in this purpose, that were proved to be most efficient in other settings: kl-UCB, Bayes-UCB and Thompson Sampling. For each of them, we prove a finite time regret bound which, together with a lower bound we obtain as well, establishes asymptotic optimality in some cases. Our goal is also to compare these three strategies from a theoretical and empirical perspective both at the same time. We give simple, self-contained proofs that emphasize their similarities, as well as their differences. While both Bayesian strategies are automatically adapted to the geometry of information, the numerical experiments carried out show a slight advantage for Thompson Sampling in practice.

Mots clés: credit risk; multi-armed bandits; thresholding bandits; bayesian policy

Domaines: Statistiques [math.ST]

Mastane Achab, Stéphan Clémençon, Aurélien Garivier. Profitable Bandits. Proceedings of Machine Learning Research, 2018, 95, pp.694-709. ⟨hal-02023057⟩