acceptodds
Withdrawn from ICLR 2027

Contextual Linear Bandits for Matching Markets

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

22 views

Abstract

An extensive line of work studies bandit learning in two-sided matching markets, where the goal is to learn unknown preferences and converge to a stable matching through repeated interactions. Existing approaches predominantly focus on the tabular setting, where regret guarantees scale with the number of arms . This dependence severely limits scalability in large markets commonly encountered in real-world applications. In this paper, we study contextual matching markets and leverage arm features to accelerate preference learning. For the strict preference setting, we propose a decentralized G-optimal design-based algorithm that achieves a player-optimal regret of , where denotes the number of players, denotes the feature dimension, is the time horizon, denotes the sampling probability of arm and is the preference gap. This result significantly improves scalability when . We further extend our framework to matching markets with indifference and develop an arm-proposing exploration algorithm that achieves a regret of . To the best of our knowledge, this is the first work that simultaneously addresses both contextual information and tied preferences. In addition, to characterize the hardness of our problem, we establish an instance-dependent regret lower bound of . Our framework also recovers existing guarantees in the tabular setting as a special case. Experiments demonstrate that our methods substantially outperform existing approaches in large-scale markets.

Primary area:
learning theory
Keywords:
Bandits,Matching Markets

Reviews

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

The paper studies online matching markets with linear preferences. Under strict preferences, the authors propose an algorithm attaining regret O(dmax⁡[1,Nπ]log⁡T/Δ2)O(d\max[1,N\pi]\log T/\Delta^2), where π\pi is the largest sampling probability. With tied preferences, the authors propose a computationally efficient algorithm which achieve O(Nd2log⁡2T/Δ2)O(Nd^2\log^2 T/\Delta^2) regret. These leading terms reduce dependence on the number of arms. The authors also provide a lower bound for the setting.

Critical strengths

The main strength of the paper is the relevance of the problem setting. I agree with the authors that the tabular formulation, which treats each player–arm pair independently, can limit scalability in large matching markets. Exploiting linear structure through arm features is therefore a valuable direction.

Another strength is the breadth of the theoretical analysis. The authors establish regret upper bounds, derive a lower bound, and extend their approach to markets with tied preferences. Although the upper and lower bounds do not match, these results provide quite a strong characterisation of the setting.

Critical weaknesses

One of my main concerns is the presentation, which I found difficult to follow. The paper would benefit from a clearer structure, with more descriptive subsections and paragraphs. The problem setting would also benefit from a more explicit description. In particular, I would suggest including a “Learner–environment interaction” protocol specifying what each player knows initially, which actions are taken in each round, how the matching is determined, what feedback is observed etc.

I also do not totally get which is the main technical challenge behind employing standard linear bandit techniques to matching markets. The current exposition does not help on this point. Specifically, It is not clear from the text which are the unique challenges that does not allow an easy transfer from linear bandits techniques to the setting studied (up to employing existing ideas on matching market).

Thus, for now, I am not going to support acceptance of the paper. Nonetheless, since I am not an expert of the setting, I am willing to increase the score after reading the authors comment and the other reviews.

Questions for authors

See Weaknesses.

3 comments

We thank reviewer wWVo for the valuable comments. Please find our response below.

1.Response to advice on presentation.

We agree that the presentation would benefit from more detailed explanations and illustrative examples. Unfortunately, due to the 9-page space limit, we were unable to include these additional details in the current version. We will add more descriptive paragraphs and examples in the next version of the paper.

2.Discussions of the challenges and technical contributions of our work.

We agree that building blocks such as G-optimal design, the explore-then-Gale--Shapley paradigm are established upon previous literature. Our contribution is not to claim novelty for these individual components. Rather, the main technical challenge is that they are not directly compatible in a decentralized contextual matching market. In particular, a direct replacement of the tabular estimators in ETGS by linear estimators neither yields our algorithms nor implies our regret guarantees.

First, standard G-optimal exploration assumes that informative actions can be selected according to an experimental design. In a decentralized matching market, however, the realized observations are jointly determined by the actions of multiple players, arm-side priorities, and collisions. Therefore, an individually optimal linear design may not be implementable simultaneously by all players. The exploration and coordination problems are intrinsically coupled: the algorithm must realize sufficiently informative design matrices for every player while respecting decentralized interaction constraints. Our routing mechanism in Algorithm 2 is introduced precisely to establish this joint feasibility, where we recognize that this routing problem can be transferred into a classical graph theory problem and its analysis proves that the desired linear-design coverage is retained despite multi-player interference. Without this routing algorithm, CETGS may suffer a worst case regret of O(Ndlog⁡TΔ2)O\left(\frac{Nd\log T}{\Delta^2}\right) which is larger than our regret upper bound of O\\!\left(\max\left\\{ \frac{d\log T}{\Delta^2}, \max_j \frac{Nd\\,\pi_i(j)\log T}{\Delta^2} \right\\}\right). This challenge does not arise in either standard linear bandits or tabular ETGS.

Second, for the setting with indifference, beyond the existing arm-proposing mechanism, we introduce a new pure-exploration algorithm, termed CEWI. This mechanism removes the reliance of ETGS on strict preferences for generating a stable matching from another perspective. Once the players’ preferences have been sufficiently explored, CEWI automatically identifies a stable matching and thereby avoids becoming trapped in prolonged exploration. This method also achieves better statistical efficiency.

