Rotting Bandits
arXiv:1702.07274
Abstract
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.
Cited by in corpus (17)
- Regime Switching Bandits
- Rebounding Bandits for Modeling Satiation Effects
- Learning and Optimization with Seasonal Patterns
- Optimizing for the Future in Non-Stationary MDPs
- Fatigue-Aware Ad Creative Selection
- Stochastic Bandits with Delay-Dependent Payoffs
- Finite Continuum-Armed Bandits
- Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback
- Online Learning for Active Cache Synchronization
- Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect
- Near Optimal Stratified Sampling
- Pair-Matching: Links Prediction with Adaptive Queries
- Generalized non-stationary bandits
- Autonomous learning of multiple, context-dependent tasks
- Slice Tuner: A Selective Data Acquisition Framework for Accurate and Fair Machine Learning Models
- Bandit problems with fidelity rewards
- Online Model Selection: a Rested Bandit Formulation