A General Framework for Bandit Problems Beyond Cumulative Objectives

Asaf Cassel (), Shie Mannor () and Assaf Zeevi ()
Additional contact information
Asaf Cassel: School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
Shie Mannor: Faculty of Electrical and Computer Engineering and Faculty of Industrial Engineering and Management, Technion, Israel Institute of Technology, Haifa 3200003, Israel; Nvidia Research, Tel Aviv 6777506, Israel
Assaf Zeevi: Graduate School of Business, Columbia University, New York, New York 10027; Data Science Institute, Columbia University, New York, New York 10027

Mathematics of Operations Research, 2023, vol. 48, issue 4, 2196-2232

Abstract: The stochastic multiarmed 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, which 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.

Keywords: Primary: 68Q32; secondary: 93E35; multiarmed bandit; risk; planning; reinforcement learning; upper confidence bound; optimism principle (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1335 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:4:p:2196-2232

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().