acceptodds
Under review as a conference paper at ICLR 2027

Refined Regret Analysis of UCB-GS in Centralized Matching Markets

Abstract

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 for each player over rounds in a market with players and arms, where is the minimum reward gap among each player's first 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 and , respectively, and that on each family the improved bound matches the lower bound up to constant factors when is sufficiently large. Numerical experiments further illustrate these improvements.

Primary area:
learning theory
Keywords:
Multi-armed Bandits, Matching Markets, Upper Confidence Bound, Gale-Shapley

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_j33TOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the centralized matching markets when one side of preference is unknown, and provides a cute refined regret analysis of an existing algorithm UCB-GS (Liu et al. 2020). The original UCB-GS algorithm has player pessimal regret O(NKΔ2log⁡(T))O(\frac{NK}{\Delta^2}\log(T)), while this work improves the analysis to O(N2log⁡(T)/Δ2+Klog⁡(T)/Δ)O(N^2\log(T)/\Delta^2 + K\log(T)/\Delta)/. Also, the authors extend the analysis to many-to-one centralized matching markets and improve upon existing analysis.

Critical strengths
  1. The paper provides a clear comparison of assumptions and regret bounds in centralized matching markets. The paper shows the regret bound improvement over previous analysis, especially in terms of NN and KK.

  2. The paper provides a thorough analysis on both one-to-one matching markets and many-to-one matching markets.

Critical weaknesses
  1. My biggest concern is limited significance. The paper provides a cute re-analysis of an existing algorithm, and analyzes its player-pessimal regret when the matching market is centralized. However, existing papers (e.g., Kong & Li 2023) often study the stronger player-optimal regret, and they usually focus on decentralized matching markets. Therefore the current form of the paper has very limited significance, unless the authors can explain clearly why it is meaningful to study a sub-optimal algorithm under a narrower problem setting while we already have nicer solutions. The authors should also state clearly the difference of player-optimal stable matching and player-pessimal stable matching, and there is a line of works on decentralized markets. All these factors put the paper at an awkward position.

  2. The novelty of upper-lower bound tightness is unclear. The analysis improves upon the original analysis only if N is much smaller than K. However, the restricted two families seem to suggest N=K. This suggests that the original UCB-GS's regret upper bound is also tight, and it would be nice to derive a lower bound without such restrictions.

  3. The experiments are also weak since they only provide N=2,3,4,5N = 2,3,4,5, while existing literature often has much larger scales. It is hard to understand whether the analysis scales to large matching markets.

Questions for authors
  1. Compared to Liu et. al, what is the insight of your analysis? What can readers learn from your insights and potentially propose new algorithms? Why are your insights significant to matching market designers?

  2. UCB-GS is a sub-optimal algorithm because it fails to find a player-optimal solution and only stability is guaranteed. There are some UCB alternatives that have better theoretical guarantees and experimental performance. Can you extend your analysis to those stronger settings and algorithms?

8 comments
AuthorsOpenReview ↗

Response to Reviewer j33T [1/4]

We thank the reviewer for the careful review and for recognizing the improvements in our regret bounds and the thorough analysis of both one-to-one and many-to-one matching markets. We have uploaded a revised manuscript with changes highlighted in blue, and we address the concerns and questions below.


W1: Significance of analyzing the player-pessimal regret of UCB-GS in centralized markets.
A1: We agree that existing algorithms, such as ETGS (Kong & Li, 2023) and AETGS (Kong et al., 2024), provide logarithmic player-optimal regret guarantees in general markets, including in decentralized settings, whereas UCB-GS can incur linear player-optimal regret in some markets (Liu et al., 2020, Example 4). However, we believe that studying UCB-GS and refining its regret analysis remain meaningful. In the revision, we show that UCB-GS can achieve logarithmic player-optimal regret under Ergin-acyclic arm priorities, which allow multiple stable matchings. We also show that UCB-GS can incur lower regret than AETGS on some markets. Moreover, beyond reducing the dependence of its player-pessimal regret bound from NKNK to N2N^2 in general markets, the counting ideas developed in our analysis also apply to player-optimal regret and lead to a new algorithm, AETGS-SBU, whose player-optimal regret bound improves upon that of AETGS when N=KN=K.

First, UCB-GS can achieve logarithmic player-optimal regret when the market has suitable structure. The player-optimal and player-pessimal stable matchings assign each player its most and least preferred stable partners, respectively. Under the α\alpha-condition, the stable matching is unique, and Kong et al. (2024, Theorem 6.2) establish such a guarantee for UCB-GS. In the revision, we further show that under Ergin-acyclic arm priorities, UCB-GS achieves player-optimal regret O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) for every player, even when multiple stable matchings exist (Theorem 16, Section 7). This condition restricts only the known arm priorities and allows arbitrary strict player preferences.

