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