Constant Regret Algorithms for Online Decision-Making

You get a stream of jobs coming to a cloud computing cluster, each with its own memory/CPU requirements, and you want to load them on machines so as to minimize the resources used. Or maybe you are selling airplane seats to customers, and can keep adjusting prices over time to maximize profits. How much do you lose if you only know the statistics of the arrival process, but not the exact sequence of jobs/customers? I will present a class of finite-horizon control problems, where we see a random stream of arrivals from some known distribution, and need to select actions, with the final objective depending only on the aggregate type-action counts; this includes many widely-studied control problems including online resource-allocation, dynamic pricing, generalized assignment, online bin packing, and bandits with knapsacks. For such settings, I will introduce a unified algorithmic paradigm, and provide a simple yet general condition under which these algorithms achieve constant regret, i.e., additive loss compared to the hindsight optimal solution which is independent of the horizon and state-space. These results stem from an elementary coupling argument, which may prove useful for many other questions in online decision-making. Time permitting, I will illustrate this by showing how we can use this technique to incorporate side information and historical data in these settings, and achieve constant regret with as little as a single data trace.

Sid Banerjee is an associate professor in the School of Operations Research at Cornell, working on topics at the intersection of data-driven decision-making, network algorithms and market design. His research is supported by grants from the NSF (including an NSF CAREER award), the ARL Network Sciences division, and Engaged Cornell. He received his PhD from the ECE Department at UT Austin, and was a postdoctoral researcher in the Social Algorithms Lab at Stanford. He also served as a technical consultant with the research science group at Lyft from 2014-18.

Abstract

Siddhartha Banerjee, Cornell University