Rotting Bandits
  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.
