New Results on Primal-Dual Algorithms for Online Allocation Problems With Applications to ...
14Haihao Lu (Chicago Booth School of Business)
https://simons.berkeley.edu/talks/new-results-primal-dual-algorithms-online-allocation-problems-applications-budget-pacing
Structure of Constraints in Sequential Decision-Making
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 talk, 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 non-stationary 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 algorithms, such as, online mirror descent and PI controller. Our proposed algorithms are simple, fast, robust to estimation errors, and do not require convexity in the revenue function, consumption function and action space, in contrast to existing methods for online allocation problems. The major motivation of this line of research is the applications to budget pacing in online advertising.