# Structured Stochastic Linear Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2016.

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

- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms](https://mlsanity.com/paper/2306.12383/) (2023)
- [Interactive Learning with Pricing for Optimal and Stable Allocations in Markets](https://mlsanity.com/paper/2212.06891/) (2022)
- [Interactive Recommendations for Optimal Allocations in Markets with Constraints](https://mlsanity.com/paper/2207.04143/) (2022)

## Abstract (arXiv)

The stochastic linear bandit problem proceeds in rounds where at each round the algorithm selects a vector from a decision set after which it receives a noisy linear loss parameterized by an unknown vector. The goal in such a problem is to minimize the (pseudo) regret which is the difference between the total expected loss of the algorithm and the total expected loss of the best fixed vector in hindsight. In this paper, we consider settings where the unknown parameter has structure, e.g., sparse, group sparse, low-rank, which can be captured by a norm, e.g., L1, L(1,2), nuclear norm. We focus on constructing confidence ellipsoids which contain the unknown parameter across all rounds with high-probability. We show the radius of such ellipsoids depend on the Gaussian width of sets associated with the norm capturing the structure. Such characterization leads to tighter confidence ellipsoids and, therefore, sharper regret bounds compared to bounds in the existing literature which are based on the ambient dimensionality.