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

Oct 7, 2026

Expected Sample Complexity in Multi-Armed Bandits

Sample complexity is a widely used metric in sequential decision-making problems, defined as the number of suboptimal decisions during the interaction between the agent and an environment. We study the sample complexity of stochastic multi-armed bandit problems and introduce the expected sample complexity performance measure, analyzing it in a novel framework called approximately correct in expectation (ACE). We show that ACE guarantees imply almost sure convergence to the optimal expected reward, in contrast to high-probability guarantees found in other frameworks, and also show how to convert ACE guarantees into explicit expected regret bounds. We further show that, in contrast to existing measures, deterministic algorithms cannot obtain favorable ACE bounds, and analyze stochastic algorithms in two settings: when the allowed suboptimality level εε is known to the algorithm and when it is unknown. In the former, we devise an explore-then-εε-greedy algorithm, and in the latter, we analyze the expected sample complexity of Thompson sampling. Finally, we establish nearly matching lower bounds for both settings, showing that the algorithms are tight in εε and proving a performance separation between the two regimes.
Sep 29, 2026

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

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For KK-armed bandits with AA optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a O~(K−AKAT)\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big) minimax regret, where TT is the total number of interactions and O~(⋅)\tilde O(\cdot) drops all constant and logarithmic factors, improving the previous O~(KT/A)\tilde{O}(\sqrt{KT/A}) regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of AA up to O~(1)\tilde{O}(1) factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of KK-armed bandits with AA over the entire range of 1≤A≤K−11 \leq A \leq K-1.
Apr 16, 2026

Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

We study the tail behavior of regret in stochastic multi-armed bandits for algorithms that are asymptotically optimal in expectation. While minimizing expected regret is the classical objective, recent work shows that even such algorithms can exhibit heavy regret tails, incurring large regret with non-negligible probability. Existing sharp characterizations of regret tails are largely restricted to parametric settings, such as single-parameter exponential families. In this work, we extend the \KLinf\KLinf-UCB algorithm of to a broad nonparametric class of reward distributions satisfying mild assumptions, and establish its asymptotic optimality in expectation. We then analyze the tail behavior of its regret and derive a novel upper bound on the regret tail probability. As special cases, our results recover regret-tail guarantees for both bounded-support and heavy-tailed (moment-bounded) bandit models. Moreover, for the special case of finitely-supported reward distributions, our upper bound matches the known lower bound exactly. Our results thus provide a unified and tight characterization of regret tails for asymptotically optimal KL-based UCB algorithms, going beyond parametric models.