cs.LGFeb 20, 2025

Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling

Authors: Hao Qin, Kwang-Sung Jun, Chicheng Zhang

Organizations: Department of Mathematics, University of Arizona, Tucson, AZ 85721 · Department of Computer Science, University of Arizona, Tucson, AZ 85721

Abstract

We study the problem of KK-armed bandits with reward distributions belonging to a one-parameter exponential distribution family. In the literature, several criteria have been proposed to evaluate the performance of such algorithms, including Asymptotic Optimality, Minimax Optimality, Sub-UCB, and variance-adaptive regret bound. Thompson Sampling-based and Upper Confidence Bound-based algorithms have been employed to achieve some of these criteria. However, none of these algorithms simultaneously satisfy all the aforementioned criteria. In this paper, we design an algorithm, Exponential Kullback-LeiblerMaillard Sampling (abbrev. Exp-KL-MS), that achieves multiple optimality criteria simultaneously, including Asymptotic Optimality, minimax ratio with a ln⁡(K)\sqrt{\ln (K)} factor, Sub-UCB, and a variance-adaptive regret bound. Our algorithm design follows the Minimum Empirical Divergence framework~\citep{honda2011asymptotically,maillard2011apprentissage}, with the exploration probability of arm aa proportional to exp(−L(Nt−1,a)KL(μ^t−1,a,max⁡a′μ^t−1,a′))\text{exp}\left(-L(N_{t-1, a}) \text{KL}(\hatμ_{t-1, a}, \max_{a'} \hatμ_{t-1, a'})\right), where L(⋅)L(\cdot) is an inverse temperature function, Nt−1,aN_{t-1, a} is the number of times arm aa has been pulled before time tt, μ^t−1,a\hatμ_{t-1, a} is the empirical mean of arm aa before time tt, and KL(⋅,⋅)\text{KL}(\cdot, \cdot) is the Kullback-Leibler divergence between two distributions in the one-parameter exponential distribution family. Our analysis allows different choices of inverse temperature function L(k)L(k). We also provide numerical simulations demonstrating the effectiveness of our algorithms.

Figures & tables

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Expected Sample Complexity in Multi-Armed Bandits

    Oct 7, 2026Nadav Sukenik, Nadav MerlisMulti-Armed BanditsRegret Minimization

  2. Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

    Sep 29, 2026Kaixuan Ji, Qiwei Di, Qingyue Zhao +2Multi-Armed BanditsMinimax Regret

  3. Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

    Apr 16, 2026Subhodip Panda, Shubhada AgrawalMulti-Armed BanditsUCB Algorithms