【NeurIPS 2019】最大熵的蒙特卡洛规划算法

• 论文题目：Maximum Entropy Monte-Carlo Planning

所解决的问题？

1. 作者提出了一个新的stochastic softmax bandit框架；
2. 将其扩展到MCTS上，得到了Maximum Entropy for Tree Search (MENTS)算法。

  将softmax state value引入，在back-propaganda过程中会更容易收敛。作者在理论和实验部分都验证了这两个想法。

背景

MCTS

   Monte Carlo Tree Search (MCTS)是一种非常好的能够获取全局最优的算法，同时也可以通过引入先验知识对其进行加强。它的核心问题在于exploitation和exploration的平衡。而MCTS的收敛性高度依赖于state value的 estimation。而MCTS通过simulation获得当前状态的估计这种做法并不是非常高效，因此在sample的过程中你的policy会发生改变，导致你的序列期望收益会发生漂移(drift)，因此 UCT can only guarantee a polynomial convergence rate of finding the best action at the root。MCTS主要可以分为两步：1. tree policy选择action，直到到达叶子节点。2. 一个evaluation function需要评估simulation return，你可以选择近函数近似的方式来逼近这个值，但是在MCTS中采用的是roll-out policy获取simulation return。

  maximum upper confidence bound(UCB)算法用于平衡探索和利用：

Maximum Entropy Policy Optimization

  最大熵的策略优化问题其实就是在expected reward目标上引入一个entropy的约束。可表示为：

  其中的关系为：

  因此用softmax value function去替代hard-max operator可以得到softmax operator：

 最后可以得到optimal softmax policy：

Softmax Value Estimationin Stochastic Bandit

基于上述讨论作者提出了一种解决序贯决策中softmax value估计的办法(Empirical Exponential Weight (E2W) )，直观的理解就是期望足够的探索用于保证得到较好的估计值，进而使得policy收敛于最优策略π ∗ 。动作的采样分布如下所示：

所采用的方法？

  作者将MCTS和maximum entropy policy结合起来，得到MENTS算法，能够获得更快的收敛速度。两点创新：

1. 使用E2W算法作为树搜索的策略；

2. 使用softmax value评估每个节点并用于simulations的反向传播。

  其中Q-Value的估计使用softmax backup。

取得的效果？

我的微信公众号名称：深度学习先进智能决策

微信公众号ID：MultiAgent1024

公众号介绍：主要研究深度学习、强化学习、机器博弈等相关内容！期待您的关注，欢迎一起学习交流进步！