Exploration via Feature Perturbation in Contextual Bandits

2025/10/20 by Yi, Seouh-won, Oh, Min-hwan
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2510.17390

Abstract

We propose feature perturbation, a simple yet effective exploration strategy for contextual bandits that injects randomness directly into feature inputs, instead of randomizing unknown parameters or adding noise to rewards. Remarkably, this algorithm achieves O(d√(T)) worst-case regret bound for generalized linear contextual bandits, while avoiding the O(d^3/2√(T)) regret typical of existing randomized bandit algorithms. Because our algorithm eschews parameter sampling, it is both computationally efficient and naturally extends to non-parametric or neural network models. We verify these advantages through empirical evaluations, demonstrating that feature perturbation not only surpasses existing methods but also unifies strong practical performance with the near-optimal regret guarantees.

Citations

• When and why randomised exploration works (in linear bandits)
• Improved Regret of Linear Ensemble Sampling
• A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits
• Generalized Linear Bandits with Limited Adaptivity
• Exploration via linearly perturbed loss minimisation
• Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion
• Jointly Efficient and Optimal Algorithms for Logistic Bandits
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
• Neural Thompson Sampling
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• Bandit Algorithms
• On Frequentist Regret of Linear Thompson Sampling
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability
• Improved Optimistic Algorithms for Logistic Bandits
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
• Randomized Exploration in Generalized Linear Bandits
• Perturbed-History Exploration in Stochastic Linear Bandits
• Randomized Prior Functions for Deep Reinforcement Learning
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Noisy Networks for Exploration
• Scalable Generalized Linear Bandits: Online Computation and Hashing
• Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles
• Deep Residual Learning for Image Recognition
• Explaining and Harnessing Adversarial Examples
• (More) Efficient Reinforcement Learning via Posterior Sampling
• The MNIST Database of Handwritten Digit Images for Machine Learning Research [Best of the Web]
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

Related

• Learning Neural Contextual Bandits Through Perturbed Rewards
• Neural Contextual Bandits with UCB-based Exploration
• Sparse Nonparametric Contextual Bandits
• Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits
• Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis