Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Exploration via Feature Perturbation 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.
Proposes feature perturbation (FP), which injects shared Gaussian noise into arm feature vectors instead of parameters or rewards, achieving O~(d sqrt(T)) worst-case regret for generalized linear contextual bandits.
Problem
Randomized exploration in contextual bandits (TS, PHE) suffers an extra sqrt(d) factor in worst-case regret, O~(d^{3/2} sqrt T), versus the O~(d sqrt T) of optimistic methods; the question is whether randomized exploration can close this gap.
Approach
Perturb the observed arm feature vectors with a shared Gaussian scalar-direction noise scaled by per-arm uncertainty (weighted Gram matrix), then select greedily under the fixed MLE; the one-dimensional projection avoids the union bound over d dimensions that causes the sqrt(d) penalty.
Key results
- GLM-FP achieves O~(d sqrt(kappa_* T) + d^2/kappa) regret, avoiding the sqrt(d) penalty of TS-type randomized methods and removing dependence on the number of arms.
- In linear and logistic simulations averaged over 100 runs, GLM-FP reports the lowest cumulative regret across tested dimensions, outperforming RandUCB, PHE, TS, UCB and epsilon-greedy.
- Neural FP (DeepFP) with arm-wise Gaussian input noise of variance I/t outperforms NeuralUCB, NeuralTS and FTPL on shuttle, isolet and mushroom.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use feature perturbation for exploration | GLM-FP · Linear contextual bandits | cumulative regret | Helped |
| Use feature perturbation for exploration | GLM-FP · Logistic contextual bandits | cumulative regret | Helped |
| Use feature perturbation for exploration | DeepFP · Shuttle | cumulative regret | Helped |
| Use feature perturbation for exploration | DeepFP · Isolet | cumulative regret | Helped |
| Use feature perturbation for exploration | DeepFP · Mushroom | cumulative regret | Helped |
| Use feature perturbation instead of parameter sampling | GLM-FP versus Thompson Sampling · Generalized linear contextual bandits | worst-case regret bound | Helped |
Surprising findings
- Under linear models, feature perturbation induces the same per-arm marginal distribution as RandUCB and TS, yet the coupled shared perturbation yields a better regret bound than TS.
Limitations
- Regret bound depends on instance-dependent kappa, which may scale exponentially small for logistic bandits.
- Theoretical guarantees are given for GLMs; neural extension is empirical only.
Experimental setup
Datasets: shuttle isolet mushroom
Benchmarks: UCI shuttle UCI isolet UCI mushroom
Metrics: cumulative regret
Baselines: epsilon-greedy UCB LinTS PHE RandUCB NeuralUCB NeuralTS FTPL
Builds on: Thompson Sampling Perturbed History Exploration RandUCB OFUGLB NeuralUCB
Closest papers by meaning
- Learning Neural Contextual Bandits through Perturbed Rewards (ICLR 2022 · similarity 0.92)
- Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates (ICML 2026 · similarity 0.91)
- Neural Contextual Bandits with UCB-based Exploration (ICML 2020 · similarity 0.91)
- A Perturbation Approach to Unconstrained Linear Bandits (ICML 2026 · similarity 0.90)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.89)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 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.