# Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2019.

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

- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Bandit Phase Retrieval](https://mlsanity.com/paper/2106.01660/) (2021)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Pure Exploration and Regret Minimization in Matching Bandits](https://mlsanity.com/paper/2108.00230/) (2021)
- [Indexed Minimum Empirical Divergence for Unimodal Bandits](https://mlsanity.com/paper/2112.01452/) (2021)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [A Scalable Recommendation Engine for New Users and Items](https://mlsanity.com/paper/2209.06128/) (2022)
- [Efficient Generalized Low-Rank Tensor Contextual Bandits](https://mlsanity.com/paper/2311.01771/) (2023)
- [Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/2510.25811/) (2025)
- [Thompson Sampling for Unimodal Bandits](https://mlsanity.com/paper/2106.08187/) (2021)
- [Adversarial Online Collaborative Filtering](https://mlsanity.com/paper/2302.05765/) (2023)
- [Online Matrix Completion: A Collaborative Approach with Hott Items](https://mlsanity.com/paper/2408.05843/) (2024)
- [Thompson Sampling-Based Learning and Control for Unknown Dynamic Systems](https://mlsanity.com/paper/2506.22186/) (2025)
- [Efficient Matroid Bandit Linear Optimization Leveraging Unimodality](https://mlsanity.com/paper/2512.00605/) (2025)
- [Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Sampling](https://mlsanity.com/paper/2602.15972/) (2026)

## Abstract (arXiv)

Stochastic Rank-One Bandits (Katarya et al, (2017a,b)) are a simple framework for regret minimization problems over rank-one matrices of arms. The initially proposed algorithms are proved to have logarithmic regret, but do not match the existing lower bound for this problem. We close this gap by first proving that rank-one bandits are a particular instance of unimodal bandits, and then providing a new analysis of Unimodal Thompson Sampling (UTS), initially proposed by Paladino et al (2017). We prove an asymptotically optimal regret bound on the frequentist regret of UTS and we support our claims with simulations showing the significant improvement of our method compared to the state-of-the-art.