In this paper, we study the stochastic combinatorial multi-armed bandit problem under semi-bandit feedback. While much work has been done on algorithms that optimize the expected reward for linear as well as some general reward functions, we study a variant of the problem, where the objective is to be risk-aware. More specifically, we consider the problem of maximizing the Conditional Value-at-Risk (CVaR), a risk measure that takes into account only the worst-case rewards. We propose new algorithms that maximize the CVaR of the rewards obtained from the super arms of the combinatorial bandit for the two cases of Gaussian and bounded arm rewards. We further analyze these algorithms and provide regret bounds. We believe that our results provide the first theoretical insights into combinatorial semi-bandit problems in the risk-aware case.


翻译:在本文中,我们研究了半匪帮反馈下的多武装盗匪问题。虽然在优化线性以及某些一般奖励功能的预期奖赏的算法方面做了大量工作,但我们研究了问题的一个变体,其目标在于风险意识。更具体地说,我们考虑了最大限度地提高风险值(CVaR)的问题,这是一个只考虑最坏情况奖励的风险评估措施。我们提出了新的算法,为Gaussian和捆绑式手臂奖励的两个案例最大限度地利用组合式盗匪超级手臂奖赏的CVaR。我们进一步分析了这些算法,并提供了遗憾。我们认为,我们的结果为风险意识案件中的组合半黑手党问题提供了初步的理论见解。

0
下载
关闭预览

相关内容

【经典书】算法C语言实现,Algorithms in C. 672页pdf
专知会员服务
79+阅读 · 2020年8月13日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
LibRec 每周算法:parameter-free contextual bandits (SIGIR'15)
LibRec智能推荐
5+阅读 · 2017年6月12日
Arxiv
0+阅读 · 2022年2月2日
Arxiv
3+阅读 · 2021年5月18日
Optimization for deep learning: theory and algorithms
Arxiv
102+阅读 · 2019年12月19日
Arxiv
9+阅读 · 2018年1月30日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
LibRec 每周算法:parameter-free contextual bandits (SIGIR'15)
LibRec智能推荐
5+阅读 · 2017年6月12日
Top
微信扫码咨询专知VIP会员