强化学习：贝尔曼方程与马尔可夫决策过程

一、简介

贝尔曼方程和马尔可夫决策过程是强化学习非常重要的两个概念，大部分强化学习算法都是围绕这两个概念进行操作。尤其是贝尔曼方程，对以后理解蒙特卡洛搜索、时序差分算法以及深度强化学习算法都至关重要。这篇文章主要介绍贝尔曼方程。

常用的资料：

《Reinforcement Learning: An Introduction》 author: Richard S.Sutton and Andrew G.Barto

UCL Course: https://www.davidsilver.uk/teaching/

博客园：https://www.cnblogs.com/pinard/

二、马尔可夫决策过程

熟悉自然语言处理的同学一定对马尔可夫（Markov）并不陌生，隐马尔科夫模型，条件随机场中都有利用到马尔可夫性质。马尔可夫描述这样一个随机过程：如果一个系统有 $N$ 个状态 $S_1,S_2,…,S_N$ ，随着时间的推移，该系统从某一个状态转移到另一个状态。如果用 $q_t$ 表示系统在时间 $t$ 的状态变量，那么 $t$ 时刻的状态取值为 $S_j$ 的概率取决于前 $t - 1$ 个时刻，该概率为：
$\tag{1} p(q_t=S_j|q_{t-1}=S_i,q_{t-2}=s_k,…)$
意思很好理解，就是某一时刻状态的取值，取决于前面所有时刻的状态，画图表示为：
在这里插入图片描述

在这里插入图片描述

这样一看，模型就简化很多了，虽然可能会带来模型上的误差，但相比较于难以计算的复杂度，这点误差还是可以接受的。2. 时间独立性假设。可以设想这么一个情况，如果时刻 $j$ 和时刻 $j + 1$ 的状态是 $a$ 和 $b$ ，在 $i$ 和 $i + 1$ 时刻的状态也分别是 $a$ 和 $b$ ，那么时间独立性可以表示为：
$\begin{aligned} p_1&=p(q_{j+1}=b|q_j=a)\\ p_2&=p(q_{i+1}=b|q_i=a)\\\tag{3} p_1&=p_2 \end{aligned}$
也就是只要前一个时刻的状态是 $a$ ，那么后一个时刻的状态是 $b$ 的概率是固定的，此概率和 $a$ 所在的时刻（ $i$ 或者 $j$ ）无关。那么既然和时间是无关的，那么由状态 $a$ 转移到状态 $b$ 的概率就可以写作：
$p(b|a)\tag{4}$
从而，我们得到马尔可夫模型，一阶独立性假设和时间独立性假设。

三、强化学习中的马尔可夫决策过程

回想一下强化学习中的一个重要概念，概率转化模型，也就是 $p^a_{ss^,}$ ，代表的是，在状态 $s$ 下，采取动作 $a$ 后，转移到状态 $s^,$ 的概率。此变量的定义其实已经暗含了马尔科夫假设：状态 $s^,$ 发生的概率仅仅和上一时刻的状态 $s$ 相关。当然，还和动作 $a$ 相关，但这个动作 $a$ 可以看作是环境的输入（想一想条件随机场）。因此，可以用数学表达为：
$p_{ss^,}^a=p(s^,|s,a)\tag{5}$
这个假设极大的简化了强化学习的状态转移矩阵。此外，除了马尔可夫假设之外，还有一个比较重要的假设，就是对策略 $\pi$ 的假设，回想一下策略 $\pi$ 的定义，在状态 $s$ 下，agent采取动作 $a$ 的概率，表达为概率形式：
$\begin{aligned} \pi(a|s)=p(a|s) \end{aligned}$
其实也隐含了一个假设，那就是agent的动作 $a$ 只和状态 $s$ 有关。

四、贝尔曼方程

如果要说强化学习中最重要的一个公式，那么非贝尔曼方程莫属了，本文将以图表和公式的形式来解释贝尔曼方程，争取能以一种接近人的思维去解释贝尔曼方程。

