机器学习 | 强化学习（7） | 融合学习与规划（Integrating Learning and Planning）

7-融合学习与规划（Integrating Learning and Planning）

1.导论

基于模型的强化学习（Model-Based Reinforcement Learning）

在上一个课程中，是从记录序列中直接学习策略的
在过往的课程中，是从记录序列中直接学习价值函数的
而本次课程，则是从记录序列中直接学习模型的
然后采用规划（Planning）来构建一个价值函数或者策略
将学习（Learning）与规划（Planning）融合到一个架构中

基于模型（Model-Based）和无模型（Model-Free）强化学习

无模型强化学习
- 无模型
- 从经验序列中学习价值函数或者策略
基于模型强化学习
- 从序列中学习一个模型
- 通过模型来规划价值函数或者策略

2.基于模型的强化学习（Model-Based RL）

价值/策略 -> 交互 -> 经验序列 -> 模型学习 -> 模型 -> 规划 -> 价值/策略 ->....

基于模型强化学习的优点

优点：

可以基于监督学习的方法快速学习
能够解释模型的不确定性

缺点：

先学习一个模型，再构建策略函数，中间过程导致了两次近似误差的产生

什么为模型？

对于一个模型(mathcal{M})则是代表一个由参数(eta)进行控制的$MDPmathcal{langle S, A, P, R angle} $
我们假定状态空间(mathcal{S})和动作空间(mathcal{A})是已知的
为此一个模型(mathcal{M=langle P_eta,R_eta angle})代表着状态转移概率(mathcal{P_etaapprox P})以及回报(mathcal{R_etaapprox R})

[egin{align} S_{t+1}&simmathcal{P_eta}(S_{t+1}|S-t,A_t) \ R_{t+1}&simmathcal{R_eta}(R_{t+1}|S-t,A_t) end{align} ]
一般来说假设状态转移以及回报是符合条件性独立的

即：

[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] ]

模型学习（Model Learning）

目标：从经验序列({S_1,A_1,R_2dots,S_T})估计模型(mathcal{M_eta})
显然这是一个监督学习问题：