Second, UCB-GS can incur lower regret than AETGS on some markets. In Appendix N, we construct a family of serial dictatorship markets with N=KN=K and Δ4=Δ\Delta_4=\Delta. For the highest-priority player, AETGS continues sampling all candidate arms until it can distinguish its two best arms, which are close in mean reward, whereas UCB-GS samples clearly inferior arms less often. For sufficiently large TT, this player incurs player-optimal regret O(log⁡T/Δ)O(\log T/\Delta) under UCB-GS and Θ(Nlog⁡T/Δ2)\Theta(N\log T/\Delta^2) under AETGS with known TT (Theorem 40). On 20 random serial dictatorship markets with N=K=8N=K=8 and T=106T=10^6, the mean regret is also lower under UCB-GS for all eight players (Appendix N.2).

Third, our analysis not only improves the player-pessimal regret bound of UCB-GS in general markets, but its two counting refinements also apply to player-optimal regret analysis and algorithm design. Liu et al. (2020) bound its player-pessimal regret in general markets by O(NKlog⁡T/Δ22)O(NK\log T/\Delta_2^2), whereas Kong et al. (2024) establish a sharper bound of O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) under the α\alpha-condition. Our Theorem 9 establishes a bound of O(Klog⁡T/Δ+N2log⁡T/Δ2)O(K\log T/\Delta+N^2\log T/\Delta^2) without requiring this condition, and we discuss the tightness of our refined bounds in A2. In the revision, we further apply the two refinements developed in our analysis (Section 4) beyond player-pessimal regret. We apply triplet count sharing (the first refinement) to establish that, under Ergin-acyclic arm priorities, UCB-GS achieves player-optimal regret O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) for every player (Theorem 16). We also apply observation count sharing (the second refinement) to design a new algorithm, AETGS-SBU, which achieves player-optimal regret O(Nlog⁡T/Δ42)O(N\log T/\Delta_4^2) when N=KN=K and TT is known (Theorem 37, Appendix L), improving upon the published O(N2log⁡T/Δ42)O(N^2\log T/\Delta_4^2) bound for AETGS in the same setting. We give further details in A5.

Our analysis focuses on the centralized setting, in which a platform selects the matching in each round. This setting isolates the regret caused by learning preferences from the cost of coordinating players, and our refinements concern the former. Whether they can be extended to decentralized algorithms is an interesting direction for future work.

Finally, as the reviewer suggested, we have clarified in the revised introduction that player-optimal and player-pessimal stable regret coincide when the stable matching is unique and can otherwise differ by a term linear in TT.

AuthorsOpenReview ↗

Response to Reviewer j33T [2/4]

W2: Tightness of the regret bounds and dependence on NN and KK.
A2: We clarify that neither market family in Section 6 assumes N=KN=K, and the original regret bound Λi(T)\Lambda_i(T) for UCB-GS (Liu et al., 2020) is not tight on either family. The first family has N=2N=2 and K≥4K\ge 4 (Section 6.1), while the second has N=K−1N=K-1 (Section 6.2). On the first family, the original bound for the target player is Λ2(T)=Θ(K3log⁡T)\Lambda_2(T)=\Theta(K^3\log T), whereas this player’s expected regret under UCB-GS is Θ(K2log⁡T)\Theta(K^2\log T). On the second family, the original bound for the target player is Λ1(T)=Θ(K3/2log⁡T)\Lambda_1(T)=\Theta(K^{3/2}\log T), whereas this player’s expected regret under UCB-GS is Θ(Klog⁡T)\Theta(\sqrt K\log T). In both cases, the original bound overestimates the expected regret by a factor of Θ(K)\Theta(K), while our refined bounds, Γ2(T)\Gamma_2(T) on the first family and Ψ1(T)\Psi_1(T) on the second, match it up to constant factors (Theorems 12–15).

Our analysis establishes tighter regret bounds for UCB-GS in general matching markets, especially when NN is much smaller than KK. Compared with the closed-form bound O(NKlog⁡T/Δ22)O(NK\log T/\Delta_2^2) of Liu et al. (2020), our closed-form bound O(Klog⁡T/Δ+N2log⁡T/Δ2)O(K\log T/\Delta+N^2\log T/\Delta^2) in Theorem 9 reduces NKNK to N2N^2 and replaces the gap Δ2\Delta_2, the minimum reward gap over all pairs of arms, with Δ≥Δ2\Delta\ge\Delta_2, the minimum adjacent reward gap among each player’s top min⁡N+1,K\min\\{N+1,K\\} arms. Moreover, our refined bounds satisfy Ψi(T)≤Γi(T)≤Λi(T)\Psi_i(T)\le\Gamma_i(T)\le\Lambda_i(T) on every market (Theorem 7).

