Optimal Online Regret for Context-Lumpable Bandits
Not on the map. Why?
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.
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
12 of 16 references.
References · 12
- 2014Online Clustering of Banditscited by 102
- 2019Bilinear Bandits with Low-rank Structurecited by 55
- 2020Low-Rank Generalized Linear Bandit Problemscited by 49
- 2016On Context-Dependent Clustering of Banditscited by 44
- 2024Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problemscited by 20
- 2023Optimal Algorithms for Latent Bandits with Cluster Structurecited by 12
- 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 10
- 2024Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditscited by 10
- 2024Low-rank Matrix Bandits with Heavy-tailed Rewardscited by 7
- 2024Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recoverycited by 6
- 2023Context-lumpable stochastic banditscited by 4
- 2024Leveraging Offline Data in Linear Latent Contextual Banditscited by 3
Built on by
Not cited yet.