Tata Institute of Fundamental Research

The Compensated Coupling (or How the Future is the Great Guide for the Present)

STCS Annual Symposium
Speaker: Siddhartha Banerjee (Cornell University)
Organiser: Raghuvansh Saxena
Date: Tuesday, 13 Aug 2024, 14:30 to 15:30
Venue: AG-69

(Scan to add to calendar)
Abstract: 

I will present the compensated coupling: a simple paradigm for designing sequential decision-making policies based on sample-pathwise comparisons against a hindsight benchmark. This approach generalizes many standard results used in studying Markov decision processes and reinforcement learning, but also gives us new policies which are much simpler and more effective than existing heuristics. For a large class of widely-studied sequential decision-making problems -- including network revenue management, dynamic pricing, generalized assignment, online bin packing, online assortment optimization and bandits with knapsacks -- I will illustrate how under a wide range of conditions, our approach achieves additive loss compared to the hindsight optimal which is independent of the horizon and state-space. Time permitting, I will try and describe how we can use this technique to incorporate side information and historical data, and achieve constant regret with as little as a single data trace.

Short Bio:

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), ARO, AFOSR, and Engaged Cornell, and has received multiple awards including the INFORMS Applied Probability Society Best Publication award in 2021 and the Erlang Prize in 2022. He received his B.Tech from IIT Madras and 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.