Research map / Bandits and online learning / Contextual bandits and Thompson sampling
How Does Variance Shape the Regret in Contextual Bandits?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies how reward variance shapes regret in realizable contextual bandits with general function approximation, proving eluder-dimension-dependent variance-aware lower and upper bounds under weak and strong adversaries and with model classes.
Problem
Variance-dependent (second-order) regret for realizable contextual bandits with general function classes, where the eluder dimension may affect whether regret can scale with total variance rather than rounds T.
Approach
Shows the eluder dimension controls variance-dependent regret: a weak adversary yields Omega(sqrt(min{A,d} Lambda)+d) lower bound, achieved by VarCB which combines SquareCB-style inverse gap weighting, a disagreement check, variance-weighted confidence sets, and a Prod-based online regression oracle; a strong adversary yields a d*sqrt(Lambda) type bound.
Key results
- Weak adversary with revealed variance: regret lower bound Omega(sqrt(min{A,d} Lambda)+d) and matching upper bound O~(sqrt(A Lambda)+d) when A<=d<=sqrt(AT).
- Strong adversary: lower bound Omega(sqrt(d Lambda)+d) and upper bound O~(d sqrt(Lambda)+d), off by sqrt(d).
- With a Gaussian model class, O~(sqrt(A Lambda_inf)+d) upper bound matching a lower bound; the prior bound of O~(sqrt(d Lambda_circ)+d) is shown to be unimprovable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reveal the variance before each round in the weak-adversary setting | VarCB · Weak adversary, contextual bandits | regret upper bound: \sqrt{A\Lambda \log|\mathcal{F}|} + \delu\log|\mathcal{F}| | Helped |
| Let the adversary choose variance after observing the learner's action, rather than before it | Realizable contextual bandits · Strong adversary versus weak adversary | regret lower bound: \min\{\sqrt{\delu\Lambda} + \delu, \sqrt{AT}\} versus \sqrt{\min\{A,\delu\}\Lambda} + \delu | Hurt |
| Use a Gaussian model class that provides reward-distribution information | DistVarCB · Gaussian model class, maximum action variance | regret upper bound: \sqrt{A\Lambda_{\infty} \log|\mathcal{M}|} + \delu\log|\mathcal{M}| | Helped |
| Measure variance using chosen actions rather than maximum action variance | Model-class contextual bandits · Model class, variance of chosen actions | regret lower bound: \sqrt{\delu\Lambda_{\circ}} + \delu | Mixed |
Surprising findings
- The conjecture that regret scales as sqrt(A Lambda) regardless of eluder dimension fails; the eluder dimension contributes a lower-order term even when variance is small.
- The natural minimax-to-second-order replacement of T by variance does not hold in general contextual bandits.
Limitations
- Upper bound for weak adversary requires variance revealed at the start of each round; general unrevealed case open.
- Strong adversary upper bound is off from lower bound by a sqrt(d) factor.
- Distributional upper bound assumes Gaussian noise.
Experimental setup
Metrics: regret
Baselines: SquareCB AdaCB SAVE
Builds on: SquareCB eluder dimension SAVE AdaCB Prod algorithm
Closest papers by meaning
- Catoni Contextual Bandits are Robust to Heavy-tailed Rewards (ICML 2025 · similarity 0.91)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.91)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.90)
- Mixed-Effects Contextual Bandits (AAAI 2024 · similarity 0.90)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.