Unimodal Mono-Partite Matching in a Bandit Setting

Romaric Gaudel, Matthieu Rodet

Introduction

Matching players in online games or participants in collaborative platforms is a complex task when their mutual preferences are unknown. This problem, framed as monopartite matching in a bandit setting, requires an algorithm to suggest pairings, observe outcomes, and iteratively improve its strategy to maximize successful connections. The primary challenge is the "curse of dimensionality": as the number of players $2L$ grows, the number of possible matchings increases factorially, making traditional search methods computationally prohibitive.

The Unimodality Approach

The core innovation of this research is the application of unimodality to the matching space. By assuming a "rank-1" structure—where the success probability of a match between players $i$ and $j$ is the product of their individual attractiveness parameters ($\theta_i \times \theta_j$)—the authors demonstrate that the reward function over the graph of all possible matchings has a single peak (the optimal matching).

This structural insight allows for the development of the GRAB (parametric Graph for unimodal RAnking Bandit) algorithm. Instead of exploring the entire space, GRAB focuses on the neighborhood of the current best-guess matching, moving "uphill" toward the optimum. An enhanced version, GRAB+, further accelerates convergence by comparing individual user strengths rather than entire matchings.

Key Results and Scaling

Theoretical analysis proves that GRAB achieves a regret bound of $O(\frac{L}{\Delta} \log T)$, where $L$ is the number of pairs. Crucially, this represents a linear scaling with respect to the number of players, a significant improvement over previous methods that scaled more aggressively.

Regret scaling $R(T)\Delta_{min}$ as a function of the number of pairs $L$. While the SAM algorithm's regret grows sharply, GRAB (GRAB1) and GRAB+ (GRAB2) maintain much lower, linear growth.

In empirical evaluations, GRAB and GRAB+ consistently outperformed the previous state-of-the-art SAM algorithm. As shown in the simulations, GRAB reduced normalized regret by approximately 2x, while GRAB+ achieved a reduction of over 5x.

Cumulative regret $R(t)$ over time for different player pool sizes ($L=2, 4, 10$). GRAB algorithms show steady, lower regret compared to SAM, which suffers from high initial regret as the problem complexity increases.

Conclusion

Beyond performance, GRAB offers practical advantages: it does not require prior knowledge of the time horizon ($T$) and maintains a manageable per-iteration computational complexity of $O(L^3)$. However, the reliance on the rank-1 assumption is a notable limitation. In real-world scenarios, player preferences may be driven by factors like skill parity rather than a single attractiveness score. Future work will explore relaxing this assumption while preserving the efficiency of the unimodal search approach.

Summary updated

Abstract

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.
BibTeX
@misc{gaudel2022unimodal,
  author = {Romaric Gaudel and Matthieu Rodet},
  title = {{Unimodal Mono-Partite Matching in a Bandit Setting}},
  year = {2022},
  eprint = {2208.01511},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.01511},
}
Figure