We agree that a lower bound for general markets would be valuable. Sankararaman et al. (2021) establish a regret lower bound with linear dependence on NN under serial dictatorship. Such markets satisfy the α\alpha-condition, under which our regret bound for UCB-GS also has linear dependence on NN (Theorem 11 with unit capacities). Whether the quadratic dependence on NN in our general regret bound (Theorem 9) is necessary remains open.

W3: Experimental evaluation on larger matching markets.
A3: We would like to note that our regret analysis applies to arbitrary market sizes under the stated assumptions (Theorems 9 and 11) and does not depend on the market sizes used in the experiments.

We have also added experiments with K=15K=15 arms and N∈8,9,10N\in\\{8,9,10\\} players (Appendix K.4, Figure 6). For each market size, we generate 20 random markets and run UCB-GS 10 times per market over T=100,000T=100{,}000 rounds. At T=100,000T=100{,}000, the mean Γ1(T)\Gamma_1(T) is at least 48.3%, 53.6%, and 53.7% lower than the mean Λ1(T)\Lambda_1(T) for N=8,9,10N=8,9,10, respectively. The mean Ψ1(T)\Psi_1(T) is a further 6.2%, 6.3%, and 7.1% lower than the mean Γ1(T)\Gamma_1(T). These results show that both refinements remain effective at larger market sizes.

AuthorsOpenReview ↗

Response to Reviewer j33T [3/4]

Q1: New analytical insights and implications for algorithm and market design.
A4: Our main insight is that regret can be bounded more tightly by jointly accounting for different matchings and blocking triplets rather than treating them separately. First, Liu et al. (2020) bound regret by choosing a separate cover of blocking triplets for each arm that the target player may receive. Since the same triplet can block matchings assigning different arms to the target, its count bound may be applied repeatedly. Our first refinement, triplet count sharing, jointly accounts for these matchings through the LP Γi(T)\Gamma_i(T) (Section 4.1). Second, different blocking triplets can share the same assigned player-arm pair, so the rounds in which they block the selected matching contribute to the same observation count. Our second refinement, observation count sharing, establishes a new joint count bound of O(log⁡T/d2+H)O(\log T/d^2+\sqrt H) for HH such triplets with gaps at least dd, rather than the O(Hlog⁡T/d2)O(H\log T/d^2) obtained by summing their individual bounds (Theorem 6). Incorporating this bound yields the stronger LP Ψi(T)\Psi_i(T) (Section 4.2).

Our analysis also reveals how the structure of stable matchings limits the number of assigned player-arm pairs that need to be counted. For the second class of matchings in Proposition 10, the blocking triplets in the cover have their assigned arms among the NN arms used by the player-pessimal stable matching, giving at most N2N^2 assigned player-arm pairs. A further argument based on the player join of stable matchings handles the third class with at most N−1N-1 additional blocking triplets. Together, these arguments remove the dependence on KK from the Δ−2\Delta^{-2} term of the general regret bound (Theorem 9).

These insights also inform the analysis of player-optimal regret and the design of online learning algorithms. For regret analysis, we apply the idea of triplet count sharing (the first refinement) to establish a player-optimal regret bound of O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) for UCB-GS under Ergin-acyclic arm priorities (Theorem 16). For algorithm design, observation count sharing (the second refinement) suggests coordinating exploration so that observations can be used across successive proposals. Applying this principle, we develop a new algorithm, AETGS-SBU (Appendix L), which uses synchronized exploration blocks to achieve player-optimal regret O(Nlog⁡T/Δ42)O(N\log T/\Delta_4^2) when N=KN=K and TT is known, improving upon the published O(N2log⁡T/Δ42)O(N^2\log T/\Delta_4^2) bound for AETGS in the same setting (Theorem 37). For designers of centralized matching platforms, these results identify a sufficient condition on known arm priorities under which UCB-GS guarantees logarithmic player-optimal regret and show how coordinated exploration can improve regret guarantees. We discuss these extensions further in A5.

Reviewer_FzXYOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper revisits the regret analysis of UCB-GS in centralized matching markets. The authors identify two sources of overcounting in the existing analysis and propose two refinements based on sharing blocking-triplet counts and observation counts. By exploiting the structural properties of stable matchings, the paper establishes an improved player-pessimal stable regret bound of (O(K\log{T}/\varDelta +N^{2}\log{T}/{\varDelta }^{2})). The results are further extended to many-to-one matching markets. The authors also construct two market families to demonstrate the tightness of the refined bounds and provide numerical experiments to illustrate the improvements.

