# Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity

arXiv: https://arxiv.org/abs/2306.06291 · HTML: https://mlsanity.com/paper/2306.06291/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 75 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 30 of 36)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Distributed learning of deep neural network over multiple agents](https://mlsanity.com/paper/1810.06060/) (2018)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Transfer Learning for High-dimensional Linear Regression: Prediction, Estimation, and Minimax Optimality](https://mlsanity.com/paper/2006.10593/) (2020)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Transfer Learning under High-dimensional Generalized Linear Models](https://mlsanity.com/paper/2105.14328/) (2021)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Challenges of Big Data Analysis](https://mlsanity.com/paper/1308.1479/) (2013)
- [Multi-Task Learning for Contextual Bandits](https://mlsanity.com/paper/1705.08618/) (2017)
- [Meta-learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2005.08531/) (2020)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Meta Dynamic Pricing: Transfer Learning Across Experiments](https://mlsanity.com/paper/1902.10918/) (2019)
- [Sequential Transfer in Multi-armed Bandit with Finite Set of Models](https://mlsanity.com/paper/1307.6887/) (2013)
- [Adaptive and Robust Multi-Task Learning](https://mlsanity.com/paper/2202.05250/) (2022)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2008.11918/) (2020)
- [Learning from Similar Linear Representations: Adaptivity, Minimaxity, and Robustness](https://mlsanity.com/paper/2303.17765/) (2023)
- [Online Sparse Reinforcement Learning](https://mlsanity.com/paper/2011.04018/) (2020)
- [Predicting with Proxies: Transfer Learning in High Dimension](https://mlsanity.com/paper/1812.11097/) (2018)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Distributed linear regression by averaging](https://mlsanity.com/paper/1810.00412/) (2018)
- [Multi-task Representation Learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2202.10066/) (2022)
- [Statistical Inference for Online Decision-Making: In a Contextual Bandit Setting](https://mlsanity.com/paper/2010.07283/) (2020)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)

## Built on by (most cited first, 7 of 7)

- [TransFusion: Covariate-Shift Robust Transfer Learning for High-Dimensional Regression](https://mlsanity.com/paper/2404.01153/) (2024)
- [Guided Adversarial Robust Transfer Learning with Source Mixing](https://mlsanity.com/paper/2309.06534/) (2023)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [Transfer Faster, Price Smarter: Minimax Dynamic Pricing under Cross-Market Preference Shift](https://mlsanity.com/paper/2505.17203/) (2025)
- [Empirical Bayesian Multi-Bandit Learning](https://mlsanity.com/paper/2510.26284/) (2025)
- [Adaptive Multi-task Learning for Multi-sector Portfolio Optimization](https://mlsanity.com/paper/2507.16433/) (2025)
- [Deep Multitask Learning for Mixed-Type Outcomes with Shared Sparsity](https://mlsanity.com/paper/2607.00995/) (2026)

## Abstract (arXiv)

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 towards 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 paper. 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.