Monte Carlo Tree Search (MCTS) 蒙特·卡罗尔树搜索

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/Solo95/article/details/103218744

Monte Carlo Tree Search

• 为什么要学习MCTS
• 一部分原因是过去12年AI最大的成就莫过于Alpha Go，一个超越任何人类的围棋玩家
• 引入基于模型的RL思想和规划(planning)的好处

Introudction

Model-Based Reinforcement Learning

• 前面的博文：从经验中直接学习价值函数或者策略
• 这篇博文：从经验中直接学习模型(Transition or Reward model)
• 并且使用规划(planning)来构建一个价值函数或者策略
• 整合学习和规划到一个单独的架构

planning，取一个已知的world模型然后使用价值迭代或者策略迭代或者动态规划，尝试去计算出一个用于这些给定模型的策略。

Model-Based and Model-Free RL

• Model-Free RL
  • 没有模型
  • 从经验中学习价值函数(和/或策略)
• Model-Based RL
  • 从经验中学习一个模型
  • 从该模型中规划出价值函数(和/或策略)

当你有一个simulator(模拟器)的时候，你可以从模拟器中获取经验，然后：

• DP
• model-free RL
• policy search

在这里插入图片描述

在这里插入图片描述

Model-Based RL

在这里插入图片描述

Advantages of Model-Based RL

• 优点:
  • 能高效地使用监督学习的方法去学习模型
  • 可以推理模型不确定性(像用于探索/利用权衡的上界置信边界(upper confidence bound))
• 缺点：
  • 首先要学习出一个模型，然后再构建一个价值函数 $$这样会有两个近似误差来源

变迁动态，大体上会被认为随机的，所以需要能产生分布预测的监督学习。奖励模型可以被看出是标量，所以可以使用非常经典的基于回归的方法。

还有一个需要提及的model-based reinforcement learning的优势，在迁移方面是非常强大的。Model-Based RL的一个好处是如果你学习了一个world的动态模型，如果有人更改了奖励函数，隐含着你可以做零改动迁移(zero shot transfer)，直接用原来的模型再加上新的奖励函数去计算一个新的计划。

MDP Model Refresher

• 一个模型M\mathcal{M}M表示了一个被η\etaη参数化的MDP<S,A,P,R><\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R}><S,A,P,R>
• 假定状态空间S\mathcal{S}S和动作空间A\mathcal{A}A是已知的
• 那么一个模型M=<Pη,Rη>\mathcal{M}=<\mathcal{P}_\eta,\mathcal{R}_\eta>M=<Pη​,Rη​>表示了状态变迁Pη≈P\mathcal{P}_\eta \approx\mathcal{P}Pη​≈P且Rη≈R\mathcal{R}_\eta \approx \mathcal{R}Rη​≈R St+1∼Pη(St+1∣St,At)S_{t+1} \sim \mathcal{P}_\eta(S_{t+1}|S_t,A_t)St+1​∼Pη​(St+1​∣St​,At​) Rt+1=Rη(Rt+1∣St,At)R_{t+1} = \mathcal{R}_\eta(R_{t+1}|S_t,A_t)Rt+1​=Rη​(Rt+1​∣St​,At​)
• 典型地，假定状态变迁和奖励之间的条件性独立 P[St+1,Rt+1∣St,At]=P[St+1∣St,At]P[Rt+1∣St,At]\mathbb{P}[S_{t+1},R_{t+1}|S_t,A_t]=\mathbb{P}[S_{t+1}|S_t,A_t]\mathbb{P}[R_{t+1}|S_t,A_t]P[St+1​,Rt+1​∣St​,At​]=P[St+1​∣St​,At​]P[Rt+1​∣St​,At​]

Model Learning

• 目标：从经验S1,A1,R2,...,ST{S_1,A_1,R_2,...,S_\Tau}S1​,A1​,R2​,...,ST​中估计模型Mη\mathcal{M}_\etaMη​
• 这是一个监督学习问题 S1,A1→R2,S2S_1,A_1\rightarrow R_2,S_2S1​,A1​→R2​,S2​ S2,A2→R3,S3S_2,A_2\rightarrow R_3,S_3S2​,A2​→R3​,S3​ ......... ST−1,AT−1→RT,STS_{\Tau-1},A_{\Tau-1}\rightarrow R_{\Tau},S_{\Tau}ST−1​,AT−1​→RT​,ST​
• 学习s,a→rs,a\rightarrow rs,a→r是一个回归问题
• 学习s,a→s′s,a\rightarrow s's,a→s′是一个(概率)密度评估问题
• 选择损失函数，e.g. 均方误差，KL散度，…
• 找到使得实验误差最小化的参数集η\etaη