Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations
This provides improved regret bounds for resource allocation problems in operations research and online optimization, though it is incremental in refining existing theoretical results.
The paper tackles the asymptotic behavior of shadow prices in linear programs as the number of customers increases, showing concentration, convergence to normality, and variance decreasing as Θ(1/n), and uses this to prove that expected regret in online linear programs is Θ(log n), tightening prior bounds.
I study how the shadow prices of a linear program that allocates an endowment of $nβ\in \mathbb{R}^{m}$ resources to $n$ customers behave as $n \rightarrow \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 $Θ(1/n)$. I use these results to prove that the expected regret in \cites{Li2019b} online linear program is $Θ(\log n)$, both when the customer variable distribution is known upfront and must be learned on the fly. I thus tighten \citeauthors{Li2019b} upper bound from $O(\log n \log \log n)$ to $O(\log n)$, and extend \cites{Lueker1995} $Ω(\log n)$ lower bound to the multi-dimensional setting. I illustrate my new techniques with a simple analysis of \cites{Arlotto2019} multisecretary problem.