Critical strengths
  • The paper provides a technically interesting refinement of the existing regret analysis. In particular, identifying the two sources of overcounting and incorporating the corresponding constraints into linear programming formulations offers a systematic perspective on the analysis of UCB-GS.

  • The theoretical analysis is relatively comprehensive, including extensions to many-to-one markets and lower-bound constructions that establish tightness on specific market families.

Critical weaknesses
  • Limited significance of improving player-pessimal stable regret. My main concern is the significance of the improved regret guarantee relative to existing results. The paper focuses on player-pessimal stable regret, which is a substantially weaker benchmark than player-optimal stable regret. In markets with multiple stable matchings, the difference between these two regret notions can grow linearly with the time horizon. Consequently, a logarithmic player-pessimal regret bound does not necessarily imply sublinear player-optimal regret. Given that existing algorithms, such as AETGS, already provide player-optimal stable regret guarantees under their respective assumptions, it is unclear how much additional insight or practical value is gained from further tightening the weaker guarantee for UCB-GS.

  • Limited broader impact of the theoretical refinements.Although the proposed analysis is technically interesting, the paper does not introduce a new algorithm or improve the actual performance of UCB-GS. More importantly, it remains unclear whether these analytical techniques can be extended to stronger algorithms or lead to improved guarantees under the more meaningful player-optimal benchmark. Without such a connection, the contribution appears primarily incremental in terms of its broader significance.

Questions for authors
  • Given that existing algorithms have established stronger player-optimal stable regret guarantees, what is the main motivation for further refining the player-pessimal regret analysis of UCB-GS? Beyond obtaining a tighter upper bound for an existing algorithm, what broader theoretical insight does this work provide?

  • Can the proposed analytical techniques be extended to obtain improved player-optimal regret guarantees, either for UCB-GS or for other matching bandit algorithms? If not, what are the fundamental obstacles?

4 comments
AuthorsOpenReview ↗

Response to Reviewer FzXY [1/2]

We thank the reviewer for the thoughtful review and for recognizing the systematic perspective provided by our LP-based refinements. We have uploaded a revised manuscript with changes highlighted in blue, and we address the concerns and questions below.


W1 & Q1: Motivation for refining the player-pessimal regret analysis and studying UCB-GS.
A1: One of our main motivations is the difference between two existing regret bounds for UCB-GS. Liu et al. (2020) establish a player-pessimal regret bound of O(NKlog⁡T/Δ22)O(NK\log T/\Delta_2^2) in markets with arbitrary strict preferences, whereas Kong et al. (2024, Theorem 6.2) establish a bound of O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) under the α\alpha-condition. This raises the question of how much of the improvement under the α\alpha-condition can be recovered for UCB-GS under arbitrary strict preferences. We address this question by establishing a general player-pessimal regret bound of O(Klog⁡T/Δ+N2log⁡T/Δ2)O(K\log T/\Delta+N^2\log T/\Delta^2) for UCB-GS (Theorem 9). This result reduces the dependence from NKNK to N2N^2 in the term involving Δ−2\Delta^{-2}, without requiring the α\alpha-condition.

We agree that player-pessimal regret is a weaker benchmark, since the two regret notions can differ by a term linear in TT when multiple stable matchings exist, and that AETGS already guarantees logarithmic player-optimal regret in general markets. Although UCB-GS cannot have such a guarantee in general markets, since its player-optimal regret can be linear on some instances (Liu et al., 2020, Example 4), it can still achieve logarithmic player-optimal regret when the market has suitable structure. Kong et al. (2024, Theorem 6.2) establish this under the α\alpha-condition. However, the stable matching is unique under this condition, so the two regret notions coincide. In the revision, we further study when UCB-GS can achieve logarithmic player-optimal regret in markets with multiple stable matchings. Our new Theorem 16 (Section 7) establishes that in one-to-one markets with Ergin-acyclic arm priorities, UCB-GS achieves a player-optimal regret of O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) for every player. This condition restricts only the known arm priorities and holds, for example, when all arms rank the players in the same order. It allows arbitrary strict player preferences and permits multiple stable matchings.

