When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence
This work shows that simple greedy sampling can achieve polylogarithmic regret without explicit dependence on this complexity measure, and reveals a trade-off between greedy sampling and upper confidence bound-style exploration: greedy sampling enjoys stronger regret guarantees when KL regularization is sufficiently st...