Interviews Substitute for Reversibility: Two Regret Floors in Irreversible Matching Markets

Learning in two-sided matching markets has been studied almost exclusively under a quiet assumption: matches can be remade. Yet the matching decisions that matter most — hiring, residency, marriage — are absorbing: a wrong commitment cannot be unwound. We study what is learnable when the assumption is dropped. Two structural features govern everything: whether matches are *recoverable* or *absorbing*, and whether agents have a *safe information channel* — interviews, modeled as pre-commitment draws from a pair's true reward distribution that pay no reward and commit nothing. Our results fill in the irreversible half of a 2×2. Without interviews, irreversible matching is unlearnable: a coupling argument shows that any algorithm's pre-commitment behavior is identical across instances whose optimal matchings differ, so some instance forces binary stable regret at least T/2 — an impossibility, not a rate (Theorem 2). With k interviews per round, learnability returns at exactly Θ(σ² log T / (k·Δ_A²)), where Δ_A is the market's admissible gap; in the matching lower bound, the 1/T error demanded by an unrecoverable commitment is precisely what keeps the log T (Theorem 3). The recoverable cells are imported from the literature (Basu; Mirfakhar et al.). The dichotomy reads cleanly: *under recoverability interviews are an accelerator; under irreversibility they are a necessity* — a safe channel substitutes for the ability to undo, and widening it cheapens the floor linearly. A reproducible Rust artifact confirms all four cells, with Δ_A at once the theorem's parameter, the computed object, and the measured driver of regret.