- 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 , where is the largest sampling probability. With tied preferences, the authors propose a computationally efficient algorithm which achieve 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
Reply 2
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.
Reply 1
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(Δ2NdlogT) 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.