首页> 外文期刊>Neural computation >Per-Round Knapsack-Constrained Linear Submodular Bandits
【24h】

Per-Round Knapsack-Constrained Linear Submodular Bandits

机译:每轮背负背包约束的线性次模匪

获取原文
获取原文并翻译 | 示例

摘要

Linear submodular bandits has been proven to be effective in solving the diversification and feature-based exploration problem in information retrieval systems. Considering there is inevitably a budget constraint in many web-based applications, such as news article recommendations and online advertising, we study the problem of diversification under a budget constraint in a bandit setting. We first introduce a budget constraint to each exploration step of linear submodular bandits as a new problem, which we call per-round knapsack-constrained linear submodular bandits. We then define an -approximation unit-cost regret considering that the submodular function maximization is NP-hard. To solve this new problem, we propose two greedy algorithms based on a modified UCB rule. We prove these two algorithms with different regret bounds and computational complexities. Inspired by the lazy evaluation process in submodular function maximization, we also prove that a modified lazy evaluation process can be used to accelerate our algorithms without losing their theoretical guarantee. We conduct a number of experiments, and the experimental results confirm our theoretical analyses.
机译:事实证明,线性次模块化强盗可有效解决信息检索系统中的多样化和基于特征的探索问题。考虑到在许多基于Web的应用程序中不可避免地存在预算约束,例如新闻文章推荐和在线广告,我们研究了在强盗环境下预算约束下的多样化问题。首先,我们将预算约束引入到线性子模块化强盗的每个探索步骤中,作为一个新问题,我们将其称为每轮背包约束线性子模块化强盗。然后,考虑到子模函数最大化是NP-hard,我们定义一个近似单位成本后悔。为了解决这个新问题,我们提出了两种基于修改后的UCB规则的贪婪算法。我们证明了这两种算法具有不同的后悔界限和计算复杂性。受子模块函数最大化中的惰性评估过程的启发,我们还证明了改进的惰性评估过程可用于加速算法,而不会失去其理论保证。我们进行了许多实验,实验结果证实了我们的理论分析。

著录项

  • 来源
    《Neural computation》 |2016年第12期|2757-2789|共33页
  • 作者单位

    Centre for Artificial Intelligence Faculty of Engineering and Information Technology University of Technology Sydney Sydney NSW 2007 Australia baosheng.yu@student.uts.edu.au;

    Department of Computing and Information Systems University of Melbourne Victoria 3010 Australia meng.fang@unimelb.edu.au;

    Centre for Artificial Intelligence Faculty of Engineering and Information Technology University of Technology Sydney Sydney NSW 2007 Australia Dacheng.Tao@uts.edu.au;

  • 收录信息 美国《科学引文索引》(SCI);美国《化学文摘》(CA);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号