Online resource allocation, a critical component of the broader online learning field, has garnered significant attention for its role in numerous applications, including online job scheduling, quality control for video streaming, and decision making in trading markets. The primary objective is to allocate limited resources to time-varying customer demands to maximize profit for both the decision maker and the customer. The online nature of this problem, coupled with the uncertainty of future demands and available resources, makes it inherently challenging.
Various techniques have been employed to design online decision-making algorithms, ranging from data-driven machine learning-based algorithms to theoretical approaches like online convex optimization or Lyapunov optimization. While data-driven approaches train decision-making algorithms on specific datasets without providing guarantees, theoretical approaches bound the minimum performance of the decision maker but lack the flexibility to adapt when sufficient information about past sequences becomes available. Bridging this gap, the first part of the thesis focuses on developing an online algorithm that provides worst-case guarantees and can be tuned using training data.
In this thesis, we propose a novel technique for designing and analyzing online decision-making algorithms that provide worst-case guarantees on performance while also being adaptable to available datasets. We validate this technique on two well-known problems in the domain of online resource allocation. Next, we examine the problem of online bitrate and view adaptation control for 360-degree video streaming, which is a subset of the online resource allocation area. We introduce a new algorithm for the online 360-degree video streaming problem and implement a new fully simulated environment to test and evaluate online bitrate control algorithms. Finally, we outline a future plan for designing a near-optimal algorithm for an extended version of online decision-making and its application in complex systems such as online matching for ride-sharing services.
Advisors: Mohamad Hajiesmaili and Ramesh Sitaraman