Third, the tabular arm-proposing algorithm of [1] enjoys substantially better computational efficiency, which motivates us to adapt it to the contextual linear setting. Although replacing the least-sampled-arm criterion with a maximum-variance criterion may appear conceptually natural, this modification creates a new and nontrivial challenge in the regret analysis. In the tabular setting, selecting the least-sampled arm ensures that, within each phase, the numbers of observations collected from any two candidate arms differ by at most one. Consequently, a suboptimal arm cannot be selected excessively often during a single phase. This balancing property no longer holds in contextual linear matching markets. In particular, an arm with low expected reward but high predictive variance may be repeatedly selected throughout a phase because it remains informative about an insufficiently explored direction in the feature space. When the phase length is large, these repeated selections can accumulate substantial regret. Therefore, a direct phase-based extension of the arm-proposing method may incur prohibitively large regret. To obtain sublinear regret in the contextual linear setting, we introduce an instant-communication mechanism that couples geometry-aware exploration in the linear feature space with decentralized multi-player coordination. By allowing updated preference estimates to be broadcast and acted upon within each phase, the proposed mechanism prevents outdated uncertainty estimates from repeatedly selecting low-reward arms and avoids the additional regret induced by exponentially increasing phase lengths.

Finally, we provide the first instance-dependent lower bound in contextual matching markets, which identifies the unavoidable contributions of both multi-player competition and linear preference learning, thereby establishing a benchmark for future algorithmic developments. Taken together, the technical contribution is not a mechanical combination of previous linear bandit literature, but the development and analysis of coordination, exploration, and communication mechanisms that make contextual generalization compatible with decentralized stable matching.

[1] Fang Kong, Jingqi Tang, Mingzhu Li, Pinyan Lu, John CS Lui, and Shuai Li. Bandit learning in matching markets with indifference. In The Thirteenth International Conference on Learning Representations, 2025.

I would like to thank the Authors for the response, but after reading both the authors responses and in particular the other reviews I am still not convinced about the paper meeting the acceptance bar. Nonetheless, since as I specified I am not an expert in this particular field, I will take into account Reviewers comments throughout the final discussion.

Reviewer_yj4COpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies decentralized bandit learning in two-sided matching markets under a linear contextual reward model. By exploiting the shared feature structure across arms, the authors aim to reduce the dependence on the number of arms in regret guarantees. For markets with strict preferences, the paper proposes CETGS, which combines G-optimal experimental design with collision-free exploration based on bipartite edge coloring and achieves player-optimal stable regret guarantees. The framework is further extended to markets with indifference through CEWI and the computationally more efficient C-EAGS algorithm. The authors also establish an instance-dependent regret lower bound and provide numerical experiments comparing their algorithms with existing approaches.

Critical strengths
  1. Combining G-optimal design with collision-free exploration based on bipartite edge coloring provides a principled approach to coordinating information-efficient exploration in decentralized matching markets. The resulting regret guarantees improve the dependence on the number of arms in the leading terms when the feature dimension is small.

  2. The paper considers both strict and tied preferences, and further develops an enumeration-free algorithm to address the computational limitations of the initial extension. The theoretical results and numerical experiments demonstrate the potential benefits of exploiting contextual information in matching markets.

Critical weaknesses
  1. A central contribution is reducing the dependence on KK. However, the finite-time bounds in Appendices F, H, and I still contain KK-dependent terms, including O(NK)O(NK) and O(NK2)O(NK^2), which may be substantial in large markets. Moreover, the experiments are conducted on relatively small markets, providing limited evidence for scalability to large KK.

  2. While CEWI achieves a regret bound of O(Ndlog⁡T/Δ2)O(Nd\log T/\Delta^2), it suffers from exponential computational complexity. The computationally efficient C-EAGS avoids enumeration but has a worse regret guarantee of O(Nd2log⁡2T/Δ2)O(Nd^2\log^2 T/\Delta^2). Moreover, no corresponding lower bound is established for the indifference setting, leaving it unclear whether this trade-off is fundamental or can be further improved.

Questions for authors

1.Could the authors clarify when the additional KK-dependent costs become negligible and compare the complete finite-time regret bounds with previous contextual matching works? Do these previous approaches also incur similar hidden KK-dependent costs?

2.Several algorithmic ideas appear closely related to existing methods for non-contextual matching markets. Could the authors clarify the specific technical challenges introduced by the linear contextual setting and identify which parts of the algorithm design and analysis require genuinely new arguments?

5 comments

We thank reviewer yj4C for the valuable comments. Please find our response below.

1.Clarification of the of the KK-independence statement.

Our result is primarily intended to characterize the horizon- and gap-dependent learning complexity. In particular, the regret bounds take the form O\\!\left(\max\left\\{ \frac{d\log T}{\Delta^2}, \max_j \frac{Nd\\,\pi_i(j)\log T}{\Delta^2} \right\\}\right)+O(NK), O(Ndlog⁡TΔ2)+O(NK2)O\left(\frac{Nd\log T}{\Delta^2}\right)+O(NK^2) and O(Nd2log⁡2TΔ2)+O(NK2)O\left(\frac{Nd^2\log^2 T}{\Delta^2}\right)+O(NK^2) where the dependence on KK is additive and does not multiply either log⁡T\log T or 1/Δ21/\Delta^2. Therefore, under the standard asymptotic regime in which the market size is fixed and the horizon TT grows, the first term determines the leading dependence on TT.

Importantly, the additive KK term does not arise from estimating the unknown linear preference parameter. Instead, it is incurred by the coordination and information-sharing procedure required in the general decentralized multi-player market, where each player does not directly observe the preferences or observations of the other players. A term of this form also appears in regret bounds for tabular matching markets, where it is typically treated as a lower-order contribution. This distinction is supported by our centralized-market result: when a central server can coordinate the players and aggregate their information, the additional information-sharing procedure is unnecessary, and the corresponding KK-dependent term is eliminated.

