← 研踪 PaperTrailarXiv:2502.14379 · v3
Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
首次提交 2025-02-20 17:12
版本更新 2026-11-04 12:26
雷达观测 2026-11-05 11:10
摘要
We study the problem of $K$-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 $\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 $a$ proportional to $\text{exp}\left(-L(N_{t-1, a}) \text{KL}(\hatμ_{t-1, a}, \max_{a'} \hatμ_{t-1, a'})\right)$, where $L(\cdot)$ is an inverse temperature function, $N_{t-1, a}$ is the number of times arm $a$ has been pulled before time $t$, $\hatμ_{t-1, a}$ is the empirical mean of arm $a$ before time $t$, and $\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)$. We also provide numerical simulations demonstrating the effectiveness of our algorithms.
作者备注：12 pages of the main body, 52 pages in total, accepted by TMLR
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-04 12:26 · 最新观测版本
Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
We study the problem of $K$-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 $\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 $a$ proportional to $\text{exp}\left(-L(N_{t-1, a}) \text{KL}(\hatμ_{t-1, a}, \max_{a'} \hatμ_{t-1, a'})\right)$, where $L(\cdot)$ is an inverse temperature function, $N_{t-1, a}$ is the number of times arm $a$ has been pulled before time $t$, $\hatμ_{t-1, a}$ is the empirical mean of arm $a$ before time $t$, and $\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)$. We also provide numerical simulations demonstrating the effectiveness of our algorithms.
查看此版本解读 →查看此版本原文 ↗