PhD Thesis Defense: Ali Zeynali, Online Sequential Decision Making for Resource Allocation
Content
Speaker:
Abstract:
Online resource allocation is a fundamental problem in sequential decision-making, with applications in cloud computing, video streaming, and transportation systems. In these settings, a decision maker must allocate limited resources over time to uncertain and dynamically evolving demand without exact or reliable knowledge of future inputs. The inherent uncertainty in both demand and resource availability makes achieving strong empirical performance while maintaining robustness a central challenge.
This thesis studies online resource allocation across different regimes of uncertainty, including uncertainty in demand, resources, or both. In addition, it aims to bridge the gap between data-driven adaptivity and worst-case performance guarantees.
The first part considers settings where resource availability varies over time while demand remains relatively stable, motivated by the problem of online adaptive bitrate control for 360-degree video streaming. We design an algorithm that jointly performs view and bitrate adaptation to optimize user quality-of-experience under fluctuating network conditions. The algorithm operates based on the current state of the streaming session and does not require knowledge of future bandwidth conditions. We provide both theoretical guarantees and empirical validation.
The second part studies online resource allocation in settings where demand evolves dynamically and may be subject to adversarial perturbations, motivated by applications in multi-task server systems. We develop algorithms that explicitly account for stochastic and adversarially revealed demand, delayed information, and temporal dependencies, enabling robust and stable performance under bursty and unpredictable workloads.
The third part studies settings where both resources and demand evolve dynamically, leading to a highly coupled and stochastic environment. As a concrete application, we consider online matching in ride-sharing systems. We develop an emission-aware online matching algorithm that balances service efficiency with environmental impact, and provide theoretical guarantees along with empirical improvements over existing methods.
The final part of the thesis addresses the gap between theoretical and data-driven algorithm design. We develop a framework for data-driven online resource allocation with worst-case guarantees by constructing parameterized classes of algorithms in which every policy admits provable competitive guarantees. This enables learning-based selection of policies using historical data while preserving robustness to adversarial inputs.
Advisors:
Mohammad Hajiesmaili and Ramesh Sitaraman