Rotting Bandits
The Multi-Armed Bandits (MAB) framework highlights the trade-off 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.
The paper introduces a novel variant of the multi-armed problem, motivated by practice.
      
      The approach is technically sound and well grounded. There are a few typos and minor concerns (listed 
      below), despite which I believe this paper can be accepted.      
      
      Decaying bandits - e.g., Komiyama and Qin 2014, Heidari, Kearns and Roth 2016 - are mentioned, but Deteriorating bandits - e.g., Gittins 1979, Mandelbaum 1987, Kaspi and Mandelbaum 1998, etc. - are not
      
      Can't you use algorithms from non-stationary MABs, which you say are "most related to our problem", for benchmarking? It's quite unfair to use only UCB variants.
      
      Line 15: "expanse" -> "expense"
      Line 19: you have skipped a number of key formulations and break-throughs between 1933 and 1985
      Line 31-32: probably a word is missing in the sentence
      Line 63: "not including" what?
      Line 68: "equal objective" -> "equivalent objective"
      Line 68: this is an unusual definition of regret, in fact this expression is usually called "suboptimality", as you only compare to the optimal policy which is based on past allocations and observations. Regret is usually defined as distance from the objective achievable if one knew the unknown parameters. 
      Line 105: in the non-vanishing case, do you allow \mu_i^c = 0 or negative?      
      Line 106-118: some accompanying text describing the intuition behind these expressions would be helpful
      Line 119,144: headings AV and ANV would be more reasonable than names of the heuristics      
      Line 160: "w.h.p" -> "w.h.p."
      Table 1: "CTO" is ambiguous, please use the full algorithm acronyms  
      Figure 1: it would be desirable to explain the apparent non-monotonicity
      Line 256: It would be helpful for the reader if this sentence appeared in the Introduction. Btw, the term "rested bandits" is not very common; instead "classic bandits" is a much more popular term