Our result shows that the dependence on KK can be separated from the leading statistical learning terms O\\!\left(\max\left\\{ \frac{d\log T}{\Delta^2}, \max_j \frac{Nd\\,\pi_i(j)\log T}{\Delta^2} \right\\}\right), O(Ndlog⁡TΔ2)O\left(\frac{Nd\log T}{\Delta^2}\right) and O(Nd2log⁡2TΔ2)O\left(\frac{Nd^2\log^2 T}{\Delta^2}\right). Further reducing the dependence on KK is primarily a question of designing more communication-efficient multi-player coordination mechanisms, rather than improving the underlying learning algorithm.

2. Communication comparison with related contextual matching works

Under strict preference, CETGS suffers an extra O(NK)O(NK) regret due to the index pahse. This additional regret only appears in our general decentralized setting and disappears when there exist a central server. [1] assumes study a centralized setting which is free from the communication cost depednt wit KK, while [2] assumed a shared information board to synchronize exploration, without separately charging additional rounds for communication. In addition, we can use the subscript of players as their index and thereby avoiding the index phase with O(NK)O(NK) regret without loss of generality. We employ such index phase to be consistent with previous decentralized literature [3].

Both [1] and [2] did not investigate the indifference setting without approximations. In our decentralized market, since each player only has access to its own local information, players can only infer other players' preferences by observing their arm selections during the respective phases. This will result in a worst case regret of O(NK2)O(NK^2) when players have to share their full preference through the learning process under indifference.

3.Discussions of the lower bound under indifference.

We agree that an additional lower bound under the indifference setting will help readers better understand the learning difficulty of this specific setting. However, establishing this lower bound is much more difficult than in the strict preference setting, as both players and arms may have arbitrary tied preferences. This lower bound under indifference has not been established even in the simpler tabular case. In addition, since the indifference setting is a harder problem setting than the strict preference setting, the lower bound of \Omega \left( \max \left\\{ \frac{N \log T}{\Delta^2}, \frac{d \log T}{\Delta} \right\\} \right) in the strict preference setting can also be seen as a lower bound for the indifference setting. We will reserve the derivation of this lower bound under indifference for future work.

4.Discussions of the tradeoff between C-EAGS and CEWI.

The extra dlog⁡Td\log T factor of C-EAGS comparing to CEWI is an artifact of the analysis rather than an foundamental tradeoff between regret upper bound and computation efficiency. As in Eq.(20) we use the inequality

∑t=1TI(max⁡j∈Ai∖Ei∣Cj∣Vi,t−1−1>Δ4βt)⋅(Δ4βt)2≤∑t=1T(1∧max⁡aj∈Ai,t∣Ci,j∣Vi,t−1−12).\sum_{t=1}^{T} \mathbb{I}\left( \max_{j\in\mathcal{A}_i\setminus\mathcal{E}_i} \\|C_j\\|_{V_{i,t-1}^{-1}} > \frac{\Delta}{4\sqrt{\beta_t}} \right) \cdot \left(\frac{\Delta}{4\sqrt{\beta_t}}\right)^2 \leq \sum_{t=1}^{T} \left( 1\wedge \max_{a_j\in\mathcal{A}_{i,t}} \\|C_{i,j}\\|_{V_{i,t-1}^{-1}}^2 \right).

where

βt=λM+2log⁡1δ+dlog⁡(dλ+tL2dλ).\sqrt{\beta_t} = \sqrt{\lambda}M + \sqrt{ 2\log\frac{1}{\delta} + d\log\left( \frac{d\lambda+tL^2}{d\lambda} \right) }.

introduces one dlog⁡Td\log T factor and

∑t=1T(1∧max⁡aj∈Ai,t∣Ci,j∣Vi,t−1−12)≤2log⁡det⁡(Vi,T)det⁡(λI)≤2dlog⁡(1+TL2λd).\sum_{t=1}^{T} \left( 1 \wedge \max_{a_j \in \mathcal{A}_{i,t}} \\|C_{i,j}\\|_{V_{i,t-1}^{-1}}^2 \right) \leq 2\log \frac{\det(V_{i,T})}{\det(\lambda I)} \leq 2d\log\left( 1+\frac{TL^2}{\lambda d} \right).

account for the other.

5.Discussions of the challenges and technical contributions.

We agree that building blocks such as the explore-then-Gale--Shapley paradigm are established upon previous non-contextual literature. Our contribution is not to claim novelty for these individual components. Rather, the main technical challenge is that they are not directly compatible in a decentralized contextual matching market. In particular, a direct replacement of the tabular estimators in ETGS by linear estimators neither yields our algorithms nor implies our regret guarantees.

First, we employ G-optimal design during expoloration in CETGS. However standard G-optimal exploration assumes that informative actions can be selected according to an experimental design. In a decentralized matching market, however, the realized observations are jointly determined by the actions of multiple players, arm-side priorities, and collisions. Therefore, an individually optimal linear design may not be implementable simultaneously by all players. The exploration and coordination problems are intrinsically coupled: the algorithm must realize sufficiently informative design matrices for every player while respecting decentralized interaction constraints. Our routing mechanism in Algorithm 2 is introduced precisely to establish this joint feasibility, where we recognize that this routing problem can be transferred into a classical graph theory problem and its analysis proves that the desired linear-design coverage is retained despite multi-player interference. Without this routing algorithm, CETGS may suffer a worst case regret of O(Ndlog⁡TΔ2)O\left(\frac{Nd\log T}{\Delta^2}\right) which is larger than our regret upper bound of O\\!\left(\max\left\\{ \frac{d\log T}{\Delta^2}, \max_j \frac{Nd\\,\pi_i(j)\log T}{\Delta^2} \right\\}\right). This challenge does not arise in either standard linear bandits or tabular ETGS.

