Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates

Technical Summary: Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates

Problem Definition
This paper investigates the additive regret in the multi-secretary problem, defined as the gap between the expected reward of an optimal offline "prophet" (who observes all $T$ values before selecting at most $k$) and the expected reward of the optimal online policy. The performance is measured against the prophet benchmark, which selects the largest $k$ realized values.

The order of this regret depends critically on the local structure of the value distribution $F$. Prior literature established that for distributions with connected support and bounded densities (e.g., uniform), the regret is $O(\log T)$. However, for distributions with separated support intervals (gapped distributions), previous work by Besbes et al. (2024) and Jiang et al. (2025a) established an upper bound of $O((\log T)^2)$ for the case where the density is bounded away from zero near the gap (the $\beta=0$ case). It remained an open question whether this extra logarithmic factor was necessary or merely an artifact of the analysis techniques used to derive the upper bounds.

Methodology: Bellman Certificates
The authors introduce a unified framework based on Bellman certificates to derive tight lower bounds. Unlike previous approaches that relied on constructing specific "hard" instances and analyzing indistinguishability for arbitrary online policies, this method constructs explicit feasible solutions to a relaxation of the exact Bellman recursion for the regret.

The core of the methodology involves:

1. Recursion Decomposition: The paper derives a Bellman equation for the regret $B_s(c)$ (the gap at state $s, c$) by subtracting the online dynamic programming recursion from the offline prophet recursion.
2. Certificate Construction: A candidate regret function $B = (B_s(c))$ is constructed. To prove a lower bound, it suffices to show that $B$ satisfies a specific one-sided Bellman inequality (the "certificate inequality") across the state space, along with boundary conditions.
3. Comparison Principle: The authors prove that if a non-negative function $B$ satisfies the certificate inequality, then $B_T(k)$ is a lower bound on the true optimal regret. This converts the problem of finding a lower bound into the constructive problem of designing a feasible certificate.
4. Mechanism Identification: The certificate inequality decomposes the regret evolution into three terms:
   • Deterministic Drift ($M_s(c)$): The cost of transporting the certificate value through time and capacity.
   • Order-Statistic Jensen Term: A positive slack term arising from the convexity of the reward function relative to the distribution's shape.
   • Finite-Difference Perturbation: A term dependent on the spatial gradient of the certificate.

The framework isolates the mechanism of support gaps: in a gapped distribution, the "slack" (Jensen term) is generated only when the prophet's marginal order statistic fluctuates near the support edges, while the "penalty" (finite-difference term) is suppressed when the threshold lies in the empty gap. This separation allows for a larger feasible certificate.

Key Contributions and Results

1. Tight Lower Bound for Bounded-Density Gapped Distributions ($\beta=0$):
   The paper proves an $\Omega((\log T)^2)$ lower bound for the simplest gapped instance: a mixture of two separated uniform distributions. The bound holds at the critical capacity $k_T = \lfloor qT \rfloor$, where $q$ is the probability mass of the upper support.

   • Implication: This result confirms that the $O((\log T)^2)$ upper bounds previously derived for bounded-density gapped instances are tight. Consequently, the log-squared regret bound for network revenue management models with continuous, bounded-density rewards (Jiang et al., 2025a) cannot be improved in general.

2. Tight Lower Bound for Vanishing-Density Gapped Distributions ($\beta>0$):
   For gapped distributions where the density vanishes near the gap edges (characterized by an exponent $\beta > 0$), the paper proves a lower bound matching the upper bound of Besbes et al. (2024), which includes an additional logarithmic factor.

   • Regime: This result is established for capacities shifted from the critical capacity by a moderate deviation of order $\sqrt{T} \log T$.
   • Result: The regret grows as $\Omega(R_\beta(T) (\log T)^{(\beta+2)/(2(\beta+1))})$, matching the existing upper bounds.

3. Unified Framework:
   The paper provides a single analytical framework (Bellman certificates) that resolves the lower-bound questions for both bounded-density and vanishing-density gapped regimes, replacing disparate hard-instance constructions with a systematic certificate design.

Significance and Claims
The paper claims that the extra logarithmic factor in the regret for gapped distributions is necessary, not an artifact of analysis. Specifically:

• It resolves the open question of whether the $O((\log T)^2)$ bound for bounded-density gapped instances is tight in the single-resource multi-secretary setting.
• It demonstrates that the Bellman-certificate framework is a powerful tool for converting lower-bound problems into explicit construction problems, offering a structural alternative to policy-level indistinguishability arguments.
• The results clarify the fundamental limits of online resource allocation in the presence of distributional gaps, showing that even in the simplest single-resource case with uniform mixtures, the regret order is strictly higher than in the connected-support case.

The paper does not propose new algorithms or applications but focuses strictly on establishing theoretical limits (lower bounds) to characterize the inherent difficulty of the problem under specific distributional assumptions.