acceptodds
Under review as a conference paper at ICLR 2027

Tie-Safe Stable Learning for Two-Sided Unknown Matching Markets

Abstract

This paper characterizes, up to universal constants, the class-wise asymptotic logarithmic regret of two-sided matching markets with unknown preferences and possible exact ties. Under aggregate regret against the coordinate-wise lowest player payoffs among weakly stable matchings, learning is governed by comparisons that certify stability or rule out unstable outcomes, rather than complete preference recovery. A signed certificate view isolates two complementary structural margins. The certificate margin measures how strongly some stable matching rejects every deviation, while, when , the preservation margin measures the smallest blocking strength of any unstable matching. For players and arms, both regimes obey the same core–tail complexity law , where the two terms correspond to resolving core comparisons and screening outside arms. Upper and policy-uniform lower bounds match, establishing the sharp class-wise rate , with when and at the zero-certificate boundary. Neither the leading logarithmic term nor the horizon-independent remainder depends on the global minimum positive preference gap. Aggregate Core–Tail Learning (ACTL) attains both guarantees without knowing either margin, the tie pattern, or the underlying regime. A communication-aware decentralized variant preserves the same class-wise order over connected bounded-bandwidth local networks when communication consumes physical time.

Primary area:
learning theory
Keywords:
multi-armed bandits, matching markets, stable matching

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_CDX5OpenReview ↗
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
  1. 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
  1. 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.

  2. 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
  1. 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.

  2. 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
AuthorsOpenReview ↗

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 Δ\Delta 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:

  1. Ties do not inherently cause infinite regret: Prior matching bandit works under indifference (e.g., Kong et al., 2025) already handle exact ties with finite logarithmic regret parameterized by the smallest positive preference gap Δmin⁡\Delta_{\min}.
  2. The two cases are governed by the certificate margin Δ\Delta, not preference gaps (Contributions 1–2): Stability learning does not require differentiating every arm's value; it only requires certifying that for every proposed deviation, at least one endpoint rejects it.
    • Δ>0\Delta > 0 (Positive certificate margin): Some stable matching rejects every deviation with margin at least Δ\Delta at a rejecting endpoint. Crucially, such markets can contain arbitrary exact ties elsewhere, provided those ties do not obstruct deviation rejection.
    • Δ=0\Delta = 0 (Zero rejection margin): Every stable matching has at least one deviation with zero rejection margin—e.g., a player is indifferent between her partner and a deviating arm that strictly prefers her—even if positive preference gaps elsewhere are large.