Second, for the setting with indifference, beyond the existing arm-proposing mechanism, we introduce a new pure-exploration algorithm, termed CEWI. This mechanism removes the reliance of ETGS on strict preferences for generating a stable matching from another perspective. Once the players’ preferences have been sufficiently explored, CEWI automatically identifies a stable matching and thereby avoids becoming trapped in prolonged exploration. This method also achieves better statistical efficiency.

Third, the tabular arm-proposing algorithm of [3] enjoys substantially better computational efficiency, which motivates us to adapt it to the contextual linear setting. Although replacing the least-sampled-arm criterion with a maximum-variance criterion may appear conceptually natural, this modification creates a new and nontrivial challenge in the regret analysis. In the tabular setting, selecting the least-sampled arm ensures that, within each phase, the numbers of observations collected from any two candidate arms differ by at most one. Consequently, a suboptimal arm cannot be selected excessively often during a single phase. This balancing property no longer holds in contextual linear matching markets. In particular, an arm with low expected reward but high predictive variance may be repeatedly selected throughout a phase because it remains informative about an insufficiently explored direction in the feature space. When the phase length is large, these repeated selections can accumulate substantial regret. Therefore, a direct phase-based extension of the arm-proposing method may incur prohibitively large regret.

To obtain sublinear regret in the contextual linear setting, we introduce an instant-communication mechanism that couples geometry-aware exploration in the linear feature space with decentralized multi-player coordination. By allowing updated preference estimates to be broadcast and acted upon within each phase, the proposed mechanism prevents outdated uncertainty estimates from repeatedly selecting low-reward arms and avoids the additional regret induced by exponentially increasing phase lengths.

Finally, we provide the first instance-dependent lower bound in contextual matching markets, which identifies the unavoidable contributions of both multi-player competition and linear preference learning, thereby establishing a benchmark for future algorithmic developments. Taken together, the technical contribution is not a mechanical combination of previous linear bandit literature, but the development and analysis of coordination, exploration, and communication mechanisms that make contextual generalization compatible with decentralized stable matching.

[1] Shiyun Lin, Simon Mauras, Vianney Perchet, and Nadav Merlis. Adaptive bandit algorithms for contextual matching markets. b.

[2] Satush Parikh, Soumya Basu, Avishek Ghosh, and Abishek Sankararaman. Competing bandits in decentralized contextual matching markets. arXiv preprint arXiv:2411.11794, 2024.

[3] Fang Kong, Jingqi Tang, Mingzhu Li, Pinyan Lu, John CS Lui, and Shuai Li. Bandit learning in matching markets with indifference. In The Thirteenth International Conference on Learning Representations, 2025.

Reviewer_2tx7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies linear matching markets with fixed arm features. It combines G-optimal exploration with Gale–Shapley under strict preferences and proposes enumeration-based and enumeration-free algorithms for markets with tied preferences.

Critical strengths

Combining G-optimal design with collision-free routing solves both informative exploration and coordination among competing players. This improves the regret bound with the dimension dd dependence of the leading regret term within the fixed-feature setting.

Critical weaknesses
  1. Arm features and players’ preference parameters are fixed. Prior contextual matching studies (referenced in this paper) allow contexts, preference rankings, and stable matchings to change over time. Improvements within the simpler environment should be distinguished from improvements over general contextual matching results.

  2. Theorem 5.1 shows the regret O(Nd2log⁡2T/Δ2)O(Nd^2 \log^2 T/\Delta^2), where the previous result is O(NKlog⁡T/Δ2)O(NK\log T / \Delta^2). The improvement holds when d2log⁡T<Kd^2\log T < K. Since the regret bound of Theorem 4.1 shows when TT goes infinity (or else, there is dependence with KK), the improvement of Theorem 5.1 does not make sense.

  3. The Theorem 4.1 uses the minimum gap among the N+1N+1 arms, but [1] use other definition of gap. I think comparing directly with relevant literature should be more clear.

[1] Shiyun Lin, Adaptive bandit algorithms for contextual matching markets, ICML 2026

Questions for authors

Linear contextual matching bandits are well-studied in previous literatures. Regardless of improvement over fixed-feature settings, the paper should be more clear what are the contributions and the improvements over previous studies. The paper’s claims of improvement seem to be inaccurate or insufficiently qualified, making confusion about the contributions, as described in the weaknesses. I would like authors to discuss this accurately.

5 comments

We thank reviewer 2tx7 for the valuable comments. Please find our response below.

1.Discussions of the improvements and contributions of our work.

We agree that building blocks such as G-optimal design, the explore-then-Gale--Shapley paradigm are established upon previous literature. Our contribution is not to claim novelty for these individual components. Rather, the main technical challenge is that they are not directly compatible in a decentralized contextual matching market. In particular, a direct replacement of the tabular estimators in ETGS by linear estimators neither yields our algorithms nor implies our regret guarantees.

First, standard G-optimal exploration assumes that informative actions can be selected according to an experimental design. In a decentralized matching market, however, the realized observations are jointly determined by the actions of multiple players, arm-side priorities, and collisions. Therefore, an individually optimal linear design may not be implementable simultaneously by all players. The exploration and coordination problems are intrinsically coupled: the algorithm must realize sufficiently informative design matrices for every player while respecting decentralized interaction constraints. Our routing mechanism in Algorithm 2 is introduced precisely to establish this joint feasibility, where we recognize that this routing problem can be transferred into a classical graph theory problem and its analysis proves that the desired linear-design coverage is retained despite multi-player interference. Without this routing algorithm, CETGS may suffer a worst case regret of O(Ndlog⁡TΔ2)O\left(\frac{Nd\log T}{\Delta^2}\right) which is larger than our regret upper bound of O\\!\left(\max\left\\{ \frac{d\log T}{\Delta^2}, \max_j \frac{Nd\\,\pi_i(j)\log T}{\Delta^2} \right\\}\right). This challenge does not arise in either standard linear bandits or tabular ETGS.

