初探强化学习(11)Dyna类型的强化学习

为什么研究Dyna类型的强化学习呢？
主要是因为这个类型的强化学习是融合了model-based和model free两个类型的强化学习。
主要参考的博客是这个。说实话，我也是时隔三天后，第三次看了这个博客才彻底明白的。至于为什么名师，是因为我中间分析了一下周莫凡的代码，同时我把这个博客最后的部分给看了，之前两次看这个博客之所以没看懂，第一是没有看代码，脑袋里没有具体的实现形式，第二个就是没仔细看文章。
下面为了方便自己以后能随时过来看文章，我决定把他的博客直接搬到我这里。

Dyna

由于不可能精确和完美的拟合真正环境，纯基于模型的强化学习效果往往很差。那有没有什么办法可以在一定程度上避免这一点呢？
那就把基于模型 + 不基于模型的强化学习结合起来吧！也就是Dyna算法框架了。

它既在模型中学习，也在交互中学习。即Dyna框架在每个迭代轮中，会先和环境交互，并更新价值函数、策略函数，接着进行n次模型的模拟预测，同样更新价值函数、策略函数。这样同时利用上了和环境交互的经历以及模型的预测。

根据描述，就需要有两个相互独立的模型，一个根据状态$s$和动作$a$得到下一个状态$s’$（策略函数），另一个根据当前状态$s$和动作$a$预测环境的奖励$r$（价值函数）。其中

• 从 $s$,$a$ 学习 $r$ 的预测过程是一个回归问题(regression problem)。
• 从 $s$,$a$ 学习 $s’$ 的选择过程是一个密度估计问题(density estimation problem)。

Dyna-Q

先看Dyna算法步骤：

具体解析步骤：

• 先初始化状态$s$和其任意动作$a$所对应的状态价值$Q(s,a)$。
• 初始化尝试要理解得到的模型$Model(s,a)$。
  $上面两步就是第一行的初始化$
• a)对于每一轮迭代，直接使用当前状态$S$,
• b)使用 ϵ-贪婪策略获取动作A，$A<-e-greddy(S,Q)$
• c)执行动作$A$，得到新状态$S’$和奖励$R$
• d)然后用Q-Learning更新价值函数$Q(S,A)$，$Q(S,A)=Q(S,A)+\alpha [R+\gamma maxaQ(S\prime ,a)-Q(S,A)]$
• e)用$R，S’$更新模型$Model(s，a)$—-
• （与真实环境交互完毕后，进行n次模拟）
  • 每次模拟都随机选择一个之前出现过的状态$S$, 并在此基础上随机选择一个动作$A$
  • 基于模型$Model(S,A)$得到$S′ $和$R$
  • 再使用Q-Learning更新价值函数：$Q(S,A)=Q(S,A)+\alpha [R+\gamma maxaQ(S\prime ,a)-Q(S,A)]$

    def learn(self):
        self.steps_per_episode = []
        for ep in range(self.episodes):
            while not self.maze.end:
                action_index = self.choose_action()
                self.state_actions.append((self.state, action_index))
                nxtState, reward = self.maze.step(action_index)
                # update Q-value
                self.Q_values[self.state][action_index] += self.lr * (reward + np.max(list(self.Q_values[nxtState].values())) - self.Q_values[self.state][action])
                # update model
                if self.state not in self.model.keys():
                    self.model[self.state] = { 
   }
                self.model[self.state][action_index] = (reward, nxtState)
                self.state = nxtState
                # loop n times to randomly update Q-value
                for _ in range(self.steps):
                    # randomly choose an state
                    rand_idx = np.random.choice(range(len(self.model.keys())))
                    _state = list(self.model)[rand_idx]
                    # randomly choose an action
                    rand_idx = np.random.choice(range(len(self.model[_state].keys())))
                    _action = list(self.model[_state])[rand_idx]
                    _reward, _nxtState = self.model[_state][_action]
                    self.Q_values[_state][_action] += self.lr * (_reward + np.max(list(self.Q_values[_nxtState].values())) - self.Q_values[_state][_action])
                    # end of game
            if ep % 10 == 0:
                print("episode", ep)
            self.steps_per_episode.append(len(self.state_actions))
            self.reset()

下面开始我的搬运工作，一字不差的搬运

