# Variance-Dependent Regret Lower Bounds for Contextual Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 15 Mar 2025.

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

- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (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)
- [Variance-Aware Sparse Linear Bandits](https://mlsanity.com/paper/2205.13450/) (2022)
- [How Does Variance Shape the Regret in Contextual Bandits?](https://mlsanity.com/paper/2410.12713/) (2024)

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

- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Stochastic Linear Bandits with Parameter Noise](https://mlsanity.com/paper/2601.23164/) (2026)
- [Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts](https://mlsanity.com/paper/2606.09802/) (2026)
- [Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set](https://mlsanity.com/paper/2607.23679/) (2026)

## Abstract (arXiv)

Variance-dependent regret bounds for linear contextual bandits, which improve upon the classical tildeO(d√K) regret bound to tildeO(d√sumk=1Kσk2), where d is the context dimension, K is the number of rounds, and σ2k is the noise variance in round k, has been widely studied in recent years. However, most existing works focus on the regret upper bounds instead of lower bounds. To our knowledge, the only lower bound is from Jia et al. (2024), which proved that for any eluder dimension delu and total variance budget Lambda, there exists an instance with sumk=1Kσk2≤ Lambda for which any algorithm incurs a variance-dependent lower bound of Omega(√deluLambda). However, this lower bound has a √d gap with existing upper bounds. Moreover, it only considers a fixed total variance budget Lambda and does not apply to a general variance sequence σ12,ldots,σK2. In this paper, to overcome the limitations of Jia et al. (2024), we consider the general variance sequence under two settings. For a prefixed sequence, where the entire variance sequence is revealed to the learner at the beginning of the learning process, we establish a variance-dependent lower bound of Omega(d √sumk=1Kσk2 /log K) for linear contextual bandits. For an adaptive sequence, where an adversary can generate the variance σk2 in each round k based on historical observations, we show that when the adversary must generate σk2 before observing the decision set Dk, a similar lower bound of Omega(d√ sumk=1Kσk2 /log6(dK)) holds. In both settings, our results match the upper bounds of the SAVE algorithm (Zhao et al., 2023) up to logarithmic factors.