Second, for the setting with indifference, beyond the existing arm-proposing mechanism, we introduce a new pure-exploration algorithm, termed CEWI. This mechanism removes the reliance of ETGS on strict preferences for generating a stable matching from another perspective. Once the players’ preferences have been sufficiently explored, CEWI automatically identifies a stable matching and thereby avoids becoming trapped in prolonged exploration. This method also achieves better statistical efficiency.

Third, the tabular arm-proposing algorithm of [5] enjoys substantially better computational efficiency, which motivates us to adapt it to the contextual linear setting. Although replacing the least-sampled-arm criterion with a maximum-variance criterion may appear conceptually natural, this modification creates a new and nontrivial challenge in the regret analysis. In the tabular setting, selecting the least-sampled arm ensures that, within each phase, the numbers of observations collected from any two candidate arms differ by at most one. Consequently, a suboptimal arm cannot be selected excessively often during a single phase. This balancing property no longer holds in contextual linear matching markets. In particular, an arm with low expected reward but high predictive variance may be repeatedly selected throughout a phase because it remains informative about an insufficiently explored direction in the feature space. When the phase length is large, these repeated selections can accumulate substantial regret. Therefore, a direct phase-based extension of the arm-proposing method may incur prohibitively large regret. To obtain sublinear regret in the contextual linear setting, we introduce an instant-communication mechanism that couples geometry-aware exploration in the linear feature space with decentralized multi-player coordination. By allowing updated preference estimates to be broadcast and acted upon within each phase, the proposed mechanism prevents outdated uncertainty estimates from repeatedly selecting low-reward arms and avoids the additional regret induced by exponentially increasing phase lengths.

Finally, we provide the first instance-dependent lower bound in contextual matching markets, which identifies the unavoidable contributions of both multi-player competition and linear preference learning, thereby establishing a benchmark for future algorithmic developments. Taken together, the technical contribution is not a mechanical combination of previous linear bandit literature, but the development and analysis of coordination, exploration, and communication mechanisms that make contextual generalization compatible with decentralized stable matching.

2.Discussions of the improvements in Theorem 5.1.

We agree that d2log⁡T>Kd^2\log T > K may not hold uniformly as the horizon TT may scales. The motivation behind C-EAGS is to develop a computationally efficient algorithm that eliminates the dependence on KK in the leading regret term. Therefore, the regret bound of C-EAGS can be viewed as a complementary result to the existing O(NKlog⁡TΔ2)O\left(\frac{NK\log T}{\Delta^2}\right) bound, offering a different trade-off between KK, dd, and TT. In contrast, CEWI achieves a regret bound of O(Ndlog⁡TΔ2)O\left(\frac{Nd\log T}{\Delta^2}\right), which improves upon the existing bound when d≪Kd\ll K, albeit at the cost of higher computational complexity.

3.Comparison with relevant literature using the same gap.

We agree that comparing with literature using the same gap would provide clearer presentation. Our work is consistent with the line of tabular matching market works [1-5], where we introduced linear contexts to facilitate the learning process. In our work we compare our work with [6] and [7] to recognize the contributions of ours and theirs and to distinguish the different setting and results of these works. [6] used a probabilistic gap which is not directly comparable to ours and [7] assumed the spectrum assumption. In addition, both works did not extent to settings with ties without appriximations.

On the other hand, [1-3, 5] are directly comparable literature using the same definition of preference gaps introduced in Appendix A Table 1 with Δ1≥Δ4≥Δ3≥Δ2\Delta_1 \ge \Delta_4 \ge \Delta_3 \ge \Delta_2. In matching markets with strict preferences our CETGS achieves a player-optimal regret upper bound O\\!\left(\max\left\\{ \frac{d\log T}{\Delta_3^2}, \max_j \frac{Nd\\,\pi_i(j)\log T}{\Delta_3^2} \right\\}\right), comparing to the results in [1] $O \left( \frac{K \log T}{\Delta_2^2} \right) $, [3] $O \left( \frac{K \log T}{\Delta_3^2} \right) $ and [2] $O \left( \frac{N^2 \log T}{\Delta_4^2} + \frac{K \log T}{\Delta_4} \right) $, our CETGS uses the gap no smaller than [1] and [3] while eliminating the dependence of KK in the regret leading term incurred by [1-3]. Under the indifference setting, all work used Δ2\Delta_2 (non-zero). Our CEWI achieves an upper bound of O(Ndlog⁡TΔ22)O \left( \frac{Nd \log T}{\Delta_2^2} \right) which improves the result O(NKlog⁡TΔ22)O \left( \frac{NK \log T}{\Delta_2^2} \right) in [5] as d≪Kd \ll K. In addition, we provide a computation-efficient algorithm C-EAGS which achieves a regret upper bound of O(Nd2log⁡2TΔ22)O \left( \frac{Nd^2 \log^2 T}{\Delta_2^2} \right) which is also independent from KK and complements with the upper bound in [5]. We provide the full comparison of related works in Appendix A Table 1.

[1] Yirui Zhang, Siwei Wang, and Zhixuan Fang. Matching in multi-arm bandit with collision. Advances in Neural Information Processing Systems, 35:9552–9563, 2022

