# Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 85 references that are in the map.
- First posted on arXiv 1 Oct 2022.

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [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)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Experimental Design in Two-Sided Platforms: An Analysis of Bias](https://mlsanity.com/paper/2002.05670/) (2020)
- [Stochastic Low-Rank Bandits](https://mlsanity.com/paper/1712.04644/) (2017)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [Stochastic Rank-1 Bandits](https://mlsanity.com/paper/1608.03023/) (2016)
- [Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling](https://mlsanity.com/paper/1912.03074/) (2019)
- [Dynamic Assortment Personalization in High Dimensions](https://mlsanity.com/paper/1610.05604/) (2016)
- [Context-Based Dynamic Pricing with Online Clustering](https://mlsanity.com/paper/1902.06199/) (2019)
- [Data-Pooling in Stochastic Optimization](https://mlsanity.com/paper/1906.00255/) (2019)
- [Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits](https://mlsanity.com/paper/2210.00025/) (2022)
- [Learning Markov models via low-rank optimization](https://mlsanity.com/paper/1907.00113/) (2019)
- [Multitask Learning and Bandits via Robust Statistics](https://mlsanity.com/paper/2112.14233/) (2021)
- [How Big Should Your Data Really Be? Data-Driven Newsvendor: Learning One Sample at a Time](https://mlsanity.com/paper/2107.02742/) (2021)
- [On Low-rank Trace Regression under General Sampling Distribution](https://mlsanity.com/paper/1904.08576/) (2019)
- [Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure](https://mlsanity.com/paper/2206.03569/) (2022)
- [Online Evaluation of Audiences for Targeted Advertising via Bandit Experiments](https://mlsanity.com/paper/1907.02178/) (2019)
- [Optimal Pricing with a Single Point](https://mlsanity.com/paper/2103.05611/) (2021)
- [Uncertainty Quantification For Low-Rank Matrix Completion With Heterogeneous and Sub-Exponential Noise](https://mlsanity.com/paper/2110.12046/) (2021)

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

- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [Collaborative Intelligence in Sequential Experiments: A Human-in-the-Loop Framework for Drug Discovery](https://mlsanity.com/paper/2405.03942/) (2024)
- [Mostly Beneficial Clustering: Aggregating Data for Operational Decision Making](https://mlsanity.com/paper/2311.17326/) (2023)

## Abstract (arXiv)

Multi-armed bandit (MAB) algorithms are efficient approaches to reduce the opportunity cost of online experimentation and are used by companies to find the best product from periodically refreshed product catalogs. However, these algorithms face the so-called cold-start at the onset of the experiment due to a lack of knowledge of customer preferences for new products, requiring an initial data collection phase known as the burn-in period. During this period, standard MAB algorithms operate like randomized experiments, incurring large burn-in costs which scale with the large number of products. We attempt to reduce the burn-in by identifying that many products can be cast into two-sided products, and then naturally model the rewards of the products with a matrix, whose rows and columns represent the two sides respectively. Next, we design two-phase bandit algorithms that first use subsampling and low-rank matrix estimation to obtain a substantially smaller targeted set of products and then apply a UCB procedure on the target products to find the best one. We theoretically show that the proposed algorithms lower costs and expedite the experiment in cases when there is limited experimentation time along with a large product set. Our analysis also reveals three regimes of long, short, and ultra-short horizon experiments, depending on dimensions of the matrix. Empirical evidence from both synthetic data and a real-world dataset on music streaming services validates this superior performance.