Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations

Operations Research · 2025 · Volume 73 · Issue 4

DOI: 10.1287/opre.2022.0036

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 / 𝑛 ) Θ ⁢ ( 1 / n ) . I use these results to prove that the expected regret in an online linear program is Θ ⁡ ( l o g 𝑛 ) Θ ⁡ ( 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 𝑂 ⁡ ( l o g 𝑛 l o g l o g 𝑛 ) O ⁡ ( log n log log n ) to 𝑂 ⁡ ( l o g 𝑛 ) O ⁡ ( log n ) , and it extends the Ω ⁡ ( l o g 𝑛 ) Ω ⁡ ( 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. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.0036 .

Keywords

Stochastic Models, online linear program, multisecretary problem, network revenue management, dual convergence, regret bounds, empirical process, dual convergence

Enable JavaScript for citation tools and additional paper interactions.