[2] Fang Kong, Zilong Wang, and Shuai Li. Improved analysis for bandit learning in matching markets. Advances in Neural Information Processing Systems, 37:91904–91929, 2024.

[3] Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching markets. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1512–1522. SIAM, 2023.

[4] Lydia T Liu, Feng Ruan, Horia Mania, and Michael I Jordan. Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1–34, 2021.

[5] Fang Kong, Jingqi Tang, Mingzhu Li, Pinyan Lu, John CS Lui, and Shuai Li. Bandit learning in matching markets with indifference. In The Thirteenth International Conference on Learning Representations, 2025.

[6] Shiyun Lin, Simon Mauras, Vianney Perchet, and Nadav Merlis. Adaptive bandit algorithms for contextual matching markets. b.

[7] Satush Parikh, Soumya Basu, Avishek Ghosh, and Abishek Sankararaman. Competing bandits in decentralized contextual matching markets. arXiv preprint arXiv:2411.11794, 2024.

Thank you for the explanation. I appreciate the technical challenges, and I do not question that the proposed algorithms make a contribution in the setting studied by the paper. Explaining why the proposed algorithms are technically nontrivial clarifies the contribution within the paper’s setting.

However, I remain concerned about how the term “contextual” is used to position the contribution. This paper studies a stationary, fixed-feature subclass, whereas the prior contextual matching work ([6,7] from Reply 2) considers changing contexts that can alter players’ rankings and the stable matching.

If this difference is why the authors consider the results not directly comparable, then the paper should not present its results as a general improvement over "contextual matching bandits". It should explicitly scope its contribution to decentralized matching with fixed linear arm features and leave the future work on changing-context settings. Without this clarification, the unqualified framing may lead readers to infer that the paper addresses the broader changing-context problem, which it does not study.

This issue is central, and is written in Weakness 1. I am concerned that the Reply has not adequately addressed it. Since this clarification affects how the paper’s contribution and novelty should be assessed, I remain hesitant to support acceptance.

Reviewer_Jqv2OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies bandit learning in two-sided matching markets under a linear contextual model. Each arm has a known feature vector, and each player’s reward is the inner product of the arm’s features with an unknown preference vector. The authors propose CETGS for strict preferences, a decentralized explore-then-Gale-Shapley algorithm. It uses a G-optimal design to choose which arms to sample and an edge-coloring routing scheme to schedule exploration without collisions. They propose CEWI for market indifference, which enumerates semi-stable matchings and is exponential-time, and C-EAGS, a computationally efficient arm-proposing Linear-UCB variant with instant communication. A lower bound and experiments against tabular and contextual baselines are also provided.

Overall: The paper makes a natural and useful extension of matching-market bandits to the contextual setting, and the G-optimal design plus edge-coloring routing is a clean combination. However, the K-independence claims rest on treating sizeable K-dependent terms as lower order, the lower bound does not certify tightness, and the experiments do not test the large-K regime that motivates the work.

Critical strengths

(a) Combining G-optimal design with König’s edge-coloring theorem to schedule collision-free exploration is elegant. It completes the required sampling in the minimum number of global time slots, and the design reduces exploration to at most d(d+1)/2 arms instead of all K.

(b) The framework handles both strict preferences and indifference. It recovers the existing tabular guarantees (ETGS and AE-AGS) as special cases when contexts are one-hot, which is a nice sanity check. The variance-based arm selection in C-EAGS is a sensible generalization of the “fewest samples” heuristic in the tabular case.

Critical weaknesses

(i) K-independence is a bit overstated. The full bounds contain an NK index-phase term, and CEWI and C-EAGS also carry a 2NK^2 communication term. In the large markets the paper targets, K may be comparable to T or polynomially large, so these terms are not negligible and can dominate the d log T/(Delta^2) term.

(ii) The lower bound does not establish tightness. It uses gap1, while the upper bounds use gap3 (strict) or gap2 (indifference), so the two are not directly comparable. The d log T/Delta term in the lower bound still leaves a 1/Delta gap compared to the upper bound term of d log T/(Delta^2).

(iii) The experiments do not match the initial motivation in the abstract. All experiments use d = 2 and very small N (up to 9). For instance, where K is large under indifference, and none where d is moderately large.

(iv) The model assumes fixed, known, exactly realizable linear features, known arm-side preferences, and synchronized decentralized communication through deliberate non-proposals and collisions.

Questions for authors

(1) How does the regret behave when K grows with T, or when K is in the tens of thousands? Can the index phase and the O(NK*K) communication be reduced, for example by communicating only within the support of the design or within the current active arm set?

(2) Can the lower bound be stated under the same gap definition as the upper bound, with delta allowed to vary freely? Is the extra d log T factor of C-EAGS over CEWI (d^2 log^2 T versus d log T) inherent to enumeration-free algorithms, or an artifact of the analysis?

(3) How robust is CETGS to misspecification, i.e., when rewards are only approximately linear in the features?

5 comments

We thank reviewer Jqv2 for the valuable comments.

Please find our response below.

1.Clarification of the KK-independence statement.

Our result is primarily intended to characterize the horizon- and gap-dependent learning complexity. In particular, the regret bounds take the form O(max⁡{dlog⁡TΔ2, max⁡jNd πi(j)log⁡TΔ2})+O(NK)O(\max\lbrace \frac{d\log T}{\Delta^2},\ \max_{j}\frac{Nd\,\pi_i(j)\log T}{\Delta^2}\rbrace)+O(NK), O(Ndlog⁡TΔ2)+O(NK2)O(\frac{Nd\log T}{\Delta^2})+O(NK^2) and O(Nd2log⁡2TΔ2)+O(NK2)O(\frac{Nd^2\log^2 T}{\Delta^2})+O(NK^2) where the dependence on KK is additive and does not multiply either log⁡T\log T or 1/Δ21/\Delta^2. Therefore, under the standard asymptotic regime in which the market size is fixed and the horizon TT grows, the first term determines the leading dependence on TT.

