Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits

In this paper, we generalize the concept of heavy-tailed multi-armed bandits to adversarial environments, and develop robust best-of-both-worlds algorithms for heavy-tailed multi-armed bandits (MAB), where losses have $\alpha$-th ($1<\alpha \le 2$) moments bounded by ${\sigma }^{\alpha }$, while the variances may not exist. Specifically, we design an algorithm $\mathtt{\text{HTINF}}$, when the heavy-tail parameters $\alpha$ and $\sigma$ are known to the agent, $\mathtt{\text{HTINF}}$ simultaneously achieves the optimal regret for both stochastic and adversarial environments, without knowing the actual environment type a-priori. When $\alpha ,\sigma$ are unknown, $\mathtt{\text{HTINF}}$ achieves a $\log T$-styleinstance-dependentregretinstochasticcasesand$o(T)$ no-regret guarantee in adversarial cases. We further develop an algorithm $\mathtt{\text{AdaTINF}}$, achieving $\mathcal O(\sigma K^{1-\nicefrac 1\alpha}T^{\nicefrac{1}{\alpha}})$ minimax optimal regret even in adversarial settings, without prior knowledge on $\alpha$ and $\sigma$. This result matches the known regret lower-bound (Bubeck et al., 2013), which assumed a stochastic environment and $\alpha$ and $\sigma$ are both known. To our knowledge, the proposed $\mathtt{\text{HTINF}}$ algorithm is the first to enjoy a best-of-both-worlds regret guarantee, and $\mathtt{\text{AdaTINF}}$ is the first algorithm that can adapt to both $\alpha$ and $\sigma$ to achieve optimal gap-indepedent regret bound in classical heavy-tailed stochastic MAB setting and our novel adversarial formulation.