提出新型扰动机制,让强化学习策略在多臂赌博机中实现最优表现。
Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems
- 引入非对称无界扰动,扩展了经典跟随扰动领导者算法的适用范围。
- 首次在两臂场景下证明对称无界扰动可实现最优性能保证。
- 揭示了对称扰动在多臂场景中的潜在局限,推动算法设计深入研究。
Follow-the-Regularized-Leader (FTRL) 策略通过混合正则化已实现多种场景下的最优双面表现(Best-of-Both-Worlds, BOBW),而类似结果在 Follow-the-Perturbed-Leader (FTPL) 中因分析困难受限。本文重新审视经典 FTRL-FTPL 对偶性,针对一类广义的非对称无界 Fréchet 型扰动(包括结合 Gumbel 与 Fréchet 尾部的混合扰动)建立了 FTPL 的 BOBW 保证。该结果不仅拓展了 FTPL 的理论边界,还为设计可与混合正则化竞争的替代策略提供了新思路。受两臂博弈早期观察启发,我们进一步探究 1/2- Tsallis 熵与 Fréchet 型扰动的关系,数值实验表明其对应对称的 Fréchet 型扰动,并据此建立了两臂场景下首个对称无界扰动的 BOBW 保证。然而,在一般多臂情形中,我们发现对称 Fréchet 型扰动会破坏标准 BOBW 分析的关键条件,此问题在非对称或非负的 Fréchet 型扰动中未出现。尽管该反例不否定其他分析路径的可能性,但它提示不能直接将两臂结论推广至一般情形,强调需进一步研究 FTPL 在更广泛设置下的行为机制。
原文摘要 · Abstract (English)
Follow-the-Regularized-Leader (FTRL) policies have achieved Best-of-Both-Worlds (BOBW) results in various settings through hybrid regularizers, whereas analogous results for Follow-the-Perturbed-Leader (FTPL) remain limited due to inherent analytical challenges. To advance the analytical foundations of FTPL, we revisit classical FTRL-FTPL duality for unbounded perturbations and establish BOBW results for FTPL under a broad family of asymmetric unbounded Fréchet-type perturbations, including hybrid perturbations combining Gumbel-type and Fréchet-type tails. These results not only extend the BOBW results of FTPL but also offer new insights into designing alternative FTPL policies competitive with hybrid regularization approaches. Motivated by earlier observations in two-armed bandits, we further investigate the connection between the $1/2$-Tsallis entropy and a Fréchet-type perturbation. Our numerical observations suggest that it corresponds to a symmetric Fréchet-type perturbation, and based on this, we establish the first BOBW guarantee for symmetric unbounded perturbations in the two-armed setting. In contrast, in general multi-armed bandits, we find an instance in which symmetric Fréchet-type perturbations violate the key condition for standard BOBW analysis, which is a problem not observed with asymmetric or nonnegative Fréchet-type perturbations. Although this example does not rule out alternative analyses achieving BOBW results, it suggests the limitations of directly applying the relationship observed in two-armed cases to the general case and thus emphasizes the need for further investigation to fully understand the behavior of FTPL in broader settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。