Low-rank Matrix Bandits with Heavy-tailed Rewards

In stochastic low-rank matrix bandit, the expected reward of an arm is equal to the inner product between its feature matrix and some unknown d1 by d2 low-rank parameter matrix Theta^* with rank r ll d1wedge d2. While all prior studies assume the payoffs are mixed with sub-Gaussian noises, in this work we loosen this strict assumption and consider the new problem of underlinelow-rank matrix bandit with underlineheavy-underlinetailed underlinerewards (LowHTR), where the rewards only have finite (1+δ) moment for some δ ∈ (0,1]. By utilizing the truncation on observed payoffs and the dynamic exploration, we propose a novel algorithm called LOTUS attaining the regret bound of order tilde O(d^frac32r^frac12T^frac11+δ/tildeDrr) without knowing T, which matches the state-of-the-art regret bound under sub-Gaussian noises~citeplu2021low,kang2022efficient with δ = 1. Moreover, we establish a lower bound of the order Omega(d^fracδ1+δ r^fracδ1+δ T^frac11+δ) = Omega(T^frac11+δ) for LowHTR, which indicates our LOTUS is nearly optimal in the order of T. In addition, we improve LOTUS so that it does not require knowledge of the rank r with tilde O(dr^frac32T^frac1+δ1+2δ) regret bound, and it is efficient under the high-dimensional scenario. We also conduct simulations to demonstrate the practical superiority of our algorithm.