无需预先知道极端分布参数,仍能实现近最优的在线决策性能。
Parameter-Free Heavy-Tailed Bandits
- 设计自适应探索算法,不依赖尾部参数即可运行。
- 证明未知参数下存在可计算的性能代价边界。
- 适用于金融投资等极端事件频发场景的决策系统。
重尾分布广泛存在于金融投资、在线广告和网络管理等序列决策问题中,罕见但极端的结果可能主导整体表现。重尾老虎机模型假设奖励 $X$ 满足 $\bE[|X|^{1+ε}]\leq u$,其中尾指数 $ε\in(0,1]$ 且矩界 $u<+\infty$。然而,现有绝大多数最小化后悔值的算法需事先已知这些参数,这在实践中极为受限:$ε$ 和 $u$ 决定极端事件的频率与幅度,恰恰最难从有限观测中可靠估计。针对 COLT 2025 Genalti 与 Metelli 提出的开放问题,本文解决了重尾老虎机的无参数自适应问题,并刻画了未知尾部参数带来的后悔代价。首先研究固定 $ε$ 时对矩界 $u$ 的自适应,证明任何未知 $u$(或其上界)的算法必须在分布相关与分布无关的后悔之间权衡。随后提出一种调度探索算法,无需知晓 $u$,其性能逼近该权衡前沿,仅差对数因子。最后,通过将探索调度校准至 $ε=1$ 端点,该算法亦可在不知晓 $ε$ 时实例化,对任意固定 $ε>0$ 实现次线性后悔,而任何算法都无法在所有 $ε\in(0,1]$ 上统一保证次线性后悔。整体结果在无额外分布假设下解决开问题,并给出自适应未知重尾的精确统计代价刻画。
原文摘要 · Abstract (English)
Heavy-tailed distributions arise naturally in sequential decision-making problems such as financial investment, online advertising, and network management, where rare but extreme outcomes can dominate performance. Heavy-tailed bandits model online decision-making in these settings by assuming only that rewards $X$ satisfy $\mathbb{E}[|X|^{1+ε}]\leq u$, for some tail exponent $ε\in(0,1]$ and moment bound $u<+\infty$. However, most existing regret minimization algorithms require these parameters to be known. This assumption is particularly restrictive in practice: $ε$ and $u$ govern the frequency and magnitude of rare events and are therefore precisely the quantities that are hardest to infer reliably from limited observations. Motivated by an open problem posed by Genalti and Metelli at COLT 2025, we resolve the assumption-free adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters. We first study adaptation to the moment bound $u$ for a fixed tail exponent $ε$. We prove that every algorithm unaware of $u$, or of any upper bound on it, must obey a sharp trade-off between its distribution-dependent and distribution-free regret guarantees. We then introduce a scheduled-exploration algorithm that requires no knowledge of $u$ and matches the resulting adaptation frontier up to logarithmic factors. Finally, we show that the same algorithm can be instanced without knowing $ε$ by calibrating its exploration schedule to the endpoint $ε=1$. It achieves sublinear regret for every fixed $ε>0$, while no algorithm can guarantee sublinear regret uniformly over all $ε\in(0,1]$. Altogether, our results resolve the COLT open problem without additional distributional assumptions and provide a sharp characterization of the statistical cost of adapting to unknown heavy tails.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。