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

• Published in: Operations research 2023-01, Vol.71 (1), p.101-119
• Main Authors: Balseiro, Santiago R., Lu, Haihao, Mirrokni, Vahab
• Format: Article
• Language: English
• Subjects: Algorithms; Asymptotic properties; Auctioning; Consumption; Convexity; Decision making; nonconvexity; nonstationarity; Online advertising; online allocation problem; Operations research; Optimization; Revenue; Revenue management
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.2021.2242

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. Online allocation problems with resource constraints are central problems in revenue management and online advertising. In these problems, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates reward. The objective is to maximize cumulative rewards subject to a constraint on the total consumption of resources. In this paper, we consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model that is unknown to the decision maker. We design a general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. In particular, our algorithms are asymptotically optimal under independent and identically distributed inputs as well as various nonstationary stochastic input models, and they attain an asymptotically optimal fixed competitive ratio when the input is adversarial. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent. By choosing the reference function accordingly, we recover the dual subgradient descent and dual multiplicative weights update algorithm. The resulting algorithms are simple, fast