新算法同时满足多种最优性，提升多臂赌博机性能。
Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
- 基于KL散度设计采样策略，自适应调整探索力度。
- 理论证明可实现渐近最优、极小最大后悔值等多重最优性。
- 适合追求理论严谨性和实际性能平衡的研究者。
研究了奖励分布属于单参数指数分布族的K臂赌博机问题。现有算法在渐近最优性、极小最大后悔界、子UCB以及方差自适应最坏情况后悔界等多个评价标准中难以兼顾。本文提出一种新算法——指数型KL马伊拉尔采样（Exp-KL-MS），首次实现渐近最优性、带√ln(K)因子的极小最大后悔界、子UCB性质及方差自适应最坏情况后悔界的同时满足。该算法通过基于指数分布族的KL散度构造采样机制，确保在理论上全面优于已有方法。
原文摘要 · Abstract (English)
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 worst-case 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-Leibler Maillard Sampling (abbrev. Exp-KL-MS), that can achieve multiple optimality criteria simultaneously, including Asymptotic Optimality, Minimax Optimality with a $\sqrt{\ln (K)}$ factor, Sub-UCB, and variance-adaptive worst-case regret bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。