Near-Optimal Regret for KL-Regularized Multi-Armed Bandits

Researchers developed a new analysis of KL-regularized multi-armed bandits (MABs) using KL-UCB algorithm, achieving near-optimal regret bounds. The study provides the first high-probability regret bound with linear dependence on the number of arms and establishes matching lower bounds, offering comprehensive understanding across all regularization regimes.