• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Performance evaluation review >Statistically Efficient, Polynomial-Time Algorithms for Combinatorial Semi-Bandits
【24h】

Statistically Efficient, Polynomial-Time Algorithms for Combinatorial Semi-Bandits

机译：组合半刺槐的统计有效，多项式时间算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider combinatorial semi-bandits over a set X ⊂ {0,1}~d where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the smallest known regret bound R(T) = O(Δ_(min)/d(ln m)~2(ln T) after T rounds, where m = max_(x∈X) 1~T x. How-ever, ESCB has computational complexity O(|X|), which is typically exponential in d, and cannot be used in large dimensions. We propose the first algorithm that is both computationally and statistically efficient for this problem with regret R(T) = O(Δ_(min)/d(ln m)~2(ln T) and computational asymptotic complexity O(δ_T~(-1)poly(d)), where δ_T is a function which vanishes arbitrarily slowly. Our approach involves carefully designing AESCB, an approximate version of ESCB with the same regret guarantees. We show that, whenever budgeted linear maximization over X can be solved up to a given approximation ratio, AESCB is implementable in polynomial time O(δ_T~(-1)poly(d)) by repeatedly maximizing a linear function over X subject to a linear budget constraint, and showing how to solve these maximization problems efficiently. Additional algorithms, proofs and numerical experiments are given in the complete version of this work.
机译：我们考虑在SET x⊂{0,1}〜d上的组合半键，其中奖励在跨物体上不相关。对于此问题，算法ESCB产生最小已知的遗憾R（T）= O（在T轮后Δ_（min）/ d（ln m）〜2（ln t），其中m = max_（x∈x）1 〜t x。HOW-EVER，ESCB具有计算复杂性O（| x |），其在D中通常是指数的，并且不能用于大维度。我们提出了在计算上和统计上有效的第一算法遗憾R（t）= O（Δ_（min）/ d（ln m）〜2（ln t）和计算渐近复杂度o（Δ_t〜（-1）poly（d）），其中Δ_t是任意消失的函数慢慢地。我们的方法涉及仔细设计AESCB，一个具有相同遗憾保证的ESCB的近似版本。我们表明，每当X上的预算线性最大化可以解决给给定的近似比，AESCB可用于多项式时间O（Δ_t〜 （-1）聚（d））通过反复大致地通过X上的线性函数，在线预算约束，并且展示如何有效地解决这些最大化问题。额外的al在这项工作的完整版本中给出了摩托车，证据和数值实验。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号