2023 Theses Doctoral

Beyond Worst-Case Analysis for Sequential Decision Making

Perivier, Noemie

Traditionally, algorithms have been evaluated through worst-case analysis, where the input is presumed to take its worst possible configuration. However, in many real-world settings, the data is not adversarially constructed and, on the contrary, exhibits some recognizable patterns. This often leads worst-case guarantees to be poor indicators of algorithms' performance. To overcome this limitation, a growing body of work on Beyond Worst-Case analysis has recently emerged.

In this thesis, we are concerned with sequential decision-making problems, where an agent must take successive decisions over multiple time steps without knowing in advance the forthcoming input. Examples of such settings include ride-sharing, online retail or job scheduling. Motivated by the unprecedented surge of data in these domains, which may help to overcome worst-case barriers by allowing to predict at least partially the future, we explore three distinct frameworks for Beyond Worst-Case analysis of sequential decision-making: (i) semi-random models, (ii) parametric models, and (iii) algorithms with predictions. While they all pursue the same objective — using previously collected data to provide stronger theoretical guarantees —, these frameworks mainly differ in the way the data is utilized. We examine each of them separately and present novel results for five different online optimization problems: minimum cost matching, assortment optimization (with and without inventory constraints), pricing and scheduling.