📖
Stochastic bandits with vector losses: Minimizing $\ell^\infty$-norm of relative losses
Xuedong Shang, Han Shao, Jian Qian

Stochastic bandits with vector losses: Minimizing $\ell^\infty$-norm of relative losses

Author / Organization:
Science & Mathematics Published 2020 Verification Pending

Overview & Synopsis

Multi-armed bandits are widely applied in scenarios like recommender systems, for which the goal is to maximize the click rate. However, more factors should be considered, e.g., user stickiness, user growth rate, user experience assessment, etc. In this paper, we model this situation as a problem of K-armed bandit with multiple losses. We define relative loss vector of an arm where the i-th entry compares the arm and the optimal arm with respect to the i-th loss. We study two goals: (a) finding the arm with the minimum $\ell^\infty$-norm of relative losses with a given confidence level (which refers to fixed-confidence best-arm identification); (b) minimizing the $\ell^\infty$-norm of cumulative relative losses (which refers to regret minimization). For goal (a), we derive a problem-dependent sample complexity lower bound and discuss how to achieve matching algorithms. For goal (b), we provide a regret lower bound of Ω(T 2/3) and provide a matching algorithm.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Stochastic bandits with vector losses: Minimizing $\ell^\infty$-norm of relative losses
Author / Organization Xuedong Shang, Han Shao, Jian Qian
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2020
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-51770
Original Source Link Visit Source Page on hal.science »