Conservative mechanism is a desirable property in decision-making problems which balance the tradeoff between the exploration and exploitation. We propose the novel \emph{conservative contextual combinatorial cascading bandit ($C^4$-bandit)}, a cascading online learning game which incorporates the conservative mechanism. At each time step, the learning agent is given some contexts and has to recommend a list of items but not worse than the base strategy and then observes the reward by some stopping rules. We design the $C^4$-UCB algorithm to solve the problem and prove its n-step upper regret bound for two situations: known baseline reward and unknown baseline reward. The regret in both situations can be decomposed into two terms: (a) the upper bound for the general contextual combinatorial cascading bandit; and (b) a constant term for the regret from the conservative mechanism. We also improve the bound of the conservative contextual combinatorial bandit as a by-product. Experiments on synthetic data demonstrate its advantages and validate our theoretical analysis.


翻译:保守机制是平衡勘探与开发之间平衡的决策问题中的一种可取的财产。 我们提议了新颖的 \ emph{ 保守背景组合式连锁条纹(C$4$-bandit)},这是一个包含保守机制的连锁在线学习游戏。 在每一个步骤中,学习代理都给出了一些背景,必须建议一份项目清单,但并不比基本战略更差,然后通过一些停止规则来观察奖励。我们设计了$C$4$-UCB算法来解决问题,并证明它对于两种情况(已知基线奖赏和未知基线奖赏)具有正步的上层后悔感。两种情况下的遗憾可以分解为两个条件:(a) 总背景组合式连锁条纹带;(b) 保守机制的遗憾持续期。我们还改进了保守背景组合带带带作为副产品的约束。关于合成数据的实验显示了其优势并证实了我们的理论分析。

0
下载
关闭预览

相关内容

专知会员服务
43+阅读 · 2021年5月26日
专知会员服务
55+阅读 · 2021年5月17日
专知会员服务
37+阅读 · 2020年10月15日
专知会员服务
52+阅读 · 2020年9月7日
【IJCAI2020】图神经网络预测结构化实体交互
专知会员服务
42+阅读 · 2020年5月13日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
ICLR 2018最佳论文AMSGrad能够取代Adam吗
论智
6+阅读 · 2018年4月20日
推荐|深度强化学习聊天机器人(附论文)!
全球人工智能
4+阅读 · 2018年1月30日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年6月4日
Arxiv
0+阅读 · 2021年6月4日
VIP会员
相关VIP内容
专知会员服务
43+阅读 · 2021年5月26日
专知会员服务
55+阅读 · 2021年5月17日
专知会员服务
37+阅读 · 2020年10月15日
专知会员服务
52+阅读 · 2020年9月7日
【IJCAI2020】图神经网络预测结构化实体交互
专知会员服务
42+阅读 · 2020年5月13日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
ICLR 2018最佳论文AMSGrad能够取代Adam吗
论智
6+阅读 · 2018年4月20日
推荐|深度强化学习聊天机器人(附论文)!
全球人工智能
4+阅读 · 2018年1月30日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员