A General Framework for Bandit Problems Beyond Cumulative Objectives
  The stochastic multi-armed bandit (MAB) problem is a common model for
sequential decision problems. In the standard setup, a decision maker has to
choose at every instant between several competing arms, each of them provides a
scalar random variable, referred to as a "reward." Nearly all research on this
topic considers the total cumulative reward as the criterion of interest. This
work focuses on other natural objectives that cannot be cast as a sum over
rewards, but rather more involved functions of the reward stream. Unlike the
case of cumulative criteria, in the problems we study here the oracle policy,
that knows the problem parameters a priori and is used to "center" the regret,
is not trivial. We provide a systematic approach to such problems, and derive
general conditions under which the oracle policy is sufficiently tractable to
facilitate the design of optimism-based (upper confidence bound) learning
policies. These conditions elucidate an interesting interplay between the arm
reward distributions and the performance metric. Our main findings are
illustrated for several commonly used objectives such as conditional
value-at-risk, mean-variance trade-offs, Sharpe-ratio, and more.
