We study the adversarial multi-armed bandit problem and create a completely online algorithmic framework that is invariant under arbitrary translations and scales of the arm losses. We study the expected performance of our algorithm against a generic competition class, which makes it applicable for a wide variety of problem scenarios. Our algorithm works from a universal prediction perspective and the performance measure used is the expected regret against arbitrary arm selection sequences, which is the difference between our losses and a competing loss sequence. The competition class can be designed to include fixed arm selections, switching bandits, contextual bandits, or any other competition of interest. The sequences in the competition class are generally determined by the specific application at hand and should be designed accordingly. Our algorithm neither uses nor needs any preliminary information about the loss sequences and is completely online. Its performance bounds are the second order bounds in terms of sum of the squared losses, where any affine transform of the losses has no effect on the normalized regret.
翻译:我们研究对抗性多武装土匪问题,并创建一个完全在线的算法框架,这种框架在任意翻译和武器损失的尺度下是无差别的。我们研究我们的算法对通用竞争等级的预期性能,这使它适用于各种各样的问题。我们的算法从普遍预测的角度和所使用的业绩计量是预期对任意选择武器序列的遗憾,即我们的损失和竞争性损失顺序之间的差别。竞争等级可以设计成包括固定的手臂选择、换换手、背景强盗或任何其他利益竞争。竞争等级的顺序一般由手头的具体应用程序决定,因此应当据此设计。我们的算法既不使用也不需要关于损失顺序的任何初步信息,而是完全在线的。其性能界限是平方损失总和的第二顺序,即损失的任何折叠式转换都不会对归正的遗憾产生影响。