# Equipping Experts/Bandits with Long-term Memory

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2019.

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

- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Refined Regret for Adversarial MDPs with Linear Function Approximation](https://mlsanity.com/paper/2301.12942/) (2023)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms](https://mlsanity.com/paper/2202.13001/) (2022)
- [Improved Regret Bounds for Tracking Experts with Memory](https://mlsanity.com/paper/2106.13021/) (2021)
- [Adversarial Network Optimization under Bandit Feedback: Maximizing Utility in Non-Stationary Multi-Hop Networks](https://mlsanity.com/paper/2408.16215/) (2024)
- [Gradient-Free Warm-Start Library Recovery: an Amortized-Regret Separation](https://mlsanity.com/paper/2606.21253/) (2026)
- [Tracking a Small Set of Experts in Online Convex Optimization](https://mlsanity.com/paper/2610.20416/) (2026)

## Abstract (arXiv)

We propose the first reduction-based approach to obtaining long-term memory guarantees for online learning in the sense of Bousquet and Warmuth, 2002, by reducing the problem to achieving typical switching regret. Specifically, for the classical expert problem with K actions and T rounds, using our framework we develop various algorithms with a regret bound of order O(√T(Sln T + n ln K)) compared to any sequence of experts with S-1 switches among n ≤ minS, K distinct experts. In addition, by plugging specific adaptive algorithms into our framework we also achieve the best of both stochastic and adversarial environments simultaneously. This resolves an open problem of Warmuth and Koolen, 2014. Furthermore, we extend our results to the sparse multi-armed bandit setting and show both negative and positive results for long-term memory guarantees. As a side result, our lower bound also implies that sparse losses do not help improve the worst-case regret for contextual bandits, a sharp contrast with the non-contextual case.