In the problem of (binary) contextual bandits with knapsacks (CBwK), the agent receives an i.i.d. context in each of the $T$ rounds and chooses an action, resulting in a random reward and a random consumption of resources that are related to an i.i.d. external factor. The agent's goal is to maximize the accumulated reward under the initial resource constraints. In this work, we combine the re-solving heuristic, which proved successful in revenue management, with distribution estimation techniques to solve this problem. We consider two different information feedback models, with full and partial information, which vary in the difficulty of getting a sample of the external factor. Under both information feedback settings, we achieve two-way results: (1) For general problems, we show that our algorithm gets an $\widetilde O(T^{\alpha_u} + T^{\alpha_v} + T^{1/2})$ regret against the fluid benchmark. Here, $\alpha_u$ and $\alpha_v$ reflect the complexity of the context and external factor distributions, respectively. This result is comparable to existing results. (2) When the fluid problem is linear programming with a unique and non-degenerate optimal solution, our algorithm leads to an $\widetilde O(1)$ regret. To the best of our knowledge, this is the first $\widetilde O(1)$ regret result in the CBwK problem regardless of information feedback models. We further use numerical experiments to verify our results.


翻译:在使用 knapsacks (CBwK) 的背景强盗( 二进制) 问题中, 代理商在每轮美元交易中都收到一.d. 上下文, 并选择一个行动, 导致随机奖励和随机消耗与i. d. 外部因素有关的资源。 代理商的目标是在初始资源限制下最大限度地增加累积的奖励。 在这项工作中, 我们结合了在收入管理方面证明成功的再解决过度主义, 并采用分配估算技术来解决这个问题。 我们考虑两种信息反馈模型, 包括全部和部分信息, 难以获得外部因素样本。 在两种信息反馈环境下, 我们取得了双向的结果:(1) 对于一般问题, 我们的算法得到了 $( Täalpha_ u} + T ⁇ alpha_ v} + T ⁇ % 1/2} 。 我们的算法比液基准更成功, 我们的计算结果更复杂和外部因素分布。 当我们的最佳计算结果 与整个O 的算法性结果比起来, 我们的算算为 。

0
下载
关闭预览

相关内容

不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
72+阅读 · 2022年6月28日
专知会员服务
25+阅读 · 2021年4月2日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Latest News & Announcements of the Industry Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年7月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年1月26日
Arxiv
0+阅读 · 2023年1月25日
VIP会员
相关VIP内容
相关资讯
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Latest News & Announcements of the Industry Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年7月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员