Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Conservative Contextual Bandits: Beyond Linear Representations
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 conservative contextual bandit algorithms (C-SquareCB and C-FastCB) for general non-linear costs using inverse gap weighting with online regression oracles, with neural network instantiations giving sub-linear and first-order regret under a baseline safety constraint.
Problem
Conservative contextual bandits with general non-linear cost functions, where the agent must keep cumulative cost within (1+alpha) of a baseline policy while minimizing regret; existing UCB-style methods only handle multi-armed or linear settings.
Approach
Combine inverse gap weighting exploration with an online regression oracle (squared or KL loss) and a per-round safety check that falls back to the baseline action when the cumulative-cost constraint could be violated, avoiding confidence sets around general function classes.
Key results
- C-SquareCB and C-FastCB show sub-linear cumulative regret and beat Conservative LinUCB on the openml datasets, with C-FastCB better on some datasets.
- Theory: C-SquareCB regret O(sqrt(KT) + K/alpha) with neural networks and OGD; C-FastCB first-order regret O(sqrt(K L* log L*) + K(1+1/alpha)).
- Empirically the conservative algorithms maintain the performance constraint while vanilla counterparts violate it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use C-SquareCB instead of Conservative Linear UCB | Conservative contextual bandits with neural cost estimation · OpenML multiclass classification datasets | cumulative regret | Helped |
| use C-FastCB instead of Conservative Linear UCB | Conservative contextual bandits with neural cost estimation · OpenML multiclass classification datasets | cumulative regret | Helped |
| use C-FastCB instead of C-SquareCB | Conservative contextual bandits · some OpenML multiclass classification datasets | cumulative regret | Helped |
| add the safety condition (ablation) | SquareCB · OpenML multiclass classification datasets | percentage of constraints violated | Helped |
| add the safety condition (ablation) | FastCB · OpenML multiclass classification datasets | percentage of constraints violated | Helped |
Surprising findings
- Prior work showed NeuralUCB and Neural Thompson Sampling regret bounds can be Omega(T) in the worst case, motivating the IGW-based approach.
Limitations
- Assumes a realizable function class and an online regression oracle with bounded regret.
- Regret term for baseline actions grows with the oracle regret in the general (non-neural) case, unlike the linear setting.
- Requires the NTK matrix to be positive definite, which holds only if context vectors do not overlap.
Experimental setup
Datasets: openml multiclass classification datasets
Benchmarks: openml multiclass classification bandit datasets
Metrics: cumulative regret percentage of constraint violations
Baselines: Conservative LinUCB vanilla SquareCB without safety condition vanilla FastCB without safety condition
Builds on: SquareCB FastCB Conservative LinUCB NeuralUCB Neural Tangent Kernel
Closest papers by meaning
- Conservative Contextual Linear Bandits (NeurIPS 2017 · similarity 0.94)
- Improved Algorithms for Conservative Exploration in Bandits (AAAI 2020 · similarity 0.92)
- Stage-wise Conservative Linear Bandits (NeurIPS 2020 · similarity 0.91)
- Contextual Conservative Interleaving Bandits (ICML 2023 · similarity 0.90)
- Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.89)
- High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions (ICML 2025 · similarity 0.88)
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.