Logarithmic Regret in Multisecretary and Online Linear Programming Problems with Continuous Valuations

I study a general revenue management problem in which $ n $ customers arrive sequentially over $ n $ periods, and you must dynamically decide which to satisfy. Satisfying the period-$ t $ customer yields utility $ u_{t} \in \mathbbm{R}_{+} $ and decreases your inventory holdings by $ A_{t} \in \mathbbm{R}_{+}^{M} $. The customer vectors, $ (u_{t}, A_{t}')' $, are \iid, with $ u_{t} $ drawn from a finite-mean continuous distribution and $ A_{t} $ drawn from a bounded discrete or continuous distribution. I study this system's \emph{regret}, which is the additional utility you could get if you didn't have to make decisions on the fly. I show that if your initial inventory endowment scales linearly with $ n $ then your expected regret is $ \Theta(\log(n)) $ as $ n \rightarrow \infty $. I provide a simple policy that achieves this $ \Theta(\log(n)) $ regret rate. Finally, I extend this result to \cites{Arlotto2019} multisecretary problem with uniformly distributed secretary valuations.