A General Framework for Bandit Problems Beyond Cumulative Objectives
This work addresses a foundational gap in sequential decision-making for researchers and practitioners, offering a systematic approach to diverse performance metrics beyond cumulative sums, though it is incremental in extending existing bandit methods.
The paper tackles the limitation of standard multi-armed bandit problems that focus on cumulative rewards by developing a general framework for handling non-cumulative objectives like conditional value-at-risk and Sharpe-ratio, showing that optimism-based learning policies can be designed under tractable conditions for the oracle policy.
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.