RL-Lec8 整合学习与规划

介绍

本节主要介绍如何从经历中直接学习模型、如何构建一个模型、如何基于模型来进行“规划”，再在此基础上将“学习”和“规划”整合起来。

无模型（Model-Free）强化学习：没有模型，从经验中学习值函数（或策略）。
基于模型（Model-Based）强化学习：通过经验学模型，利用模型规划值函数（或策略）。

前面介绍的主要是无模型的强化学习方法，后面讲主要关注基于模型的强化学习。

基于模型的强化学习

当学习值函数或策略变得很困难时，学习模型可能是一条不错的路径，模型可以从一个方面对个体理解环境提供帮助，但不会完全是真实的环境运行机制，会存在一定程度上的近似。不过，通过模型，个体不再局限于如何最大化奖励本身，还能在一定程度上了解采取的行动是否有效，具备一定的推理能力。

模型 $\mathcal M$ 是一个 MDP $\langle\mathcal S,\mathcal A,\mathcal P,\mathcal R\rangle$ 的参数化 ($\eta$) 表现形式，其中假定状态空间 $\mathcal S$ 和行动空间 $\mathcal A$ 是已知的。这样，模型 $\mathcal M=\langle\mathcal P_\eta,\mathcal R_\eta\rangle$ 呈现了状态转移 $\mathcal P_\eta\approx\mathcal P$ 和奖励 $\mathcal R_\eta\approx\mathcal R$：

$S_{t+1}\sim\mathcal P_\eta(S_{t+1}\mid S_t,A_t),\quad R_{t+1}=\mathcal R_\eta(R_{t+1}\mid S_t,A_t).$

通常我们需要假设状态转移函数和奖励函数是条件独立的，即

$\mathbb P(S_{t+1},R_{t+1}\mid S_t,A_t)=\mathbb P(S_{t+1}\mid S_t,A_t)\mathbb P(R_{t+1}\mid S_t,A_t).$

我们可以用监督式学习来构建模型，目标是从经历 ${S_1,A_1,R_2,\dots,S_T}$ 中估计一个模型 $\mathcal M_\eta$，训练集为

$S_1,A_1\rightarrow R_2,S_2,\quad S_2,A_2\rightarrow R_3,S_3,\quad\cdots,\quad S_{T-1},A_{T-1}\rightarrow R_T,S_T.$

从 $s,a$ 学习 $r$ 的过程是一个回归问题，学习 $s’$ 的过程是一个密度估计问题。进一步选择一个损失函数（如MSE、KL散度等），通过优化参数 $\eta$ 来最小化经验损失，就可以解决上述问题。

根据使用的算法不同，可以有如下多种模型：

查表式（Table Lookup Model）
线性期望模型（Linear Expectation Model）
线性高斯模型（Linear Gaussian Model）
高斯决策模型（Gaussian Process Model）
深信度神经网络模型（Deep Belief Network Model）

查表模型

下面以查表式模型来解释模型的构建，它的主要想法是通过经历得到各状态行为转移概率和奖励，把这些数据存入表中，使用时直接检索。其中，状态转移概率和奖励计算方法如下：

$\begin{array}{rl} \hat{\mathcal P}_{ss'}^a=&\!\!\!\!\displaystyle\dfrac{1}{N(s,a)}\sum_{t=1}^T\pmb 1((S_t,A_t,S_{t+1})=(s,a,s')),\\ \hat{\mathcal R}_s^a=&\!\!\!\!\displaystyle\dfrac{1}{N(s,a)}\sum_{t=1}^T\pmb 1((S_t,A_t)=(s,a))R_t. \end{array}$

在实际应用中，在学习的每一步，记录状态转换 $\langle S_t,A_t,R_{t+1},S_{t+1}\rangle$，从模型采样构建虚拟经历时，从这些片段中随机选择符合 $\langle s,a,\cdot,\cdot\rangle$ 的一个片段，提供给个体进行值函数或策略函数的更新。

