Algorithms and Theory of Bandits in Practical Setups

Abstract

Multi-armed bandit is a central paradigm for interactive machine learning, where an agent must learn efficiently from adaptive feedback. From a data collection point of view, bandit algorithms can be applied as a tool for efficient sequential data collection and serve as a powerful method to solve many real-world problems. This perspective leads to the pure exploration problem, where the goal is to focus entirely on data exploration during the learning process and use the collected data for a final task, such as decision-making or model training. A key aspect of this framework is that individual data collection steps do not have an immediate impact on a final objective. This distinguishes the pure exploration framework, which has recently shown its strength in many practical problems, from the more traditional regret minimization framework with a cumulative objective. In this dissertation, three problems are studied around this theme, ranging from theoretical foundations to practical applications. The first problem addresses a gap in the theoretical understanding of simple regret, a fundamental yet under-explored performance measure in pure exploration; since its proposal, a rigorous, instance-dependent characterization has been lacking. The second problem arises in experimental settings, such as clinical trials, where bandits are a powerful tool for accelerating discovery. However, factors like user non-compliance can confound the experimental results. We address the question of how to design efficient pure exploration algorithms to support critical decision-making in the presence of such confounding factors. The third problem concerns the alignment of Large Language Models (LLMs), which often requires a high-quality preference dataset that is expensive to collect. We study how to design efficient data exploration strategies to improve the sample efficiency of preference learning. These three problems share the common theme of efficient data collection for a final task, where the immediate impact of each data collection step is disregarded in favor of the terminal objective. This dissertation tackles these three problems by developing a suite of novel algorithms and analyses to address each of them. A common goal across all contributions is the provision of an instance-dependent guarantee for each problem. This is more practical and fine-grained than the worst-case bounds commonly seen in the literature, providing a more complete, problem instance level characterization that reflects the intrinsic difficulty of each specific task.