Tight Bounds for Bandit Combinatorial Optimization
Tight Bounds for Bandit Combinatorial Optimization
复制标题
Bandit 组合优化的紧界
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Tomer Koren
中科院分区：
文献类型：
--
作者：
Alon Cohen;Tamir Hazan;Tomer Koren
我们重新研究了最优后悔率在强盗组合优化-一个基本框架下的不确定性，抽象了许多组合预测问题的顺序决策。我们证明，在这种情况下，可达到的遗憾增长为$widetilde{Theta}（k^{3/2}sqrt{dT}）$，其中$d$是问题的维数，$k$是最大瞬时损失的界，反驳了Audibert，Bubeck和Lugosi（2013）的猜想，他们认为最佳速率应该是$widetilde{Theta}（ksqrt{dT}）$的形式。我们的界限适用于几个重要的情况下的框架，特别是，意味着一个严格的约束研究的强盗最短路径问题。这样，我们也解决了Cesa-Bianchi和Lugosi（2012）提出的一个开放问题。
We revisit the study of optimal regret rates in bandit combinatorial optimization---a fundamental framework for sequential decision making under uncertainty that abstracts numerous combinatorial prediction problems. We prove that the attainable regret in this setting grows as $widetilde{Theta}(k^{3/2}sqrt{dT})$ where $d$ is the dimension of the problem and $k$ is a bound over the maximal instantaneous loss, disproving a conjecture of Audibert, Bubeck, and Lugosi (2013) who argued that the optimal rate should be of the form $widetilde{Theta}(ksqrt{dT})$. Our bounds apply to several important instances of the framework, and in particular, imply a tight bound for the well-studied bandit shortest path problem. By that, we also resolve an open problem posed by Cesa-Bianchi and Lugosi (2012).