# Low-rank Matrix Bandits with Heavy-tailed Rewards

arXiv: https://arxiv.org/abs/2404.17709 · HTML: https://mlsanity.com/paper/2404.17709/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 26 Apr 2024.

## Builds on (most cited first, 15 of 15)

- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/2004.13465/) (2020)
- [A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery](https://mlsanity.com/paper/1603.08315/) (2016)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Thresholded Lasso Bandit](https://mlsanity.com/paper/2010.11994/) (2020)
- [Generalized High-Dimensional Trace Regression via Nuclear Norm Regularization](https://mlsanity.com/paper/1710.08083/) (2017)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms](https://mlsanity.com/paper/2106.02979/) (2021)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)

## Built on by (most cited first, 7 of 7)

- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update](https://mlsanity.com/paper/2503.00419/) (2025)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits](https://mlsanity.com/paper/2510.00803/) (2025)
- [Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors](https://mlsanity.com/paper/2609.33025/) (2026)
- [Optimal Online Regret for Context-Lumpable Bandits](https://mlsanity.com/paper/2610.18258/) (2026)

## Abstract (arXiv)

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.