Finally, in the revision, we show that UCB-GS can incur lower regret than AETGS on some markets. In Appendix N, we construct a family of serial dictatorship markets with N=KN=K and Δ4=Δ\Delta_4=\Delta. For the highest-priority player, AETGS continues sampling all candidate arms until it can distinguish its two best arms, which are close in mean reward, whereas UCB-GS samples clearly inferior arms less often. For sufficiently large TT, this player incurs player-optimal regret O(log⁡T/Δ)O(\log T/\Delta) under UCB-GS and Θ(Nlog⁡T/Δ2)\Theta(N\log T/\Delta^2) under AETGS with known TT (Theorem 40). On 20 random serial dictatorship markets with N=K=8N=K=8 and T=106T=10^6, the mean regret is also lower under UCB-GS for all eight players (Appendix N.2).

Q1: What broader theoretical insights does the analysis provide beyond a tighter regret bound?
A2: Beyond obtaining tighter regret bounds, our analysis in Section 4 shows that different matching outcomes and blocking triplets can lead to repeated counting of the same exploration cost. First, a single blocking triplet can block matchings that assign different arms to the target player, so its count bound should be applied once across these assignments. Second, different blocking triplets can share the same assigned player-arm pair, so the rounds in which they block the selected matching contribute to the same observation count. The two market families in Section 6 show that the refinements remove factors of order KK and NN, respectively, from the corresponding regret bounds, and that the refined bounds match the regret of UCB-GS up to constant factors on these families.

Our analysis also shows how the structure of stable matchings can improve the general regret bound. For the second class of matchings in Proposition 10, every blocking triplet in the cover has its assigned arm among the NN arms used by the player-pessimal stable matching. This limits the number of assigned player-arm pairs in the cover for this class to at most N2N^2, even when KK is much larger than NN, and helps remove the factor KK from the Δ−2\Delta^{-2} term of the general bound. We discuss how the two refinements extend to player-optimal regret and other algorithms in A3.

AuthorsOpenReview ↗

Response to Reviewer FzXY [2/2]

W2 & Q2: Can these ideas yield improved player-optimal regret bounds for UCB-GS or other algorithms?
A3: Yes. In the revision, we apply the idea of triplet count sharing (the first refinement) to derive a new player-optimal regret bound for UCB-GS, and the idea of observation count sharing (the second refinement) to design a new algorithm, AETGS-SBU, with an improved player-optimal regret guarantee.

  • Player-optimal stable regret of UCB-GS under Ergin-acyclic priorities (Section 7). We apply the idea of triplet count sharing to the player-optimal regret analysis of UCB-GS. A player can receive an arm worse than its player-optimal stable partner even when the selected matching is stable under the true preferences, so this loss cannot always be charged to a blocking triplet. Under Ergin-acyclic arm priorities, we show that every such loss can instead be traced to a ranking error, in which some player ranks its assigned arm above its player-optimal stable partner despite preferring the latter. Since this player observes its assigned arm, we can bound how often each error occurs. Instead of applying this bound to errors made by other players separately for each assignment to the target player, we apply it once across these assignments, reducing their contribution from O(KNlog⁡T/Δ2)O(KN\log T/\Delta^2) to O(Nlog⁡T/Δ2)O(N\log T/\Delta^2) (Appendix M.2). UCB-GS thus achieves a player-optimal regret of O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) for every player (Theorem 16), even when multiple stable matchings exist.
  • Player-optimal stable regret of AETGS-SBU when N=KN=K (Appendix L). We design AETGS-SBU (Algorithm 2) by applying observation count sharing across a player’s successive proposals. Compared with AETGS (Kong et al., 2024), it organizes exploration into synchronized blocks, and every exploring player samples all of its remaining candidate arms in each complete block, so that observations from earlier blocks cover every arm it may still propose to after a rejection. When N=KN=K and TT is known, AETGS-SBU achieves player-optimal regret of O(Nlog⁡T/Δ42)O(N\log T/\Delta_4^2) for every player under arbitrary strict preferences (Theorem 37), improving upon the published O(N2log⁡T/Δ42)O(N^2\log T/\Delta_4^2) bound for AETGS in the same setting.

We appreciate your valuable review and are more than happy to answer any further questions.

References:

  • Liu et al. (2020). Competing Bandits in Matching Markets. AISTATS.
  • Kong et al. (2024). Improved Analysis for Bandit Learning in Matching Markets. NeurIPS.

I would like to thank the authors for the effort, leading to new results regarding the player optimal regret bound. While I still have concern on the technical novelty, I will raise my score to weak accept.

Thank you for your thoughtful follow-up and for raising the score. We are grateful for your recognition of our new results on player-optimal regret. Regarding your remaining concern about technical novelty, we discuss the technical contributions of our analysis in detail in our response to Reviewer 6ePH (A1), and we would be happy to provide any further clarification you may find helpful. Your constructive comments have helped us strengthen the manuscript.

We sincerely appreciate your time and effort in reviewing our work.

