# Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2024.

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

- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure](https://mlsanity.com/paper/2503.04010/) (2025)
- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Infrequent Exploration in Linear Bandits](https://mlsanity.com/paper/2510.26000/) (2025)
- [Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?](https://mlsanity.com/paper/2601.20694/) (2026)
- [Personalized Alignment Revisited: The Necessity and Sufficiency of User Diversity](https://mlsanity.com/paper/2605.09119/) (2026)
- [Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits](https://mlsanity.com/paper/2609.28718/) (2026)
- [Elicitation and Decision Geometry in Single-Index Bandits](https://mlsanity.com/paper/2609.35622/) (2026)

## Abstract (arXiv)

We study the performance guarantees of exploration-free greedy algorithms for the linear contextual bandit problem. We introduce a novel condition, named the textitLocal Anti-Concentration (LAC) condition, which enables a greedy bandit algorithm to achieve provable efficiency. We show that the LAC condition is satisfied by a broad class of distributions, including Gaussian, exponential, uniform, Cauchy, and Student's~t distributions, along with other exponential family distributions and their truncated variants. This significantly expands the class of distributions under which greedy algorithms can perform efficiently. Under our proposed LAC condition, we prove that the cumulative expected regret of the greedy algorithm for the linear contextual bandit is bounded by O(operatornamepoly log T). Our results establish the widest range of distributions known to date that allow a sublinear regret bound for greedy algorithms, further achieving a sharp poly-logarithmic regret.