2026 Theses Doctoral

Bandits, Knapsacks, and Active Learning: Algorithms and Lower Bounds for Sequential Decision-Making

Aznag, Abdellah

The quality of a decision is inextricably linked to the quality of the data that informs it. Yet in many operational settings---from revenue management to clinical trials---data collection is subject to real costs and constraints, making 𝘩𝘰𝘸 to collect data a first-order design problem. This thesis develops principled policies for sequential data collection in complex systems, organized around two themes: 𝘥𝘦𝘤𝘪𝘴𝘪𝘰𝘯-𝘢𝘸𝘢𝘳𝘦 collection, where data acquisition is coupled to a downstream optimization objective, and 𝘳𝘦𝘭𝘪𝘢𝘣𝘪𝘭𝘪𝘵𝘺-𝘢𝘸𝘢𝘳𝘦 collection, where the goal is to build estimates that are uniformly reliable across a heterogeneous environment.

In the first part, we study decision-aware collection in the context of dynamic assortment optimization under the Multinomial Logit choice model with finite inventory. We propose MNLwK-UCB, an algorithm that achieves 𝑂̃(𝑁 + √𝑁𝑇) regret uniformly across all inventory regimes, matching the infinite-inventory benchmark and improving upon all prior bounds. The analysis introduces a modular regret decomposition that isolates the cost of learning from the cost of inventory mismanagement.

In the second part, we turn to reliability-aware collection for multi-group mean estimation. We develop Variance-UCB and a unified width-based regret analysis showing that the true bottleneck for data collection is not distributional complexity but the relative knowledge gap between the system's structure and the decision-maker's prior knowledge. Our bounds eliminate the 𝜎⁻¹/min dependence present in all prior work, resolving an open question of Carpentier et al. 2011).

In the third part, we establish the fundamental limits of the reliability-aware collection problem through a local minimax framework. We introduce the Variance Local Curvature, an information-geometric functional that quantifies the intrinsic difficulty of learning each group's variance within a given hypothesis class, and we identify the precise gap between achievable and optimal performance.