Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds

本文研究了在敌对和随机K臂赌博机中Follow-the-Perturbed-Leader (FTPL)策略的最优性。尽管Follow-the-Regularized-Leader (FTRL)框架在各种正则化选择下被广泛使用，但是依赖于随机扰动的FTPL框架却没有得到太多关注，尽管其内在的简单性。在敌对赌博机中，有一种猜想认为，如果扰动遵循Fr\'{e}chet型尾巴的分布，FTPL可能会达到$\mathcal{O}(\sqrt{KT})$的遗憾。Honda等人最近的研究表明，具有形状$\alpha=2$的Fr\'{e}chet分布的FTPL确实实现了这种界限，并且值得注意的是，在随机赌博机中实现对数遗憾，这意味着FTPL的Best-of-Both-Worlds (BOBW)能力。然而，这个结果只在一定程度上解决了上述猜想，因为他们的分析严重依赖于这种形式的Fr\'{e}chet分布。在本文中，我们建立了一个足够的条件，使得扰动在敌对环境中实现$\mathcal{O}(\sqrt{KT})$的遗憾，包括Fr\'{e}chet、Pareto和Student-$t$分布等。我们还展示了FTPL在某些Fr\'{e}chet型尾巴分布下实现BOBW的可行性。我们的结果不仅有助于通过极值理论的视角解决现有的猜想，而且可能通过从FTPL到FTRL的映射提供有关正则化函数的影响的见解。

本文研究了在敌对和随机K臂赌博中Follow-the-Perturbed-Leader（FTPL）策略的最优性。具体来说，研究了FTPL框架下随机扰动和特定分布下的最优性，以及在何种情况下可以实现最小化遗憾值。

本文建立了一种足够的条件，使得在敌对情况下，扰动可以实现最小化遗憾值，该条件包括了Fréchet、Pareto和Student-t分布等多种分布。研究表明，FTPL框架下的随机扰动可以实现最小化遗憾值，并且在某些特定的Fréchet分布下，可以实现最佳的两种世界（BOBW）能力。

本文的研究结果为解决现有猜想提供了新的见解，并通过极值理论的视角，对FTRL中正则化函数的影响进行了分析。实验设计中使用了不同的分布和数据集，并提供了开源代码。

近期在这个领域中的相关研究包括：Follow-the-Regularized-Leader (FTRL)框架下的正则化函数选择、敌对赌博中的最优性、随机赌博中的最优性等。其中，相关论文包括“Follow the Regularized Leader: Optimal Rates and Adaptivity”、“Adversarial Bandits: Optimal Rates and Adaptive Algorithms”等。