2017/02/23 by Nir Levine, Levine, Nir, Koby Crammer +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mobile Crowdsensing and Crowdsourcing
paper · pdf · doi:10.48550/arxiv.1702.07274
openalex publication_date 2017/02/23 · openalex created_date 2023/03/20 · openalex updated_date 2026/07/28
The Multi-Armed Bandits (MAB) framework highlights the tension between acquiring new knowledge (Exploration) and leveraging available knowledge (Exploitation). In the classical MAB problem, a decision maker must choose an arm at each time step, upon which she receives a reward. The decision maker's objective is to maximize her cumulative expected reward over the time horizon. The MAB problem has been studied extensively, specifically under the assumption of the arms' rewards distributions being stationary, or quasi-stationary, over time. We consider a variant of the MAB framework, which we termed Rotting Bandits, where each arm's expected reward decays as a function of the number of times it has been pulled. We are motivated by many real-world scenarios such as online advertising, content recommendation, crowdsourcing, and more. We present algorithms, accompanied by simulations, and derive theoretical guarantees.