[egin{align} S_1,A_1& ightarrow R_2,S_2 \ S_2,A_2& ightarrow R_3,S_3 \ &vdots \ S_{T-1},A_{T-1}& ightarrow R_T,S_T end{align} ]
学习 (s,a ightarrow r)即是回归问题
学习(s,a ightarrow s')即是密度估计问题（即是学习密度概率函数或者说分布）
选择一个损失函数，如MSE、KL散度等
寻找参数(eta)以最小化经验误差

一些模型的典型例子

查表法模型（Table Lookup Model）
线性期望模型（Linear Expectiation Model）
线性高斯模型（Linear Gaussian Model）
高斯过程模型（Gaussian Process Model）
深度微型网络（Deep Belief Network Model）
...

查表模型（Table Lookup Model）

模型显然是一个显式的马尔科夫决策过程(mathcal{hat P,hat R})
计算访问每个状态动作对的访问次数(N(s,a))

[egin{align} mathcal{hat P^a_{s,s'}} & = frac{1}{N(s,a)}sum^{T}_{t=1}mathbf 1(S_t, A_t,S_{t+1}=s,a,a') \ mathcal{hat R^a_{s,s'}} & = frac{1}{N(s,a)}sum^{T}_{t=1}mathbf 1(S_t, A_t=s,a)R_t end{align} ]
或者换一种说法
- 在每一个时间辍t中记录经验元组(langle S_t,A_t, R_{t+1},S_{t+1} angle)
- 对于一个采样模型，随机性地采样形如(langle s,a,cdot,cdot angle)的元素

模型规划（Planning with a model）

*Planning即是Solving

给定模型(mathcal{M_eta=langle P_eta,R_eta angle})
解决(MDPmathcal{langle S,A,P_eta,R_eta angle})
用你喜欢的算法即可：
- 价值迭代
- 策略迭代
- 树形搜索
- ...

基于采样的规划（Sample-Based Planning）

简易却是强大的规划方法
只用模型来生成样本
从模型中进行采样

[egin{align} S_{t+1} & sim mathcal{P_eta}(S_{t+1}|S_t,A_t) \ R_{t+1} & = mathcal{R_eta}(R_{t+1}|S_t,A_t) end{align} ]
通过无模型的强化学习方法去采样，例如说：
- 蒙特卡罗控制
- SARSA算法
- Q--Learning
基于采样的规划（Sample-Based Planning）一般来说都比较高效

非精准模型的规划

给定非完美的模型(mathcal{langle P_eta,R_eta angle eq langle P,R angle})
基于模型强化学习的表现决定或者说限制了拟合(MDPmathcal{langle S,A,P_eta, R_eta angle})的最优策略

即是基于模型的强化学习只能跟他估计所用的模型一致
那么当模型不够精确之时，在规划的过程中只能得到一个次优解的策略
方法1：当模型完全出错之时，采用无模型的强化学习
方法2：显式地描述模型的不确定性

3.融合架构（Integrated Architectures）

真实序列与模拟序列

我们这里定义两种来源的经验序列

真实序列（Real experience）从环境中进行的取样（真正的MDP）

[S' sim mathcal{P^a_{s,s;}} \ R = mathcal{R^a_s} ]
模拟序列（Simulated experience）从模型中进行的取样的（近似MDP）

[egin{align} S'& sim mathcal{P_eta(S'|S,A)} \ R & = mathcal{R_eta}(R|S,A) end{align} ]

基于模型（Model-Based）和无模型（Model-Free）强化学习

无模型强化学习
- 无模型
- 从经验序列中学习价值函数或者策略
基于模型强化学习（通过基于采样的规划）
- 从序列中学习一个模型
- 通过模型来规划价值函数或者策略
Dyna（pronounce: daina）（二者的融合体）
- 从真实经验序列中学习一个模型
- 学习并且规划处一个价值函数（或者策略）从混合的真实与模拟经验序列

Dyna-Q算法

对所有的(sinmathcal{S})以及所有的(ainmathcal{A(s)})，初始化 (Q(s,a))以及模型(Model(s,a))

一直循环：

(Sleftarrow) 目前的状态（非终结态）
(Aleftarrowepsilon-greedy(S,Q))
执行动作(A)，得到回报(R)以及下一状态(S')
(Q(S,A)leftarrow Q(S,A)+alpha[R + gammamax_a Q(S',a)-Q(S,A)])
(Model(S,A) leftarrow R,S')（假设是确定性的环境)
循环(n)次

(Sleftarrow) 随机取样过去观测到的状态

(Aleftarrow)随机取样在(S)中会采取的动作

(R,S'leftarrow Model(S,A))

(Q(S,A) leftarrow Q(S,A) + alpha[R + gammamax_a Q(S',a) - Q(S,A)])

其中中间循环(n)次也可以看做是思考次数

尤其适合变化性的环境

4.基于模拟的搜索（Simulation-Based Search）

前向搜索（Forward search）

前向搜索算法通过向前预测来选取最佳的动作
通过建立基于目前状态(s_t)作为根的搜索树（Search Tree）
通过一个MDP的模型来向前预测
其实并不需要整个MDP，只是从目前出发的一部分MDP

基于模拟的搜索（Simulation-Based Search）

前向搜索图采用基于采样的规划
通过模型模拟出从现在开始的经验序列
在模拟出来的序列中应用无模型的强化学习
首先基于模型模拟从目前状态开始的经验序列

[{color{red}{s^k_t},A^k_t,R^k_{t+1},dots,S^k_T}^K_{k=1}simmathcal{M_v} ]
在模拟出来的序列中应用无模型强化学习（按你喜欢的即可）
- 蒙特卡罗·控制( ightarrow)蒙特卡罗搜索（Monte-Carlo Search）
- SARSA( ightarrow) TD搜索

简易蒙特卡罗搜索（Simple Monte-Carlo Search）

给定模型(mathcal{M_v})以及一个模拟策略(pi)
对于所有动作(ain mathcal{A})
- 然后基于目前状态(s_t)（是真实的）去模拟(K)个状态
  
  [{color{red}{s_t,a},R^k_{t+1},S^k_{t+1},A^k_{t+1},dots,S^k_T}^K_{k=1}sim mathcal{M_v,pi} ]
- 通过均值返回回报去评估每一个动作（蒙特卡罗评估）
  
  [Q(color{red}{s_t,a})=frac{1}{K}sum^K_{k=1}G_tmathop{ ightarrow}^P q_pi(s_t,a) ]
- 选择具有目前最大价值的动作
  
  [a_t=mathop{argmax}_{ain A}Q(s,a) ]

蒙特卡罗树搜索（Monte-Carlo Tree Search）（评估）

给定模型(mathcal{M_v})
通过目前的模拟策略(pi)从目前状态(s_t)模拟K步序列

[{color{red}{s_t}A^k_t,R^k_{t+1},S^k_{t+1},A^k_{t+1},dots,S^k_T}^K_{k=1}sim mathcal{M_v,pi} ]
然后构建一个包含（模拟中）访问过的状态以及动作的搜索树
通过从(s,a)出发的每一步序列返回的均值返回回报评估状态的(Q(s,a))

[Q(color{red}{s,a})=frac{1}{N(s,a)}sum^K_{k=1}sum^T_{u=t}mathbf1(S_u,A_u=s,a)G_umathop{ ightarrow}^P q_pi(s,a) ]
- 选择具有目前最大价值的动作
  [a_t=mathop{argmax}_{ain A}Q(s,a) ]

蒙特卡罗树搜索（模拟）

在蒙特卡罗树搜索中，模拟策略(pi)是可以被更新改进的
每一次模拟都包含了两部分（入树与出树）
- 树策略（改进）：通过最大化(Q(S,A))进行动作选择
- 缺省策略（修正过）：随机选择动作
重复（每次循环如此）
- 通过蒙特卡罗评估去评估状态(Q(S,A))
- 改进树策略例如通过(epsilon-greddy(Q))
然后将蒙特卡罗控制应用在模拟出来的经验序列中
将会收敛于最优的搜索树，(Q(S,A) ightarrow q_*(S,A))

*从目前状态出发树策略一直下推以取代缺省策略

蒙特卡罗树搜索的优点

高度选择性的最优优先搜索
动态评估所有状态（不像例如动态规划那样）
通过采样来破坏维度曲线（curse dimensionality）*大概指的是状态随着树分支的增加以几何级数的趋势爆发
黑箱模型的杰作（只需采样）
计算处理上地高效，支持并行处理

时序差分搜索（Temporal-Difference Search）

基于模拟的搜索
采用TD来取代蒙特卡罗（自助法）
蒙特卡罗树搜索应用蒙特卡罗控制到部分MDP上
同理时序差分搜索应用SARSA控制到部分MDP上

蒙特卡罗对比时序差分搜索

对于无模型强化学习，自助法比较有用
- TD学习减少了方差但是增加偏差
- TD学习一般比蒙特卡罗更为高效
- (TD(lambda))比蒙特卡罗非常非常高效
对于基于模拟的搜索，自助法一样好用
- TD搜索减少方差但是增加偏差
- TD搜索一般比蒙特卡罗搜索要更为高效
- (TD(lambda))比蒙特卡罗搜索要非常非常高效

时序差分搜索

模拟从目前状态(s_t)开始的经验序列
估计动作-价值函数(Q(s,a))
对于每一步模拟，tguo1SARSA去更新动作价值函数

[Delta Q(S,A) = alpha(R + gamma Q(S',A') - Q(S,A)) ]
选择动作基于动作价值函数(Q(s,a))
- 例如说(epsilon-greedy)
同样Q也适用于函数近似

Dyna-2

在Dyna-2之中，智能体存储了两个特征权重的数据集
- 长期记忆
- 短期记忆（动态工作中）
长期记忆是从真实经验序列通过时序差分学习更新出来的
- 通用的知识可以应用于所有状态序列
短期记忆是基于模拟经验序列通过时序差分学习更新出来的
整个价值函数是长期记忆与短期记忆的求和