倾斜采样问题：乐观性、后验采样与对数级遗憾

arXiv:2610.21908v1 公告类型：新 摘要：许多现代学习系统的用途并不是选择单个最优动作，而是采样多样化的高质量输出。这类系统的例子包括熵正则化强化学习、RLHF 以及奖励引导的生成建模。受这些应用场景启发，我们研究倾斜采样：一种在线学习问题，其目标是从由未知奖励函数诱导的 Gibbs 分布中进行采样。我们将采样遗憾定义为学习者分布与 Gibbs 目标分布之间的累积 KL 散度，并按温度进行归一化；这对应于熵正则化奖励最大化中的次优差距。我们的框架推广了近年来在多臂老虎机和强化学习中基于采样以及 KL 正则化的表述。我们的主要贡献是提出一个通用的遗憾分析框架，用于刻画倾斜采样与经典遗憾最小化之间不同的不确定性结构。由于一阶不确定性，标准遗憾的规模为 $\widetilde{O}(\sqrt{T})$；而采样遗憾由置信区间宽度的平方决定，因此在固定温度的标准设置下，其关于 $T$ 呈对数级增长。我们构建了 UCB 和 Thompson sampling 的采样对应方法（UCS 和 TS$^2$），并给出统一的遗憾分解，从而解释并扩展近期的对数级保证，其中包括基于后验随机 Gibbs 分布的新界所得到的首个贝叶斯采样遗憾分解。我们的结果表明，从软最优分布中学习采样，在统计上不同于学习识别一个硬最优解。