用一种新的平滑度对抗强盗

Dec, 2015

Fighting Bandits with a New Kind of Smoothness

Jacob Abernethy, Chansoo Lee, Ambuj Tewari

TL;DR定义了一种新的算法家族，用于对抗性多臂赌博问题，并提供基于凸平滑的简单分析技术。通过使用 Tsallis 熵进行正则化，证明了它的最小极大后悔度为 Θ(√TN)；同时，对于具有有界危害率的微扰分布，广泛类的扰动方法可获得近乎最优的后悔率，低至 O(√TN log N)，例如 Gumbel、Weibull、Frechet、Pareto 和 Gamma 分布都满足此特性。

Abstract

We define a novel family of algorithms for the adversarial multi-armed bandit problem, and provide a simple analysis technique based on convex smoothing. We prove two main results. First, we show that regularizat