马尔可夫奖励过程 (MRP)

马尔可夫奖励过程（MRP）构成了理解通向 Dyna-Q 算法的基础。MRP 是一种随机过程，描述了一个系统的演变，并与每个状态转移相关联的奖励。它的特征包括：

  • 状态空间 (S)： 系统可能处于的一组状态。
  • 转移概率 (P)： 对于每个状态，转移到其他状态的概率。
  • 奖励函数 (r)： 一个为每个状态转移分配奖励值的函数。

价值函数的公式：

\[V(s)=r(s)+\gamma\sum_{s'\in S}p(s'|s)V(s')\]

马尔可夫决策过程 (MDP)

基于马尔可夫随机过程（MRP），马尔可夫决策过程（MDP） 引入了代理可以采取的行动的概念，以影响系统的状态转移。MDP 增加了：

  • 行动空间 (A)： 代理可以选择的一组可能的行动。
  • 策略 (π): 从状态到动作的映射，规定了智能体的行为。

状态价值函数和动作价值函数之间的关系：在使用策略中，状态的价值等于在该状态下基于策略采取所有动作的概率与相应的价值相乘再求和的结果：

\[V^{\pi}(s)=\sum_{a\in A}\pi(a|s)Q^{\pi}(s,a)\]

动作价值函数：使用策略时，状态下采取动作的价值等于即时奖励加上经过衰减后的所有可能的下一个状态的状态转移概率与相应的价值的乘积：

\[Q^{\pi}(s, a)=r(s, a)+\gamma\sum_{s'\in S}P(s'|s,a)V^{\pi}(s')\]

贝尔曼期望方程

解决马尔可夫决策过程（MDP）的一个关键工具是贝尔曼方程。该方程表达了一个状态的价值与其后继状态价值之间的关系。在策略π下，状态价值函数（V）的贝尔曼方程为：

\[V^{\pi}(s)=\sum_{a \in A} \pi(a | s)\left(r(s, a)+\gamma \sum_{s' \in S} p\left(s' | s, a\right) V^{\pi}\left(s'\right)\right)\] \[Q^\pi(s, a) = r(s, a) + \gamma \sum_{s' \in S} p(s' \mid s, a) \sum_{a' \in A} \pi(a' \mid s') Q^\pi(s', a')\]

贝尔曼最优方程

\[V^{*}(s)=max _{a \in \mathcal{A}}\left\{r(s, a)+\gamma \sum_{s' \in \mathcal{S}} p\left(s' | s, a\right) V^{*}\left(s'\right)\right\}\] \[Q^{*}(s, a)=r(s, a)+\gamma \sum_{s' \in \mathcal{S}} p\left(s' | s, a\right) max _{a' \in \mathcal{A}} Q^{*}\left(s', a'\right)\]

动态规划

动态规划（DP）算法，如策略迭代和价值迭代，利用贝尔曼方程在已知环境动态（转移概率和奖励）的情况下解决马尔可夫决策过程（MDP）。

基于动态规划的强化学习算法主要有两种：一是策略迭代（policy iteration），二是价值迭代（value iteration）。其中，策略迭代由两部分组成：策略评估（policy evaluation）和策略提升（policy improvement）。具体来说，策略迭代中的策略评估使用贝尔曼期望方程来得到一个策略的状态价值函数，这是一个动态规划的过程；而价值迭代直接使用贝尔曼最优方程来进行动态规划，得到最终的最优状态价值，然后通过价值函数导出对应的策略，导出策略的公式和策略提示的公式一致，计算出状态为$s$的情况下，哪个$a$会产生最大的状态价值函数，然后这个动作$a$就加大概率。

策略迭代在以下两个步骤之间交替：

  1. 策略评估： 计算给定策略的状态价值函数（V）。
\[V^{k + 1}(s)=\sum_{a \in A} \pi(a|s)\left(r(s, a)+\gamma\sum_{s' \in S}P\left(s'|s, a\right)V^{k}\left(s'\right)\right)\]
  1. 策略提升： 根据计算得出的状态值更新策略，选择能够导致更高状态值的行动，以最大化代理在一段时间内获得的期望累积奖励。
\[\pi'(s)=arg max _{a} Q^{\pi}(s, a)=arg max _{a}\left\{r(s, a)+\gamma \sum_{s'} P\left(s' | s, a\right) V^{\pi}\left(s'\right)\right\}\]

价值迭代则直接通过贝尔曼最优性方程迭代更新价值函数，该方程考虑了从一个状态可以实现的最大可能价值：

\[V^{k + 1}(s)=\max_{a\in\mathcal{A}}\{r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P(s'|s,a)V^{k}(s')\}\]

无模型强化学习

当环境的动态未知时，无模型强化学习算法被使用。这些方法通过与环境的互动直接从经验中学习。两个显著的无模型算法是Sarsa和Q-learning。

时间差分

时间差分是一种用来估计一个策略的价值函数的方法，它结合了蒙特卡洛和动态规划算法的思想。时序差分方法和蒙特卡洛的相似之处在于可以从样本数据中学习，不需要事先知道环境；和动态规划的相似之处在于根据贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的价值估计。

回顾一下蒙特卡洛方法对价值函数的增量更新方式：

\[V\left(s_{t}\right) \leftarrow V\left(s_{t}\right)+\alpha\left[G_{t}-V\left(s_{t}\right)\right]\]

蒙特卡洛方法必须要等整个序列结束之后才能计算得到这一次的回报$G_{t}$，而时序差分方法只需要当前步结束即可进行计算。具体来说，时序差分算法用当前获得的奖励加上下一个状态的价值估计来作为在当前状态会获得的回报，即：

\[V\left(s_{t}\right) \leftarrow V\left(s_{t}\right)+\alpha\left[r_{t}+\gamma V\left(s_{t+1}\right)-V\left(s_{t}\right)\right]\]

其中$r_{t}+\gamma V\left(s_{t+1}\right)-V\left(s_{t}\right)$通常被称为时序差分（temporal difference，TD）误差（error），时序差分算法将其与步长的乘积作为状态价值的更新量。

Sarsa 和 Q-learning都基于时间差分（TD）学习。它们通过更新动作价值函数（Q 值）的估计来学习，Q 值表示在某一状态下采取某个动作的预期回报，然后通过Q值去导出策略。Q值维护在一个2维的数据中Q_table(s,a)，导出策略的算法就是看状态$s$下，哪个动作$a$下的Q值最大，那么对应的动作$a$的概率就就大。

Sarsa算法

Sarsa 是一种 在线策略 算法，这意味着它学习当前所遵循策略的价值。它的更新规则使用在下一个状态中采取的行动，该行动是从当前策略中采样得出的：用贪婪算法根据动作价值选取动作来和环境交互，再根据得到的数据用时序差分算法更新动作价值估计。

\[Q\left(s_{t}, a_{t}\right) \leftarrow Q\left(s_{t}, a_{t}\right)+\alpha\left[r_{t}+\gamma Q\left(s_{t+1}, a_{t+1}\right)-Q\left(s_{t}, a_{t}\right)\right]\]

多步Sarsa算法

多步Sarsa 是为了结合蒙特卡洛方法低偏差和时序差分算法低方差的优势，使用$n$步的奖励，然后使用之后状态的价值估计。用公式表示：

\[Q\left(s_{t}, a_{t}\right) \leftarrow Q\left(s_{t}, a_{t}\right)+\alpha\left[r_{t}+\gamma r_{t+1}+\cdots+\gamma^{n} Q\left(s_{t+n}, a_{t+n}\right)-Q\left(s_{t}, a_{t}\right)\right]\]

Q-Learning算法

Q-learning则是一种离线策略算法，这意味着它学习最优策略的价值，而不管它在探索时遵循的策略是什么。它的更新规则使用下一个状态中所有可能动作的最大 Q 值：

\(Q\left(s_{t}, a_{t}\right) \leftarrow Q\left(s_{t}, a_{t}\right)+\alpha\left[R_{t}+\gamma max _{a} Q\left(s_{t+1}, a\right)-Q\left(s_{t}, a_{t}\right)\right]\)

在线策略算法与离线策略算法

我们称采样数据的策略为行为策略（behavior policy），称用这些数据来更新的策略为目标策略（target policy）。在线策略（on-policy）算法表示行为策略和目标策略是同一个策略；而离线策略（off-policy）算法表示行为策略和目标策略不是同一个策略。Sarsa 是典型的在线策略算法，而 Q-learning 是典型的离线策略算法。判断二者类别的一个重要手段是看计算时序差分的价值目标的数据是否来自当前的策略，具体而言：

  • 对于 Sarsa，它的更新公式必须使用来自当前策略采样得到的五元组$(s, a, r, s, a’)$，因此它是在线策略学习方法；
  • 对于 Q-learning，它的更新公式使用的是四元组$(s, a, r, s’)$来更新当前状态动作对的价值$Q(s,a)$，数据中的$s$和$a$是给定的条件，$r$和$a’$皆由环境采样得到，该四元组并不需要一定是当前策略采样得到的数据，也可以来自行为策略，因此它是离线策略算法。 image.png

Dyna-Q

最后，Dyna-Q是一种基于模型的算法，结合了无模型和基于模型方法的各个方面。

  1. Q-learing更新： 基于来自环境的真实经验更新 Q 值。
  2. 模型更新： 使用经历过的转变更新环境模型。
  3. Q-planing： 在一定数量的步骤中，使用从模型生成的模拟经验进行 Q-learing更新。 Dyna-Q 基于经验转移维护环境模型。该模型随后用于生成模拟经验，这些模拟经验与真实经验一起用于通过 Q-learing更新 Q 值。模拟经验通过允许算法从假设场景中学习，帮助提高算法的样本效率。

整体展示

马尔可夫算法.excalidraw.svg

留下评论