# Stochastic Linear Bandits with Parameter Noise

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

## Key facts

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

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

- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [On the Complexity of Bandit Linear Optimization](https://mlsanity.com/paper/1408.2368/) (2014)
- [Variance-Dependent Regret Lower Bounds for Contextual Bandits](https://mlsanity.com/paper/2503.12020/) (2025)
- [Rarely-switching linear bandits: optimization of causal effects for the real world](https://mlsanity.com/paper/1905.13121/) (2019)
- [Risk-Aware Linear Bandits: Theory and Applications in Smart Order Routing](https://mlsanity.com/paper/2208.02389/) (2022)

## Abstract (arXiv)

We study the stochastic linear bandits with parameter noise model, in which the reward of action a is a^top θ where θ is sampled i.i.d. We show a regret upper bound of widetildeO (√d T log (K/δ) σ2max) for a horizon T, general action set of size K of dimension d, and where σ2max is the maximal variance of the reward for any action. We further provide a lower bound of widetildeOmega (d √T σ2max) which is tight (up to logarithmic factors) whenever log (K) ≈ d. For more specific action sets, ℓp unit balls with p ≤ 2 and dual norm q, we show that the minimax regret is widetildeTheta (√dT σ2q), where σ2q is a variance-dependent quantity that is always at most 4. This is in contrast to the minimax regret attainable for such sets in the classic additive noise model, where the regret is of order d √T. Surprisingly, we show that this optimal (up to logarithmic factors) regret bound is attainable using a very simple explore-exploit algorithm.