Near-optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representation

Multi-task representation learning exploits the shared structure among related tasks by learning a common latent representation, thereby improving sample efficiency. This paper introduces a novel approach to multi-task representation learning in heterogeneous linear bandits. We consider $T$ concurrent heterogeneous linear bandit tasks, each with feature dimension $d$, whose reward parameters share a common latent representation of dimension $r \ll \min\{d, T\}$, capturing the underlying task relatedness. We propose RepUCB, a novel Upper Confidence Bound (UCB) algorithm that leverages shared low-rank representations to enhance learning in a sample-efficient manner. Our algorithm first collects data through an exploration phase, estimates the shared representation, and then performs UCB-based learning on our proposed confidence set. We provide theoretical guarantees for the confidence set and prove that the unknown reward parameters lie within the confidence set with high probability. We derive cumulative regret bound and show that the proposed approach achieves $\widetilde{O}(\sqrt{drNT})$, a significant improvement over solving the $T$ tasks independently, resulting in a regret of $\widetilde{O}(dT\sqrt{N})$. We performed numerical simulations to validate the performance of our algorithm for different problem sizes and compared with baseline algorithms.

We study the multi-task linear regression problem in the presence of contaminated tasks. We address the setting where the unknown parameters of a majority of tasks are close in the $\ell_2$-norm, while a fraction of tasks are arbitrary outliers. Existing theoretical frameworks for this problem rely heavily on the assumption that the empirical second moment of each task has a minimum eigenvalue bounded away from zero (order $Ω(1)$). Crucially, this assumption fails in many high-dimensional scenarios, rendering prior guarantees vacuous. To overcome this limitation, we propose an estimator based on matrix-weighted norm regularization. We also introduce a relative balancedness condition, quantified by a balancedness constant, that compares each task's second moment with the average inlier geometry and relaxes the need for taskwise second-moment lower bounds. In favorable regimes with moderate balancedness, our prediction MSE bounds match the rate of Duan and Wang (2023) under substantially weaker spectral assumptions; the resulting task-overall MSE is minimax optimal up to logarithmic factors. Furthermore, we demonstrate that our estimator enjoys a safety guarantee: when the relevant balancedness constant is large or infinite, or when tasks are unrelated, the method performs no worse than independent task learning.

Learned representations are often invariant to rotational transformations, leaving individual dimensions non-identifiable and interchangeable. We study how Matryoshka Representation Learning (MRL) induces a task-aligned privileged basis distinct from variance-based or regularizer-induced orderings. In the linear setting, we prove that full-prefix MRL recovers the ordered principal directions, and can be computed efficiently using shared statistics. Empirically, we demonstrate that MRL yields consistent per-dimension structure aligned with task signal, where coordinate magnitude reflects informativeness.