mlsanityData to 14 Oct 2026

Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms

arXiv 2202.13001 ↗First posted 25 Feb 2022cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We study a sequential decision problem where the learner faces a sequence of K-armed bandit tasks. The task boundaries might be known (the bandit meta-learning setting), or unknown (the non-stationary bandit setting). For a given integer M≤ K, the learner aims to compete with the best subset of arms of size M. We design an algorithm based on a reduction to bandit submodular maximization, and show that, for T rounds comprised of N tasks, in the regime of large number of tasks and small number of optimal arms M, its regret in both settings is smaller than the simple baseline of tildeO(√KNT) that can be obtained by using standard algorithms designed for non-stationary bandit problems. For the bandit meta-learning problem with fixed task length τ, we show that the regret of the algorithm is bounded as tildeO(NM√M τ+N2/3Mτ). Under additional assumptions on the identifiability of the optimal arms in each task, we show a bandit meta-learning algorithm with an improved tildeO(N√M τ+N1/2√M K τ) regret.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 27 of its 63 references that are in the map. First posted on arXiv 25 Feb 2022.

Builds on

27 of 63 references.

References · 27

  1. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
  2. 2019Adaptive Gradient-Based Meta-Learning Methodscited by 183
  3. 2020Provable Meta-Learning of Linear Representationscited by 161
  4. 2014Online Clustering of Banditscited by 102
  5. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  6. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
  7. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  8. 2019Provable Guarantees for Gradient-Based Meta-Learningcited by 67
  9. 2021Meta-Thompson Samplingcited by 63
  10. 2019Learning-to-Learn Stochastic Gradient Descent with Biased Regularizationcited by 49
  11. 2020Meta-learning with Stochastic Linear Banditscited by 46
  12. 2020Meta-learning for mixed linear regressioncited by 44
15 more
  1. 2020Latent Bandits Revisitedcited by 44
  2. 2015Simple regret for infinitely many armed banditscited by 39
  3. 2013Sequential Transfer in Multi-armed Bandit with Finite Set of Modelscited by 38
  4. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  5. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  6. 2018Incremental Learning-to-Learn with Statistical Guaranteescited by 16
  7. 2019Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problemcited by 14
  8. 2020Non-Stationary Latent Banditscited by 12
  9. 2019Equipping Experts/Bandits with Long-term Memorycited by 10
  10. 2017Sparse Stochastic Banditscited by 8
  11. 2021From Finite to Countable-Armed Banditscited by 8
  12. 2020Algorithms for slate bandits with non-separable reward functionscited by 6
  13. 2020Meta-Learning Bandit Policies by Gradient Ascentcited by 5
  14. 2018Infinite Arms Bandit: Optimality via Confidence Boundscited by 4
  15. 2021Transfer Learning in Bandits with Latent Continuitycited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 1; 2024: 1; 2025: 1; 2026: 1.

8 papers.

  1. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  2. 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
  3. 2022Meta-Learning Adversarial Banditscited by 5
  4. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 4
  5. 2024Meta Learning in Bandits within Shared Affine Subspacescited by 4
  6. 2022Online Meta-Learning in Adversarial Multi-Armed Banditscited by 2
  7. 2025Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Banditscited by 1
  8. 2026Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Banditscited by 0