Thus, regret complexity is governed by local resistance to deviations (Δ\Delta and Δpres\Delta_{\mathrm{pres}}) rather than the finest preference differences (Δmin⁡\Delta_{\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:

  • Certificate (L53–55). This concept underpins our first contribution. For a matching WW, the signed certificate g(W)g(W) is the smallest rejection margin over all deviations (the minimum extent to which at least one endpoint rejects a deviating pair). It is negative iff some pair blocks WW, so WW is weakly stable iff g(W)≥0g(W)\ge 0. The certificate margin is Δ=max⁡Wg(W)\Delta=\max_W g(W) (illustrated in the new Figure 1).
  • Core and tail (L67–70). For a fixed stable matching, the core is the N2N^2 edges between players and the NN matched arms; the tail is the N(K−N)N(K-N) edges to the remaining outside arms, matching the two terms of Ψ(h)=N2/h2+N(K−N)/h\Psi(h)=N^2/h^2+N(K-N)/h.
  • Pilot (L82–84). The initial phase that samples every edge ⌈log⁡(eT)⌉\lceil\log(eT)\rceil times and fixes a reference matching.
  • Validation engine. Removed. We now say validation, which samples the core by rotating players over the reference arms and the tail by moving one player at a time to an outside arm (L84–86; Section 5.1, L374–377).
  • Policy-uniform (L78–80). The lower-bound constant and horizon threshold do not depend on the policy, which may even know the hard family.

Further readability revisions:

  • ACTL. The abstract now states "We propose an algorithm, Aggregate Core–Tail Learning (ACTL)" (L28), and the introduction expands the acronym at first use (L76), fixing the premature uses at L69/L71 of the submission.
  • Contributions (L103–123). Each bullet now begins with what we do and states one concrete result; the fourth item ("Loss-based charging") states the mechanism separating our bound from prior ones (see Part 2).
  • Other terms & consistent wording. "Tie-safe" (L47–48), edge (L38), blocking strength (L63–65), margin class (L77–78), LC-ACTL (L92), and fallback rounds (L404–408; Table 3) are defined at first use, and appendix role names are removed from Section 4. We reserve "baseline" for compared methods, writing "benchmark" for βi\beta_i and "reference matching" for WcW_c, and replace "regime/branch" with "case", "preference type", or "mode".
  • Section 5 reorganization. We have restructured Section 5 to make the algorithm significantly easier to follow. Specifically, a new diagram (Figure 3 in the revision) outlines the complete workflow of ACTL. Together with the revised exposition, this workflow enables readers to clearly trace the algorithmic execution, understand the core–tail exploration mechanism, and see how it yields the optimal matching regret bound. It also highlights key structural distinctions from standard UCB–GS.
AuthorsOpenReview ↗

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 Ψ\Psi 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 log⁡T\log T. 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 NN arms of a reference matching. An outside exploration moves one player to one of the K−NK-N 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 ΔK\Delta_{\mathrm{K}}, the smallest positive player-side gap, which gives O(NKlog⁡T/ΔK2)O(NK\log T/\Delta_{\mathrm{K}}^2) per player (their Theorem 4.1 and Appendix B). An unstable round costs at most NN in total positive-part regret, so the same argument gives O(N2Klog⁡T/ΔK2)O(N^2K\log T/\Delta_{\mathrm{K}}^2) for the quantity we bound. In contrast, our Theorem 3 establishes an O((N2/h2+N(K−N)/h)log⁡T)O((N^2/h^2+N(K-N)/h)\log T) regret. When the smallest gap is on the player side, ΔK=Δmin⁡≤h\Delta_{\mathrm{K}}=\Delta_{\min}\le h, so
Ψ(h)≤N2ΔK2+N(K−N)ΔK≤N2KΔK2,\Psi(h)\le\frac{N^2}{\Delta_{\mathrm{K}}^2}+\frac{N(K-N)}{\Delta_{\mathrm{K}}}\le\frac{N^2K}{\Delta_{\mathrm{K}}^2},
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 KK, and each tail edge costs 1/h1/h rather than 1/h21/h^2. Second, hh 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, h=Δ=0.1h=\Delta=0.1 is fixed while a gap on one player's list shrinks. Their gap ΔK\Delta_{\mathrm{K}} falls from 0.03990.0399 to 0.00050.0005, so their leading coefficient grows about 6,3606{,}360-fold, while Ψ(h)\Psi(h) 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 11.111.1–23.523.5 times that of ACTL-Practical.

AuthorsOpenReview ↗

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 Ψ(h)\Psi(h) (proof sketch, L462–473).

  • Core. There are NN rotations. Each round samples NN core edges in parallel at total loss at most NN, and each rotation is played O(log⁡T/h2)O(\log T/h^2) times. This gives O(N2log⁡T/h2)O(N^2\log T/h^2).
  • 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 ss, each exploration costs ss, and the edge needs only O(log⁡T/max⁡{h,s}2)O(\log T/\max\lbrace h,s\rbrace^2) explorations, because differences below hh never need to be resolved. The product is at most O(log⁡T/h)O(\log T/h) per edge; over the N(K−N)N(K-N) outside edges this gives the tail term. ACTL sets these targets from estimates, qi,a=⌈1024τ/max⁡{h~,s~i,a}2⌉q_{i,a}=\lceil1024\tau/\max\lbrace \tilde h,\tilde s_{i,a}\rbrace^2\rceil (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 hh from −1.09-1.09 to −0.30-0.30 and raises tail regret by 1.41.4–3.93.9 times.

Keeping the account when Δ=0\Delta=0 (L475–490). Here no matching can be certified, and h=Δpresh=\Delta_{\mathrm{pres}} 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 log⁡(KN)=Nlog⁡K\log(K^N)=N\log K. 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.

  1. The guarantees in Table 1 cover exact ties or two-sided learning, but not both. We cover both, including markets with Δ=0\Delta=0.
  2. We prove matching lower bounds, up to universal constants, for the two-sided model.
  3. The rate depends on the margin hh rather than the global gap; neither the leading term nor L⋆\mathcal L_\star depends on Δmin⁡\Delta_{\min}.

We hope that these revisions make the paper easier to evaluate, and we would welcome any further suggestions.

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

This paper characterizes the asymptotic logarithmic regret of two-sided matching markets where the preferences of both sides are unknown and exact ties are allowed. Since a player-optimal weakly stable matching need not exist under indifference, the regret is measured against the coordinate-wise lowest weakly stable payoff of each participant. The authors introduce a signed stability certificate g(W)g(W) together with two complementary margins: the certificate margin Δ\Delta and the preservation margin Δpres\Delta_{\text{pres}}. It also shows that learning only requires those comparisons that certify stability or rule out unstable outcomes, rather than complete preference recovery. Both regimes obey the same core tail complexity Ψ(h)=N2/h2+N(K−N)/h\Psi(h)=N^2/h^2+N(K-N)/h, and matching policy-uniform lower bounds and adaptive upper bounds establish the sharp rate Θ(Ψ(h)log⁡T)\Theta(\Psi(h)\log T), which does not depend on the global minimum gap Δmin⁡\Delta_{\min}. A single regime-adaptive algorithm attains both rates without knowing either margin or the tie pattern, and a communication-aware variant preserves the same order on connected bounded-bandwidth local networks. Experiments on synthetic families validate the predicted scalings.

Critical strengths
  1. The policy-uniform lower bounds and the adaptive upper bound match up to universal constants in both margin classes, even against policies that know the hard family. The resulting rate is interpretable: N2/h2N^2/h^2 corresponds to resolving core comparisons at constant loss per test, while N(K−N)/hN(K-N)/h corresponds to screening outside arms with shortfall-adaptive probes.

  2. The signed certificate and the Δ\Delta / Δpres\Delta_{\text{pres}} dichotomy explain clearly why Δmin⁡\Delta_{\min} is irrelevant and why a second margin is necessary at Δ=0\Delta=0. Proposition 1 further makes Δpres\Delta_{\text{pres}} an operational quantity.

  3. Monotone-only target updates, never-reset edge counts, and a single-candidate iterator with O(NK)O(NK) work per round and O(Nlog⁡K)O(N\log K)-bit state (Prop. 3) together handle the unknown scale, the combinatorial explosion of the matching space, and the unknown witness-discovery time.

Critical weaknesses
  1. The remainder is large and its regime of validity is unexplored. L⋆L^\star contains 1/Δ41/\Delta^4 and 1/Δpres41/\Delta_{\text{pres}}^4, and the Δ>0\Delta>0 branch also depends on Δpres\Delta_{\text{pres}}. At moderate Δ\Delta it is likely to dominate Ψ(h)log⁡T\Psi(h)\log T for any practical TT, yet the paper never states when the leading term becomes operative.

  2. The experiments do not test the specified algorithm. ACTL-Practical recalibrates the pilot factor, ε\varepsilon, the UCB bonus, and most strikingly the target constants, from 10241024 in Section E.5 to 0.06250.0625. The results therefore validate the structural mechanism rather than Theorem 3 as stated.

  3. All instances are the paper's own lower-bound constructions plus random strict markets; there are no general random tie markets beyond the constructed 2×22\times 2 module, no larger NN (only N≤7N \leq 7), and no comparison on tied instances with prior tie-aware baselines such as Kong et al. (2025) [1] (even when adapted with empirical or oracle arm-side preferences). Table 4 also reads like a horse race against author-implemented baselines that optimize a different criterion at a horizon where their certification phases barely trigger.

Questions for authors
  1. Could you give explicit constants, or a table of the horizon TT at which Ψ(h)log⁡T\Psi(h)\log T overtakes L⋆L^\star, for example at N=5N=5, K=10K=10, Δ=0.05\Delta=0.05?

  2. Is the target constant 10241024 merely conservative, or is the specified algorithm effectively vacuous at T≤220T\le 2^{20}? Would it be possible to report a run with the specified constants?

  3. Could you add random tie markets, larger NN, and a comparison with Kong et al. (2025) (e.g., under plug-in or known arm preferences)?

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

4 comments
AuthorsOpenReview ↗

Response to Reviewer D7S1 (Part 1/3)

We thank the reviewer for the concrete requests. We now provide the requested crossover calculation, report runs with the specified theoretical constants, and add comprehensive evaluations on random-tie markets, larger markets, and head-to-head comparisons with Kong et al. (2025). We also clarify that the same ACTL policy provides an all-horizon safety guarantee alongside sharp class-wise asymptotic scaling. These theoretical bounds complement our empirical evidence. All references refer to the revised manuscript.

Weakness 1 and Question 1: size of the remainder and when the leading term becomes operative.

1. All-horizon finite-time logarithmic guarantee.

We first emphasize a crucial structural property of our policy: ACTL does not need to wait for any asymptotic crossover to achieve a rigorous logarithmic regret guarantee.

Specifically, Theorem 3 and Appendix F.11, Eq. (26), simultaneously establish an all-horizon finite-time safety bound for the exact same ACTL policy:

ERPΣ(T)≤min⁡{NT,CsafeN2KBTδsafe2,Csharp[Ψ(h⋆)log⁡(eT)+L⋆]},\mathbb E R_P^\Sigma(T)\le\min\left\lbrace NT, \frac{C_{\mathrm{safe}}N^2KB_T}{\delta_{\mathrm{safe}}^2}, C_{\mathrm{sharp}}[\Psi(h_\star)\log(eT)+\mathcal L_\star] \right\rbrace,

where BT=log⁡(8NK(T+1)5)B_T=\log(8NK(T+1)^5) and constants are universal. When Δ>0\Delta>0, h⋆=Δh_\star=\Delta and δsafe=min⁡{Δ,Δpres}\delta_{\mathrm{safe}}=\min\lbrace \Delta,\Delta_{\mathrm{pres}}\rbrace; when Δ=0\Delta=0, both equal Δpres\Delta_{\mathrm{pres}}. Likewise, Equation (4) bounds per-participant regret by min⁡{T,CsafeNKBT/δsafe2}\min\lbrace T,C_{\mathrm{safe}}NKB_T/\delta_{\mathrm{safe}}^2\rbrace across all horizons.

This safety branch is fully operative from T=1T=1, including during unresolved-pilot horizons, without requiring margin knowledge or algorithmic switching: validation is strictly controlled by sample targets, and unstable fallback rounds are amortized against insufficiently sampled edges. Total regret is rigorously logarithmic across all practical horizons under the same ACTL specification.

2. The requested crossover calculation.

With the finite-time safety guarantee established, we address the reviewer's specific question regarding the point T×T_\times where the sharp leading term Ψ(h⋆)log⁡(eT)\Psi(h_\star)\log(eT) overtakes the displayed conservative remainder L⋆\mathcal L_\star.

For N=5N=5, K=10K=10, and Δ=Δpres=0.05\Delta=\Delta_{\mathrm{pres}}=0.05, the shared universal constant CC cancels in the ratio log⁡(eT×)=L⋆/Ψ(Δ)\log(eT_\times)=\mathcal L_\star/\Psi(\Delta). Assuming Δpres=0.05\Delta_{\mathrm{pres}}=0.05 (which enters the remainder), we have Ψ(Δ)=10,500\Psi(\Delta)=10{,}500 and L⋆=80,000,000(1+log⁡1000)≈6.33×108\mathcal L_\star=80{,}000{,}000(1+\log1000)\approx6.33\times10^8. This yields:

log⁡(eT×)≈60,250(or log⁡10T×≈26,166).\log(eT_\times) \approx 60{,}250 \quad (\text{or } \log_{10}T_\times \approx 26{,}166).

3. What this crossover signifies.

As the calculation shows, the refined leading term does not dominate the conservative remainder at practical horizons in this setting. However, as is common in finite-time concentration analyses for multi-agent bandits, worst-case union-bound envelopes overstate the empirical onset horizon by orders of magnitude: in direct simulations with the unscaled theoretical constant 10241024 (Appendix B.8, Table 9; see Part 2), ACTL completes all validation targets within T≈2×105T\approx 2\times 10^5 rounds and plays 100% stable matchings thereafter. Theoretically, the crossover reflects an artifact of comparing loose martingale union bounds rather than the operational lifespan of ACTL:

  • Crossover between bound terms vs. onset of no-regret: The crossover solely identifies when the refined minimax coefficient Ψ(h⋆)\Psi(h_\star) supersedes the worst-case remainder envelope; it does not indicate when logarithmic regret begins (which is guaranteed immediately by the safety bound above).
  • The sharp branch's theoretical role: The sharp branch exists to establish the optimal class-wise asymptotic scaling Ψ(h)=N2/h2+N(K−N)/h\Psi(h)=N^2/h^2+N(K-N)/h, matching our policy-uniform lower bounds up to universal constants.
  • The h⋆−4h_\star^{-4} dependency in L⋆\mathcal L_\star accounts for unresolved pilots under frozen-pilot concentration (discussed in Appendix F.12), not an unavoidable learning cost.

In summary, ACTL provides immediate finite-time safety across all horizons via Eq. (26), while Theorem 3 guarantees that its asymptotic rate matches the minimax lower bound.

AuthorsOpenReview ↗

Response to Reviewer D7S1 (Part 2/3)

Weakness 2 and Question 2: are the specified constants vacuous?

Conservatism vs. Practical Scaling. The theoretical constant 10241024 ensures that confidence radii remain sufficiently tight under worst-case martingales; it was not tuned for empirical brevity.

To evaluate ACTL transparently across regimes:

  1. ACTL refers strictly to the theoretical specification covered by Theorem 3.
  2. ACTL-Practical preserves the complete algorithmic architecture (pilot, mode selection, core rotations, shortfall-adaptive tail probes, commitment tests, and UCB-GS fallback) while rescaling exploration constants to practical magnitudes—a standard practice in bandit deployments.

Evaluating the specified ACTL (Appendix B.8, Table 9): We simulated ACTL as specified up to T=220T=2^{20} (and T=222T=2^{22} for N=5N=5, K=10K=10):

  • Target completion: Because 4ε≥14\varepsilon\ge1, ACTL enters PRESERVE with targets ⌈1024bt⌉\lceil1024 b_t\rceil. Measured completion rounds match target counts almost exactly (e.g., round 200,677200{,}677 vs. predicted 200,675200{,}675 for N=K=3N=K=3).
  • Post-validation stability: Across tested markets with Δ=0\Delta=0, all 3.0×1073.0\times10^7 subsequent fallback rounds are played at weakly stable matchings, empirically confirming the stability mechanism.
  • Safe commitment: All 50 commitments were strictly stable (zero commitments when Δ=0\Delta=0). In an expanded sweep of 16,00016{,}000 runs (T≤2×105T\le2\times10^5), all 6,3856{,}385 commitments were stable.
  • Cost: Regret under theoretical constants is 32–598x higher than ACTL-Practical, with 96–100% incurred during conservative validation.

Ablation of constants (Table 7): Restoring the theoretical target constant in ACTL-Practical increases regret 21- to 181-fold, while the exploration bonus accounts for a 3.6- to 15-fold increase. Pilot length and radius scale have minor effects. Crucially, the diagnostic scaling experiments in Appendix B.3–B.4 verify that the fitted scaling exponents (−2.22-2.22 for core, −1.09-1.09 for tail) tightly match the theoretical h−2h^{-2} and h−1h^{-1} dependencies, proving that the core-tail mechanism governs empirical behavior rather than hyperparameter tuning.

AuthorsOpenReview ↗

Response to Reviewer D7S1 (Part 3/3)

Weakness 3 and Question 3: coverage and baselines.

  • Random-tie markets (Tables 6 and 8): We added extensive benchmarks on randomly generated markets with exact ties across four verified strata: strict (Δ>0.01\Delta>0.01), ties with Δ>0\Delta>0, zero-certificate (Δ=0\Delta=0), and near-boundary (0<Δ≤0.0010<\Delta\le0.001), with 800 paired runs per stratum.
  • Market dimension scaling (Table 6): Core scaling experiments are now extended up to N=13N=13. At d=0.2d=0.2, ACTL-Practical incurs mean regrets of 1,1091{,}109, 3,5483{,}548, and 6,9356{,}935 for N=5,9,13N=5,9,13, exhibiting a fitted empirical exponent of 1.91.9 against the theoretical N2N^2 scaling.
  • Comparison with Kong et al. (2025) (Appendix B.9, Table 10): We benchmarked AE-AGS over 14 market cells with 100 paired runs each (9,800 runs total), testing both their oracle-arm setting and a plug-in adaptation. Against oracle AE-AGS, ACTL-Practical achieves lower mean regret in 9 of 14 cells (11–24x lower on their own random-market benchmarks). Against the plug-in version with matched exploration bonus, ACTL-Practical achieves lower regret in 11 cells (3 inconclusive).
  • Baselines at longer horizons (Appendix B.10, Table 11): We extended Table 5 up to T=220T=2^{20}. At these horizons the identification-based methods (Basu-SS, E-PSM) pay large certification costs. ACTL-Practical plays a weakly stable matching in 86–100% of rounds at T=220T=2^{20}; UCB–GS with the matched bonus has the lowest mean regret in five of six settings, and ACTL-Practical has the lowest on the zero module.

Where does the design help in practice?

Standard UCB-GS acts optimistically by computing full matchings, which performs well in benign random markets where deviations rarely propagate. However, in structured markets where probing an unverified pair triggers a chain of displacements, uncoordinated exploration causes severe collateral losses.

Appendix B.12 tests this explicitly in a noisy zero-certificate cascade market (N=18N=18, K=34K=34, Δpres=1/16\Delta_{\mathrm{pres}}=1/16, T=105T=10^5):

  • ACTL-Practical restricts candidate probes to one-player moves or two-player swaps around an empirical reference matching, preventing full-chain disruption.
  • Over 12 paired noisy seeds, this mechanism cuts direct tail regret by 69% (paired 95% CI [68%, 71%]) and aggregate regret by 36% ([34%, 39%]) compared to matched-bonus UCB-GS (and cuts them by 75% and 48% versus UCB-GS with the same pilot).
  • Disabling the local checks in an ablation at K=19K=19 causes aggregate regret to surge from 59,75459{,}754 to 166,951166{,}951, directly validating that localizing exploration loss provides significant practical protection in cascading environments.

We also delineate the boundaries of this effect: in unconstrained wide markets (K=50K=50), aggregate regret is comparable to plain UCB-GS (+3.3%, CI includes equality), and lower shortfall regret involves a modest trade-off in the stable-round fraction (41% vs. 61% at K=34K=34).

Conclusion.

The revision couples a mathematically tight minimax characterization with broad empirical benchmarking, concrete crossover computations, and controlled diagnostic evidence of localized exploration, clearly distinguishing theoretical worst-case safety from practical deployment regimes. We thank the reviewer for prompting these comprehensive additions.

I would like to thank the authors for the response. I will keep my positive score.

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

The paper studies repeated matching with unknown preferences on both sides and exact ties. It measures aggregate positive-part player regret against each player’s lowest payoff across weakly stable matchings. The paper establishes matching class-wise asymptotic logarithmic bounds with Ψ(h)=N2/h2+N(K−N)/h\Psi(h)=N^2/h^2+N(K-N)/h, and analyzes a paid local-communication extension.

Critical strengths
  1. The core–tail law separates constant-loss core tests from shortfall-adaptive outside-arm exploration. This paper proposed matching upper and lower bounds, this forms a substantial theoretical contribution.

  2. ACTL retains samples, enlarges validation targets, and uses fallback play rather than equating candidate enumeration with execution.

Critical weaknesses
  1. The finite-sample and welfare scope of the sharp class-wise rate needs greater prominence.

  2. The connection to practical finite-horizon learning remains limited.

Questions for authors
  1. Could the paper more directly distinguish the instance-wise-asymptotic-then-supremum statement for positive-certificate classes from a uniform finite-time statement?

  2. In zero-certificate instances, how do regret and candidate-discovery progress evolve before the relevant witnesses are encountered?

  3. How much does each change from the theoretical constants to ACTL-Practical contribute?

  4. Could you report pilot misclassification, erroneous commitment, and stable-round fractions?

3 comments
AuthorsOpenReview ↗

Response to Reviewer siDN (Part 1/3)

We thank the reviewer for the insightful comments on the core–tail law, the analytical mechanisms, and the need to clarify the scope of our theoretical and empirical guarantees. Our revision makes the all-horizon finite-time guarantee explicit, elucidates the offline nature of candidate screening before witness discovery, and provides extensive calibration and stability diagnostics. The central takeaway is that the same ACTL policy provides an immediate, all-horizon logarithmic safety guarantee alongside sharp class-wise asymptotic scaling, while empirical performance under practical constants is validated through targeted structural ablations. All references refer to the revised manuscript.

Weakness 1: finite-sample and welfare scope.

Core–tail mechanism. ACTL allocates exploration by charging each action its true welfare loss: core rotations test all core edges in parallel at constant total regret per round, whereas outside-arm probes move only one player and scale their sample targets inversely with her shortfall. This decouples exploration costs, establishing the core–tail law:

Ψ(h)=N2/h2+N(K−N)/h.\Psi(h)=N^2/h^2+N(K-N)/h.

Stability does not require complete ranking recovery: deviation testing can be certified locally, yielding an inverse-linear (1/h1/h) rather than quadratic (1/h21/h^2) rate on outside arms. Section 5.2 now details this mechanism before the formal proofs.

All-horizon finite-time guarantee. Theorem 3 and Appendix F.11, Eq. (26), apply simultaneously to ACTL, establishing that for every horizon TT:

ERPΣ(T)≤min⁡{NT,CsafeN2KBTδsafe2,Csharp[Ψ(h⋆)log⁡(eT)+L⋆]},\mathbb{E} R_P^\Sigma(T)\le\min\left\lbrace NT, \frac{C_{\mathrm{safe}}N^2KB_T}{\delta_{\mathrm{safe}}^2}, C_{\mathrm{sharp}}[\Psi(h_\star)\log(eT)+\mathcal{L}_\star] \right\rbrace,

where BT=log⁡(8NK(T+1)5)B_T=\log(8NK(T+1)^5) and constants are universal. When Δ>0\Delta>0, h⋆=Δh_\star=\Delta and δsafe=min⁡{Δ,Δpres}\delta_{\mathrm{safe}}=\min\lbrace \Delta,\Delta_{\mathrm{pres}}\rbrace; when Δ=0\Delta=0, both equal Δpres\Delta_{\mathrm{pres}}. Equation (4) similarly bounds per-participant regret by min⁡{T,CsafeNKBT/δsafe2}\min\lbrace T,C_{\mathrm{safe}}NKB_T/\delta_{\mathrm{safe}}^2\rbrace; summing over the NN players yields the aggregate bound with the same universal constant.

ACTL does not need to wait for any asymptotic crossover to achieve a logarithmic guarantee. The safety bound applies immediately from T=1T=1—even before the pilot resolves the margin—without requiring margin knowledge or algorithmic switching: validation is strictly controlled by sample targets, and unstable fallback rounds are amortized against insufficiently sampled edges. The sharp branch then refines the asymptotic rate to the optimal minimax coefficient Ψ(h⋆)\Psi(h_\star).

The welfare benchmark is mathematically necessary. Under ties, a player-optimal weakly stable matching does not exist in general (Manlove, 2002). Our coordinate-wise benchmark βi\beta_i (the lowest payoff player ii receives across weakly stable matchings) is universally well-defined and requires no arbitrary selection rule.

Furthermore, Appendix I proves an impossibility barrier: without a known gap lower bound, achieving logarithmic indifferent regret on an exact-tie instance is fundamentally incompatible with simultaneously guaranteeing O(log⁡T/Δmin⁡2)O(\log T/\Delta_{\min}^2) player-optimal player regret and arm-pessimal arm regret on nearby strict instances. Hence, our benchmark βi\beta_i is not a compromised heuristic, but the canonical objective for two-sided learning under indifference. Every weakly stable matching achieves zero positive-part regret under this benchmark.

Question 1: asymptotic-then-supremum versus uniform finite time.

Section 5.3 now explicitly defines the scope and order of limits:

  • Positive-certificate classes (Δ≥h\Delta\ge h): We take lim sup⁡T→∞\limsup_{T\to\infty} on each fixed market before taking the supremum over the class, because lower-bounding Δ\Delta does not bound Δpres\Delta_{\mathrm{pres}}, which governs fallback exploration after an inaccurate pilot and enters L⋆\mathcal{L}_\star.
  • Zero-certificate class (Δ=0,Δpres≥h\Delta=0, \Delta_{\mathrm{pres}}\ge h): The condition Δpres≥h\Delta_{\mathrm{pres}}\ge h bounds the remainder L⋆\mathcal{L}_\star uniformly, so the supremum and the horizon limit can be exchanged.
  • Both margins bounded below (Δ≥h,Δpres≥h\Delta\ge h, \Delta_{\mathrm{pres}}\ge h): The finite-time bound is uniformly controlled across all markets:

sup⁡νEνRPΣ(T)≤min⁡{NT,CsafeN2KBTh2,CΨ(h)log⁡(eT)+CN2Kh4log⁡eNKh}.\sup _ {\nu}\mathbb E _ {\nu} R _ P^\Sigma(T) \le\min\left\lbrace NT, \frac{C _ {\mathrm{safe}}N^2KB _ T}{h^2}, C\Psi(h)\log(eT)+C\frac{N^2K}{h^4}\log\frac{eNK}{h} \right\rbrace.

AuthorsOpenReview ↗

Response to Reviewer siDN (Part 2/3)

Weakness 2: connection to practical finite-horizon learning.

Architecture preservation. ACTL-Practical preserves the entire algorithmic architecture—pilot, mode choice, validation rotations, shortfall-adaptive probes, doubling-snapshot updates, and UCB-GS fallback—while rescaling the theoretical martingale constants (e.g., target constant 1024) to empirical magnitudes, a standard practice in bandit deployments. The diagnostic scaling experiments (Appendix B.3–B.4) verify that the fitted scaling exponents (−2.22-2.22 for core, −1.09-1.09 for tail) tightly match the theoretical h−2h^{-2} and h−1h^{-1} laws, proving that the core–tail mechanisms govern empirical rates.

The role of validation as structural insurance. Why does formal validation appear conservative in benign random markets? In random markets without deceptive blocking structures, greedy exploration (plain UCB-GS) rarely triggers propagation chains, allowing it to perform well without explicit safeguards. However, validation serves as essential insurance against worst-case cascades.

To isolate this mechanism causally, Appendix B.12 tests a noisy zero-certificate cascade market (N=18N=18, K=34K=34, h=1/16h=1/16, T=105T=10^5), where exploring an unverified pair can trigger a chain of displacements:

  • Across 12 paired noisy seeds, a local-check variant of ACTL-Practical cuts direct tail regret by 69% (paired 95% CI [68%, 71%]) and aggregate regret by 36% ([34%, 39%]) compared to matched-bonus UCB-GS (and cuts them by 75% and 48% versus UCB-GS with the same pilot).
  • In an ablation at K=19K=19, disabling only the local checks causes aggregate regret to surge from 59,75459{,}754 to 166,951166{,}951.

This controlled diagnostic confirms the central design principle: isolating exploration loss prevents catastrophic cascade penalties.

AuthorsOpenReview ↗

Response to Reviewer siDN (Part 3/3)

Question 2: what happens before the relevant witnesses appear?

The analytical witnesses are at most N+1N+1 matchings (one attaining each βi\beta_i and one attaining −Δpres-\Delta_{\mathrm{pres}}), all visited within one enumeration pass (Lemma 21). Crucially, evaluating a candidate is an offline computation on frozen pilot data, not an instruction to play it. Sections 5.1–5.2 establish the three-stage guarantee under ε≤h/16\varepsilon\le h/16 and standard concentration:

  1. Validation is strictly bounded before discovery: Lemma 19 proves that h^≥7h/8\widehat h\ge7h/8 and β^i≥βi−ε\widehat\beta_i\ge\beta_i-\varepsilon, preventing oversized targets. Because cumulative counts are retained as targets grow, validation regret is pathwise bounded by O(Ψ(h)BT)O(\Psi(h)B_T) on every prefix.
  2. Unstable fallback is controlled via doubling snapshots: An unstable cache established before discovery must contain a played edge with confidence radius at least h/2h/2. Replaying it forces count doublings and cache refreshes (Lemmas 24–26). The candidate stream enters only through its logarithm (log⁡(KN)=Nlog⁡K\log(K^N)=N\log K), contributing solely to the horizon-independent remainder L⋆\mathcal L_\star.
  3. Weak stability holds after discovery: Once the witnesses are processed, completed targets resolve all comparisons of size hh, guaranteeing that every newly computed UCB-GS cache is weakly stable (Lemmas 22–23).

Empirical trajectories outpace conservative theory (Appendix B.11). In simulations on zero-module markets (N=K∈{5,7,9}N=K\in\lbrace 5,7,9\rbrace), substantial stability is established long before complete enumeration:

  • For N=9N=9, 72–77% of the final median regret is accrued by round 5×1045\times10^4, when only 13% of candidate matchings have been evaluated; after this point, unstable rounds become negligible.
  • While the empirical estimator h^\widehat h acts as a conservative upper envelope (plateauing near 0.23–0.30 rather than reaching hh), candidate screening successfully eliminates unstable matchings.
  • At N=K=7N=K=7, ACTL-Practical achieves 43–47% lower sample mean regret than matched-bonus UCB-GS across four margins.

Question 3: how much does each recalibration contribute?

Table 7 isolates each parameter's effect by varying one constant at a time in both directions across six market families (100 paired runs each):

  • Target constant (dominates): Restoring the theoretical target constant (10241024) in ACTL-Practical increases regret 21- to 181-fold; conversely, reducing only this constant in the theoretical ACTL cuts regret to 0.04–0.44 of its original magnitude.
  • Exploration bonus: Restoring the theoretical bonus constant raises practical regret 3.6- to 15-fold.
  • Pilot length & radius scale: These have minor effects, though restoring the pilot constant can raise regret by up to 51%.

This decomposition confirms that practical performance differences stem almost entirely from standard martingale concentration conservatism, while the core–tail structural mechanisms remain invariant.

Question 4: pilot misclassification, erroneous commitments, and stability.

Table 8 reports these diagnostics across 16 market settings:

  • Pilot mode selection: ACTL-Practical enters CERTIFY in 8–9% of zero-certificate runs due to empirical noise. Crucially, this misclassification is harmless: ACTL-Practical never commits to an unstable matching, and PRESERVE fallback continues to play stable matchings. The theoretical ACTL with specified constants never selects CERTIFY when Δ=0\Delta=0.
  • Commitment safety is 100%: Across all 16,00016{,}000 runs with specified constants at T≤2×105T\le2\times10^5, and all 50 runs in Table 9, every single commitment (6,435 in total) was strictly weakly stable, with zero commitments when Δ=0\Delta=0.
  • Stable-round fractions: Outside near-boundary strata, ACTL-Practical achieves 92–99.9% stable rounds. Near-boundary markets (Δ≤10−3\Delta\le10^{-3}) remain challenging for all methods, reflecting fundamental statistical separation limits.

Conclusion.

The revision provides a clean separation between mathematical guarantees and practical exploration dynamics: the theoretical ACTL provides universal all-horizon safety alongside optimal minimax scaling, while our empirical diagnostics confirm that isolating exploration loss provides concrete, structure-specific protection against market instability.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response: Summary of Changes in the Revised PDF

We thank all reviewers for their careful reading and constructive comments. We have uploaded a revised PDF. Substantive changes (new definitions, statements, paragraphs, and experiments) are shown in blue; consistent renaming of a term is not highlighted. The main text still fits in ten pages. The main changes are listed below, with the reviewers whose comments prompted them.

  1. Presentation and terminology (CDX5).
  • Every technical term is defined at its first use: certificate, core and tail, pilot, policy-uniform, tie-safe, margin class, and fallback rounds. Appendix A adds a glossary (Table 3).
  • The abstract introduces ACTL as our algorithm, and the introduction expands the name at its first use. The five Contributions each state one concrete result.
  • A small new Figure 1 in Section 3 shows the certificate values g(W)g(W) on a signed axis: stable matchings in [0,Δ][0,\Delta], unstable ones at or below −Δpres-\Delta_{\mathrm{pres}}, and why Δ=0\Delta=0 forces learning to rule out the unstable side.
  • "Baseline" now refers only to compared methods. We write "benchmark" for βi\beta_i, "reference matching" for WcW_c, and "case", "preference type", or "mode" in place of "regime" and "branch".
  1. Comparison with Kong et al. (2025) (CDX5, D7S1).
  • A new paragraph in the introduction ("Comparison with prior bounds") and a new column in Table 1 put the bounds on the same aggregate scale. When the smallest gap is on the player side, our leading coefficient Ψ(h)\Psi(h) is at most theirs up to constants. It is smaller when K>NK>N or when hh stays fixed while Δmin⁡→0\Delta_{\min}\to0. Our additive term is larger.
  • The caption of the lower-bound figure (Figure 1 in the submission, now Figure 2) now states that the figure illustrates the lower-bound mechanisms and is not a comparison with prior work.
  • Appendix B.2 reports the growth of their coefficient, measured by their player-side gap, on our gap-decoupling sweep.
  1. Section 5: algorithm and proof sketches (CDX5, siDN).
  • Section 5.1 is reorganized around a workflow figure (Figure 3). It defines the reference matching, the core, and the tail with a small example, gives the sample targets q0q_0 and qi,aq_{i,a} explicitly, and explains the motivation for Preserve before stating its updates. Algorithm 1 labels the four steps of each round. Implementation details remain in Appendix E.
  • The proof sketch of Theorem 3 shows where each term of Ψ(h)\Psi(h) comes from by charging each validation action its own loss. A second sketch explains why screening up to KNK^N candidates enters the regret only through log⁡(KN)=Nlog⁡K\log(K^N)=N\log K.
  • Section 5.4 explains when LC-ACTL communicates and what is played meanwhile, on a local network and in-band.
  1. Finite-horizon scope (D7S1, siDN).
  • After Theorem 3 we state the all-horizon bound ERPΣ(T)≤min⁡{NT,CN2KBT/δsafe2,CΨ(h⋆)log⁡(eT)+CL⋆}\mathbb E R_P^\Sigma(T)\le\min\lbrace NT, CN^2KB_T/\delta_{\mathrm{safe}}^2, C\Psi(h_\star)\log(eT)+C\mathcal L_\star\rbrace (Eq. (26), Appendix F.11).
  • New Appendix F.12 discusses when the pilot resolves the margin with the specified constants, why L⋆\mathcal L_\star contains h⋆−4h_\star^{-4} terms, and why the Δ>0\Delta>0 remainder depends on Δpres\Delta_{\mathrm{pres}}.
  1. New experiments (all reviewers). Appendix B is substantially extended; the main text now points to it after the Contributions.
  • B.7: from UCB–GS to ACTL-Practical (Tables 6–8). This section adds random markets with exact ties in four exactly enumerated strata, core markets up to N=13N=13, a one-constant ablation, and diagnostics on pilot mode, commitments, and stable rounds. At a matched exploration bonus, ACTL-Practical performs on par with UCB–GS.
  • B.8: the specified constants (Table 9). The validation targets are met at the predicted rounds, and all commitments are at stable matchings. Regret is 32–598 times that of ACTL-Practical at the tested horizons.
  • B.9: AE-AGS (Table 10). We compare with AE-AGS on 14 cells, under oracle and plug-in arm preferences.
  • B.10: published baselines at longer horizons (Table 11). Table 5 is rerun at T=218T=2^{18} and 2202^{20}. We also added an exact fallback for the super-stable subroutine; it never changes the subroutine's answer.
  • B.11: trajectories on the zero-certificate module (Figure 8, Table 12). These cover markets with up to 362,880362{,}880 matchings and show the behavior before all candidates have been screened.
  • B.12: a cascade market (Table 13). Here an unverified probe can displace several players, and ACTL-Practical limits this loss.

For the new runs in B.7 and B.9, the cells, seeds, and decision rules were fixed before any run. The responses to individual reviewers give the details.

AuthorsOpenReview ↗

General Response (follow-up): Summary of Readability & Clarity Revisions

We thank the reviewers for the follow-up feedback. In response to the concern that technical terminology still obscured the central insights in the main text, we have uploaded an updated PDF. Substantive follow-up revisions are highlighted in green (while Round 1 additions remain in blue). All theorems, algorithm specifications, and experimental results remain unchanged; the main text still fits strictly within 10 pages (pp. 1–10), with a new one-page proof roadmap added in Appendix F (p. 41).

The follow-up changes fall into four groups:

  1. Front-loaded core–tail intuition and plain-language framing (Abstract, p. 1, L11–31; Section 1, pp. 2–3, L70–117).

    • Rewrote the Abstract in plain words, explaining why core tests cost a constant (displacing other players) while outside-arm tests cost only the tested player's shortfall.
    • Added a dedicated Key idea: a combinatorial core and a bandit tail paragraph on page 2 (L70–77) presenting the Ψ(h)=N2/h2+N(K−N)/h\Psi(h) = N^2/h^2 + N(K-N)/h accounting intuitively before any algorithmic machinery.
    • Moved Comparison with prior bounds immediately after Key idea (p. 2, L79–85) and added a concrete numerical illustration against Kong et al. (2025) (N=5,K=10,h=ΔK=0.05N=5, K=10, h=\Delta_{\mathrm{K}}=0.05: coefficient 100,000 vs. 10,500), clarifying all three simultaneous gains beyond reducing O(NK)O(NK) to O(N(K−N))O(N(K-N)): (i) removing KK from the N2N^2 core term, (ii) improving the tail term from 1/h21/h^2 to 1/h1/h, and (iii) keeping hh fixed while Δmin⁡→0\Delta_{\min}\to 0—all while learning both sides' preferences.
    • Replaced the dense ACTL summary paragraph with a three-step plain-language walk-through (p. 2, L90–98) and tightened the Contributions bullets (pp. 2–3, L105–117).
  2. Removed opaque jargon from the main text (Sections 1–5, pp. 1–10).

    • Removed five technical labels from the main narrative—"policy-uniform", "margin class", "coordinate-wise benchmark", "strict linear extension", and "witness"—replacing each with a direct plain-language description (pp. 1–3, Section 2, Section 3, Section 4, and Section 5.2).
    • Removed the introduction's pointer to Appendix A's glossary so Table 3 serves strictly as an optional reference index rather than a prerequisite for reading the main text.
    • Added the operational takeaway of Proposition 1 (p. 5, L245–246) and stated upfront that the remainder of the paper uses only Δ\Delta and Δpres\Delta_{\mathrm{pres}} (p. 5, L247–248).
  3. Reorganized Section 5.1 and Theorem 3 proof sketches (pp. 7–10, L336–491).

    • Section 5.1 now opens by explicitly stating the three unknown quantities ACTL faces and the distinct roles of its three matchings—the core reference WcW_c, candidate ZZ, and cached fallback McacheM_{\mathrm{cache}} (p. 7, L336–342)—and writes out h~\tilde h and s~i,a\tilde s_{i,a} in both modes (p. 8, L378–381).
    • Added plain-language explanations for why the −4ε-4\varepsilon screening rule separates stable from unstable candidates (p. 8, L394–397), why the UCB–GS cache is refreshed only at a new snapshot or power of two in tt and held otherwise (p. 8, L399–403), and what TRY-COMMIT checks (pp. 8–9, L405–407, L432–434).
    • Rebuilt Theorem 3's proof sketches around the unifying zero-regret principle—a player who keeps a stable partner suffers zero regret (p. 9, L461–473)—explicitly contrasting the bandit tail (1/h1/h) with a displacing probe (1/h21/h^2), and clarified in steps (i)–(iii) why candidate screening when Δ=0\Delta = 0 takes rounds without costing samples and keeps waiting regret in the constant term via log⁡(KN)=Nlog⁡K\log(K^N) = N\log K (pp. 9–10, L475–491).
  4. New one-page visual proof roadmap for Theorem 3 (Appendix F, pp. 40–41, Figure 9).

    • Added a guiding summary at the opening of Appendix F (p. 40, L2131–2133) and a full-page schematic (Figure 9, p. 41, L2162–2211) tracing how the concentration, snapshot-doubling, validation, commitment, and pre-discovery/post-discovery fallback lemmas fit together, color-coding where every cost is charged: core (blue), tail (green), finite-time remainder L⋆\mathcal{L}_\star (orange), or zero (gray).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.