Pith. sign in

REVIEW 2 minor 35 references

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

T0 review · 0 major / 2 minor · reviewed 2026-07-03 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For mixtures of two separated uniforms at critical capacity, the multi-secretary problem requires Omega((log T)^2) additive regret.

desk verdict The paper gives the first explicit Ω((log T)^2) lower bound for gapped multi-secretary instances via Bellman certificates, showing the extra log factor in prior upper bounds is necessary. read the letter →

arxiv 2607.02150 v1 pith:SXW4N6DU submitted 2026-07-02 cs.DS cs.LG

Jiawei Zhang This is my paper · ORCID
classification cs.DScs.LG
keywords multi-secretaryproblemadditiveregretsupportgapsBellmancertificateslowerboundsonlinealgorithmsprophetinequalities
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper shows that the extra logarithmic factor in regret upper bounds for the multi-secretary problem is necessary when value distributions have gaps in their support. It constructs an explicit lower bound of order (log T)^2 for the optimal online policy versus the offline prophet benchmark, using a mixture of two separated uniform distributions at the critical capacity. This matches known O((log T)^2) upper bounds and proves them tight even in the one-resource case. The argument relies on Bellman certificates as feasible solutions to a relaxed version of the dynamic programming recursion.

What carries the argument

Bellman certificates: feasible solutions to a relaxation of the exact Bellman recursion that convert lower bounds into explicit constructions and identify why support gaps permit larger regret.

What would settle it

An explicit computation of the optimal online policy's expected regret for the two-uniform mixture instance at sufficiently large T that yields o((log T)^2) would disprove the lower bound.

Watch

Extended reading notes

Core claim

For a mixture of two separated uniform distributions at the critical capacity, the optimal regret grows at least on the order of (log T)^2. The same framework also yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges.

Load-bearing premise

The model uses bounded-density distributions with support gaps and measures additive regret relative to the offline prophet reward in the standard multi-secretary setting.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper proves that the optimal additive regret in the multi-secretary problem is Ω((log T)^2) for a mixture of two separated uniform distributions at critical capacity. This is obtained by constructing an explicit Bellman certificate that is feasible for a relaxation of the exact Bellman recursion; the same framework yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges (appendix). The result shows that existing O((log T)^2) upper bounds for bounded-density gapped instances are tight even in the one-resource case.

Significance. If the certificate construction is valid, the result is significant: it closes the gap between upper and lower bounds for the gapped case, confirming that support gaps force the extra logarithmic factor relative to connected-support distributions. The Bellman-certificate framework is a clear strength—it converts the lower-bound argument into an explicit, verifiable object rather than an information-theoretic or minimax argument—and the paper directly matches the cited upper bounds for this canonical instance.

minor comments (2)
  1. The abstract states that the certificate 'converts lower bounds into explicit certificate constructions'; a short paragraph in the introduction summarizing the key algebraic steps of the construction (without full proof) would help readers assess feasibility before reaching the technical sections.
  2. Notation for the 'critical capacity' parameter should be introduced with an explicit formula (e.g., as a function of the two uniform supports) the first time it appears, rather than only in the instance definition.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the paper. The report accurately summarizes our contribution in establishing matching Ω((log T)^2) lower bounds for the multi-secretary problem under gapped distributions using explicit Bellman certificates, confirming the tightness of existing upper bounds even in the single-resource case.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper's central derivation constructs an explicit Bellman certificate as a feasible solution to a relaxation of the exact Bellman recursion for the specific two-uniform mixture instance, directly yielding the Ω((log T)^2) lower bound on additive regret relative to the offline prophet. This construction is presented as independent of the cited O((log T)^2) upper bounds and does not reduce any prediction or claim to a fitted input, self-definition, or load-bearing self-citation; the framework converts the certificate feasibility into the regret lower bound without circular reduction. The argument remains self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract supplies no information on free parameters, axioms, or invented entities; assessment is limited to the stated claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates." pith.science (2026). https://pith.science/paper/SXW4N6DU

@misc{pith2026260702150,
  author       = {Pith},
  title        = {Pith review of: Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SXW4N6DU}},
  note         = {Machine review of arXiv:2607.02150}
}
abstract

This paper studies additive regret in the multi-secretary problem, defined as the gap between the expected offline prophet reward and the reward of the best online policy. Prior work established \(O(\log T)\) regret for bounded-density distributions with connected support and \(O((\log T)^2)\) upper bounds for bounded-density distributions with support gaps. It was unknown whether the extra logarithmic factor is necessary even in the one-resource model. We prove that it is necessary. For a mixture of two separated uniform distributions at the critical capacity, the optimal regret grows at least on the order of \((\log T)^2\). Thus the existing \(O((\log T)^2)\) upper bounds for bounded-density gapped instances, including those implied by network revenue management models with continuous rewards, are tight in this simplest specialization. The same framework also yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges; this companion result is given in the appendix. The proofs use Bellman certificates: feasible solutions to a relaxation of the exact Bellman recursion. This framework converts lower bounds into explicit certificate constructions and identifies why support gaps permit larger regret.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    SIAM Journal on Computing 43(2):930--972

    Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing 43(2):930--972

    work page 2014

  2. [2]

    Stochastic Systems 9(3):231--260

    Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231--260

    work page 2019

  3. [3]

    Stochastic Systems 10(2):170--191

    Arlotto A, Xie X (2020) Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards. Stochastic Systems 10(2):170--191

    work page 2020

  4. [4]

    Management Science 71(6):4877--4894

    Banerjee S, Freund D (2024) Good prophets know when the end is near. Management Science 71(6):4877--4894

    work page 2024

  5. [5]

    Operations Research 72(5):2168--2189

    Balseiro SR, Besbes O, Pizarro D (2024) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Operations Research 72(5):2168--2189

    work page 2024

  6. [6]

    Operations Research 73(3):1273--1288

    Besbes O, Kanoria Y, Kumar A (2024) Dynamic resource allocation: Algorithmic design principles and spectrum of achievable performances. Operations Research 73(3):1273--1288

    work page 2024

  7. [7]

    Oxford University Press

    Boucheron S, Lugosi G, Massart P (2013) Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press

    work page 2013

  8. [8]

    Operations Research 73(4):2188--2203

    Bray RL (2024) Logarithmic regret in multisecretary and online linear programs with continuous valuations. Operations Research 73(4):2188--2203

    work page 2024

