Asymptotic Regret Bounds for Multi-Task Linear Bandits with Shared Low-Rank Structure

We study multi-task finite-arm linear bandits whose task parameters form a low-rank matrix. We characterize the asymptotic instance-dependent regret by a rank-aware information-allocation prob- lem. The lower bound is first expressed through rank-constrained confusing (Cfu) alternatives that preserve all true optimal-arm means and therefore isolate the positive-regret task–arm pairs that require logarithmic exploration. Under a local rank-Cfu stability condition, this reduced coefficient equals the coefficient of the full rank-constrained alternative family. Guided by this geometry, we propose Multi-Tasks Deficit-Tracking (MTDT), an empirical plug-in algorithm combining rank- aware certification, forced estimation, and deficit tracking. Under local oracle regularity, MTDT attains the rank-aware logarithmic regret coefficient as its tuning parameters vanish. Synthetic rank-one and rank-two experiments show substantial reductions in the leading exploration cost relative to independent-task baselines.