The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems

A Novel Class of Robust and Fast Algorithms for Online Allocation Problems A central problem in operations research is allocating limited resources sequentially to maximize cumulative rewards. Applications abound and include network revenue management and internet advertising among many others. Existing data-driven algorithms are tailored for convex settings with either adversarial or stochastic inputs. Many modern applications of online allocations problems, however, are nonconvex. Furthermore, algorithms for adversarial inputs may be too conservative in practice, whereas algorithms for stochastic inputs can perform poorly when the model is misspecified. In the paper “The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems,” Balseiro, Lu, and Mirrokni present a novel class of algorithms for nonconvex online allocation problems that attain good performance simultaneously in stochastic and adversarial input models and also in various nonstationary settings. The resulting algorithms are simple, fast, and robust to noise and corruption in the observations, in contrast to existing methods from the literature.