Variance-Dependent Regret Lower Bounds for Contextual Bandits

Jiafan He, Quanquan Gu

Variance-dependent regret bounds for linear contextual bandits, which improve upon the classical $\tilde{O}(d\sqrt{K})$ regret bound to $\tilde{O}(d\sqrt{{\sum }_{k=1}^K{\sigma }_k^2})$, wher…