Unimodal Mono-Partite Matching in a Bandit Setting
This work provides incremental improvements in regret bounds for a specific bandit matching problem, relevant to scenarios like online recommendations or rankings.
The paper tackles the problem of finding an optimal monopartite matching in a weighted graph under a bandit setting, reducing the expected regret bound from O((L log(L))/Δ log(T)) to O(L/Δ log(T)) and further to O(LΔ/Δ̃² log(T)) by leveraging unimodality and refocusing on pairwise user comparisons.
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 \cite{ADMA}, creating an algorithm with an expected regret matching $O(\frac{L\log(L)}Δ\log(T))$ with $2L$ players, $T$ iterations and a minimum reward gap $Δ$. We reduce this bound in two steps. First, as in \cite{GRAB} and \cite{UniRank} we use the unimodality property of the expected reward on the appropriate graph to design an algorithm with a regret in $O(L\frac{1}Δ\log(T))$. Secondly, we show that by moving the focus towards the main question `\emph{Is user $i$ better than user $j$?}' this regret becomes $O(L\fracΔ{\tildeΔ^2}\log(T))$, where $\TildeΔ > Δ$ derives from a better way of comparing users. Some experimental results finally show these theoretical results are corroborated in practice.