# Bernoulli Rank-1 Bandits for Click Feedback

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2017.

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

- [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)
- [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)
- [Pure Exploration and Regret Minimization in Matching Bandits](https://mlsanity.com/paper/2108.00230/) (2021)
- [Efficient Generalized Low-Rank Tensor Contextual Bandits](https://mlsanity.com/paper/2311.01771/) (2023)
- [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)
- [Active multiple matrix completion with adaptive confidence sets](https://mlsanity.com/paper/2605.02458/) (2026)

## Abstract (arXiv)

The probability that a user will click a search result depends both on its relevance and its position on the results page. The position based model explains this behavior by ascribing to every item an attraction probability, and to every position an examination probability. To be clicked, a result must be both attractive and examined. The probabilities of an item-position pair being clicked thus form the entries of a rank-1 matrix. We propose the learning problem of a Bernoulli rank-1 bandit where at each step, the learning agent chooses a pair of row and column arms, and receives the product of their Bernoulli-distributed values as a reward. This is a special case of the stochastic rank-1 bandit problem considered in recent work that proposed an elimination based algorithm Rank1Elim, and showed that Rank1Elim's regret scales linearly with the number of rows and columns on "benign" instances. These are the instances where the minimum of the average row and column rewards μ is bounded away from zero. The issue with Rank1Elim is that it fails to be competitive with straightforward bandit strategies as μ rightarrow 0. In this paper we propose Rank1ElimKL which simply replaces the (crude) confidence intervals of Rank1Elim with confidence intervals based on Kullback-Leibler (KL) divergences, and with the help of a novel result concerning the scaling of KL divergences we prove that with this change, our algorithm will be competitive no matter the value of μ. Experiments with synthetic data confirm that on benign instances the performance of Rank1ElimKL is significantly better than that of even Rank1Elim, while experiments with models derived from real data confirm that the improvements are significant across the board, regardless of whether the data is benign or not.