Beyond task diversity: provable representation transfer for sequential multitask linear bandits
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 R d , thereby sharing a low-rank representation. Current literature typically assumes that the tasks are diverse, i.e., their parameters uniformly span the mdimensional 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 multitask 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 τ md under the ellipsoid action set assumption. This result can significantly improve upon the baseline of Õ (N d √ τ ) that does not leverage the low-rank structure when the number of tasks N is sufficiently large and m ≪ d. We also demonstrate empirically on synthetic data that our algorithm outperforms baseline algorithms, which rely on the task diversity assumption.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Impact of Representation Learning in Linear Bandits cites Provable Meta-Learning of Linear Representations
- Near-Optimal Representation Learning for Linear Bandits and Linear RL cites Provable Meta-Learning of Linear Representations
- Provably Efficient Multi-Task Meta Bandit Learning via Shared Representations cites Impact of Representation Learning in Linear Bandits
- Provably Efficient Multi-Task Meta Bandit Learning via Shared Representations cites Near-Optimal Representation Learning for Linear Bandits and Linear RL
- Provably Efficient Multi-Task Meta Bandit Learning via Shared Representations cites Improved Regret Bounds of Bilinear Bandits using Action Space Analysis
- Provably Efficient Multi-Task Meta Bandit Learning via Shared Representations cites Provable Meta-Learning of Linear Representations
Cited by top-tier papers1
Builds on4
- Provable Meta-Learning of Linear RepresentationsNilesh Tripuraneni, Chi Jin, Michael I. JordanICML 2021 · 218 citations
- Near-Optimal Representation Learning for Linear Bandits and Linear RLJiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li et al.ICML 2021 · 60 citations
- Impact of Representation Learning in Linear BanditsJiaqi Yang, Wei Hu, Jason D. Lee, Simon Shaolei DuICLR 2021 · 58 citations
- Improved Regret Bounds of Bilinear Bandits using Action Space AnalysisKyoungseok Jang, Kwang-Sung Jun, Se-Young Yun, Wanmo KangICML 2021 · 10 citations
Related papers
- Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual BanditsJiabin Lin, Shana Moothedath, Namrata VaswaniICML 2024 · 9 citations
- Provably Efficient Lifelong Reinforcement Learning with Linear RepresentationSanae Amani, Lin Yang, Ching-An ChengICLR 2023
- Offline Multitask Representation Learning for Reinforcement LearningHaque Ishfaq, Thanh Nguyen-Tang, Songtao Feng, Raman Arora et al.NeurIPS 2024 · 15 citations
- Leveraging Offline Data in Linear Latent Contextual BanditsChinmaya Kausik, Kevin Tan, Ambuj TewariICML 2025
- Stochastic Contextual Bandits with Long Horizon RewardsYuzhen Qin, Yingcong Li, Fabio Pasqualetti, Maryam Fazel et al.AAAI 2023 · 3 citations