在前面我们讨论了基于价值的强化学习(Value Based RL)和基于策略的强化学习模型(Policy Based RL)，本篇我们讨论最后一种强化学习流派，基于模型的强化学习(Model Based RL)，以及基于模型的强化学习算法框架Dyna。
本篇主要参考了UCL强化学习课程的第8讲和Dyna-2的论文。

1 基于模型的强化学习简介

基于价值的强化学习模型和基于策略的强化学习模型都不是基于模型的，它们从价值函数，策略函数中直接去学习，不用学习环境的状态转移概率模型，即在状态$s$下采取动作$a$,转到下一个状态$s\prime$的概率$P_{ss\prime }^a$。
而基于模型的强化学习则会尝试从环境的模型去学习，一般是下面两个相互独立的模型：一个是状态转移概率预测模型P，输入当前状态$s$和动作$a$，预测下一个状态$s\prime$。另一个是奖励预测模型R，输入当前状态$s$和动作$a$，预测环境的奖励$r$。即模型可以描述为下面两个式子：
—————————————— $S_{t+1}\sim P(S_{t+1}|S_t,A_t)$
—————————————— $R_{t+1}\sim R(R_{t+1}|R_t,A_t)$
如果模型$P$,$R$可以准确的描述真正的环境的转移模型，那么我们就可以基于模型来预测，当有一个新的状态$S$和动作$A$到来时，我们可以直接基于模型预测得到新的状态和动作奖励，不需要和环境交互。当然如果我们的模型不好，那么基于模型预测的新状态和动作奖励可能错的离谱。

从上面的描述我们可以看出基于模型的强化学习和不基于模型的强化学习的主要区别：即基于模型的强化学习是从模型中学习，而不基于模型的强化学习是通过环境交互的经历去学习。
下面这张图描述了基于模型的强化学习的思路：

2. 基于模型的强化学习算法训练流程

这里我们看看基于模型的强化学习算法训练流程，其流程和我们监督学习算法是非常类似的。
假设训练数据是若干组这样的经历：
$S_1,A_1,R_2,S_2,A_2,R_2,...,S_T$
对于每组经历，我们可以将其转化为$T-1$组训练样本，即：
$S_1,A_1\to S_2；S_1,A_1\to R_2$
$S_2,A_2\to S_3；S_2,A_2\to R_3$
…
$S_{T-1},A_{T-1}\to S_T,S_{T-1},A_{T-1}\to R_T$
右边的训练样本一起组成了一个分类模型或密度估计模型，输入状态和动作，输出下一个状态。 右边的训练样本一起组成了一个回归模型训练集，输入状态和动作，输出动作奖励值。
Note:基于模型的强化学习在这边可以体现出来。搭建模型的方式有两种：

1. 第一种是使用表格的形式将这些数据保存下来，以后使用这些模型致谢一查表的方式提取数据。
2. 第二种方式是使用监督学习的方式训练一个对应的神经网络，然后使用神经网络预测这些模型。

至此我们的强化学习求解过程和传统的监督学习算法没有太多区别了，可以使用传统的监督学习算法来求解这两个模型。

当然还可以更简单，即通过对训练样本进行查表法进行统计，直接得到$P(S_{t+1}|S_t,A_t)$的概率和$R(R_{t+1}|S_t,A_t)$的平均值，这样就可以直接预测。比使用模型更简单。

此外，还有其他的方法可以用来得到$P(S_{t+1}|S_t,A_t)$和$R(R_{t+1}|S_t,A_t)$，这个我们后面再讲。

虽然基于模型的强化学习思路很清晰，而且还有不要和环境持续交互优化的优点，但是用于实际产品还是有很多差距的。主要是我们的模型绝大多数时候不能准确的描述真正的环境的转化模型，那么使用基于模型的强化学习算法得到的解大多数时候也不是很实用。那么是不是基于模型的强化学习就不能用了呢？也不是，我们可以将基于模型的强化学习和不基于模型的强化学习集合起来，取长补短，这样做最常见的就是Dyna算法框架。

3. Dyna算法框架

Dyna算法框架并不是一个具体的强化学习算法，而是一类算法框架的总称。Dyna将基于模型的强化学习和不基于模型的强化学习集合起来，既从模型中学习，也从和环境交互的经历去学习，从而更新价值函数和（或）策略函数。如果用和第一节类似的图，可以表示如下图，和第一节的图相比，多了一个“Direct RL“的箭头，这正是不基于模型的强化学习的思路。

