Greedy sampling achieves efficient learning in contextual bandits
When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence
Machine Learning
Summary
Contextual bandits are models that help decide actions based on context to maximize rewards or preferences. This paper shows that a simple greedy approach to sampling actions can learn effectively without relying on a complex measure called the eluder dimension. The authors prove that when using KL regularization, this greedy method can get good results even with different types of feedback, including preferences between options. Their work shows when greedy exploration is enough and when more explicit exploration strategies might be needed.
What this means in practice
- •For online advertising teams: Improve targeting algorithms that choose ads by using greedy sampling with KL regularization to learn user preferences more efficiently.
- •For recommendation system developers: Design recommendation algorithms that adapt to user preference feedback without complex exploration, simplifying implementation and analysis.
Authors
Zichen Wang, Haoyang Hong, Huazheng Wang
Abstract
We study KL-regularized contextual bandits under both reward and preference feedback. We show that greedy sampling can achieve logarithmic regret without explicit dependence on the eluder dimension. For reward feedback, we establish an eluder-dimension-independent regret bound for a simple greedy algorithm that directly samples from the Gibbs policy induced by the estimated reward. We further extend this result to preference feedback under both the general preference and Bradley--Terry models, while also sharpening existing dimension-dependent guarantees. Our analysis reveals a trade-off between greedy sampling and upper confidence bound-style exploration: greedy sampling enjoys stronger guarantees when KL regularization is sufficiently strong, whereas additional exploration becomes preferable as the regularization weakens.