Implicitly Normalized Forecaster (online mirror descent with Tsallis entropy
as prox-function) is known to be an optimal algorithm for adversarial
multi-armed problems (MAB). However, most of the complexity results rely on
bounded rewards or other restrictive assumptions. Recently closely related
best-of-both-worlds algorithm were proposed for both adversarial and stochastic
heavy-tailed MAB settings. This algorithm is known to be optimal in both
settings, but fails to exploit data fully. In this paper, we propose Implicitly
Normalized Forecaster with clipping for MAB problems with heavy-tailed
distribution on rewards. We derive convergence results under mild assumptions
on rewards distribution and show that the proposed method is optimal for both
linear and non-linear heavy-tailed stochastic MAB problems. Also we show that
algorithm usually performs better compared to best-of-two-worlds algorithm.

本文提出了基于裁剪的隐式归一化预测器用于重尾分布奖励的多臂老虎机问题，在奖励分布方面假设温和的条件下，得到了收敛性结果，并且对于线性和非线性重尾随机 MAB 问题是最优的，相对于最佳两个世界算法，该算法通常表现更好。