Best-Arm Identification with High-Dimensional Features
Dohyun Ahn, Dongwook Shin, Lewen Zheng · 2024
Given a collection of stochastic systems (or arms), we focus on the problem of identifying the best system with the highest expected payoff by learning the unknown statistical characteristics of system payoffs via sequential sampling. The distributions of the system payoffs are governed by a linear model consisting of high-dimensional system features that are fixed and known, as well as unknown parameters that are common across all systems. However, due to the high dimensionality, the ordinary least-squares estimator for the unknown parameters exhibits a large variance, leading to significant errors in identifying the best system. Based on the theory of large deviations, we show that this performance degradation can be effectively addressed by using the LASSO estimator with a judiciously chosen regularization parameter. Furthermore, we provide a practical guideline for selecting the regularization parameter and design a dynamic sampling policy that improves the performance in identifying the best system.