mlsanityData to 7 Oct 2026

Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling

arXiv 1912.03074 ↗First posted 6 Dec 2019stat.ML cs.LGcited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 3; 2023: 5; 2024: 5; 2025: 4; 2026: 1.

23 papers.

Sort:

  1. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21
  2. 2024Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problemscited by 19
  3. 2021Bandit Phase Retrievalcited by 12
  4. 2023Optimal Algorithms for Latent Bandits with Cluster Structurecited by 11
  5. 2022Online Low Rank Matrix Completioncited by 9
  6. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  7. 2024Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditscited by 9
  8. 2024Best-Arm Identification in Unimodal Banditscited by 6
  9. 2024Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recoverycited by 5
  10. 2021Pure Exploration and Regret Minimization in Matching Banditscited by 4
  11. 2021Indexed Minimum Empirical Divergence for Unimodal Banditscited by 4
  12. 2022Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Armscited by 4
11 more
  1. 2025Generalized Low-Rank Matrix Contextual Bandits with Graph Informationcited by 4
  2. 2023Context-lumpable stochastic banditscited by 3
  3. 2022A Scalable Recommendation Engine for New Users and Itemscited by 1
  4. 2023Efficient Generalized Low-Rank Tensor Contextual Banditscited by 1
  5. 2021Thompson Sampling for Unimodal Banditscited by 0
  6. 2023Adversarial Online Collaborative Filteringcited by 0
  7. 2024Online Matrix Completion: A Collaborative Approach with Hott Itemscited by 0
  8. 2025Thompson Sampling-Based Learning and Control for Unknown Dynamic Systemscited by 0
  9. 2025Multimodal Bandits: Regret Lower Bounds and Optimal Algorithmscited by 0
  10. 2025Efficient Matroid Bandit Linear Optimization Leveraging Unimodalitycited by 0
  11. 2026Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Samplingcited by 0