mlsanityData to 7 Oct 2026

Impact of Representation Learning in Linear Bandits

arXiv 2010.06531 ↗First posted 13 Oct 2020cs.LGcited by 51

Not on the map. Why?

Abstract (arXiv)

We study how representation learning can improve the efficiency of bandit problems. We study the setting where we play T linear bandits with dimension d concurrently, and these T bandit tasks share a common k (ll d) dimensional linear representation. For the finite-action setting, we present a new algorithm which achieves widetildeO(T√kN + √dkNT) regret, where N is the number of rounds we play for each bandit. When T is sufficiently large, our algorithm significantly outperforms the naive algorithm (playing T bandits independently) that achieves widetildeO(T√d N) regret. We also provide an Omega(T√kN + √dkNT) regret lower bound, showing that our algorithm is minimax-optimal up to poly-logarithmic factors. Furthermore, we extend our algorithm to the infinite-action setting and obtain a corresponding regret bound which demonstrates the benefit of representation learning in certain regimes. We also present experiments on synthetic and real-world data to illustrate our theoretical findings and demonstrate the effectiveness of our proposed algorithms.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 18; 2023: 7; 2024: 12; 2025: 5; 2026: 4.

51 papers.

Sort:

By area:

  1. 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
  2. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  3. 2021On the Power of Multitask Representation Learning in Linear MDPcited by 30
  4. 2021Multi-Agent Multi-Armed Bandits with Limited Communicationcited by 29
  5. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  6. 2022Towards Sample-efficient Overparameterized Meta-learningcited by 21
  7. 2022Multi-task Representation Learning with Stochastic Linear Banditscited by 20
  8. 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representationcited by 16
  9. 2022Mixed-Effect Thompson Samplingcited by 14
  10. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  11. 2022Non-Stationary Representation Learning in Sequential Linear Banditscited by 13
  12. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 13
38 more
  1. 2022Provable General Function Class Representation Learning in Multitask Bandits and MDPscited by 12
  2. 2024Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learningcited by 10
  3. 2022Linear Stochastic Bandits over a Bit-Constrained Channelcited by 9
  4. 2022Distributed Linear Bandits under Communication Constraintscited by 8
  5. 2023Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricingcited by 8
  6. 2022Meta Representation Learning with Contextual Linear Banditscited by 6
  7. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  8. 2024Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Banditscited by 6
  9. 2021Incentivizing Exploration in Linear Bandits under Information Gapcited by 5
  10. 2022Joint Representation Training in Sequential Tasks with Shared Structurecited by 5
  11. 2022Reward Imputation with Sketching for Contextual Batched Banditscited by 5
  12. 2022On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structurecited by 5
  13. 2023Multi-task Representation Learning for Pure Exploration in Bilinear Banditscited by 5
  14. 2024Diffusion Models Meet Contextual Banditscited by 5
  15. 2024Task Diversity Shortens the ICL Plateaucited by 5
  16. 2021Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Banditscited by 4
  17. 2022Meta Learning MDPs with Linear Transition Modelscited by 4
  18. 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
  19. 2024Meta Learning in Bandits within Shared Affine Subspacescited by 4
  20. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 3
  21. 2023Provable Pathways: Learning Multiple Tasks over Multiple Pathscited by 3
  22. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  23. 2024Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraintscited by 2
  24. 2024Learning Goal-Conditioned Representations for Language Reward Modelscited by 2
  25. 2022Representation Learning for Context-Dependent Decision-Makingcited by 1
  26. 2023Online Modeling and Monitoring of Dependent Processes under Resource Constraintscited by 1
  27. 2024IBCB: Efficient Inverse Batched Contextual Bandit for Behavioral Evolution Historycited by 1
  28. 2024Open Problem: Active Representation Learningcited by 1
  29. 2024Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samplescited by 1
  30. 2025Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Banditscited by 1
  31. 2025Towards Understanding the Benefit of Multitask Representation Learning in Decision Processcited by 1
  32. 2025SharedRep-RLHF: A Shared Representation Approach to RLHF with Diverse Preferencescited by 1
  33. 2026Provable Multi-Task Reinforcement Learning: A Representation Learning Framework with Low Rank Rewardscited by 1
  34. 2024FCOM: A Federated Collaborative Online Monitoring Framework via Representation Learningcited by 0
  35. 2025Decentralized Contextual Bandits with Network Adaptivitycited by 0
  36. 2025Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measurecited by 0
  37. 2026RepUCB: Representation Learning-Based UCB for Heterogeneous Multi-Task Linear Banditscited by 0
  38. 2026Multi-Task Representation Learning for Conservative Linear Banditscited by 0

50 most cited of 51 All 51 (JSON)