Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits
This addresses a limitation in sequential multi-task learning for bandit problems, providing a provable method for real-world applications where task diversity is not guaranteed.
The paper tackles the problem of lifelong learning in linear bandits without assuming task diversity, developing an algorithm that learns and transfers low-rank representations, achieving a regret guarantee of ˜O(Nm√τ + N^{2/3}τ^{2/3}dm^{1/3} + Nd^2 + τmd) which improves upon the baseline ˜O(Nd√τ) when N is large and m << d.
We study lifelong learning in linear bandits, where a learner interacts with a sequence of linear bandit tasks whose parameters lie in an $m$-dimensional subspace of $\mathbb{R}^d$, thereby sharing a low-rank representation. Current literature typically assumes that the tasks are diverse, i.e., their parameters uniformly span the $m$-dimensional subspace. This assumption allows the low-rank representation to be learned before all tasks are revealed, which can be unrealistic in real-world applications. In this work, we present the first nontrivial result for sequential multi-task linear bandits without the task diversity assumption. We develop an algorithm that efficiently learns and transfers low-rank representations. When facing $N$ tasks, each played over $τ$ rounds, our algorithm achieves a regret guarantee of $\tilde{O}\big (Nm \sqrtτ + N^{\frac{2}{3}} τ^{\frac{2}{3}} d m^{\frac13} + Nd^2 + τm d \big)$ under the ellipsoid action set assumption. This result can significantly improve upon the baseline of $\tilde{O} \left (Nd \sqrtτ\right)$ that does not leverage the low-rank structure when the number of tasks $N$ is sufficiently large and $m \ll d$. We also demonstrate empirically on synthetic data that our algorithm outperforms baseline algorithms, which rely on the task diversity assumption.