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.


翻译:在本文中,我们研究了一组保守的土匪问题(CBPs),有抽样处理的奖赏限制,即学习者的奖赏表现必须至少和某一基准一样。我们建议对土匪采取“一成一全”的解决办法,并将其应用到三个包含的问题,即:保守的多武装强盗(CMAB)、保守的线性强盗(CLB)和保守的环境组合强盗(CCCB)。与以前认为对预期的奖赏有高概率限制的工程不同,我们侧重于对实际得到的奖赏的样本处理限制,并实现更好的理论保障(依靠T$的独立添加剂遗憾,而不是依赖$T$独立)和实证业绩。此外,我们推广了结果,并考虑了一个新的保守的中差带问题(MV-CBPP),用预期的奖赏和变异性衡量学习成绩。关于这一长期问题,我们提供了一种新型的算法,用$O(1/T)美元标准添加剂遗憾(在累积形式上依赖T$),并通过经验评估来验证这一结果。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
51+阅读 · 2020年9月7日
专知会员服务
18+阅读 · 2020年9月2日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Msfvenom 常用生成 Payload 命令
黑白之道
9+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年2月18日
Arxiv
0+阅读 · 2021年2月12日
Arxiv
0+阅读 · 2021年2月12日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
51+阅读 · 2020年9月7日
专知会员服务
18+阅读 · 2020年9月2日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Msfvenom 常用生成 Payload 命令
黑白之道
9+阅读 · 2019年2月23日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员