首先引入一个变量，叫做动作价值函数， $q_{\pi}(s,a)$ ，它的含义是在状态 $s$ 下，采取动作 $a$ 后所期望获得的总回报。对比一下价值函数 $v_\pi (s)$ 的定义，状态s下，期望获得的总回报，显然，二者的区别在于动作价值函数在状态 $s$ 下多了一个动作 $a$ 的限制。言语无法解释，直接上图：

在这里插入图片描述

假设agent初始状态为 $A$ ，在 $t = 1$ 时刻，采取了动作 $a_{11}$ (其他可能的动作 $a_{12},a_{13}$ )，那么之后可能发生的状态都如红框中所示，而动作价值函数 $q_\pi(s,a)$ 代表的就是红框中所能获得回报期望，也就是状态 $A$ 到达所有红框中叶子节点（终点）的回报期望值。从上节的定义中可知，价值函数 $v_\pi (s)$ 代表从状态 $s$ 到达所有叶子节点的总回报的期望，因此可以看出来，动作价值函数只是价值函数的一部分。那么怎么由动作价值函数去获得价值函数呢？看下图：
在这里插入图片描述

如图所示，我们可以把整个状态树可以分成三个分支，分别代表执行 $a_{11}$ 产生的动作价值函数 $q_\pi(A,a_{11})$ ，执行 $a_{12}$ 产生的动作价值函数 $q_\pi(A,a_{12})$ ，和执行 $a_{13}$ 产生的动作价值函数 $q_\pi(A,a_{13})$ 。而价值函数 $v_\pi(A)$ 由于代表的是 $A$ 到达所有叶子节点的回报的期望，因此，将这三个分支相加不就是总的价值函数了吗？由此可以得到下式
$v_\pi(s)=\pi(a_{11}|A) q_\pi(A,a_{11})+\pi(a_{12}|A)q_\pi(A,a_{12})+\pi(a_{13}|A)q_\pi(A,a_{13})\tag{6}$
注意由于是求期望，我们还要乘以各自分支发生的概率 $\pi(a|s)$ 。从而，我们得到了第一个重要的公式，也就是关联动作价值函数和价值函数的等式：
$v_\pi(s)=\sum_{a}\pi(a|s)q_\pi(s,a)\tag{7}$
它代表的是，一个状态的价值函数，由此状态可能发生的动作价值函数构成，也就是一棵树可以由若干个分支构成，每一个分支是由一个动作产生，这个动作的概率由 $\pi$ 决定，此分支的动作价值函数记为 $q_\pi(s,a)$ 。

贝尔曼方程

在这里插入图片描述

如图所示，状态 $s$ 选择一个动作后，可能会转到某一个橘色状态，如果我们知道了橘色状态的价值（橘色节点代表的子树所有叶子节点奖励的总和的期望值），那么我们就不需要知道计算到叶子节点了，因为橘色的状态足以代表叶子节点。从而，贝尔曼方程实际上为我们提供了一个递归的方式求解问题：计算根节点的价值时，不需要遍历整棵树，而只需要利用根节点的子节点价值。这不是递归的典型特点吗？一个大的问题（求解整棵树的价值)可以由子问题去求解（子节点的价值)。同理，我们也可以得到动作价值函数的贝尔曼方程：
$q_\pi(s,a)=E_\pi(R_{t+1}+\gamma Q(S_{t+1}, A_{t+1})|S_t=s, A_t=a)\tag{17}$
贝尔曼方程是我们后续动态规划、时序差分算法的基础，一定要理解其中的含义。

动作价值函数和价值函数的关系

在这里插入图片描述

这些公式，我们都可以找到他们的物理含义，都可以找到他们在状态树上的定义，我们一定要理解着去记忆，明白他们数学推导后的物理含义。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/209690.html原文链接：https://javaforall.net

强化学习：贝尔曼方程与马尔可夫决策过程