# Optimal Online Regret for Context-Lumpable Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 16 references that are in the map.
- First posted on arXiv 13 Oct 2026.

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

- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Leveraging Offline Data in Linear Latent Contextual Bandits](https://mlsanity.com/paper/2405.17324/) (2024)

## Abstract (arXiv)

We study stochastic contextual bandits with an unknown context-lumpable structure. The S contexts are partitioned into r blocks, and every arm has the same mean reward across contexts in the same block. Under arbitrary context distributions and without separation assumptions, we design an algorithm with expected regret widetildeO(√r(S+K)T), matching the lower bound of Lee et al. (2023) up to logarithmic factors and improving their previous upper bound by a factor of r. The algorithm operates over dyadic accuracy levels, using a baseline policy and confidence-based early stopping to control exploration. It then performs cross-context elimination: since rewards are identical within a block, one selected arm eliminates all surviving records from that block, requiring at most r selections at each level. Multi-scale exploration assigns finer accuracies to frequent blocks and coarser accuracies to rare blocks, yielding a near-optimal arm for every block while keeping the weighted policy error small.