# UniRank: Unimodal Bandit Algorithm for Online Ranking

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 29 references that are in the map.
- First posted on arXiv 2 Aug 2022.

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

- [Top-K Off-Policy Correction for a REINFORCE Recommender System](https://mlsanity.com/paper/1812.02353/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [TopRank: A practical algorithm for online stochastic ranking](https://mlsanity.com/paper/1806.02248/) (2018)
- [Multiple-Play Bandits in the Position-Based Model](https://mlsanity.com/paper/1606.02448/) (2016)
- [Online Learning to Rank in Stochastic Click Models](https://mlsanity.com/paper/1703.02527/) (2017)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)
- [DCM Bandits: Learning to Rank with Multiple Clicks](https://mlsanity.com/paper/1602.03146/) (2016)
- [Learning to Rank in the Position Based Model with Bandit Feedback](https://mlsanity.com/paper/2004.13106/) (2020)
- [Pure Exploration and Regret Minimization in Matching Bandits](https://mlsanity.com/paper/2108.00230/) (2021)
- [BanditRank: Learning to Rank Using Contextual Bandits](https://mlsanity.com/paper/1910.10410/) (2019)

## Abstract (arXiv)

We tackle a new emerging problem, which is finding an optimal monopartite matching in a weighted graph. The semi-bandit version, where a full matching is sampled at each iteration, has been addressed by citeADMA, creating an algorithm with an expected regret matching O(fracLlog(L)Deltalog(T)) with 2L players, T iterations and a minimum reward gap Delta. We reduce this bound in two steps. First, as in citeGRAB and citeUniRank we use the unimodality property of the expected reward on the appropriate graph to design an algorithm with a regret in O(Lfrac1Deltalog(T)). Secondly, we show that by moving the focus towards the main question `Is user i better than user j?' this regret becomes O(LfracDeltatildeDelta2log(T)), where TildeDelta > Delta derives from a better way of comparing users. Some experimental results finally show these theoretical results are corroborated in practice.