- 论文题目：Maximum Entropy Monte-Carlo Planning
所解决的问题？
- 作者提出了一个新的
stochastic softmax bandit框架； - 将其扩展到
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算法，能够获得更快的收敛速度。两点创新：
- 使用
E2W算法作为树搜索的策略；
- 使用
softmax value评估每个节点并用于simulations的反向传播。
其中Q-Value的估计使用softmax backup。
取得的效果？
我的微信公众号名称：深度学习先进智能决策
微信公众号ID：MultiAgent1024
公众号介绍：主要研究深度学习、强化学习、机器博弈等相关内容！期待您的关注，欢迎一起学习交流进步！
