How Does Variance Shape the Regret in Contextual Bandits?

2024/10/16 by Zeyu Jia, Jia, Zeyu, Jian Qian +5 · 6 citations
Decision Sciences · #Decision-Making and Behavioral Economics #FOS: Computer and information sciences #Forecasting Techniques and Applications #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.2410.12713

openalex publication_date 2024/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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 d_elu-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 Ω(√min\A,d_elu\Λ+d_elu) is unavoidable when d_elu≤√(AT), where A is the number of actions, T is the total number of rounds, and Λ is the total variance over T rounds. For the A≤ d_elu regime, we derive a nearly matching upper bound O(√(AΛ)+d_elu) 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 Ω(√(d_eluΛ)+d_elu) is unavoidable when √(d_eluΛ)+d_elu≤√(AT). In this setting, we provide an upper bound of order O(d_elu√Λ+d_elu). 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 O(√(d_eluΛ)+d_elu) established in their work is unimprovable when √d_eluΛ+d_elu≤√(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 O(√(AΛ)+d_elu).

Cited by

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
• Ksurf-Drone: Attention Kalman Filter for Contextual Bandit Optimization in Cloud Resource Allocation
• Complexity as Advantage: A Regret-Based Perspective on Emergent Structure
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
• Second-Order Bounds for [0,1]-Valued Regression via Betting Loss
• Constrained Online Decision-Making: A Unified Framework

Related

• Variance-Dependent Regret Lower Bounds for Contextual Bandits
• Second Order Bounds for Contextual Bandits with Function Approximation
• Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
• Sparsity, variance and curvature in multi-armed bandits
• Linear Contextual Bandits with Adversarial Corruptions