arXiv:2606.09191cs.LGstat.ML2026-06

新算法让风险规避的老虎机问题在理论上达到最优,无需假设奖励分布形式。

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

论文配图:Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards
图 1 · 摘自论文原文
  • 基于非参数贝叶斯方法,不依赖参数假设,直接处理风险函数。
  • 在子高斯奖励下,后悔率逼近理论最低限,对多种风险度量均成立。
  • 适用于复杂风险指标如夏普比率,且仅需风险函数连续性,条件更弱。

我们证明了 $ρ ext{-}ℎℌℏℏ_{ℋℍ}$——一种用于风险规避老虎机问题的无锚点非参数汤普森采样算法——在任意连续风险函数 $ρ$(包括 CVaR、均值-方差、夏普比率、扭曲风险度量等)下,其后悔率与实例相关下界在 $\log n$ 主项上匹配,从而实现了渐近最优性。该结果适用于密度有界且尾部为子高斯的分布类,包含高斯臂。无论有界支持还是子高斯尾部情形,均只需 $ρ$ 的连续性,比以往参数化汤普森采样所需的支配性条件、以及 UCB 类算法所需的 Lipschitz 条件更弱。这首次为非 Lipschitz 风险度量(如夏普比率)提供了实例最优保证,且无需参数化奖励假设。有界支持情形作为铺垫先行构建,共享相同证明结构。关键技术贡献为离散化引理(有界支持)与截断离散化引理(子高斯尾部),分别通过狄利克雷聚合性质将增长字母表的狄利克雷后验投影到固定网格上,使所有多项式因子保持固定次数且独立于样本量,突破了阻碍先前证明的超指数障碍。

原文摘要 · Abstract (English)

We prove that $ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}$, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in $\log n$, establishing it as asymptotically optimal for any continuous risk functional $ρ$ (CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms. Both this result and its bounded-support counterpart require only continuity of $ρ$: strictly weaker than the dominance condition of prior parametric Thompson Sampling results, and strictly weaker than the Lipschitz condition of UCB-type algorithms, yielding the first instance-optimal guarantees for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions. The bounded-support case is developed first as a stepping stone sharing the same proof structure. The key technical contributions are a discretisation lemma (bounded support) and a truncated discretisation lemma (sub-Gaussian tails), each projecting the growing-alphabet Dirichlet posterior onto a fixed grid via the Dirichlet aggregation property, holding all polynomial prefactors at fixed degree independent of sample size and breaking the super-exponential barrier that blocked prior proofs.

强化学习贝叶斯优化风险规避汤普森采样

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