Stochastic Bandits with Vector Losses: Minimizing -Norm of Relative Losses
arXiv:2010.08061
Abstract
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 -armed bandit with multiple losses. We define relative loss vector of an arm where the -th entry compares the arm and the optimal arm with respect to the -th loss. We study two goals: (a) finding the arm with the minimum -norm of relative losses with a given confidence level (which refers to fixed-confidence best-arm identification); (b) minimizing the -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 and provide a matching algorithm.
arXiv comment14 pages
References in corpus (11)
- Further Optimal Regret Bounds for Thompson Sampling
- lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
- Optimal Best Arm Identification with Fixed Confidence
- Thompson Sampling for 1-Dimensional Exponential Family Bandits
- Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
- Gamification of Pure Exploration for Linear Bandits
- Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
- Pure Exploration with Multiple Correct Answers
- Structure Adaptive Algorithms for Stochastic Bandits
- Gradient Ascent for Active Exploration in Bandit Problems
- Sub-sampling for Efficient Non-Parametric Bandit Exploration