- 论文题目: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)
算法用于平衡探索和利用:
$$\operatorname{UCB}(s, a)=Q(s, a)+c \sqrt{\frac{\log N(s)}{N(s, a)}}$$
其中$N(s)=\sum_{a}N(s,a)$,$c$是控制exploration
的参数。
Maximum Entropy Policy Optimization
最大熵的策略优化问题其实就是在expected reward
目标上引入一个entropy
的约束。可表示为:
$$\max _{\pi}\{\pi \cdot \mathbf{r}+\tau \mathcal{H}(\pi)\}$$
其中$\tau$是控制exploration
的参数。定义softmax
$\mathcal{F_{\tau}}$和soft indmax
$\mathbf{f}_{\tau}$:
$$\mathbf{f}_{\tau}(\mathbf{r})=\exp \left\{\left(\mathbf{r}-\mathcal{F}_{\tau}(\mathbf{r})\right) / \tau\right\} $$
$$\quad \mathcal{F}_{\tau}(\mathbf{r})=\tau \log \sum_{a} \exp (r(a) / \tau)$$
其中的关系为:
$$\mathcal{F}_{\tau}(\mathbf{r})=\max _{\pi}\{\pi \cdot \mathbf{r}+\tau \mathcal{H}(\pi)\}=\mathbf{f}_{\tau}(\mathbf{r}) \cdot \mathbf{r}+\tau \mathcal{H}\left(\mathbf{f}_{\tau}(\mathbf{r})\right)$$
因此用softmax value function
去替代hard-max operator
可以得到softmax operator
:
$$Q_{\mathrm{sft}}^{*}(s, a)=R(s, a)+\mathbb{E}_{s^{\prime} | s, a}\left[V_{\mathrm{sft}}^{*}\left(s^{\prime}\right)\right]$$
$$V_{\mathrm{sft}}^{*}(s)=\tau \log \sum_{a} \exp \left\{Q_{\mathrm{sft}}^{*}(s, a) / \tau\right\}$$
最后可以得到optimal softmax policy
:
$$\pi_{\mathrm{sft}}^{*}(a | s)=\exp \left\{\left(Q_{\mathrm{sft}}^{*}(s, a)-V_{\mathrm{sft}}^{*}(s)\right) / \tau\right\}$$
Softmax Value Estimationin Stochastic Bandit
在stochastic bandit
中,环境给定的reward
是随机的,或者说会满足一个分布。stochastic softmax bandit
问题与传统的stochastic bandits
问题的区别在于,它不是期望去找到最大化期望奖励的policy
,而是去估计softmax value
$V_{sft}^{*} = \mathcal{F}_{\tau}(\mathbf{r})$。定义$U_{t}=\sum_{a} \exp \left\{\hat{r}_{t}(a) / \tau\right\}$,$U^{*}=\sum_{a} \exp \left\{r_{t}(a) / \tau\right\}$。因此会有$V_{t} = \mathcal{F}_{\tau}(\hat{r}_{t})=\tau logU_{t}$,我们的目标就变成了最小化均方差误差$\mathcal{E}$。
$$\mathcal{E}_{t}=\mathbb{E}\left[\left(\hat{U}^{*}-U_{t}\right)^{2}\right]$$
基于上述讨论作者提出了一种解决序贯决策中softmax value
估计的办法(Empirical Exponential Weight (E2W) ),直观的理解就是期望足够的探索用于保证得到较好的估计值,进而使得policy
收敛于最优策略$\pi^{*}$。动作的采样分布如下所示:
$$\pi_{t}(a)=\left(1-\lambda_{t}\right) \mathbf{f}_{\tau}(\hat{\mathbf{r}})(a)+\lambda_{t} \frac{1}{|\mathcal{A}|}$$
其中 $\lambda_{t}=\varepsilon|\mathcal{A}| / \log (t+1)$,表示探索的衰减系数。
所采用的方法?
作者将MCTS
和maximum entropy policy
结合起来,得到MENTS
算法,能够获得更快的收敛速度。两点创新:
- 使用
E2W
算法作为树搜索的策略;
$$\pi_{t}(a | s)=\left(1-\lambda_{s}\right) \mathbf{f}_{\tau}\left(\mathbf{Q}_{\mathrm{sft}}(s)\right)(a)+\lambda_{s} \frac{1}{|\mathcal{A}|}$$
- 使用
softmax value
评估每个节点并用于simulations
的反向传播。
其中Q-Value
的估计使用softmax backup
。
$$Q_{\mathrm{sft}}\left(s_{t}, a_{t}\right)=\left{\begin{array}{ll}
r\left(s_{t}, a_{t}\right)+R & t=T-1 \
r\left(s_{t}, a_{t}\right)+\mathcal{F}_{\tau}\left(\mathrm{Q}_{\mathrm{sft}}\left(s_{t+1}\right)\right) & t<T-1
\end{array}\right.$$
取得的效果?
我的微信公众号名称:深度学习先进智能决策
微信公众号ID:MultiAgent1024
公众号介绍:主要研究深度学习、强化学习、机器博弈等相关内容!期待您的关注,欢迎一起学习交流进步!