mlsanityData to 14 Oct 2026

UniRank: Unimodal Bandit Algorithm for Online Ranking

arXiv 2208.01515 ↗First posted 2 Aug 2022cs.LG cs.DScited by 0

Not on the map. Why?

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.

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

14 of 29 references.

References · 14

  1. 2018Top-K Off-Policy Correction for a REINFORCE Recommender Systemcited by 182
  2. 2015Cascading Bandits: Learning to Rank in the Cascade Modelcited by 77
  3. 2016Cascading Bandits for Large-Scale Recommendation Problemscited by 45
  4. 2015Combinatorial Cascading Banditscited by 40
  5. 2015Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Playscited by 38
  6. 2014Unimodal Bandits: Regret Lower Bounds and Optimal Algorithmscited by 37
  7. 2018TopRank: A practical algorithm for online stochastic rankingcited by 30
  8. 2016Multiple-Play Bandits in the Position-Based Modelcited by 28
  9. 2017Online Learning to Rank in Stochastic Click Modelscited by 26
  10. 2018Online Learning to Rank with Featurescited by 18
  11. 2016DCM Bandits: Learning to Rank with Multiple Clickscited by 17
  12. 2020Learning to Rank in the Position Based Model with Bandit Feedbackcited by 10
2 more
  1. 2021Pure Exploration and Regret Minimization in Matching Banditscited by 4
  2. 2019BanditRank: Learning to Rank Using Contextual Banditscited by 3

Built on by

Not cited yet.