Show all 35 references
  1. [9]

    Management Science 66(7):2993--3009

    Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science 66(7):2993--3009

    2020

  2. [10]

    Proceedings of the 42nd ACM Symposium on Theory of Computing, 311--320

    Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proceedings of the 42nd ACM Symposium on Theory of Computing, 311--320

    2010

  3. [11]

    Operations Research 72(3):1124--1138

    Chen G, Li X, Ye Y (2024) An improved analysis of LP-based control for revenue management. Operations Research 72(3):1124--1138

    2024

  4. [12]

    arXiv preprint arXiv:2501.01716

    Chen Y, Wang W (2025) Beyond non-degeneracy: Revisiting certainty equivalent heuristic for online linear programming. arXiv preprint arXiv:2501.01716

    2025

  5. [13]

    Proceedings of the 2017 ACM Conference on Economics and Computation, 169--186

    Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Proceedings of the 2017 ACM Conference on Economics and Computation, 169--186

    2017

  6. [14]

    ACM SIGecom Exchanges 17(1):61--70

    Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019) Recent developments in prophet inequalities. ACM SIGecom Exchanges 17(1):61--70

    2019

  7. [15]

    II, 2nd ed

    Feller W (1971) An Introduction to Probability Theory and Its Applications, Vol. II, 2nd ed. Wiley

    1971

  8. [16]

    Mathematics of Operations Research 48(3):1344--1363

    Freund D, Zhao J (2022) Overbooking with bounded loss. Mathematics of Operations Research 48(3):1344--1363

    2022

  9. [17]

    Management Science 40(8):999--1020

    Gallego G, van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Science 40(8):999--1020

    1994

  10. [18]

    arXiv preprint arXiv:2501.02761

    Gao W, Ge D, Xue C, Sun C, Ye Y (2025) Beyond O( T) regret: Decoupling learning and decision-making in online linear programming. arXiv preprint arXiv:2501.02761

    2025

  11. [19]

    Operations Research 72(3):1139--1155

    Gupta V (2024) Greedy algorithm for multiway matching with bounded regret. Operations Research 72(3):1139--1155

    2024

  12. [20]

    Working paper, SSRN 5133857

    He S, Wei Y, Xu J, Yu SH (2025) Online resource allocation without re-solving: The effectiveness of primal-dual policies. Working paper, SSRN 5133857

    2025

  13. [21]

    random variables

    Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of i.i.d. random variables. The Annals of Probability 10(2):336--345

    1982

  14. [22]

    Mathematics of Operations Research 37(2):313--345

    Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research 37(2):313--345

    2012

  15. [23]

    arXiv preprint arXiv:2012.07933

    Jiang J, Zhang J (2020) Online resource allocation with stochastic resource consumption. arXiv preprint arXiv:2012.07933

    2020

  16. [24]

    Operations Research 73(3):1703--1721

    Jiang J, Ma W, Zhang J (2024) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Operations Research 73(3):1703--1721

    2024

  17. [25]

    Operations Research 73(6):3405--3420

    Jiang J, Ma W, Zhang J (2025a) Degeneracy is OK: Logarithmic regret for network revenue management with indiscrete distributions. Operations Research 73(6):3405--3420

  18. [26]

    Mathematics of Operations Research 51(2):956--987

    Jiang J, Ma W, Zhang J (2025b) Tightness without counterexamples: A new approach and new results for prophet inequalities. Mathematics of Operations Research 51(2):956--987

  19. [27]

    arXiv preprint arXiv:2408.00465

    Li G, Wang Z, Zhang J (2024) Infrequent resolving algorithm for online linear programming. arXiv preprint arXiv:2408.00465

    2024

  20. [28]

    Operations Research 70(5):2948--2966

    Li X, Ye Y (2022) Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research 70(5):2948--2966

    2022

  21. [29]

    Journal of Algorithms 29(2):277--305

    Lueker GS (1998) Average-case analysis of off-line and on-line knapsack problems. Journal of Algorithms 29(2):277--305

    1998

  22. [30]

    The Annals of Probability 12(4):1213--1216

    Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. The Annals of Probability 12(4):1213--1216

    1984

  23. [31]

    Management Science 44(11):1577--1593

    Talluri K, van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Management Science 44(11):1577--1593

    1998

  24. [32]

    Management Science 67(3):1368--1391

    Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Science 67(3):1368--1391

    2021

  25. [33]

    Operations Research 69(3):821--840

    Vera A, Banerjee S, Gurvich I (2021) Online allocation and pricing: Constant regret via Bellman inequalities. Operations Research 69(3):821--840

    2021

  26. [34]

    Working paper, SSRN 4357216

    Wei Y, Xu J, Yu SH (2023) Constant regret primal-dual policy for multi-way dynamic matching. Working paper, SSRN 4357216

    2023

  27. [35]

    Management Science, forthcoming

    Xie Y, Ma W, Xin L (2025) The benefits of delay to online decision making. Management Science, forthcoming

    2025

Pith tools

Reviewed July 3, 2026 · model on record in the stance chip above.