Bootstrapping Simulation-Based Algorithms with a Suboptimal Policy
Bootstrapping Simulation-Based Algorithms with a Suboptimal Policy
复制标题
使用次优策略引导基于模拟的算法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Leong
中科院分区：
文献类型：
--
作者：
Truong;T. Silander;Wee Sun Lee;T. Leong
对于具有大状态空间的马尔可夫决策过程，寻找最优策略通常是困难的。尽管如此，受稀疏采样（SS）启发的基于仿真的算法，如树中应用的上置信限（UCT）和前向搜索稀疏采样（FSSS），在理论和实践中都表现得相当好，尽管计算需求很高。为了提高这些算法的效率，我们采用了一个简单的增强技术与启发式的政策，以加快最佳行动的选择。一般的方法，称为辅助，增加了前瞻树的辅助武器，评估的启发式政策。在本文中，我们提供了理论依据的方法，并证明其有效性，在两个实验基准，展示了更快的收敛到一个接近最优的政策SS和FSSS。此外，为了进一步加快这些算法在早期阶段的收敛速度，我们提出了一种新的机制，联合收割机他们与UCT，使所得的混合算法是上级优于它的两个组件。
Finding optimal policies for Markov Decision Processes with large state spaces is in general intractable. Nonetheless, simulation-based algorithms inspired by Sparse Sampling (SS) such as Upper Confidence Bound applied in Trees (UCT) and Forward Search Sparse Sampling (FSSS) have been shown to perform reasonably well in both theory and practice, despite the high computational demand. To improve the efficiency of these algorithms, we adopt a simple enhancement technique with a heuristic policy to speed up the selection of optimal actions. The general method, called Aux, augments the look-ahead tree with auxiliary arms that are evaluated by the heuristic policy. In this paper, we provide theoretical justification for the method and demonstrate its effectiveness in two experimental benchmarks that showcase the faster convergence to a near optimal policy for both SS and FSSS. Moreover, to further speed up the convergence of these algorithms at the early stage, we present a novel mechanism to combine them with UCT so that the resulting hybrid algorithm is superior to both of its components.