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 d₁ by d₂ low-rank parameter matrix Θ^* with rank r d₁ d₂. 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 {low}-rank matrix bandit with {h}eavy-{t}ailed {r}ewards (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 O(d³/2r¹/2T¹/1+δ/D̃ᵣᵣ) without knowing T, which matches the state-of-the-art regret bound under sub-Gaussian noises~{lu2021low,kang2022efficient} with δ = 1. Moreover, we establish a lower bound of the order Ω(d^δ/1+δ r^δ/1+δ T¹/1+δ) = Ω(T¹/1+δ) 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 O(dr³/2T¹+δ/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.