Asymptotic Regret Bounds for Multi-Task Linear Bandits with Shared Low-Rank Structure
Abstract
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 problem. We first express the lower bound in terms of rank-constrained confusing (Cfu) alternatives that preserve all true optimal-arm means, isolating the task--arm pairs with positive regret 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-Task 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.