Online learning algorithms design with applications to clinical trial, serving system and job scheduling problem

This thesis presents novel algorithms and theoretical analyses for various online learning applications, including job scheduling, model selection in serving systems, and clinical trials. Each application is framed as a Multi-Armed Bandits (MAB) or Linear Bandits problem, tailored to its specific requirements. In the job scheduling application, we address the challenge of scheduling jobs on a set of machines in an online fashion with the overall quality of service as close as possible to an optimal offline benchmark. We design a variant of the Upper Confidence Bound (UCB) algorithm, achieving a logarithmic regret of O(ln T), which effectively balances exploration and exploitation in resource-constrained environments. For the serving system application, we develop a model selection algorithm to optimize the deployment of machine learning models across multiple servers in parallel. Framing this as a stochastic MAB problem, we propose UCB-based / Batch Elimination Framework algorithms for both online and offline settings. These approaches achieve regret bounds matching the full-information MAB regret of O(ln T). Simulations on an image classification task with the ImageNet dataset validate the algorithms’ efficiency and scalability. In the clinical trial application, motivated by the need to reduce the time and resource costs associated with treatment evaluation, we study the batched Linear Bandits problem. We prove that only O(log log T) batches are needed to achieve the minimax optimal regret of O( \sqrt{dTmin{log K,d}}), even in the more restricted batch learning model. Along the way, this result proposes the distributional optimal design, a natural extension of the optimal experiment design, and provide a both statistically and computationally efficient learning algorithm for the problem, which may be of independent interest.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Ruan, Yufei

Contributors dc:contributor

• Zhou, Yuan
• Srikant, Rayadurgam
• Chen, Xin
• Etesami, Rasoul

• Multi-Armed Bandits
• online learning

Statement dc:rights

• Copyright 2025 Yufei Ruan

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129242

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129242