Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations

Robert L. Bray ()
Additional contact information
Robert L. Bray: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208

Operations Research, 2025, vol. 73, issue 4, 2188-2203

Abstract: I use empirical processes to study how the shadow prices of a linear program that allocates an endowment of n β ∈ R m resources to n customers behave as n → ∞ . I show the shadow prices (i) adhere to a concentration of measure, (ii) converge to a multivariate normal under central-limit-theorem scaling, and (iii) have a variance that decreases like Θ ( 1 / n ) . I use these results to prove that the expected regret in an online linear program is Θ ( log n ) , both when the customer variable distribution is known upfront and must be learned on the fly. This result tightens the sharpest known upper bound from O ( log n log log n ) to O ( log n ) , and it extends the Ω ( log n ) lower bound known for single-dimensional problems to the multidimensional setting. I illustrate my new techniques with a simple analysis of a multisecretary problem.

Keywords: Stochastic; Models; online linear program; multisecretary problem; network revenue management; dual convergence; regret bounds; empirical process; dual convergence (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0036 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:4:p:2188-2203

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().