Importantly, the additive KK term does not arise from estimating the unknown linear preference parameter. Instead, it is incurred by the coordination and information-sharing procedure required in the general decentralized multi-player market, where each player does not directly observe the preferences or observations of the other players. A term of this form also appears in regret bounds for tabular matching markets, where it is typically treated as a lower-order contribution. This distinction is supported by our centralized-market result: when a central server can coordinate the players and aggregate their information, the additional information-sharing procedure is unnecessary, and the corresponding KK-dependent term is eliminated.

Our result shows that the dependence on KK can be separated from the leading statistical learning terms O(max⁡{dlog⁡TΔ2, max⁡jNd πi(j)log⁡TΔ2})O(\max\lbrace \frac{d\log T}{\Delta^2},\ \max_{j}\frac{Nd\,\pi_i(j)\log T}{\Delta^2}\rbrace), O(Ndlog⁡TΔ2)O(\frac{Nd\log T}{\Delta^2}) and O(Nd2log⁡2TΔ2)O(\frac{Nd^2\log^2 T}{\Delta^2}). Further reducing the dependence on KK is primarily a question of designing more communication-efficient multi-player coordination mechanisms, rather than improving the underlying learning algorithm.

2.Discussions of the lower bound.

We establish the lower bound to characterize the learning difficulty of contextual matching. Our results can cover the tabular lower bound Ω(max⁡{Nlog⁡TΔ2,Klog⁡TΔ})\Omega(\max\{\frac{N\log T}{\Delta^2},\frac{K\log T}{\Delta}\}) by [8] which also uses gap1\text{gap}_1. According to Table 1 we have gap1≥gap4≥gap3≥gap2\text{gap}_1 \ge \text{gap}_4 \ge \text{gap}_3 \ge \text{gap}_2, therefore the gap used in the lower bound is larger than the upper bounds (gap3\text{gap}_3 and gap2\text{gap}_2). Notice that in the tabular case the state-of-the-art upper bounds are O(Klog⁡TΔ2)O(\frac{K\log T}{\Delta^2}) and O(N2log⁡TΔ2+Klog⁡TΔ)O(\frac{N^2\log T}{\Delta^2}+\frac{K\log T}{\Delta}) which also did not match the lower bound. We will try to close the gap in future works.

3.Additional experiments on larger markets.

We provide additional experiments on larger markets below. We would like to clarify that the scale of our previous experiments was limited not by the computational complexity of our algorithms, but by the evaluation of stable regret. Specifically, computing μi,mi=min⁡m∈Mμi,mi\mu_{i,m_i} = \min_{m \in \mathcal{M}} \mu_{i,m_i}, the minimum reward player ii can obtain across all stable matchings, requires enumerating all possible matchings, which incurs exponential computational cost and becomes infeasible as NN and KK increase. To address this issue, we developed an alternative approach based on linear programming that avoids exhaustive enumeration, enabling us to evaluate our algorithms on larger markets. In the following tables, MCR denotes maximum cumulative regret and PPU denotes player-pessimal regret.

Table1: Performance with N=10N=10, d=2d=2, T=100000T = 100000, Δ=0.15\Delta = 0.15 and varying KK.

KKAlgorithmMCRPPU
15C-EAGS1,846.5116,342.00
15AE-AGS4,616.8164,375.00
15P-ETC17,230.8099,974.00
15C-ETC4,196.2442,000.00
20C-EAGS3,969.9128,504.00
20AE-AGS14,486.9196,818.00
20P-ETC17,216.01100,000.00
20C-ETC12,836.0560,000.00
25C-EAGS2,489.7020,750.00
25AE-AGS16,072.5598,185.00
25P-ETC21,353.67100,000.00
25C-ETC22,241.8275,000.00
30C-EAGS3,455.4620,881.00
30AE-AGS18,603.3699,809.00
30P-ETC17,444.47100,000.00
30C-ETC22,475.2690,000.00

Table 2: Performance with N=20N=20, d=2d=2, T=100000T = 100000, Δ=0.15\Delta = 0.15 and varying KK.

KKAlgorithmMCRPPU
25C-EAGS7,468.3162,282.00
25AE-AGS9,200.8999,092.00
25P-ETC15,312.83100,000.00
25C-ETC8,827.0575,000.00
30C-EAGS7,056.8023,764.00
30AE-AGS9,601.0698,153.00
30P-ETC16,113.40100,000.00
30C-ETC14,660.0790,000.00
35C-EAGS9,065.0334,835.00
35AE-AGS15,109.8399,756.00
35P-ETC17,290.33100,000.00
35C-ETC27,163.03100,000.00
40C-EAGS12,495.2371,308.00
40AE-AGS14,333.7999,866.00
40P-ETC17,539.63100,000.00
40C-ETC14,646.14100,000.00

Table 3: Performance with N=10N=10, K=20K=20, T=100000T = 100000, Δ=0.15\Delta = 0.15 and varying dd.

