2018/05/08 by Mastane Achab, Achab, Mastane, Stéphan Clémençon +4
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Risk and Portfolio Optimization #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1805.02908
arxiv created 2018/05/08 · openalex publication_date 2018/05/08 · arxiv updated 2018/05/09 · openalex created_date 2022/10/11 · openalex updated_date 2026/07/28
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 possible actions. For each action chosen, she then receives the sum of a random number of rewards. Her objective is to maximize her cumulated earnings. 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. 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.