SOURCE-LINKED INTELLIGENCE

When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence

arXiv · AI, language, vision and robotics · article · Sep 11, 2026 · UTC

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 betwe

Read original source ↗ Open in workspace

recordType

paper

region

Global