The goal of a typical adaptive sequential decision making problem is to design an interactive policy that selects a group of items sequentially, based on some partial observations, to maximize the expected utility. It has been shown that the utility functions of many real-world applications, including pooled-based active learning and adaptive influence maximization, satisfy the property of adaptive submodularity. However, most of existing studies on adaptive submodular maximization focus on the fully adaptive setting, i.e., one must wait for the feedback from \emph{all} past selections before making the next selection. Although this approach can take full advantage of feedback from the past to make informed decisions, it may take a longer time to complete the selection process as compared with the non-adaptive solution where all selections are made in advance before any observations take place. In this paper, we explore the problem of partial-adaptive submodular maximization where one is allowed to make multiple selections in a batch simultaneously and observe their realizations together. Our approach enjoys the benefits of adaptivity while reducing the time spent on waiting for the observations from past selections. To the best of our knowledge, no results are known for partial-adaptive policies for the non-monotone adaptive submodular maximization problem. We study this problem under both cardinality constraint and knapsack constraints, and develop effective and efficient solutions for both cases. We also analyze the batch query complexity, i.e., the number of batches a policy takes to complete the selection process, of our policy under some additional assumptions.


翻译:典型的适应性顺序决策问题的目标是设计一个互动政策,根据部分观察,按顺序选择一组项目,以尽量扩大预期的效用。已经表明,许多真实世界应用程序的效用功能,包括基于集合的积极学习和适应影响最大化,满足适应性亚调模式特性的特性。然而,关于适应性亚调模式最大化的现有研究大多侧重于完全适应性环境,即,在作出下一个选择之前,必须等待来自过去复杂程度的反馈。虽然这一方法可以充分利用过去反馈,作出知情的决定,但与非适应性解决方案相比,它可能需要更长的时间来完成选择过程,因为所有选择都是在任何观察之前事先作出的。在本文件中,我们探讨了部分适应性亚调模式最大化的问题,即允许同时进行多个选择并共同观察其实现情况。我们的方法享受适应性的好处,同时缩短了等待过去选择的观察时间,以便作出知情决定,但与不适应性解决方案的不适应性解决方案相比,我们的政策选择过程的最佳选择过程是需要更长时间的。我们所了解的次调的分级政策的分级调整结果,对于在不成熟的分级研究中进行。我们所了解的分级的分级的分级的分级选择问题也是问题,我们所了解的分级的分级的分级的分级调整后,对于研究的分级选择问题也是最了解的。我们所了解的分级的分级的分级的分级的分级的分解问题。

0
下载
关闭预览

相关内容

专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
123+阅读 · 2020年9月8日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
4+阅读 · 2021年7月1日
Arxiv
7+阅读 · 2021年5月25日
Arxiv
8+阅读 · 2021年5月20日
Residual Policy Learning
Arxiv
4+阅读 · 2018年12月15日
Arxiv
3+阅读 · 2018年10月5日
Arxiv
5+阅读 · 2018年6月12日
VIP会员
相关VIP内容
专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
123+阅读 · 2020年9月8日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Arxiv
4+阅读 · 2021年7月1日
Arxiv
7+阅读 · 2021年5月25日
Arxiv
8+阅读 · 2021年5月20日
Residual Policy Learning
Arxiv
4+阅读 · 2018年12月15日
Arxiv
3+阅读 · 2018年10月5日
Arxiv
5+阅读 · 2018年6月12日
Top
微信扫码咨询专知VIP会员