Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits

• URL: http://arxiv.org/abs/2501.13390v1
• Date: Thu, 23 Jan 2025 05:21:27 GMT
• Title: Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits
• Authors: Thang Duong, Zhi Wang, Chicheng Zhang,
• Abstract summary: We study lifelong learning in linear bandits, where a learner interacts with a sequence of linear bandit tasks. Current literature assumes that the tasks are diverse, i.e., their parameters uniformly span the $m$-dimensional subspace. We present the first nontrivial result for sequential multi-task linear bandits without the task diversity assumption.
• Score: 17.970177214029473
• License:
• Abstract: 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 $\tau$ rounds, our algorithm achieves a regret guarantee of $\tilde{O}\big (Nm \sqrt{\tau} + N^{\frac{2}{3}} \tau^{\frac{2}{3}} d m^{\frac13} + Nd^2 + \tau m d \big)$ under the ellipsoid action set assumption. This result can significantly improve upon the baseline of $\tilde{O} \left (Nd \sqrt{\tau}\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.

Related papers

• Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing [38.883540444516605]
  DARPA launched the ShELL program, which aims to explore how experience sharing can benefit distributed lifelong learning agents. We conduct both theoretical and empirical research on distributed multi-task reinforcement learning (RL), where a group of $N$ agents collaboratively solves $M$ tasks. We propose an algorithm called DistMT-LSVI, where each agent independently learns $epsilon$-optimal policies for all $M$ tasks.
  arXiv  Detail & Related papers  (2023-07-11T22:58:53Z)
• Simplifying and Understanding State Space Models with Diagonal Linear RNNs [56.33053691749856]
  This work disposes of the discretization step, and proposes a model based on vanilla Diagonal Linear RNNs. We empirically show that, despite being conceptually much simpler, $mathrmDLR$ is as performant as previously-proposed SSMs. We also characterize the expressivity of SSMs and attention-based models via a suite of $13$ synthetic sequence-to-sequence tasks.
  arXiv  Detail & Related papers  (2022-12-01T18:53:06Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  We consider the setting where we play $M$ linear bandits with dimension $d$, each for $T$ rounds, and these $M$ bandit tasks share a common $k(ll d)$ dimensional linear representation. We come up with novel algorithms that achieve $widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret bounds, which matches the known minimax regret lower bound up to logarithmic factors.
  arXiv  Detail & Related papers  (2022-03-29T15:27:13Z)
• Multi-task Representation Learning with Stochastic Linear Bandits [29.8208189270894]
  We study the problem of transfer-learning in the setting of linear bandit tasks. We consider that a low dimensional linear representation is shared across the tasks, and study the benefit of learning this representation in the multi-task learning setting.
  arXiv  Detail & Related papers  (2022-02-21T09:26:34Z)
• Provable Lifelong Learning of Representations [21.440845049501778]
  We propose a provable lifelong learning algorithm that maintains and refines the internal feature representation. We prove that for any desired accuracy on all tasks, the dimension of the representation remains close to that of the underlying representation.
  arXiv  Detail & Related papers  (2021-10-27T00:41:23Z)
• On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
  This paper presents analyses for the statistical benefit of multitask representation learning in linear Markov Decision Process (MDP) We first discover a emphLeast-Activated-Feature-Abundance (LAFA) criterion, denoted as $kappa$, with which we prove that a straightforward least-square algorithm learns a policy which is $tildeO(H2sqrtfrackappa mathcalC(Phi)2 kappa dNT+frackappa dn)
  arXiv  Detail & Related papers  (2021-06-15T11:21:06Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• Near-optimal Representation Learning for Linear Bandits and Linear RL [41.33483293243257]
  We first consider the setting where we play $M$ linear bandits with dimension $d$ concurrently. These bandits share a common $k$-dimensional linear representation so that $kll d$ and $k ll M$. We propose a sample-efficient algorithm, MTLR-OFUL, which leverages the shared representation to achieve $tildeO(MsqrtdkT + dsqrtkMT )$ regret.
  arXiv  Detail & Related papers  (2021-02-08T11:11:53Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  We study how representation learning can improve the efficiency of bandit problems. We present a new algorithm which achieves $widetildeO(TsqrtkN + sqrtdkNT)$ regret, where $N$ is the number of rounds we play for each bandit.
  arXiv  Detail & Related papers  (2020-10-13T16:35:30Z)
• Few-Shot Learning via Learning the Representation, Provably [115.7367053639605]
  This paper studies few-shot learning via representation learning. One uses $T$ source tasks with $n_1$ data per task to learn a representation in order to reduce the sample complexity of a target task.
  arXiv  Detail & Related papers  (2020-02-21T17:30:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.