Sample-Based Tree Search with Fixed and Adaptive State Abstractions
Sample-Based Tree Search with Fixed and Adaptive State Abstractions
复制标题
具有固定和自适应状态抽象的基于样本的树搜索
DOI：
--
复制
发表时间：
2017
影响因子：
5
通讯作者：
Thomas G. Dietterich
中科院分区：
文献类型：
--
作者：
Jesse Hostetler;Alan Fern;Thomas G. Dietterich
基于样本的树搜索(SBTS)是一种求解马尔可夫决策问题的方法，它利用MDP的生成模型中的随机样本来构建先行搜索树。它包括蒙特卡洛树搜索(MCTS)算法(如UCT)以及稀疏采样等算法。由于SBTS算法对状态空间的大小相对不敏感，因此SBTS非常适合于求解状态空间较大的MDP。SBTS性能的限制因素往往是样本复杂度对搜索树深度的指数依赖。构建搜索树所需的样本数为O((|A|B)d)，其中|A|是可用操作的数量，B是采取操作的可能随机结果的数量，d是树的深度。状态抽象可以通过将随机结果聚集到抽象状态来减少B。最近的工作表明，抽象树搜索通常比在基本状态空间中进行的树搜索的性能要好得多。
本文对固定状态抽象和自适应状态抽象的树搜索算法进行了理论和实验评价。我们推导了树搜索中状态抽象引起的遗憾的界，该界将抽象错误分解成由抽象的性质和搜索算法引起的三个分量。我们描述了使用固定状态抽象的流行SBTS算法的版本，并介绍了稀疏采样中的渐进抽象求精(PARSS)算法，该算法在搜索过程中自适应其抽象。我们在12个实验问题上对PARSS和固定抽象的稀疏抽样进行了评估，发现PARSS的性能优于固定抽象的搜索，即使是高度不准确的固定抽象的搜索也优于无抽象的搜索。这些结果为渐进式抽象精化奠定了基础，为新的树搜索算法提供了有前景的基础，并为渐进式精化框架内的未来工作提出了方向。
Sample-based tree search (SBTS) is an approach to solving Markov decision problems based on constructing a lookahead search tree using random samples from a generative model of the MDP. It encompasses Monte Carlo tree search (MCTS) algorithms like UCT as well as algorithms such as sparse sampling. SBTS is well-suited to solving MDPs with large state spaces due to the relative insensitivity of SBTS algorithms to the size of the state space. The limiting factor in the performance of SBTS tends to be the exponential dependence of sample complexity on the depth of the search tree. The number of samples required to build a search tree is O((|A|B)d), where |A| is the number of available actions, B is the number of possible random outcomes of taking an action, and d is the depth of the tree. State abstraction can be used to reduce B by aggregating random outcomes together into abstract states. Recent work has shown that abstract tree search often performs substantially better than tree search conducted in the ground state space.
This paper presents a theoretical and empirical evaluation of tree search with both fixed and adaptive state abstractions. We derive a bound on regret due to state abstraction in tree search that decomposes abstraction error into three components arising from properties of the abstraction and the search algorithm. We describe versions of popular SBTS algorithms that use fixed state abstractions, and we introduce the Progressive Abstraction Refinement in Sparse Sampling (PARSS) algorithm, which adapts its abstraction during search. We evaluate PARSS as well as sparse sampling with fixed abstractions on 12 experimental problems, and find that PARSS outperforms search with a fixed abstraction and that search with even highly inaccurate fixed abstractions outperforms search without abstraction. These results establish progressive abstraction refinement as a promising basis for new tree search algorithms, and we propose directions for future work within the progressive refinement framework.