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

arXiv: https://arxiv.org/abs/2211.15129 · HTML: https://mlsanity.com/paper/2211.15129/

## 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 (most cited first, 18 of 18)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Impact of Representation Learning in Linear Bandits](https://mlsanity.com/paper/2010.06531/) (2020)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Multi-Task Learning for Contextual Bandits](https://mlsanity.com/paper/1705.08618/) (2017)
- [Meta-learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2005.08531/) (2020)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Sequential Transfer in Multi-armed Bandit with Finite Set of Models](https://mlsanity.com/paper/1307.6887/) (2013)
- [Stochastic Low-Rank Bandits](https://mlsanity.com/paper/1712.04644/) (2017)
- [Efficient Representations for Life-Long Learning and Autoencoding](https://mlsanity.com/paper/1411.1490/) (2014)
- [Regret Bounds for Lifelong Learning](https://mlsanity.com/paper/1610.08628/) (2016)
- [Stochastic Linear Bandits with Hidden Low Rank Structure](https://mlsanity.com/paper/1901.09490/) (2019)
- [Meta-Learning for Simple Regret Minimization](https://mlsanity.com/paper/2202.12888/) (2022)
- [Multi-task and Lifelong Learning of Kernels](https://mlsanity.com/paper/1602.06531/) (2016)
- [Online Transfer Learning in Reinforcement Learning Domains](https://mlsanity.com/paper/1507.00436/) (2015)

## Built on by (most cited first, 5 of 5)

- [Adaptive Exploration for Multi-Reward Multi-Policy Evaluation](https://mlsanity.com/paper/2502.02516/) (2025)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [Fair Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2408.17313/) (2024)
- [Almost Asymptotically Optimal Active Clustering Through Pairwise Observations](https://mlsanity.com/paper/2602.05690/) (2026)
- [Sample Complexity of Transfer Learning: An Optimal Transport Approach](https://mlsanity.com/paper/2605.20545/) (2026)

## 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/δ).