# Unimodal Mono-Partite Matching in a Bandit Setting

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

## Key facts

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

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

- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits](https://mlsanity.com/paper/2002.07258/) (2020)
- [Pure Exploration and Regret Minimization in Matching Bandits](https://mlsanity.com/paper/2108.00230/) (2021)

## 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.