面向高维连续行动空间的蒙特卡罗树搜索算法

Monte Carlo Tree Search for High-dimensional Continuous Control Space

蒙特卡罗树搜索(Monte Carlo Tree Search,MCTS)在低维离散控制任务中取得了巨大的成功。然而,在现实生活中许多任务需要在连续动作空间进行行动规划。由于连续行动空间涉及的行动集过大,蒙特卡罗树搜索很难在有限的时间内从中筛选出最佳的行动。作为蒙特卡罗树搜索的一个变种,KR-UCT(Kernel Regression UCT)算法通过核函数泛化局部信息的方式提高了蒙特卡罗树搜索在低维连续动作空间的模拟效率。但是在与环境交互的过程中,为了找出最佳的行动,KR-UCT在每一步都需要从头进行大量的模拟,这使得KR-UCT算法仅局限于低维连续行动空间,而在高维连续行动空间难以在有限的时间内从行动空间筛选出最佳的行动。在与环境交互的过程中,智能体可以获得环境反馈回来的信息,因此,为了提高KR-UCT算法在高维行动空间的性能,可以使用这些反馈信息剪枝树搜索过程来加快KR-UCT算法在高维连续行动空间的模拟效率。基于此,文中提出了一种基于策略-价值网络的蒙特卡罗树搜索方法(KR-UCT with Policy-Value Network,KRPV)。该方法使用策略-价值网络保存智能体与环境之间的交互信息,随后策略网络利用这些信息帮助KR-UCT算法剪枝KR-UCT搜索树的宽度;而价值网络则通过泛化不同状态之间的价值信息对蒙特卡罗树搜索在深度上进行剪枝,从而提高了KR-UCT算法的模拟效率,进而提高了算法在高维连续行动任务中的性能。在OpenAI gym中的4个连续控制任务上对KRPV进行了评估。实验结果表明,该方法在4个连续控制任务上均优于KR-UCT,特别是在6维的HalfCheetah-v2任务中,使用KRPV算法所获得的奖励是KR-UCT的6倍。

Monte Carlo tree search(MCTS)has gained great success in low discrete control tasks.However,there are many tasks in real life that require selecting action sequentially in continuous action space.Kernel regression UCT(KR-UCT)is a successful attempt in low-dimensional continuous action space by using a pre-defined kernel function to exploit the similarity of different continuous actions.However,KR-UCT gets a poor performance when it comes to high-dimensional continuous action space,because KR-UCT does not use the interacting information between agent and the environment.And when it interacts with the environment,KR-UCT needs to perform a lot of simulations at each step to find the best action.In order to solve this problem,this paper proposes a method named kernel regression UCT with policy-value network(KRPV).The proposed method can filter out more representative actions from action space to perform MCTS and generalize the information between different states to pruning MCTS.The proposed method has been evaluated by four continuous control tasks of the OpenAI gym.The experimental results show that KRPV outperforms KR-UCT in all tested continuous control tasks.Especially for the six-dimensional HalfCheetah-v2 task,the rewards gained by KRPV are six-times of that of KR-UCT.