Reviewer_6ePHOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper the authors improve the existing regret bound of the well known algorithm UCB-GS for centralized matching markets. They refine the earlier player-pessimal stable regret bound of UCB-GS for both one-to-one and many-to-one markets. They figure out two sources of overcounting in the earlier analysis and refine them with the aid of LP-based counting methods, and exploit the structure of the stable matching to get the final bound. They also establish regret lower bounds on two constructed market families, showing that the refined bounds are tight up to constant factors on those families for sufficiently large TT.

Critical strengths
  • The improvement of the regret bound via an LP-based approach without any additional assumptions is an interesting theoretical contribution.
  • The presentation of the refinement section (Section 4) is good. Using toy examples before writing the formal constraints enhances the reading experience, especially when there is a lot of notation moving around.
Critical weaknesses

(Major Concerns)

  • the paper does not introduce a new algorithm, the improvement comes from a refined analysis of the existing UCB-GS. Although the LP view is interesting and the refinements are non-trivial, the main ingredients seem to be built on prior results of Liu et al.(2020) and classical stable matching results.

  • The second refinement of the LP (in Section 4) does not improve the general regret bound order-wise (as shown in Theorem 26). This seems to limit the significance of the improved LP Ψ\Psi.

  • it is not clear whether the new regret bound is optimal. The tightness results (section 6) are shown only on two specific market families, and both of them have a unique stable matching (Lemma 28 and 30), where player-pessimal and player-optimal regret are the same. So the tightness is never shown for a market with multiple stable matchings, which is exactly where the player-pessimal notion matters. Also none of these families shows the N2N^2 dependence, so it seems open whether the quadratic dependence on NN is really needed.

  • the paper focuses on the player-pessimal stable regret, although for the stronger player-optimal notion Kong et al.(2024) already give a bound of the same order in NN and KK, with equal or better reward gaps. The only advantage of UCB-GS seems to be that it does not need the knowledge of TT, which usually can be removed by standard techniques like the doubling trick. Under the α\alpha-condition both notions are the same, but general markets are a much bigger set, and the paper does not discuss whether a player-optimal guarantee without the knowledge of TT is possible there. This seems to limit the significance of improving the weaker notion.

(Minor Concerns)

  • Although the paper claims to improve the regret bound by getting rid of the α\alpha-condition assumption, the α\alpha-condition is nowhere properly defined in the main paper (it is only referred to Appendix J.5).

  • The introduction paragraph where the informal idea of the overcounting, and how to get rid of it, is discussed is not easily understandable. A lot of terms are used there before being defined, like blocking triplets, player-arm pair, etc., without any intuition or examples. A reader who is not familiar with bandits in matching markets will not be able to follow.

  • Even though the authors claim the regret improvement for many-to-one matching as one of their primary contributions, it is not introduced in the problem setting (Section 3). Introducing the important terms associated with it, like the capacitated model and responsive preferences, would be helpful.

Questions for authors
  • There is a gap between the known lower bound by Sankararaman et al. (2021) (under serial dictatorship) and the proven upper bound in this paper by a factor of NN. Could you clarify whether the source of the gap is inherent to the LP you designed or to the algorithm itself?

  • Is it possible, possibly with a different algorithm, to achieve a player-optimal stable regret guarantee in general markets without the knowledge of TT? For example, can the requirement of TT in AETGS be removed by a standard doubling trick?

6 comments
AuthorsOpenReview ↗

Response to Reviewer 6ePH [1/4]

We thank the reviewer for the careful review, for highlighting the improvement obtained by our LP analysis without additional assumptions, and for noting that the examples in Section 4 help clarify the two refinements. We have uploaded a revised manuscript with changes highlighted in blue, and we address the concerns and questions below.


W1: Novelty and technical contributions of our analysis.
A1: Our analysis builds on the count bound of Liu et al. (2020) for an individual blocking triplet and the classical result that the player join of stable matchings is also stable (Roth & Sotomayor, 1990). However, deriving the refined regret bounds Γi(T)\Gamma_i(T) and Ψi(T)\Psi_i(T) requires new counting arguments (Section 4), and establishing the general regret bound in Theorem 9 additionally requires a new construction of blocking triplet covers (Proposition 10).

The two refinements address different sources of overcounting in the existing regret analysis. First, Liu et al. (2020) bound regret by choosing a separate cover of blocking triplets for each arm that the target player may receive. Since the same triplet can block matchings assigning different arms to the target, its count bound may be applied repeatedly. Our first refinement addresses this overcounting through the LP Γi(T)\Gamma_i(T), which imposes a single constraint on the total count of all matchings blocked by each triplet (Section 4.1). Second, different blocking triplets may share the same assigned player-arm pair, so the rounds in which they block the selected matching contribute to the same observation count. We establish a new joint count bound (Theorem 6) that controls these rounds together. For HH triplets sharing the same assigned pair and having gaps at least dd, this bound is O(log⁡T/d2+H)O(\log T/d^2+\sqrt H), rather than the O(Hlog⁡T/d2)O(H\log T/d^2) obtained by summing individual triplet bounds. Incorporating these joint constraints yields the stronger LP Ψi(T)\Psi_i(T) (Section 4.2).

