Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Second Order Bounds for Contextual Bandits with Function Approximation
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.
Develops variance-aware (second-order) optimistic least squares algorithms for contextual bandits with general function approximation under mean-reward realizability, giving regret bounds scaling with the square root of cumulative noise variance times eluder dimension.
Problem
Regret of optimistic least squares for contextual bandits with function approximation scales with sqrt(T) even when reward noise variance is small; no variance-dependent (second-order) bounds existed under mean-reward realizability only.
Approach
An uncertainty-filtered multi-scale least squares procedure (regressions restricted to context-action pairs whose uncertainty width falls in dyadic buckets) yields variance-aware confidence sets; with unknown variance, cumulative variance is estimated via a filtered least squares residual and used to set confidence radii.
Key results
- Known-variance algorithm achieves regret O(sigma sqrt(eluder log(T|F|/delta) T) + B eluder log^2 T log(T|F|/delta)) for constant unknown variance sigma.
- Unknown-variance algorithm achieves regret O(eluder sqrt(sum_t sigma_t^2 log T log(T|F|/delta)) + B eluder log T log(T|F|/delta)) when variances change over time.
- Bounds improve on optimistic least squares' sqrt(T) dependence when noise variance is small.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use uncertainty-filtered multi-scale least squares with estimated variance instead of ordinary Optimistic Least Squares | Contextual bandits with function approximation · Unknown fixed variance | regret dependence on noise variance: B\sqrt{\delud(\mathcal{F}, B/T) \cdot T \cdot \log(T|\mathcal{F}|/\delta)} -> \sigma \sqrt{ \delud(\mathcal{F}, B/T) \lo | Helped |
| Use uncertainty-filtered multi-scale least squares with estimated variance instead of ordinary Optimistic Least Squares | Contextual bandits with function approximation · Changing unknown variances | regret dependence on cumulative variance: B\sqrt{ \delud(\mathcal{F}, B/T) \cdot T \cdot \log(T|\mathcal{F}|/\delta)} -> \delud\left(\mathcal{F}, \frac{B}{T}\righ | Helped |
| Use ordinary least squares without variance-aware uncertainty filtering | Contextual bandits with function approximation · Low-noise rewards | regret dependence on noise scale: B\sqrt{ \delud(\mathcal{F}, B/T) \cdot T \cdot \log(T|\mathcal{F}|/\delta)} | Hurt |
| Use linear eluder-dimension dependence for changing variances rather than the conjectured square-root dependence | Unknown-variance Second Order Optimistic Least Squares · Changing unknown variances | regret dependence on eluder dimension: \delud\left(\mathcal{F}, \frac{B}{T}\right)\sqrt{ \left(\sum_{t=1}^T \sigma_t^2 \right)\log(T)\log\left( T|\mathcal{F}|/ | Mixed |
Limitations
- Time-varying variance bound is linear in eluder dimension rather than square root, likely not sharp.
- Algorithms are computationally oblivious: confidence sets require optimization over the full function class F and multi-scale regressions per round.
- Purely theoretical; no experiments.
Experimental setup
Metrics: regret bound (theoretical)
Baselines: Optimistic Least Squares SquareCB
Builds on: Optimistic Least Squares eluder dimension SAVE Freedman's inequality
Closest papers by meaning
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- How Does Variance Shape the Regret in Contextual Bandits? (NeurIPS 2024 · similarity 0.91)
- On the Minimax Regret for Contextual Linear Bandits and Multi-Armed Bandits with Expert Advice (NeurIPS 2024 · similarity 0.90)
- Catoni Contextual Bandits are Robust to Heavy-tailed Rewards (ICML 2025 · similarity 0.90)
- Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.90)
- Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.89)
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.