基于采样的规划

规划过程就是一个MDP的过程：给定一个模型 $\mathcal M_\eta=\langle\mathcal P_\eta,\mathcal R_\eta\rangle$，通过求解MDP $\langle\mathcal S,\mathcal A,\mathcal P_\eta,\mathcal R_\eta\rangle$ 找到最优值函数或最优策略。

基于学习得到的模型 $\mathcal M_\eta$，可以用DP方法求解，也可以用基于采样的规划。这里，模型 $\mathcal M_\eta$ 只用来提供样本，基于这些样本再采用无模型强化学习方法（如MC、Sarsa、Q-Learning）来求解。这种方法通常更有效。

注意，由于实际经历的不足或者一些无法避免的缺陷，通过实际经历学习得到的模型不可能是完美的模型，最终得到的最优策略也通常与真实MDP的最优策略有差距。

架构整合：Dyna算法

当构建了一个环境的模型后，个体可以有两种经历来源：实际经历和模拟经历。

实际经历：来源于真实MDP的环境 $S’\sim\mathcal P_{ss’}^a$，$R=\mathcal R_s^a$；
模拟经历：来源于虚拟MDP的模型 $S’\sim\mathcal P_\eta(S’\mid S,A)$，$R=\mathcal R_\eta(R\mid S,A)$。

我们可以把无模型的真实经历和基于模型采样得到的模拟经历结合起来，提出一种新的架构：Dyna算法。

Dyna算法从实际经历中学习得到模型，然后联合使用实际经历和模拟经历一边学习，一边规划更新价值和（或）策略函数。Dyna-Q算法如下：

这个算法赋予了个体在与实际环境进行交互时有一段时间来思考的能力。在思考环节（f步），个体将使用模型，在之前观测过的状态空间中随机采样一个状态，同时在这个状态下曾经使用过的行为中随机选择一个行为，将两者代入模型得到新的状态和奖励，据此再次更新行动值函数。

基于模拟的搜索

首先来看前向搜索，这是一种以前向的方式选择最佳的行动的搜索方式，它把当前状态 $s_t$ 作为根节点构建一棵搜索树，并使用MDP模型进行前向搜索。这种方法的好处在于，不需要解决整个MDP，仅仅需要构建一个从当前状态开始与未来的相关的子MDP问题即可。

基于模拟的搜索借用了前向搜索的思想，其步骤如下：

从当前时刻 $t$ 开始，从模型中进行模拟采样，形成从当前状态 $s_t$ 开始到终止状态 $S_T$ 的一系列经历： $\{s_t^k,A_t^k,R_{t+1}^k,\dots,S_T^k\}_{k=1}^K\sim\mathcal M_\eta.$
然后对这个模拟经历使用无模型的强化学习方法（MC或TD等）。

简单蒙特卡洛搜索

若采用蒙特卡洛控制，则为蒙特卡洛搜索方法，其具体步骤如下：

给定一个模型 $\mathcal M_\eta$ 和一个模拟策略 $\pi$；
针对行动空间中的每一个行动 $a\in\mathcal A$，
- 从当前状态 $s_t$ 开始模拟出 $K$ 个经历： $\{s_t,a,R_{t+1}^k,\dots,S_T^k\}_{k=1}^K\sim\mathcal M_{\eta,\pi}.$
- 使用平均收获来评估当前行动 $a$ 的行动值函数： $\displaystyle q(s_t,a)=\dfrac{1}{K}\sum_{k=1}^KG_t.$
选择一个有最大 $q(s_t,a)$ 的行动作为实际要采取的行动 $a_t$。

注意，如果模拟策略 $\pi$ 本身不是很好的话，基于该策略产生的行动 $a_t$ 就可能不是状态 $s_t$ 下的最优行动。

蒙特卡洛树搜索（MCTS）

与简单蒙特卡洛搜索不同的是，蒙特卡洛树搜索方法将评估整个搜索树中每一个状态行动对的值函数，并在此基础上改善模拟策略。

