# Lasso Bandit with Compatibility Condition on Optimal Arm

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2024.

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

- [Linear Bandits with Partially Observable Features](https://mlsanity.com/paper/2502.06142/) (2025)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Navigating Sparsities in High-Dimensional Linear Contextual Bandits](https://mlsanity.com/paper/2510.08435/) (2025)
- [Infrequent Exploration in Linear Bandits](https://mlsanity.com/paper/2510.26000/) (2025)

## Abstract (arXiv)

We consider a stochastic sparse linear bandit problem where only a sparse subset of context features affects the expected reward function, i.e., the unknown reward parameter has a sparse structure. In the existing Lasso bandit literature, the compatibility conditions, together with additional diversity conditions on the context features are imposed to achieve regret bounds that only depend logarithmically on the ambient dimension d. In this paper, we demonstrate that even without the additional diversity assumptions, the textitcompatibility condition on the optimal arm is sufficient to derive a regret bound that depends logarithmically on d, and our assumption is strictly weaker than those used in the lasso bandit literature under the single-parameter setting. We propose an algorithm that adapts the forced-sampling technique and prove that the proposed algorithm achieves O(polylog dT) regret under the margin condition. To our knowledge, the proposed algorithm requires the weakest assumptions among Lasso bandit algorithms under the single-parameter setting that achieve O(polylog dT) regret. Through numerical experiments, we confirm the superior performance of our proposed algorithm.