We consider the problem of online combinatorial optimization under
semi-bandit feedback. The goal of the learner is to sequentially select its
actions from a combinatorial decision set so as to minimize its cumulative
loss. We propose a learning algorithm for this problem based on combining the
Follow-the-Perturbed-Leader (FPL) prediction method with a novel loss
estimation procedure called Geometric Resampling (GR). Contrary to previous
solutions, the resulting algorithm can be efficiently implemented for any
decision set where efficient offline combinatorial optimization is possible at
all. Assuming that the elements of the decision set can be described with
d-dimensional binary vectors with at most m non-zero entries, we show that the
expected regret of our algorithm after T rounds is O(m sqrt(dT log d)). As a
side result, we also improve the best known regret bounds for FPL in the full
information setting to O(m^(3/2) sqrt(T log d)), gaining a factor of sqrt(d/m)
over previous bounds for this algorithm.

研究在线组合优化问题下的半强化反馈，提出了一种结合 FPL 预测方法和新颖的损失估计程序（称为 Geometric Resampling）的学习算法，并且在能够进行高效离线组合优化的任何决策集合上可以有效实现。假设决策集合的元素可以用至多 m 个非零项的 d 维二进制向量来描述，证明了我们算法的期望遗憾在 T 轮后是 O (m sqrt (dT log d))，并且在全信息设置中也改进了 FPL 的最佳遗憾限制。