Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations

I use empirical processes to study how the shadow prices of a linear program that allocates an endowment of $n\beta \in {\mathbb{R}}^m$ resources to n customers behave as $n\to \infty$. 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 $\mathrm{\Theta }(1/n)$. I use these results to prove that the expected regret in an online linear program is $\mathrm{\Theta }(\log \hspace{0.17em}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 \hspace{0.17em}n\hspace{0.17em}\log \log \hspace{0.17em}n)$ to $O(\log \hspace{0.17em}n)$ , and it extends the $\mathrm{\Omega }(\log \hspace{0.17em}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.