mlsanityData to 7 Oct 2026

How Does Variance Shape the Regret in Contextual Bandits?

arXiv 2410.12713 ↗First posted 16 Oct 2024cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

We consider realizable contextual bandits with general function approximation, investigating how small reward variance can lead to better-than-minimax regret bounds. Unlike in minimax bounds, we show that the eluder dimension delu-a complexity measure of the function class-plays a crucial role in variance-dependent bounds. We consider two types of adversary: (1) Weak adversary: The adversary sets the reward variance before observing the learner's action. In this setting, we prove that a regret of Omega(√minA,deluLambda+delu) is unavoidable when delu≤√AT, where A is the number of actions, T is the total number of rounds, and Lambda is the total variance over T rounds. For the A≤ delu regime, we derive a nearly matching upper bound tildeO(√ALambda+delu) for the special case where the variance is revealed at the beginning of each round. (2) Strong adversary: The adversary sets the reward variance after observing the learner's action. We show that a regret of Omega(√deluLambda+delu) is unavoidable when √deluLambda+delu≤√AT. In this setting, we provide an upper bound of order tildeO(delu√Lambda+delu). Furthermore, we examine the setting where the function class additionally provides distributional information of the reward, as studied by Wang et al. (2024). We demonstrate that the regret bound tildeO(√deluLambda+delu) established in their work is unimprovable when √deluLambda+delu≤√AT. However, with a slightly different definition of the total variance and with the assumption that the reward follows a Gaussian distribution, one can achieve a regret of tildeO(√ALambda+delu).

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 29 of its 44 references that are in the map. First posted on arXiv 16 Oct 2024.

Builds on

29 of 44 references.

References · 29

  1. 2013Learning to Optimize Via Posterior Samplingcited by 253
  2. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  3. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  4. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  7. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  8. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  9. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  10. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  11. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  12. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
17 more
  1. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  2. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  3. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  4. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 35
  5. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  6. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  7. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  8. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  9. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  10. 2020Taking a hint: How to leverage loss predictors in contextual bandits?cited by 20
  11. 2018Make the Minority Great Again: First-Order Regret Bound for Contextual Banditscited by 17
  12. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  13. 2022Variance-Aware Sparse Linear Banditscited by 11
  14. 2024Online Estimation via Offline Estimation: An Information-Theoretic Frameworkcited by 11
  15. 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
  16. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  17. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 7; 2026: 2.

9 papers.

  1. 2025Variance-Dependent Regret Lower Bounds for Contextual Banditscited by 4
  2. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  3. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 1
  4. 2025Ksurf-Drone: Attention Kalman Filter for Contextual Bandit Optimization in Cloud Resource Allocationcited by 1
  5. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  6. 2025Constrained Online Decision-Making: A Unified Frameworkcited by 0
  7. 2025Second-Order Bounds for [0,1]-Valued Regression via Betting Losscited by 0
  8. 2025Complexity as Advantage: A Regret-Based Perspective on Emergent Structurecited by 0
  9. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0