Dyna算法框架和不同的具体的不基于模型的强化学习一起，可以得到具体的不同算法。如果我们使用基于价值函数的Q-Learning，那么我们就得到了Dyna-Q算法。我们基于Dyna-Q来看看Dyna算法框架的一般流程.

4. Dyna-Q算法流程

这里我们给出基于价值函数的Dyna-Q算法的概要流程。假设模型使用的是查表法。

1. 初始化任意一个状态$s$,和任意一个动作$a$对应的状态价值$Q(s,a)$, 初始化奖励模型$R(s,a)$和状态模型$P(s,a)$
2. for i=1 to 最大迭代次数T：
   . a) S ← current state
   . b) A ← $ϵ-greedy(S,Q)$
   . c) 执行动作A,得到新状态$S^{\prime }$和奖励R
   . d) 使用Q-Learning更新价值函数：(公式在下一行)
   $Q(S,A)=Q(S,A)+\alpha [R+\gamma ma{x}_{a}Q(S^{\prime },a)-Q(S,A)$
   . e) 使用$S,A,S^{\prime }$更新状态模型$P(s,a)$，使用$S,A,R$更新奖励模型$R(s,a)$
   . f) for j=1 to 最大次数n：
   　　　　 i) 随机选择一个之前出现过的状态S, 在状态S上出现过的动作中随机选择一个动作A
   　　　　ii) 基于模型$P(S,A)$得到$S^{\prime }$, 基于模型R(S,A)得到R
   　　　　iii) 使用Q-Learning更新价值函数：(公式在下一行)
   　　　　$Q(S,A)=Q(S,A)+\alpha [R+\gamma ma{x}_{a}Q(S^{\prime },a)-Q(S,A)]$

从上面的流程可以看出，Dyna框架在每个迭代轮中，会先和环境交互，并更新价值函数和（或）策略函数，接着进行n次模型的预测，同样更新价值函数和（或）策略函数。这样同时利用上了和环境交互的经历以及模型的预测。

5. Dyna-2算法框架

在Dyna算法框架的基础上后来又发展出了Dyna-2算法框架。和Dyna相比，Dyna-2将和和环境交互的经历以及模型的预测这两部分使用进行了分离。还是以Q函数为例，Dyna-2将记忆分为永久性记忆（permanent memory）和瞬时记忆（transient memory）, 其中永久性记忆利用实际的经验来更新，瞬时记忆利用模型模拟经验来更新。
永久性记忆的Q函数定义为：
$Q(S,A)=\varphi (S,A{)}^T\theta$
瞬时记忆的Q函数定义为：
$Q^{\prime }(S,A)=\bar{\varphi }(S,A{)}^T\bar{\theta }$
组合起来后记忆的Q函数定义为：
$\bar{Q}(S,A)=\varphi (S,A{)}^T\theta +\bar{\varphi }(S,A{)}^T\bar{\theta }$
Dyna-2的基本思想是在选择实际的执行动作前，智能体先执行一遍从当前状态开始的基于模型的模拟，该模拟将仿真完整的轨迹，以便评估当前的动作值函数。智能体会根据模拟得到的动作值函数加上实际经验得到的值函数共同选择实际要执行的动作。价值函数的更新方式类似于SARSA(λ).

Dyna-2是将环境交互的经历以及模型的预测进行了分离。即不是像Dyna一样交互完了就拿来模模拟，而是对于Q函数将被分为永久性记忆$Q(S,A)$和瞬时记忆$Q^{{}^{\prime }}(S,A)$。其中永久性记忆利用与实际环境的交互经验来更新，瞬时记忆利用与模型的模拟交互来更新。然后两者结合起来共同 对作用起选择。

以下是Dyna-2的算法流程：

6. 基于模型的强化学习总结

基于模型的强化学习一般不单独使用，而是和不基于模型的强化学习结合起来，因此使用Dyna算法框架是常用的做法。对于模型部分，我们可以用查表法和监督学习法等方法，预测或者采样得到模拟的经历。而对于非模型部分，使用前面的Q-Learning系列的价值函数近似，或者基于Actor-Critic的策略函数的近似都是可以的。

除了Dyna算法框架，我们还可以使用基于模拟的搜索(simulation-based search)来结合基于模型的强化学习和不基于模型的强化学习,并求解问题。这部分我们在后面再讨论。

今天的文章初探强化学习(11)Dyna类型的强化学习分享到此就结束了，感谢您的阅读。