Unimodal Mono-Partite Matching in a Bandit Setting

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.