Быстрые алгоритмы типа UCB для стохастических бандитов с тяжёлым и сверхтяжёлым симметричным шумом

В этой работе мы предлагаем новый метод построения алгоритмов типа UCB для стохастических многоруких бандитов на основе общих методов выпуклой оптимизации с неточным оракулом. Мы выводим оценки регрета, соответствующие скоростям сходимости методов оптимизации. Мы предлагаем новый алгоритм Clipped-SGD-UCB и показываем как теоретически, так и эмпирически, что в случае симметричного шума в награде можно достичь оценки регрета $O(\log T\sqrt{KT\log T})$ вместо $O\left (T^{\frac{1}{1+\alpha}} K^{\frac{\alpha}{1+\alpha}} \right)$ для случая, когда распределение награды удовлетворяет $\mathbb{E}_{X \in D}[|X|^{1+\alpha}] \leq \sigma^{1+\alpha} (\alpha \in (0, 1])$, то есть работать лучше, чем предполагает общая нижняя оценка для бандитов с тяжёлыми хвостами. Более того, та же оценка сохраняется даже тогда, когда распределение награды не имеет математического ожидания, то есть когда $\alpha < 0$.