Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
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.
Builds Catoni-mean-based robust confidence sets for contextual bandits with general function approximation, giving variance-dependent regret with only logarithmic reward-range dependence, for known and unknown variance.
Problem
Contextual bandits with heavy-tailed rewards or large reward range R, where standard regret bounds scale polynomially with R, and general (nonlinear) function approximation lacks robust variance-aware methods.
Approach
Uses the Catoni mean to robustly estimate the excess loss between function pairs (instead of the reward mean), yielding confidence sets with only log R dependence; for unknown variance, a peeling/SupLinUCB-style algorithm with a Catoni-based aggregate variance estimate avoids per-round variance estimation.
Key results
- Catoni-OFUL achieves regret Õ(sqrt(sum_t σ_t^2 · d_F ln N_F) + d_F ln N_F), with only logarithmic dependence on reward range R, for known variance.
- A matching lower bound Ω(sqrt(E sum_t σ_t^2)) shows the leading-order variance term is optimal.
- VACB for unknown variance achieves Õ(d_F sqrt(sum_t σ_t^2 ln N_F) + d_F (ln N_F)^{3/4}), removing the T^{1/4} term present in prior linear unknown-variance bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace range-dependent regression analysis with Catoni-based variance-weighted excess-loss estimation | Catoni-OFUL · Stochastic contextual bandits with known variances | regret bound | Helped |
| Use peeling and aggregate-variance estimation instead of per-round variance estimation | VACB · Stochastic contextual bandits with unknown variances | regret bound | Helped |
| Use Catoni-OFUL rather than OLS | Non-linear contextual bandits with known variances · Stochastic contextual bandits, known variances | regret bound | Helped |
| Use VACB rather than Unknown-Variance OLS | Non-linear contextual bandits with unknown variances · Stochastic contextual bandits, unknown variances | regret bound | Helped |
Limitations
- Algorithms are not easy to implement (version-space structure and function-dependent theta choice in Catoni estimator).
- Unknown-variance bound has worse dependence on the eluder dimension (d_F to first power with extra factors) than known-variance case.
- Purely theoretical; no empirical evaluation.
Experimental setup
Metrics: regret bound (theoretical)
Baselines: Weighted OFUL Heavy-OFUL AdaOFUL SAVE DistUCB OLS Unknown-Variance OLS
Builds on: OFUL SupLinUCB Catoni mean estimator eluder dimension Heavy-OFUL
Closest papers by meaning
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.91)
- How Does Variance Shape the Regret in Contextual Bandits? (NeurIPS 2024 · similarity 0.91)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.90)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.89)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.89)
- Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling (ICLR 2024 · 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.