Rebounding Bandits for Modeling Satiation Effects
  Psychological research shows that enjoyment of many goods is subject to
satiation, with short-term satisfaction declining after repeated exposures to
the same item. Nevertheless, proposed algorithms for powering recommender
systems seldom model these dynamics, instead proceeding as though user
preferences were fixed in time. In this work, we introduce rebounding bandits,
a multi-armed bandit setup, where satiation dynamics are modeled as
time-invariant linear dynamical systems. Expected rewards for each arm decline
monotonically with consecutive exposures to it and rebound towards the initial
reward whenever that arm is not pulled. Unlike classical bandit settings,
methods for tackling rebounding bandits must plan ahead and model-based methods
rely on estimating the parameters of the satiation dynamics. We characterize
the planning problem, showing that the greedy policy is optimal when the arms
exhibit identical deterministic dynamics. To address stochastic satiation
dynamics with unknown parameters, we propose Explore-Estimate-Plan (EEP), an
algorithm that pulls arms methodically, estimates the system dynamics, and then
plans accordingly.