For the general regret bound, a direct cover of matchings with positive regret gaps may involve up to N(K−1)N(K-1) assigned player-arm pairs. To reduce this dependence on KK, Proposition 10 partitions these matchings into three classes. The first class can be covered by triplets involving the target player and its player-pessimal stable arm. For the second class, we use the NN arms assigned by the player-pessimal stable matching, limiting the number of assigned player-arm pairs to at most N2N^2. The remaining class requires a new argument. We construct stable matchings in the market restricted to these NN arms, while preserving the target player's assignment, and use their player join to identify a common arm outside this set that is assigned in every matching of the remaining class. We further show that the holder of this arm forms a blocking pair with its player-pessimal stable arm, so at most N−1N-1 additional triplets suffice to cover the entire class. The classical player join result alone does not establish this common-arm property or the resulting cover. Combined with the first refinement, this yields the general regret bound O(Klog⁡T/Δ+N2log⁡T/Δ2)O(K\log T/\Delta+N^2\log T/\Delta^2) under arbitrary strict preferences (Theorem 9).

AuthorsOpenReview ↗

Response to Reviewer 6ePH [2/4]

W2: Significance of the second refinement (observation count sharing).
A2: We agree that the second refinement does not further improve the order of the general regret bound obtained from the first refinement and the structure of stable matchings. For completeness, we derive an explicit finite-time upper bound for Ψi(T)\Psi_i(T) using the joint observation constraints in Appendix F.4 (Theorem 26 in the submission, Theorem 28 in the revision). Nevertheless, the second refinement guarantees Ψi(T)≤Γi(T)\Psi_i(T)\leq\Gamma_i(T) for every market, and the improvement can reach a factor of order NN on some market families.

In the market family studied in Section 6.2, N=K−1N=K-1 and K−1K-1 matchings have pairwise disjoint sets of blocking triplets. The triplet constraints in the first LP therefore allow a separate count for each matching. All these matchings, however, assign aKa_K to p1p_1, so each such round adds one observation of the same player-arm pair. The joint observation constraint in the second LP bounds the total number of these rounds. For sufficiently large TT, Γ1(T)\Gamma_1(T) exceeds the actual regret of p1p_1 under UCB-GS by a factor of order NN, whereas Ψ1(T)\Psi_1(T) matches that regret up to constant factors (Theorems 14 and 15 of the revision).

The principle of observation count sharing also applies beyond the analysis of UCB-GS. In the revision, we introduce AETGS with Synchronized Block Updates (AETGS-SBU) as Algorithm 2. We organize exploration into synchronized blocks so that each player samples every remaining candidate arm in each complete block it spends exploring. After a rejection, observations from earlier blocks therefore help the player compare the remaining arms, allowing us to bound its total exploration across successive proposals. In markets with N=KN=K and arbitrary strict preferences, we establish a player-optimal regret bound of O(Nlog⁡T/Δ42)O(N\log T/\Delta_4^2) per player when TT is known (Theorem 37 in Appendix L), improving upon the published O(N2log⁡T/Δ42)O(N^2\log T/\Delta_4^2) bound for AETGS in the same setting (Kong et al., 2024).

W3: Tightness with multiple stable matchings and optimality of the general regret bound.
A3: To show that our refined bound can be tight even when multiple stable matchings exist, we construct a family of markets with N=4N = 4 players and K≥5K\geq 5 arms in Appendix O of the revision. Each market admits exactly two stable matchings. In the player-optimal stable matching, the target player p2p_2 receives a2a_2 with mean reward 3/43/4, whereas in the player-pessimal stable matching, it receives a3a_3 with mean reward 1/21/2. For sufficiently large TT, both Γ2(T)\Gamma_2(T) and Ψ2(T)\Psi_2(T) match the player-pessimal regret R2(T)=Θ(K2log⁡T)R_2(T)=\Theta(K^2\log T) of UCB-GS up to constant factors, whereas Liu et al.'s bound Λ2(T)\Lambda_2(T) is Θ(K3log⁡T)\Theta(K^3\log T) (Theorem 41). Thus, the first refinement improves the original bound by a factor of order KK, even when the two stable benchmarks differ.

