Presented By: U-M Industrial & Operations Engineering
Departmental Seminar (899): Siddhartha Banerjee, Cornell University
The Departmental Seminar Series is open to all. U-M Industrial and Operations Engineering graduate students and faculty are especially encouraged to attend.
Attend remotely via BlueJeans:
Online: https://bluejeans.com/959596695
Dial-in: 1.408.614.7898 (US or Canada only) and enter the meeting ID 959596695
Sign up to meet with the speaker (IOE graduate students only):
http://ioe2.engin.umich.edu/class/ioe899/signup.php?spkr_id=417
Title:
Constant Regret Algorithms for Online Decision-Making
Abstract:
I will present a simple algorithm that achieves constant regret in many widely studied online decision-making problems, including online resource-allocation and pricing, generalized assignment, and online bin packing. In particular, I will consider a general class of finite-horizon control problems, where we see a stream of stochastic arrivals from some known distribution, and need to select actions, with the final objective depending only on the aggregate type-action counts. 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. The results stem from an elementary sample-path coupling argument, which may prove useful for a larger class of problems in online decision-making. Time permitting, I will illustrate this by showing how we can use this technique to obtain simple data-driven implementations of the above algorithms, which achieve constant regret with as little as a single data trace.
Bio:
Sid Banerjee is an Assistant Professor in the School of Operations Research and Information Engineering (ORIE) at Cornell, as well as a field member in the CS and ECE Departments and the Center for Applied Mathematics. His research is on stochastic modeling and control, and the design of algorithms and incentives for large-scale systems. He got his PhD in ECE from UT Austin, and worked as a postdoctoral researcher in the Social Algorithms Lab at Stanford, as well as a technical consultant at Lyft. His work is supported by an NSF CAREER award, and grants from the NSF and ARL.
Attend remotely via BlueJeans:
Online: https://bluejeans.com/959596695
Dial-in: 1.408.614.7898 (US or Canada only) and enter the meeting ID 959596695
Sign up to meet with the speaker (IOE graduate students only):
http://ioe2.engin.umich.edu/class/ioe899/signup.php?spkr_id=417
Title:
Constant Regret Algorithms for Online Decision-Making
Abstract:
I will present a simple algorithm that achieves constant regret in many widely studied online decision-making problems, including online resource-allocation and pricing, generalized assignment, and online bin packing. In particular, I will consider a general class of finite-horizon control problems, where we see a stream of stochastic arrivals from some known distribution, and need to select actions, with the final objective depending only on the aggregate type-action counts. 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. The results stem from an elementary sample-path coupling argument, which may prove useful for a larger class of problems in online decision-making. Time permitting, I will illustrate this by showing how we can use this technique to obtain simple data-driven implementations of the above algorithms, which achieve constant regret with as little as a single data trace.
Bio:
Sid Banerjee is an Assistant Professor in the School of Operations Research and Information Engineering (ORIE) at Cornell, as well as a field member in the CS and ECE Departments and the Center for Applied Mathematics. His research is on stochastic modeling and control, and the design of algorithms and incentives for large-scale systems. He got his PhD in ECE from UT Austin, and worked as a postdoctoral researcher in the Social Algorithms Lab at Stanford, as well as a technical consultant at Lyft. His work is supported by an NSF CAREER award, and grants from the NSF and ARL.
Related Links
Explore Similar Events
-
Loading Similar Events...
