Constant Regret in Exchangeable Action Models: Overbooking, Bin Packing, and Beyond

          @misc{ scivideos_22738,
            doi = {},
            url = {https://old.simons.berkeley.edu/talks/constant-regret-exchangeable-action-models-overbooking-bin-packing-and-beyond},
            author = {},
            keywords = {},
            language = {en},
            title = {Constant Regret in Exchangeable Action Models: Overbooking, Bin Packing, and Beyond},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {oct},
            note = {22738 see, \url{https://scivideos.org/simons-institute/22738}}
          }
          

Abstract

Many problems in online decision-making can be viewed through a lens of exchangeable actions: over a long time-horizon of length T some arrival process allows for many opportunities to take a particular action, but the exact timing of actions is irrelevant for the eventual outcome. Examples of this phenomenon include bin packing (where it does not matter when we put an item of a given size into a given bin), knapsack (where it does not matter when we accept an item of a given value), and a range of matching problems among others (where it does not matter when we assign a request type to a given resource). In this talk we survey a number of results that capture the conditions under which such problems give rise to algorithms with uniform loss guarantees, i.e., where the additive loss relative to an optimal solution in hindsight is bounded independent of the horizon length. Our conditions characterize permissible geometries of the objective function, minimal requirements on the arrival process, and uncertainty about the underlying arrival processes, including the length of the time horizon. Based on joint works with Jiayu (Kamessi) Zhao, Chamsi Hssaine, Sid Banerjee, Thodoris Lykouris, Wentao Weng, Elisabeth Paulson, and Brad Sturt