mlsanityData to 14 Oct 2026

On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure

arXiv 2211.15129 ↗First posted 28 Nov 2022stat.ML cs.AI cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We investigate the sample complexity of learning the optimal arm for multi-task bandit problems. Arms consist of two components: one that is shared across tasks (that we call representation) and one that is task-specific (that we call predictor). The objective is to learn the optimal (representation, predictor)-pair for each task, under the assumption that the optimal representation is common to all tasks. Within this framework, efficient learning algorithms should transfer knowledge across tasks. We consider the best-arm identification problem for a fixed confidence, where, in each round, the learner actively selects both a task, and an arm, and observes the corresponding reward. We derive instance-specific sample complexity lower bounds satisfied by any (δG,δH)-PAC algorithm (such an algorithm identifies the best representation with probability at least 1-δG, and the best predictor for a task with probability at least 1-δH). We devise an algorithm OSRL-SC whose sample complexity approaches the lower bound, and scales at most as H(Glog(1/δG)+ Xlog(1/δH)), with X,G,H being, respectively, the number of tasks, representations and predictors. By comparison, this scaling is significantly better than the classical best-arm identification algorithm that scales as HGXlog(1/δ).

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 18 of its 59 references that are in the map. First posted on arXiv 28 Nov 2022.

Builds on

18 of 59 references.

References · 18

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 239
  3. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  4. 2021Meta-Thompson Samplingcited by 63
  5. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 60
  6. 2020Impact of Representation Learning in Linear Banditscited by 52
  7. 2020Low-Rank Generalized Linear Bandit Problemscited by 49
  8. 2017Multi-Task Learning for Contextual Banditscited by 47
  9. 2020Meta-learning with Stochastic Linear Banditscited by 46
  10. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  11. 2013Sequential Transfer in Multi-armed Bandit with Finite Set of Modelscited by 38
  12. 2017Stochastic Low-Rank Banditscited by 28
6 more
  1. 2014Efficient Representations for Life-Long Learning and Autoencodingcited by 23
  2. 2016Regret Bounds for Lifelong Learningcited by 19
  3. 2019Stochastic Linear Bandits with Hidden Low Rank Structurecited by 15
  4. 2022Meta-Learning for Simple Regret Minimizationcited by 10
  5. 2016Multi-task and Lifelong Learning of Kernelscited by 7
  6. 2015Online Transfer Learning in Reinforcement Learning Domainscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 2.

5 papers.

  1. 2025Adaptive Exploration for Multi-Reward Multi-Policy Evaluationcited by 6
  2. 2025Pure Exploration with Feedback Graphscited by 4
  3. 2024Fair Best Arm Identification with Fixed Confidencecited by 3
  4. 2026Almost Asymptotically Optimal Active Clustering Through Pairwise Observationscited by 0
  5. 2026Sample Complexity of Transfer Learning: An Optimal Transport Approachcited by 0