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

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

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

- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Adaptive Gradient-Based Meta-Learning Methods](https://mlsanity.com/paper/1906.02717/) (2019)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Provable Guarantees for Gradient-Based Meta-Learning](https://mlsanity.com/paper/1902.10644/) (2019)
- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [Learning-to-Learn Stochastic Gradient Descent with Biased Regularization](https://mlsanity.com/paper/1903.10399/) (2019)
- [Meta-learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2005.08531/) (2020)
- [Meta-learning for mixed linear regression](https://mlsanity.com/paper/2002.08936/) (2020)
- [Latent Bandits Revisited](https://mlsanity.com/paper/2006.08714/) (2020)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Sequential Transfer in Multi-armed Bandit with Finite Set of Models](https://mlsanity.com/paper/1307.6887/) (2013)
- [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Incremental Learning-to-Learn with Statistical Guarantees](https://mlsanity.com/paper/1803.08089/) (2018)
- [Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem](https://mlsanity.com/paper/1905.03125/) (2019)
- [Non-Stationary Latent Bandits](https://mlsanity.com/paper/2012.00386/) (2020)
- [Equipping Experts/Bandits with Long-term Memory](https://mlsanity.com/paper/1905.12950/) (2019)
- [Sparse Stochastic Bandits](https://mlsanity.com/paper/1706.01383/) (2017)
- [From Finite to Countable-Armed Bandits](https://mlsanity.com/paper/2105.10721/) (2021)
- [Algorithms for slate bandits with non-separable reward functions](https://mlsanity.com/paper/2004.09957/) (2020)
- [Meta-Learning Bandit Policies by Gradient Ascent](https://mlsanity.com/paper/2006.05094/) (2020)
- [Infinite Arms Bandit: Optimality via Confidence Bounds](https://mlsanity.com/paper/1805.11793/) (2018)
- [Transfer Learning in Bandits with Latent Continuity](https://mlsanity.com/paper/2102.02472/) (2021)

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

- [Provable Benefit of Multitask Representation Learning in Reinforcement Learning](https://mlsanity.com/paper/2206.05900/) (2022)
- [Meta-Learning Adversarial Bandit Algorithms](https://mlsanity.com/paper/2307.02295/) (2023)
- [Meta-Learning Adversarial Bandits](https://mlsanity.com/paper/2205.14128/) (2022)
- [Lifelong Bandit Optimization: No Prior and No Regret](https://mlsanity.com/paper/2210.15513/) (2022)
- [Meta Learning in Bandits within Shared Affine Subspaces](https://mlsanity.com/paper/2404.00688/) (2024)
- [Online Meta-Learning in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2205.15921/) (2022)
- [Beyond Task Diversity: Provable Representation Transfer for Sequential Multi-Task Linear Bandits](https://mlsanity.com/paper/2501.13390/) (2025)
- [Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2609.09907/) (2026)

## 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.