超越期望值：使用分布式蒙特卡洛树搜索进行风险敏感型规划

arXiv:2610.23565v1 公告类型：新 摘要：蒙特卡洛树搜索（MCTS）通常只存储标量均值估计，因此不太适用于条件风险价值（CVaR）等尾部风险目标。我们提出了 Categorical Thompson Sampling with Optimism（CATSO）和 Particle Thompson Sampling with Optimism（PATSO）两种分布式 MCTS 算法，它们在 Q-edges 上维护有限支撑的经验回传分布。CATSO 使用分类原子和 Dirichlet Thompson sampling 表示 Q-edge 分布，而 PATSO 使用自适应粒子表示这些分布。两种算法都根据 Thompson sampling 得到的 Q-edge 分布的 CVaR 加上多项式乐观奖励来选择动作，并通过对子节点 Q-edge 的 CVaR 分数进行按访问次数加权平均，传播标量延续值。针对有限深度嵌套 CVaR 规划目标，我们证明经过 n 次 rollout 后，根节点价值误差具有 $O(n^{-1/2})$ 上界，该上界也进一步约束了风险敏感型简单遗憾。CATSO 会引入固定网格离散化偏差，而设有上限的 PATSO 会引入可调节的 Wasserstein 压缩偏差。在随机规划基准测试上的实验表明，当均值最优行为与风险敏感行为存在差异时，分布式 Q-edges 能够改善下尾回报，并减少灾难性结果。