A Survey on Bandit Learning in Matching Markets

The strongest positive case is a high-multiplicity, cohort-based version of the paper’s stable-bandit problem. The paper is a survey, so it proves no new numbered computational theorem itself. Its two usable anchors are reported results from earlier work: Theorem 2, attributed to Kong et al. (2024), and Theorem 1, explicitly identified as Theorem 7 of Sankararaman et al. (2021).

My lead anchor is Theorem 2. The survey states that the adaptive online Gale–Shapley algorithm of Kong et al. (2024) achieves, for every player \(p_i\), player-optimal stable regret

\[ \operatorname{Reg}_i(T)\le O\!\left(\frac{N^2\log T}{\Delta^2}+\frac{K\log T}{\Delta}\right). \]

This is cited from Kong et al. (2024), not proved in the survey.

A natural regime is a large school-admissions or employment market. There may be millions of applicants and vacancies, but relatively few recurring applicant cohorts—say combinations of qualification, experience, location, and career objective—and relatively few school, employer, or position types. Thus \(N\) and \(K\) can be very large while the number of complete participant types \(\tau\) is moderate. Members of a player type have the same latent reward vector over arm types; members of an arm type have the same priority ordering over player types. This is exactly the kind of high-multiplicity regime in which a yearly cohort of near-identical graduates or students is a credible object.

I would define the following problem.

Cohort Player-Optimal Stable Bandit, or \(\mathrm{CPO\text{-}SB}_\infty\). An instance contains finite player types \(P\), arm types \(A\), rational player masses \(\rho_p\), rational arm capacities \(\kappa_a\), known arm priorities \(\succ_a\), a horizon \(H\), and a gap parameter \(\Delta\). The masses satisfy \(\sum_{p\in P}\rho_p\le\sum_{a\in A}\kappa_a\). A player type \(p\) has an unknown mean reward vector \(\theta_{p,\cdot}\in[0,1]^A\), shared by every member of that type. Its preference over arms is induced by \(\theta_{p,a}\). All rewards are \(1\)-subgaussian.

At round \(t\), a type-level policy chooses proposal masses \(q_{p,a}(t)\ge0\) with \(\sum_a q_{p,a}(t)=\rho_p\). Each arm type accepts up to capacity \(\kappa_a\), retaining the highest-priority proposed mass according to \(\succ_a\). Let \(x_{p,a}(t)\) be the accepted mass. Every accepted unit receives a noisy reward with mean \(\theta_{p,a}\). To prevent the continuum from becoming an accidental noiseless oracle, the information model must be explicit: a type coordinator may pool only a bounded number of sampled rewards from its cohort per round, and receives no information about other types except what the original matching feedback reveals.

For the true \(\theta\), let \(x^\star\) be the player-optimal stable mass matching, obtained by the mass version of deferred acceptance. A flow is stable when no positive amount of type \(p\) can be moved from an inferior assignment \(b\) to a preferred arm \(a\), either using unused capacity at \(a\) or displacing lower-priority mass there. The aggregate regret of a policy \(\pi\) is

\[ R^\pi(H)= \mathbb E\!\left[ \sum_{t=1}^{H}\sum_{p,a} \bigl(x^\star_{p,a}-x^\pi_{p,a}(t)\bigr)\theta_{p,a} \right]. \]

The computational problem is: given the finite rational description, \(H\), \(\Delta\), and the feedback convention, construct an anytime decentralized policy minimizing worst-case regret over all admissible \(\theta\), and determine the optimal dependence on \(\tau_P=|P|\), \(\tau_A=|A|\), masses, capacities, and \(\Delta\). A solution is an implementable policy and a regret guarantee; it is not merely the final stable flow.

I expect this to be Class A in the bounded-feedback cohort model. The adaptive Gale–Shapley structure survives aggregation: deferred acceptance operates on type masses, and the learning statistics involve only the finite set of type–arm pairs. The natural analogue of Theorem 2 should have a type-scale bound of the form

\[ O\!\left(\frac{\operatorname{poly}(\tau_P,\tau_A,\rho,\kappa)\log H}{\Delta^2} + \frac{\operatorname{poly}(\tau_P,\tau_A,\rho,\kappa)\log H}{\Delta}\right), \]

with the exact mass and capacity factors left to determine. The finite clone dictionary is straightforward: choose \(n\) clearing the denominators of \(\rho\) and \(\kappa\), replace type \(p\) by \(n\rho_p\) identical players and arm type \(a\) by \(n\kappa_a\) identical positions, and aggregate their individual matches. No preferences or outcomes have been fractionalized; only the population has been compressed.

The second, independently useful anchor is Theorem 1, which the survey labels “Theorem 7 in [Sankararaman et al., 2021].” It states, for the serial-dictatorship OSB setting,

\[ \operatorname{Reg}_i(T)\ge \max\!\left\{ \frac{(i-1)\log T}{\Delta^2}, \frac{K\log T}{\Delta} \right\}. \]

This too is cited, not proved by the survey.

Its continuous counterpart would be Mass-OSB Regret Frontier. The instance has player types \(p_1,\ldots,p_r\) with masses \(\rho_1,\ldots,\rho_r\), arm types with capacities, a common arm priority order \(p_1\succ p_2\succ\cdots\succ p_r\), and unknown type–arm reward means. Impose the OSB promise that each type’s optimal arm is compatible with the player-optimal stable mass matching. Proposal and acceptance work exactly as above.

For a designated type \(p_i\), define

\[ V_i(H;\rho,\kappa,\Delta) = \inf_{\pi} \sup_{\theta:\,\Delta(\theta)\ge\Delta} R_i^\pi(H;\theta), \]

where \(R_i^\pi\) is the regret of the mass of type \(p_i\) against its player-optimal stable assignment. The problem is to compute the optimal regret rate and an attaining or approximately attaining policy. In particular, one asks whether the discrete lower bound becomes a mass-sensitive bound with two terms: an exploration term depending on the number of arm types, and a contention term depending on the amount of higher-priority mass that can displace type \(p_i\) from its target arm.

I expect this also to be Class A, at least with finitely many types. Common priorities reduce deferred acceptance to a serial process, and exploration can be organized type by type. The continuous question is not whether the old formula survives literally: with mass capacities, the collision term should depend on quantities such as \(\rho_i\), \(\sum_{j<i}\rho_j\), and the relevant arm capacity. The interesting result would be an exact mass-sensitive frontier showing which part of the finite lower bound survives and which part disappears through type aggregation.

These mirrors cover only the paper’s stable-regret results: Theorem 2’s general decentralized player-optimal guarantee and Theorem 1’s serial-dictatorship lower bound. They do not claim to continuize the survey’s nonstationary, two-sided-unknown, incentive-compatible, adversarial, or contextual variants.

The weakest point is the information model. In the original paper, histories belong to named players. If infinitely many identical players all report their observations to a central learner, the learner may estimate a type’s reward vector almost instantly; if they never share information, the state becomes a distribution over individual histories rather than a finite type vector. Thus the bounded-feedback cohort model is an extension, not a purely direct replacement of \(N\) by masses. That objection is real. It does not destroy the mirror, because cohort-level learning is natural for platforms operating over repeated applicant or student classes, and the matching predicate, stability notion, arm priorities, and regret objective remain the authors’ own. But the observation-rate convention must be stated as part of the problem rather than hidden inside the word “continuum.”