提出可随时停止的序列淘汰法，提升蒙特卡洛树搜索根节点选择效率。
Anytime Sequential Halving in Monte-Carlo Tree Search
- 设计可任意中断的在线版本序列淘汰算法，适应不确定时间预算场景。
- 在合成问题与10种棋类游戏中表现接近最优序列淘汰法和UCB1。
- 适合需快速响应的实时决策系统或资源受限的搜索任务。
蒙特卡洛树搜索（MCTS）通常采用多臂赌博机（MAB）策略来最小化累积遗憾，如UCB1。然而，在搜索树的根节点，更应关注最小化简单遗憾。已有研究提出在根节点使用序列淘汰法（Sequential Halving），因其理论上对简单遗憾更优。但该方法需预设迭代次数，实际应用中常不切合需求。本文提出一种任何时间版本的序列淘汰算法，可在任意时刻终止并返回合理结果，同时近似序列淘汰的行为。在合成多臂赌博机问题及十种不同棋类游戏上的实验表明，该算法性能与序列淘汰法及UCB1（及其在MCTS中的对应版本）相当，具备良好竞争力。
原文摘要 · Abstract (English)
Monte-Carlo Tree Search (MCTS) typically uses multi-armed bandit (MAB) strategies designed to minimize cumulative regret, such as UCB1, as its selection strategy. However, in the root node of the search tree, it is more sensible to minimize simple regret. Previous work has proposed using Sequential Halving as selection strategy in the root node, as, in theory, it performs better with respect to simple regret. However, Sequential Halving requires a budget of iterations to be predetermined, which is often impractical. This paper proposes an anytime version of the algorithm, which can be halted at any arbitrary time and still return a satisfactory result, while being designed such that it approximates the behavior of Sequential Halving. Empirical results in synthetic MAB problems and ten different board games demonstrate that the algorithm's performance is competitive with Sequential Halving and UCB1 (and their analogues in MCTS).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。