TY - JOUR
AU - Du, Yihan
AU - Wang, Siwei
AU - Huang, Longbo
PY - 2021/05/18
Y2 - 2022/01/24
TI - A One-Size-Fits-All Solution to Conservative Bandit Problems
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 35
IS - 8
SE - AAAI Technical Track on Machine Learning I
DO -
UR - https://ojs.aaai.org/index.php/AAAI/article/view/16891
SP - 7254-7261
AB - In this paper, we study a family of conservative bandit problems (CBPs) with sample-path reward constraints, i.e., the learner's reward performance must be at least as well as a given baseline at any time. We propose a One-Size-Fits-All solution to CBPs and present its applications to three encompassed problems, i.e. conservative multi-armed bandits (CMAB), conservative linear bandits (CLB) and conservative contextual combinatorial bandits (CCCB). Different from previous works which consider high probability constraints on the expected reward, we focus on a sample-path constraint on the actually received reward, and achieve better theoretical guarantees (T-independent additive regrets instead of T-dependent) and empirical performance. Furthermore, we extend the results and consider a novel conservative mean-variance bandit problem (MV-CBP), which measures the learning performance with both the expected reward and variability. For this extended problem, we provide a novel algorithm with O(1/T) normalized additive regrets (T-independent in the cumulative form) and validate this result through empirical evaluation.
ER -