Multi-armed Bandits with Cost Subsidy
  In this paper, we consider a novel variant of the multi-armed bandit (MAB)
problem, MAB with cost subsidy, which models many real-life applications where
the learning agent has to pay to select an arm and is concerned about
optimizing cumulative costs and rewards. We present two applications,
intelligent SMS routing problem and ad audience optimization problem faced by
several businesses (especially online platforms), and show how our problem
uniquely captures key features of these applications. We show that naive
generalizations of existing MAB algorithms like Upper Confidence Bound and
Thompson Sampling do not perform well for this problem. We then establish a
fundamental lower bound on the performance of any online learning algorithm for
this problem, highlighting the hardness of our problem in comparison to the
classical MAB problem. We also present a simple variant of explore-then-commit
and establish near-optimal regret bounds for this algorithm. Lastly, we perform
extensive numerical simulations to understand the behavior of a suite of
algorithms for various instances and recommend a practical guide to employ
different algorithms.
