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

技术摘要：针对具有亚高斯回报的风险厌恶型多臂老虎机算法的渐近最优性

问题陈述
本文研究了风险厌恶目标下的多臂老虎机（MAB）问题。与旨在最大化期望回报的标准 MAB 设置不同，风险厌能设置旨在优化一般的风险泛函 $\rho$（例如，条件风险价值 CVaR、均值-方差、夏普比率或扭曲风险度量）。本文解决的具体挑战是针对 $\rho$-NPTS（由 Chang 和 Tan [2022] 提出的非参数化 Thompson Sampling 算法）的理论分析。虽然 Chang 和 Tan 证明了其参数化伴随算法（$\rho$-MTS）的实例最优性，但他们将非参数化 $\rho$-NPTS 的最优性作为一个开放问题留下了。

根本障碍在于 $\rho$-NPTS 构建了一个狄利克雷后验分布，其有效字母表大小随观测次数（$N_k$）增长。直接应用现有的尾部界限会导致 $(N_k)^{N_k/2}$ 的超指数前因子，这阻碍了对对数级遗憾界限（logarithmic regret bounds）的证明。此外，先前的研究通常需要较强的条件，例如“支配”（dominance）条件（针对参数化方法）或风险泛函的 Lipschitz 连续性（针对 UCB 类算法），这排除了重要的非 Lipschitz 泛函，如夏普比率。

方法论
作者引入了 $\rho$-NPTSSG，这是一种针对具有有界密度和亚高斯尾部（$P(B, \sigma)$）分布设计的无锚点（anchor-free）变体非参数化 Thompson Sampling 算法。其核心技术创新是一个离散化引理（以及针对亚高斯尾部的截断版本），该引理将不断增长字母表的狄利克雷后验分布投影到一个固定的网格上。

1. 离散化与聚合：
   论文定义了一个大小为 $M$ 的固定网格 $G_M$。对于任何观测到的回报序列，经验测度通过将落在同一网格箱（bin）内的观测对应的狄利克雷权重进行聚合，从而投影到该网格上。

   • 关键洞察： 利用狄利克雷分布的聚合性质，投影到已占用箱中的权重遵循一个固定维度的狄利克雷分布（$M^+ \le M$），无论样本量 $N_k$ 为多少。
   • 后果： 这种投影将尾部界限中的多项式前因子限制在次数 $(M-1)/2$，该次数独立于 $N_k$。这打破了阻碍先前证明的超指数壁垒。

2. 算法变体：

   • $\rho$-NPTS（有界支撑）： 运行在支持集在 $[0, 1]$ 且具有有界密度的分布上。它使用一个固定锚点（右端点）和一个均匀网格。
   • $\rho$-NPTSSG（亚高斯）： 运行在具有有界密度和亚高斯尾部的实数集 $\mathbb{R}$ 分布上。它移除了固定锚点（使用轮询初始化代替），并采用了截断离散化引理。该引理使用一个以经验均值为中心、宽度随样本量增长而缩小的网格，同时通过截断尾部来控制溢出概率。

3. 遗憾分析：
   证明过程遵循标准的遗憾分解，即将遗憾分解为算法抽取具有“高”Thompson 分数与“低”分数之次优臂的项。

   • 上界： 利用离散化引理将 Chang 和 Tan [2022] 的尾部界限应用于固定网格投影。$\rho$ 的连续性（特别是 $D_\infty$-连续性）确保了投影测度的风险能够近似真实风险。
   • 下界： 与 Chang 和 Tan [2022] 建立的依赖于实例的下界相匹配，该下界依赖于 Kullback-Leibler (KL) 散度最小化问题 $K^\rho_{\inf}$。

核心贡献

1. 解决开放问题： 论文证明了对于具有有界密度和亚高斯尾部的分布类中的任何连续风险泛函 $\rho$，$\rho$-NPTSSG 实现了渐近最优遗憾 $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$。
2. 更弱的条件： 该结果仅要求风险泛函 $\rho$ 的连续性（具体而言是相对于 Lévy–Prokhorov 度量的连续性）。这严格弱于：
   • 参数化 $\rho$-MTS 所需的“支配”条件。
   • UCB 类算法所需的 Lipschitz 条件。
   • 这使得针对非 Lipschitz 泛函（如夏普比率）实现首次实例最优保证成为可能，且无需假设参数化回报分布。
3. 离散化引理： 论文引入了一个技术引理，用于控制在固定分辨率下的增长字母表狄利克雷后验。该引理对于任何涉及增长支持集的狄利克雷过程的问题都具有潜在的独立研究价值。
4. 亚高斯扩展： 作者通过截断离散化方法将有界支撑的研究结果扩展到了更广泛的亚高斯分布类（包括高斯臂），从而消除了对预设支持区间的需求。

结果

• 定理 1（有界支撑）： 在仅需连续性条件下，确立了 $\rho$-NPTS 在 $P(B)$ 上的渐近最优性。
• 定理 2（亚高斯）： 确立了 $\rho$-NPTSSG 在 $P(B, \sigma)$ 上的渐近最优性。
• 实验验证： 论文通过四个实验验证了理论：
  1. $\rho$-NPTS 在 Beta 分布臂上追踪 CVaR 的实例最优下界，表现优于 Risk-LCB 基准（后者具有 $\log^2 n$ 的保证）。
  2. $\rho$-NPTS 在截断正态分布臂上实现了夏普比率的 $O(\log n)$ 遗憾，而在该情况下，由于非 Lipschitz 性，此前没有任何算法能提供保证。
  3. 该算法可以处理复合泛函（例如 $0.5 \text{CVaR} + 0.5 \text{Sharpe}$）而无需修改。
  4. $\rho$-NPTSSG 在高斯臂上收敛至实例最优下界，达到了专门的 Normal-Gamma Thompson Sampling 算法（Shah 等人 [2025]）的性能，且无需假设高斯回报。

意义与主张
本文声称解决了风险厌恶型多臂老虎机中非参数化 Thompson Sampling 的理论地位。它证明了这些算法不仅是经验性的启发式算法，而且是可证明渐近最优的。

其意义在于放宽了假设：

• 从业者可以使用原始观测值，而无需预先指定回报网格或调整字母表大小。
• 该方法适用于比以往最优方法更广泛的风险泛函类（包括夏普比率）和分布类（亚高斯）。
• 该结果通过提供一个更尖锐的、无需共轭先验或参数假设的夏普比率实例最优常数，涵盖了 Shah 等人 [2025] 的同期工作。

作者指出，有界密度假设对于证明中使用的箱概率界限是必要的，并且对于具有点质量（例如伯努利分布）的分布不成立，对于此类分布，参数化 $\rho$-MTS 仍是互补的解决方案。确定的未来研究方向包括上下文老虎机（contextual bandits）、重尾回报以及离散分布。