Anytime Sequential Halving in Monte-Carlo Tree Search
원문 초록
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).
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Adaptive Action Duration with Contextual Bandits for Deep Reinforcement Learning in Dynamic Environments
Vision Language Models are Biased
4Hammer: a board-game reinforcement learning environment for the hour long time frame
Playing Non-Embedded Card-Based Games with Reinforcement Learning
ZeroSumEval: An Extensible Framework For Scaling LLM Evaluation with Inter-Model Competition
Playing Hex and Counter Wargames using Reinforcement Learning and Recurrent Neural Networks
토론
이 논문과 연결된 포럼 글이 아직 없습니다.