提出高效阈值搜索算法，快速判断树根价值是否达标。
An Efficient Algorithm for Thresholding Monte Carlo Tree Search
- 基于追踪停止策略设计序贯采样方法，渐近最优采样量。
- 改进的比率型策略显著降低实际采样次数和每轮计算开销。
- 适合强化学习中快速评估决策树价值的场景。
我们提出了阈值蒙特卡洛树搜索问题：给定一棵树 $ T$ 和一个阈值 $θ$，玩家需判断树根节点的值是否至少为 $θ$。树中每个内部节点标记为 'MAX' 或 'MIN'，'MAX' 节点值为其子节点值的最大值，'MIN' 节点值为其子节点值的最小值。叶节点值是未知分布的均值奖励，玩家可从中采样。针对该问题，我们设计了一种 $δ$-正确序贯采样算法，基于追踪停止策略，具有渐近最优采样复杂度。我们发现，对 D-Tracking 抽取策略进行比率修正，能显著提升实际采样效率，并将每轮计算成本从线性降低至对数级别（关于分支数）。
原文摘要 · Abstract (English)
We introduce the Thresholding Monte Carlo Tree Search problem, in which, given a tree $\mathcal{T}$ and a threshold $θ$, a player must answer whether the root node value of $\mathcal{T}$ is at least $θ$ or not. In the given tree, `MAX' or `MIN' is labeled on each internal node, and the value of a `MAX'-labeled (`MIN'-labeled) internal node is the maximum (minimum) of its child values. The value of a leaf node is the mean reward of an unknown distribution, from which the player can sample rewards. For this problem, we develop a $δ$-correct sequential sampling algorithm based on the Track-and-Stop strategy that has asymptotically optimal sample complexity. We show that a ratio-based modification of the D-Tracking arm-pulling strategy leads to a substantial improvement in empirical sample complexity, as well as reducing the per-round computational cost from linear to logarithmic in the number of arms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。