无需任务多样性假设，实现低秩表示的可证明迁移学习。
Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits
- 设计新算法，在无任务多样性前提下高效学习并迁移低秩表示。
- 在N个任务、每个τ轮下，误差上界为\tilde{O}(Nm\sqrtτ + ...)
- 适合大规模多任务场景，尤其当任务数多且维度远高于秩时。
我们研究线性老虎机中的终身学习问题，其中学习者与一系列线性老虎机任务交互，其参数位于ℝᵈ的m维子空间中，共享低秩表示。现有文献通常假设任务具有多样性，即参数均匀覆盖m维子空间，从而可在所有任务揭示前学习到低秩表示，但这在现实应用中可能不成立。本文首次在无任务多样性假设下给出序列多任务线性老虎机的非平凡结果。我们提出一种高效学习并转移低秩表示的算法。在面对N个任务、每个任务持续τ轮的情况下，该算法在椭球动作集假设下达到\tilde{O}(Nm\sqrtτ + N^{2/3}τ^{2/3}dm^{1/3} + Nd² + τmd)的后悔上界。当任务数N足够大且m≪d时，此结果显著优于不利用低秩结构的基线\tilde{O}(Nd\sqrtτ)。我们在合成数据上实证表明，该算法优于依赖任务多样性的基线方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。