Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity

• 成果类型: Article; Early Access
• 署名作者: Huang, Xinmeng; Xu, Kan; Lee, Donghwan; Hassani, Hamed; Bastani, Hamsa; Dobriban, Edgar
• 署名单位: University of Pennsylvania; Arizona State University; Arizona State University-Tempe; University of Pennsylvania; University of Pennsylvania; University of Pennsylvania
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.1080/01621459.2024.2439622
• 发表日期: 2025
• 关键词: big data

摘要

Large and complex datasets are often collected from several, possibly heterogeneous sources. Multitask learning methods improve efficiency by leveraging commonalities across datasets while accounting for possible differences among them. Here, we study multitask linear regression and contextual bandits under sparse heterogeneity, where the source/task-associated parameters are equal to a global parameter plus a sparse task-specific term. We propose a novel two-stage estimator called MOLAR that leverages this structure by first constructing a covariate-wise weighted median of the task-wise linear regression estimates and then shrinking the task-wise estimates toward the weighted median. Compared to task-wise least squares estimates, MOLAR improves the dependence of the estimation error on the data dimension. Extensions of MOLAR to generalized linear models and constructing confidence intervals are discussed in the article. We then apply MOLAR to develop methods for sparsely heterogeneous multitask contextual bandits, obtaining improved regret guarantees over single-task bandit methods. We further show that our methods are minimax optimal by providing a number of lower bounds. Finally, we support the efficiency of our methods by performing experiments on both synthetic data and the PISA dataset on student educational outcomes from heterogeneous countries. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.