The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

2011-02-12 · Aurélien Garivier, Olivier Cappé

This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm satisfies a uniformly better regret bound than UCB or UCB2; second, in the special case of Bernoulli rewards, it reaches the lower bound of Lai and Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm are also optimal for specific classes of (possibly unbounded) rewards, including those generated from exponential families of distributions. A large-scale numerical study comparing KL-UCB with its main competitors (UCB, UCB2, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and stable, including for short time horizons. KL-UCB is also the only method that always performs better than the basic UCB policy. Our regret bounds rely on deviations results of independent interest which are stated and proved in the Appendix. As a by-product, we also obtain an improved regret bound for the standard UCB algorithm.

📄 PDF Abstract BibTeX arXiv:1102.2490

Code (0)

등록된 구현이 없습니다.

Replicable Bandits with UCB based Exploration

2026-04-21 · Rohan Deb, Udaya Ghai, Karan Singh, Arindam Banerjee arxiv

We study replicable algorithms for stochastic multi-armed bandits (MAB) and linear bandits with UCB (Upper Confidence Bound) based exploration. A bandit algorithm is $ρ$-replicable if two executions using shared internal…

Multi-Armed Bandits

Lipschitz Bandits with Stochastic Delayed Feedback

2025-09-30 · Zhongxuan Liu, Yue Kang, Thomas C. M. Lee arxiv

The Lipschitz bandit problem extends stochastic bandits to a continuous action set defined over a metric space, where the expected reward function satisfies a Lipschitz condition. In this work, we introduce a new problem…

Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach

2026-06-18 · Haonan Xu, Yingying Li arxiv

This paper considers stochastic linear contextual bandits (SLCB) with bounded reward noise. Existing works typically assume sub-Gaussian reward noise and bounded expected rewards, under which the optimal regret bound sca…

Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits

2026-01-31 · Sahasrajit Sarmasarkar arxiv

We present the first algorithms for generalized linear contextual bandits under shuffle differential privacy and joint differential privacy. While prior work on private contextual bandits has been restricted to linear re…

Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions

2021-03-23 · Saeed Masoudian, Yevgeny Seldin

We derive improved regret bounds for the Tsallis-INF algorithm of Zimmert and Seldin (2021). We show that in adversarial regimes with a $(\Delta,C,T)$ self-bounding constraint the algorithm achieves $\mathcal{O}\left(\le…