arXiv:2502.02486stat.MLcs.LG2025-02ICML被引 3

新算法让上下文猜拳更抗极端奖励,不依赖奖励范围上限。

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards

  • 用鲁棒统计的Catoni估计器改进上下文猜拳算法
  • 后悔值仅与累积方差相关,对奖励范围仅对数依赖
  • 无需预估方差,适合真实中奖分布极不规则场景

传统上下文猜拳算法假设每轮奖励在固定区间[0, R]内,其后悔值随奖励范围R多项式增长。然而许多实际场景存在重尾奖励,或最坏情况下的奖励范围远大于方差。本文基于鲁棒统计中的Catoni估计器,提出一种适用于一般函数近似的算法。当已知每轮奖励方差时,采用方差加权回归,建立后悔界仅依赖累积奖励方差,并对奖励范围R和轮数T呈对数依赖。对于未知方差情形,进一步设计基于剥皮法的算法,无需繁琐方差估计;在额外依赖四阶矩条件下,仍可获得基于方差的后悔界且对奖励范围仅对数依赖。通过匹配下界证明了后悔界主项的最优性。

原文摘要 · Abstract (English)

Typical contextual bandit algorithms assume that the rewards at each round lie in some fixed range $[0, R]$, and their regret scales polynomially with this reward range $R$. However, many practical scenarios naturally involve heavy-tailed rewards or rewards where the worst-case range can be substantially larger than the variance. In this paper, we develop an algorithmic approach building on Catoni's estimator from robust statistics, and apply it to contextual bandits with general function approximation. When the variance of the reward at each round is known, we use a variance-weighted regression approach and establish a regret bound that depends only on the cumulative reward variance and logarithmically on the reward range $R$ as well as the number of rounds $T$. For the unknown-variance case, we further propose a careful peeling-based algorithm and remove the need for cumbersome variance estimation. With additional dependence on the fourth moment, our algorithm also enjoys a variance-based bound with logarithmic reward-range dependence. Moreover, we demonstrate the optimality of the leading-order term in our regret bound through a matching lower bound.

上下文猜拳鲁棒学习重尾分布

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。