Refined Regret Analysis of UCB-GS in Centralized Matching Markets

In online two-sided matching markets, players seek to form stable matchings while learning their unknown preferences through repeated interactions with arms. A central platform can apply Gale-Shapley to players' upper confidence bound rankings of arms, an approach known as UCB-GS (Liu et al., 2020). We identify two sources of overcounting in the existing regret analysis of UCB-GS and sharpen it by jointly accounting for matchings blocked by the same blocking triplet and for different triplets that lead to observations of the same player-arm pair. Combining the first refinement with the structure of stable matchings, we obtain a player-pessimal stable regret bound of $O(K\log T/\Delta +N^2\log T/{\Delta }^2)$ for each player over $T$ rounds in a market with $N$ players and $K$ arms, where $\Delta$ is the minimum reward gap among each player's first $$\begin{gathered} \min \\ N+1,K \end{gathered}$$ arms. We also extend the analysis to many-to-one markets with responsive preferences. Two market families show that the two refinements can improve the preceding bounds by factors of order $K$ and $N$, respectively, and that on each family the improved bound matches the lower bound up to constant factors when $T$ is sufficiently large. Numerical experiments further illustrate these improvements.