Matching when worker types must be learned

A service platform may know which kinds of jobs are available while still learning the abilities of new workers. An assignment then has two effects: it produces a reward and supplies information that can improve later assignments. Limited job supply couples these decisions across workers. Sending one worker to a useful learning task consumes capacity that could have served someone else. Johari, Kamble and Kanoria study this interaction in a continuum market with a fixed worker lifetime and characterize the leading cost of learning as that lifetime grows (Matching While Learning, arXiv:1603.04549v7, §§3–5).

The question is whether a policy acting separately on each worker's history can learn efficiently while meeting shared capacity constraints. A reward-maximizing choice for one worker need not be the appropriate choice for the market. The benchmark therefore incorporates capacity scarcity, and the learning problem depends on the shadow prices of those capacities.

The market and its history-based decisions

There are finite nonempty sets $I$ of worker types and $J$ of job types. The worker proportions $\rho_i$ are positive and sum to one. A real job type $j$ has positive finite capacity $\mu_j$ in each period. A distinguished empty job $\kappa$ has unlimited capacity and represents leaving a worker unmatched. The known reward matrix $A$ gives the success probability $A(i,j)\in[0,1]$ of assigning type $i$ to job $j$. Its rows are distinct, and the empty job always gives zero reward. The individual worker's type is hidden.

Workers form a continuum of unit mass. Each lives for $N$ periods before independently regenerating with a newly sampled type. The system begins empty, with a cohort of mass $1/N$ entering in each of the first $N$ periods. A worker-history-only policy chooses a job distribution using that worker's previous jobs and binary outcomes, independently of other workers, identity and absolute time. The paper's exact law of large numbers gives deterministic history masses and hence an exact steady-state reward rate $W^N(\pi)$ (source, pp. 9–18).

The full-information benchmark $V^*$ maximizes $\sum_i\rho_i\sum_jx(i,j)A(i,j)$ over row-stochastic routing matrices satisfying all capacities. Its dual job prices are $p_j^*$. Generalized imbalance means that the total mass of no nonempty subset of worker types equals the total finite capacity of a subset of jobs. Under this condition the optimal job prices are unique, although the primal routing need not be unique.

Write $U(i)=\max_j(A(i,j)-p_j^*)$, and let $J(i)$ be the maximizing jobs. The strong alternatives to a label $i$ are the types $i'$ for which $J(i)\setminus J(i')$ is nonempty. For a job distribution $\alpha$, its learning cost is the expected loss in adjusted payoff, and its information rate is the least sampling-weighted Bernoulli KL divergence against those alternatives. Their optimal ratio is $C(i)$, with aggregate constant $C=\sum_i\rho_iC(i)$ (source, pp. 20–28).

The DEEM policy first explores, using uniform sampling when its maximum-posterior guess is uncertain and an optimal confirmation distribution when that guess passes a weaker confidence test. Once the required weak and strong tests pass, it freezes a type label and exploits using that label's row of a routing matrix. This matrix is constructed from exploration and labeling masses to satisfy the market's capacities.

Formalization targets

The goal is the complete Theorem 1 on page 28 of the pinned preprint. If $C>0$, every feasible sequence of worker-history-only policies satisfies

$$\liminf_{N\to\infty}\frac{N}{\log N}\bigl(V^*-W^N(\pi_N)\bigr)\ge C.$$

DEEM is feasible for every sufficiently large $N$ and satisfies the matching bound

$$\limsup_{N\to\infty}\frac{N}{\log N}\bigl(V^*-W^N(\mathrm{DEEM}_N)\bigr)\le C.$$

If $C=0$, DEEM is again eventually feasible, and a finite nonnegative market-dependent constant $K$ satisfies

$$\limsup_{N\to\infty}\frac{N}{\log\log N}\bigl(V^*-W^N(\mathrm{DEEM}_N)\bigr)\le K.$$

The supporting targets are Proposition 1 on the achievable routing polytope; Lemma 1 on transient feasibility and eventual steady state; Lemma 3 on paths to unused capacity; Proposition 3 on price uniqueness; Proposition 6's printed limsup lower bound; Lemmas 4–5 on likelihood crossings and downward passage expectations; Proposition 7 on relaxed regret; Proposition 4 on existence of exploitation routing; and Proposition 8 on DEEM's payoff. These are the source's numbered results, with their complete clauses (source, pp. 16–28 and 52–64).

What the result establishes

The same explicit constant appears in the universal lower bound and DEEM's upper bound. It identifies the leading efficiency loss of learning in this constrained market. The zero-constant regime has a distinct, smaller logarithmic scale, so retaining that clause distinguishes markets with different learning costs.

The formalization targets already have proofs claimed in the paper. They are open formal statements here, not completed machine-checked proofs. The definition layer supplies reusable finite-history probability formulas, capacity-constrained matching objects, extended information ratios, and stopping-time expectations. The formal development also makes source issues visible: the printed Proposition 6 uses limsup, while the goal requires liminf; the endpoint Bernoulli cases need treatment beyond the finite-log-increment arguments in the appendix. These findings are recorded separately and do not alter the targets.

Mathematical difficulties

Learning the type with high confidence is insufficient by itself. Errors have different consequences depending on which jobs a label permits, and a collection of individually attractive assignments may violate market capacities. The theorem controls both the exact leading regret and eventual feasibility. Singular Bernoulli rewards create infinite information values, and shared observations can correlate the likelihood walks. A formulation that assumes strictly interior rewards or independent walks would omit permitted cases.

Formalization scope

The namespace is MatchingWhileLearning.DEEM. Finite probability distributions and a general finite linear program are reused from published definitions. Paper-specific primitives remain real-valued, with no discretization of workers or capacities. Histories are stored newest-first; finite sums over their exact probabilities implement the paper's deterministic continuum profiles. This is the source's profile representation, not a separate construction of a Fubini extension.

KL and nonnegative stopping expectations use extended nonnegative reals, while scaled regret limits use extended reals. Empty strong-alternative sets have vacuous tests. Zero-information distributions are excluded from ratio minimization by an infinite objective, consistent with the source's example. The finite-hit expectation in Lemma 5 is zero only on paths where no hit occurs, as required by its indicator. The algorithms and optimization values are constructed from primitives; no regret guarantee or feasible exploitation matrix is supplied as an input assumption. The source's claimed attainment of the confirmation optimizers is an explicit conclusion wherever DEEM is used, and the optimal-value lower bound retains attainment of the minima defining the learning constants. This prevents a total-function fallback from changing the algorithm. A permitted endpoint example shows that the source's confirmation maximizer need not exist; the finding is recorded in INSIGHTS.yaml without adding a hypothesis or replacing a printed bound. Solvers are invited to prove or disprove the exact statements, including their boundary cases.

Selected references

• Ramesh Johari, Vijay Kamble and Yash Kanoria, Matching While Learning, preprint, 2020, arXiv:1603.04549v7. All statement numbers and pages refer to this version, whose PDF and printed page numbers agree.