- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 2(+1)
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies the two-sided matching markets with unknown preferences when preference ties are allowed, i.e. one can not differentiate the value difference of two arms. This is particularly challenging since many prior works prove that the regret upper bound is inverse of value gap, so the regret can be infinity if the value gap is zero. This paper studies the aggregate stable regret, and proves the regret upper bound on two cases: (1) when the value gap is zero, i.e. ties are allowed, (2) when the value gap is positive. The paper also shows a problem lower bound that matches the upper bound.
Critical strengths
- The paper proposes an algorithm named ACTL and proves its regret upper bound, and shows that the regret matches the lower bound under a specific market family.
Critical weaknesses
-
The current form of the paper is extremely badly written. There are a lot of weird terms without any explanations, e.g., certificate, core-tail, pilot, validation engine, policy-uniform. I have zero idea what these terms mean. Also, when I read Contribution 1 (Line 85-86), I do not learn anything about the contribution, and there are many such paragraphs. What's worse, the paper first introduces ACTL in Line 73, but before that, the authors uses this acronym in Line 69 and Line 71. Given its current form, I find it very difficult to evaluate the quality of the paper.
-
It's unclear what the core contribution the paper is compared to previous tie-safe literature, e.g., Kong et al., 2025. While Table 1 presents a comparison of the settings and theoretical guarantees, it does not show which algorithm has smaller regret bounds. The ACTL algorithm heavily combines UCB with GS algorithm, which is similar to many previous literature.
Questions for authors
-
Can you explain every terminology when you first use them? These terminology do not seem to be common in this field. Also, a reader will easily misunderstand that Aggregate Core-Tail Learning (ACTL) is a problem setting when they read the abstract, but it turns out to be the name of the algorithm.
-
How do I read Figure 1 to compare your method against Kong et. al. 2025? Does your regret upper bound improve upon them? If so, you should highlight the improvement.
10 comments
Response to Reviewer CDX5 (Part 2/3)
Weakness 2 and Question 2: comparison with Kong et al. (2025).
Figure 1 of the submission (Figure 2 in the revision) was not intended as a comparison with prior work; it illustrates how the two terms of arise in the lower bound, and the caption now says so (L303–304). The comparison appears in a new paragraph of the introduction (L96–101) and in Table 1, which has a new column for the aggregate coefficient of . Below we first compare how the two algorithms sample, and then why the bounds differ.
How the two algorithms sample. Kong et al. assume that arms know their true rankings, and their algorithm fundamentally relies on this one-sided preference knowledge. In AE-AGS (their Section 4 and Algorithm 2), arms propose in a Gale–Shapley procedure. Among the arms currently proposing to her, a player discards those that her confidence intervals show to be worse, and accepts the least-sampled of the remaining ones. Exploration thus happens inside the proposal and matching process. Our algorithm ACTL learns both sides from rewards and schedules two validation actions explicitly (Section 5.1, L374–377). Core validation exploration rotates the players over the arms of a reference matching. An outside exploration moves one player to one of the outside arms while every other player keeps her reference partner. This second action changes the cost of a sample: an exploration costs only the loss of the moved player.
Both bounds on the same scale. Kong et al. bound the number of unstable rounds through , the smallest positive player-side gap, which gives per player (their Theorem 4.1 and Appendix B). An unstable round costs at most in total positive-part regret, so the same argument gives for the quantity we bound. In contrast, our Theorem 3 establishes an regret. When the smallest gap is on the player side, , so
and our leading coefficient is never larger up to constants, although our learner must also learn the arms' preferences. It can be much smaller in two ways. First, the core term has no factor , and each tail edge costs rather than . Second, can stay fixed while the smallest gap tends to zero. Part 3 explains which components of ACTL produce each term.
Example. In Appendix B.2, is fixed while a gap on one player's list shrinks. Their gap falls from to , so their leading coefficient grows about -fold, while is unchanged.
Measured regret experiments. Appendix B.9 (Table 10) compares the algorithms at finite horizons, with their constants and with the true arm preferences given to AE-AGS. On the three markets generated by their random-market protocol, the mean total regret of AE-AGS is – times that of ACTL-Practical.
Response to Reviewer CDX5 (Part 3/3)
On "UCB combined with GS": what each component does.
We agree that this rule is standard (L89–90). In ACTL, standard UCB–GS is used solely as a fallback exploitation rule once validation targets are fulfilled and to propose candidates for early commitment (paragraph "Fallback and commitment", L404–408 and L432–435). Crucially, exploratory validation is governed by ACTL's dedicated schedule, not by optimistic GS proposals. Standard UCB–GS computes a whole matching from optimistic scores, so trying one edge can also change the partners of other players. An outside exploration of ACTL instead keeps every other player at her reference partner (L376–377). This gives the proof a concrete condition: when the reference matching is stable, only the moved player can incur positive-part regret during an outside probe.
Two accounts give (proof sketch, L462–473).
- Core. There are rotations. Each round samples core edges in parallel at total loss at most , and each rotation is played times. This gives .
- Tail. Once the pilot is accurate and resolves the relevant margin, the reference matching is stable, and each outside edge is explored around it. If the player's shortfall is , each exploration costs , and the edge needs only explorations, because differences below never need to be resolved. The product is at most per edge; over the outside edges this gives the tail term. ACTL sets these targets from estimates, (paragraph "Sample targets", L378–388), and the sketch shows that they stay within constant factors of the ideal ones (L479–481).
The diagnostic tail experiment (Appendix B.3) tests this allocation directly: replacing the shortfall-dependent targets with uniform ones changes the fitted exponent in from to and raises tail regret by – times.
Keeping the account when (L475–490). Here no matching can be certified, and is unknown. Preserve refines the validation targets step by step and keeps every sample, since targets only grow. The fallback loss before the critical candidates are found enters the additive term, because the discovery time appears only through . Thus the core–tail separation determines the form of the leading term, and Preserve with the fallback analysis extends it to zero-certificate markets with an unknown margin. Standard UCB–GS lacks the single-player loss condition above, so this argument does not apply to it.
What is new relative to this line of work.
- The guarantees in Table 1 cover exact ties or two-sided learning, but not both. We cover both, including markets with .
- We prove matching lower bounds, up to universal constants, for the two-sided model.
- The rate depends on the margin rather than the global gap; neither the leading term nor depends on .
We hope that these revisions make the paper easier to evaluate, and we would welcome any further suggestions.
Response to Reviewer CDX5 (Part 1/3)
We thank the reviewer for the careful reading and candid assessment of our presentation. We agree that the submission used several terms before explaining them and did not clearly compare our bounds with Kong et al. (2025). We have revised the paper accordingly; substantive additions are highlighted in blue, and line numbers below refer to the revised PDF.
Clarification on the summary: Certificate Margin Δ vs. Preference Gaps.
The summary interprets our two cases as whether the preference gap is zero (ties allowed, risking infinite regret) or positive (no ties). We clarify that our two cases are not partitioned by whether ties exist or whether preference gaps are zero:
Thus, regret complexity is governed by local resistance to deviations (Δ and Δpres) rather than the finest preference differences (Δmin).
Weakness 1 and Question 1: terminology and readability.
Every technical term is now defined at first use, and Appendix A adds a glossary (Table 3). The terms noted by the reviewer are introduced as follows:
Further readability revisions: