# Improved Regret Bounds for Tracking Experts with Memory

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 50 references that are in the map.
- First posted on arXiv 24 Jun 2021.

## Builds on (most cited first, 9 of 9)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [Efficient tracking of a growing number of experts](https://mlsanity.com/paper/1708.09811/) (2017)
- [Equipping Experts/Bandits with Long-term Memory](https://mlsanity.com/paper/1905.12950/) (2019)
- [Switching Portfolios](https://mlsanity.com/paper/1301.7413/) (2013)
- [Universal Codes from Switching Strategies](https://mlsanity.com/paper/1311.6536/) (2013)
- [Online Multitask Learning with Long-Term Memory](https://mlsanity.com/paper/2008.07055/) (2020)

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

- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [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 address the problem of sequential prediction with expert advice in a non-stationary environment with long-term memory guarantees in the sense of Bousquet and Warmuth [4]. We give a linear-time algorithm that improves on the best known regret bounds [26]. This algorithm incorporates a relative entropy projection step. This projection is advantageous over previous weight-sharing approaches in that weight updates may come with implicit costs as in for example portfolio optimization. We give an algorithm to compute this projection step in linear time, which may be of independent interest.