BriefGPT.xyz
Oct, 2016
线性赌博机高效高概率算法
An efficient high-probability algorithm for Linear Bandits
HTML
PDF
Gábor Braun, Sebastian Pokutta
TL;DR
针对线性赌博问题,通过对算法CombEXP的分析,我们扩展了其适用范围至允许任意聚合体的自适应对手情形,证明了当时间边界T满足O(T^(2/3))时的高概率后悔率,该算法强于GeometricHedge且具有计算效率,只需要对凸包上的线性优化即可。
Abstract
For the
linear bandit problem
, we extend the analysis of
algorithm combexp
from [R. Combes, M. S. Talebi Mazraeh Shahi, A. Proutiere, and M. Lelarge. Combinatorial bandits revisited. In C. Cortes, N. D. Lawrence,
→