Abstract
The online allocation of scarce resources is a canonical paradigm of decision-making under uncertainty, and is widely studied in many fields of engineering under a variety of titles (dynamic allocation/revenue management/prophet inequalities/etc.). In this talk, I will re-examine the basic online allocation problem, with the aim of building bridges to the ever-improving predictive capabilities enabled by modern machine-learning methods. To this end, I will present a new Bayesian-learning inspired algorithm for online allocation problems, and show that it achieves the first horizon-independent and budget-independent regret bounds for a wide class of online packing problems with stochastic inputs. The result follows from a simple coupling technique, and I will discuss how this may prove useful for related online decision-making settings.