To prove the regret lower bound on R2(T)R_2(T), we account for the rounds in which p2p_2 receives its better stable arm a2a_2. Whenever p1p_1 receives a3a_3, p2p_2 cannot receive it. In each such round, p2p_2's regret relative to a3a_3 is −1/4-1/4 if it receives a2a_2 and at least 3/83/8 otherwise. We show that UCB-GS assigns a3a_3 to p1p_1 on Ω(K2log⁡T)\Omega(K^2\log T) rounds, while p2p_2 receives a2a_2 only O(Klog⁡T)O(K\log T) times over TT rounds. These counts yield R2(T)=Ω(K2log⁡T)R_2(T)=\Omega(K^2\log T).

For the general regret bound, it remains open whether the quadratic dependence on NN is necessary, and we discuss it more in A6.

AuthorsOpenReview ↗

Response to Reviewer 6ePH [3/4]

W4: Why study UCB-GS when AETGS (Kong et al., 2024) already guarantees player-optimal regret?
A4: We agree that AETGS guarantees logarithmic player-optimal regret O(Klog⁡T/Δ4+N2log⁡T/Δ42)O(K\log T/\Delta_4+N^2\log T/\Delta_4^2) in general markets, with the same orders in NN and KK as our general player-pessimal bound and a gap Δ4≥Δ\Delta_4\ge\Delta. Although UCB-GS cannot have such a guarantee in general markets, since its player-optimal regret can grow linearly in TT on some instances (Liu et al., 2020, Example 4), it can still achieve logarithmic player-optimal regret when the market has suitable structure. Under the α\alpha-condition, which guarantees a unique stable matching, Kong et al. (2024, Theorem 6.2) establish the bound O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) for UCB-GS. The published AETGS bound O(Klog⁡T/Δ4+N2log⁡T/Δ42)O(K\log T/\Delta_4+N^2\log T/\Delta_4^2) also applies under the α\alpha-condition. In these bounds, the second term is linear in NN for UCB-GS and quadratic in NN for AETGS, with gaps Δ\Delta and Δ4\Delta_4, respectively.

Our new Theorem 16 in Section 7 shows that UCB-GS can achieve logarithmic player-optimal regret even when multiple stable matchings exist. In one-to-one markets with Ergin-acyclic arm priorities (Ergin, 2002), UCB-GS achieves player-optimal regret of O(Klog⁡T/Δ4+Nlog⁡T/Δ2)O(K\log T/\Delta_4+N\log T/\Delta^2) for every player. This condition restricts only the known arm priorities, so players may have arbitrary strict preferences, and it allows multiple stable matchings. Under this condition, we show that a player's loss relative to its player-optimal stable partner can be traced to an observed ranking error, in which some player ranks the arm it receives above an arm that it prefers. Applying the count bound for each ranking error made by another player separately for every assignment to the target player would give a second term of order KNlog⁡T/Δ2KN\log T/\Delta^2, whereas applying each such bound only once across these assignments, as in triplet count sharing (Section 4.1), gives Nlog⁡T/Δ2N\log T/\Delta^2 (Appendix M). The published bound for AETGS (Kong et al., 2024) also applies to these markets. For comparison, we also analyzed the original AETGS using the properties of Ergin-acyclic arm priorities but have not obtained a bound linear in NN for every player.

Finally, we show that UCB-GS can incur lower regret than AETGS on some markets. In Appendix N, we construct a family of serial dictatorship markets with N=KN=K and Δ4=Δ\Delta_4=\Delta. For the highest-priority player, AETGS continues sampling all candidate arms until it can distinguish its two best arms, which are close in mean reward, whereas UCB-GS samples clearly inferior arms less often. For sufficiently large TT, this player incurs player-optimal regret O(log⁡T/Δ)O(\log T/\Delta) under UCB-GS and Θ(Nlog⁡T/Δ2)\Theta(N\log T/\Delta^2) under AETGS with known TT (Theorem 40). On 20 random serial dictatorship markets with N=K=8N=K=8 and T=106T=10^6, the mean regret is also lower under UCB-GS for all eight players (Appendix N.2). We discuss doubling for AETGS and horizon-free player-optimal guarantees in general markets in A7.

W5-W7: Presentation of the α\alpha-condition, the introduction, and the many-to-one setting.
A5: We have revised the manuscript accordingly. Section 3 now defines the α\alpha-condition (Definition 2) and introduces the many-to-one market setting, including arm capacities, responsive preferences, and the definition of blocking pairs. We have also rewritten the corresponding part of the introduction to explain blocking triplets and assigned player-arm pairs before discussing the two sources of overcounting and how our refinements address them.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.