具体来说，在当前状态 $s_t$ 模拟出 $K$ 个经历后，MCTS构建一个包括所有个体经历过的状态和行动的搜索树，对于搜索树中的每一个状态行动对 $(s,a)$，计算从该 $(s,a)$ 开始的所有完整经历收获的平均值，以此来估计该状态行动对的值函数，即

$\displaystyle q(s,a)=\dfrac{1}{N(s,a)}\sum_{k=1}^K\sum_{u=t}^T\pmb 1((S_u,A_u)=(s,a))G_u.$

然后再选择一个有最大 $q(s_t,a)$ 的行动作为实际要采取的行动 $a_t$。

在改善模拟策略时，由于搜索树中并不包括所有状态行动对空间内的值函数估计，因此需要分为两个阶段：

树内确定性策略（Tree Policy）：选择最大化 $q(s,a)$ 的行动。
树外默认策略（Default Policy）：随机选择一个行动。

对每个模拟策略，重复上述评估与改进步骤，最终这种方法可以收敛到全局最优搜索树。

MCTS是具有高度选择性的、基于导致越好结果的行为越被优先选择的一种搜索方法，它可以动态评估各状态的价值，立足当前状态，动态更新与该状态相关的状态价值。

时序差分搜索

蒙特卡洛树搜索通过对当前状态开始的一个子MDP应用蒙特卡洛控制，那么时序差分搜索就是对当前状态开始的一个子MDP应用Sarsa学习。在基于模拟的搜索时，TD搜索多数时候也是优于MC搜索的，特别是TD($\lambda$)搜索。

对于TD搜索，其具体步骤如下：

从当前实际状态 $s_t$ 开始，模拟一系列经验，在这一过程中使用状态行动价值作为节点录入搜索树。
对搜索树内的每一个节点（状态行动对），估计其价值 $q(s,a)$。
对于模拟过程中的每一步，使用Sarsa学习更新行动值函数： $\Delta q(s,a)=\alpha(R+\gamma q(s',a')-q(s,a)).$
基于 $q$ 值，使用 $\varepsilon$-贪婪或其它探索方法来生成行动。

相比于MC搜索，TD搜索不必模拟经历到终止状态，它仅仅聚焦于某一个节点的状态，这对于一些有回路或众多旁路的节点来说更有意义。

如果采用线性的TD搜索，即对行动值函数进行参数化 $q_\theta(s,a)=\phi(s,a)^\textsf{T}\theta\approx q^\pi(s,a)$，则更新时采用

$\Delta\theta=\alpha(r_{u+1}+\gamma q_\theta(s_{u+1},a_{u+1})-q_\theta(s_u,a_u))\phi(s_u,a_u)$

即可。

Dyna-2算法

Dyna算法一边从实际经历中学习，一边从模拟经历中学习。如果将基于模拟的搜索应用到Dyna算法，就变成了Dyna-2算法。

使用Dyna-2算法的个体维护了两套特征权重：

一套反映了个体的长期记忆，该记忆是从真实经历中使用TD学习得到的，它反映了个体对于某一特定强化学习问题的普遍性的认识。
另一套反映了个体的短期记忆，该记忆是从基于模拟经历中使用TD搜索得到的，它反映了个体对于某一特定强化学习问题在特定条件下的特定的、局部适用的认识。

Dyna-2算法最终将两套特征权重下产生的价值综合起来进行决策，以期得到更优秀的策略。

这里 $q(s,a)=\phi(s,a)^\textsf{T}\theta$，$\overline{q}(s,a)=\phi(s,a)^\textsf{T}\theta+\overline{\phi}(s,a)^\textsf{T}\overline{\theta}$。

后记

本文内容来自中国科学技术大学《强化学习》（2022Fall）课件。

如对本文内容有任何疑问，请联系 watthu@mail.ustc.edu.cn。

Integrating Learning and Planning

介绍