# Online Learning with Low Rank Experts

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2016.

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

- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)
- [Pure exploration in multi-armed bandits with low rank structure using oblivious sampler](https://mlsanity.com/paper/2306.15856/) (2023)
- [The Hidden Game Problem](https://mlsanity.com/paper/2510.03845/) (2025)

## Abstract (arXiv)

We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown d-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank d. For the stochastic model we show a tight bound of Theta(√dT), and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of O(d√T) and a lower bound of Omega(√dT).