ddAlgorithmMCRPPU
2C-EAGS3,969.9128,504.00
2AE-AGS14,486.9196,818.00
2P-ETC17,216.01100,000.00
2C-ETC12,836.0560,000.00
3C-EAGS2,692.9918,168.00
3AE-AGS10,307.2775,550.00
3P-ETC17,586.76100,000.00
3C-ETC12,239.8660,000.00
4C-EAGS3,289.4324,908.00
4AE-AGS8,149.1081,896.00
4P-ETC16,208.4799,988.00
4C-ETC6,327.7054,000.00
5C-EAGS5,986.0445,363.00
5AE-AGS6,493.7984,402.00
5P-ETC15,870.6699,988.00
5C-ETC6,477.5754,000.00

From Table 1, 2 and 3 we can see that our C-EAGS suffers the least maximum cumulative regret and player-pessimal unstability among all market settings. For example, When N=10N = 10, K=20K = 20, d=2d = 2, Δ=0.15\Delta = 0.15, T=100000T = 100000, our C-EAGS suffers a maximum cumulative regret and player-pessimal unstability smaller than the second-best algorithm C-ETC by 69.07% and 52.49% respectively. These results show the efficiency and effectiveness of our C-EAGS.

4.Discussions of the problem setting.

In our work, we study bandit learning in matching markets with one-sided unknown preference following previous works [1-4]. The fixed context is an extension to the tabular setting where each context can be seen as one-hot vectors, our results in Theorem 4.1 and Theorem 5.1 cover the results in the tabular case. The known, exactly realizable linear features are standard assumptions in contextual matching literature [6-7]. In addition, we follow the decentralized communication of [5] to mitigate the drawback of the absence of a central server.

5.Discussions of improvements of the index phase and communication.

We thank reviewer Jqv2 for noting that there might be other ways of more efficient index phase and communication. In our work, we follow the decentralized index phase and communication of [5]. The main challenge in reducing index phase and communication costs is that each player only has access to its own local information. Therefore, players can only infer other players' preferences and indexes by observing their arm selections during the respective phases. This will result in a worst case regret of O(NK2)O(NK^2) when players have to share their full preference through the learning process.

6. Explanation of the extra dlog⁡Td\log T factor of C-EAGS.

The extra dlog⁡Td\log T factor of C-EAGS compared to CEWI is an artifact of the analysis. As in Eq. (20), we use the inequality

∑t=1TI(max⁡j∈Ai∖Ei∥Cj∥Vi,t−1−1>Δ4βt)⋅(Δ4βt)2≤∑t=1T(1∧max⁡aj∈Ai,t∥Ci,j∥Vi,t−1−12).\sum_{t=1}^{T} \mathbb{I}\left(\max_{j\in\mathcal{A}_i\setminus\mathcal{E}_i} \lVert C_j\rVert_{V_{i,t-1}^{-1}} > \frac{\Delta}{4\sqrt{\beta_t}}\right) \cdot \left(\frac{\Delta}{4\sqrt{\beta_t}}\right)^2 \leq \sum_{t=1}^{T} \left(1\wedge \max_{a_j\in\mathcal{A}_{i,t}} \lVert C_{i,j}\rVert_{V_{i,t-1}^{-1}}^2\right).

where

βt=λM+2log⁡1δ+dlog⁡(dλ+tL2dλ).\sqrt{\beta_t} = \sqrt{\lambda}M + \sqrt{2\log\frac{1}{\delta} + d\log\left(\frac{d\lambda+tL^2}{d\lambda}\right)}.

The resulting βt\beta_t term introduces one dlog⁡Td\log T factor, and

∑t=1T(1∧max⁡aj∈Ai,t∥Ci,j∥Vi,t−1−12)≤2log⁡det⁡(Vi,T)det⁡(λI)≤2dlog⁡(1+TL2λd).\sum_{t=1}^{T} \left(1\wedge \max_{a_j\in\mathcal{A}_{i,t}} \lVert C_{i,j}\rVert_{V_{i,t-1}^{-1}}^2\right) \leq 2\log\frac{\det(V_{i,T})}{\det(\lambda I)} \leq 2d\log\left(1+\frac{TL^2}{\lambda d}\right).

accounts for the other.

7.Discussions of linear bandits with misspecification.

In our work, we focus on incorporating contextual linear bandits to the matching market setting, aiming to resolve the KK-dependence on the regret leading term in markets with strict preferences and indifference. Hence, linear bandits with misspecification is beyond our scope of investigation. We would like to reserve this interesting topic for future work.

[1] Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log⁡2(t)\log^2(t) regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pp. 705–715. PMLR, 2021.

[2] Fang Kong, Zilong Wang, and Shuai Li. Improved analysis for bandit learning in matching markets. Advances in Neural Information Processing Systems, 37:91904–91929, 2024.

[3] Fang Kong, Junming Yin, and Shuai Li. Thompson sampling for bandit learning in matching markets. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, pp. 3164–3170. International Joint Conferences on Artificial Intelligence Organization, 2022.

[4] Lydia T Liu, Feng Ruan, Horia Mania, and Michael I Jordan. Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1–34, 2021.

[5] Fang Kong, Jingqi Tang, Mingzhu Li, Pinyan Lu, John CS Lui, and Shuai Li. Bandit learning in matching markets with indifference. In The Thirteenth International Conference on Learning Representations, 2025.

[6] Shiyun Lin, Simon Mauras, Vianney Perchet, and Nadav Merlis. Adaptive bandit algorithms for contextual matching markets. b.

[7] Satush Parikh, Soumya Basu, Avishek Ghosh, and Abishek Sankararaman. Competing bandits in decentralized contextual matching markets. arXiv preprint arXiv:2411.11794, 2024.

[8] Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference on Artificial Intelligence and Statistics, pp. 1252–1260. PMLR, 2021.

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

Related papers

Discussion (0)

Sign in to comment.