无需参数设定,统一应对重尾多臂赌博机的随机与对抗环境。
uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs
- 设计自适应学习率与截断机制,实现参数无关的鲁棒学习。
- 在两种环境中均逼近最优后悔上界,且无需预知重尾参数。
- 适合对鲁棒性要求高的在线决策场景,如推荐系统、金融交易。
本文提出一种新算法 uniINF,用于处理重尾多臂赌博机(HTMAB)问题,在随机与对抗环境下均表现出鲁棒性和自适应性。不同于传统静态损失分布的随机设置,本研究扩展至对抗场景,其中损失来自依赖于动作和时间的重尾分布。uniINF 具备‘双境最优’(Best-of-Both-Worlds, BoBW)特性,无需预先知道环境类型即可在两类环境中实现近最优后悔。此外,该算法为无参数型,无需事先知晓重尾参数 (σ, α)。理论上,uniINF 在两类环境中均达到已知参数下的最优后悔下界(仅差对数因子)。据我们所知,uniINF 是首个实现重尾 MAB 下双境最优且无参数的算法。技术上,创新性地引入日志障碍动态分析、自平衡学习率调度、自适应跳过-截断损失调节及对数后悔的停止时间分析。
原文摘要 · Abstract (English)
In this paper, we present a novel algorithm, uniINF, for the Heavy-Tailed Multi-Armed Bandits (HTMAB) problem, demonstrating robustness and adaptability in both stochastic and adversarial environments. Unlike the stochastic MAB setting where loss distributions are stationary with time, our study extends to the adversarial setup, where losses are generated from heavy-tailed distributions that depend on both arms and time. Our novel algorithm `uniINF` enjoys the so-called Best-of-Both-Worlds (BoBW) property, performing optimally in both stochastic and adversarial environments without knowing the exact environment type. Moreover, our algorithm also possesses a Parameter-Free feature, i.e., it operates without the need of knowing the heavy-tail parameters $(σ, α)$ a-priori. To be precise, uniINF ensures nearly-optimal regret in both stochastic and adversarial environments, matching the corresponding lower bounds when $(σ, α)$ is known (up to logarithmic factors). To our knowledge, uniINF is the first parameter-free algorithm to achieve the BoBW property for the heavy-tailed MAB problem. Technically, we develop innovative techniques to achieve BoBW guarantees for Parameter-Free HTMABs, including a refined analysis for the dynamics of log-barrier, an auto-balancing learning rate scheduling scheme, an adaptive skipping-clipping loss tuning technique, and a stopping-time analysis for logarithmic regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。