CS229 Lesson 17 离散与维数灾难

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了无限状态的马尔可夫决策过程。

连续状态的MDP

到目前为止，我们都是将注意力集中在具有有限数量状态的MDP上。我们现在讨论可能具有无限状态的MDP的算法。例如，对于汽车，我们可以用$(x,y,\theta,\dot x, \dot y,\dot \theta)$表示汽车的状态，包括位置$(x,y)$；方向角$\theta$，$x$和$y$方向上的加速度$\dot x$和$\dot y$；以及角速度$\dot \theta$。因此，$S =\mathbb R^6$是一个无限状态集合，因为汽车可能的位置以及方向有无限多个。

​ 在这部分中，我们将考虑状态空间为$S= \mathbb R^n$的情形，并描述解决此类MDP的方法。

4.1离散化

也许解决连续状态MDP的最简单方法是让状态空间离散化，然后使用之前所述的值迭代或策略迭代这样的算法来求解。

​ 例如，如果我们有2维状态$(s_1, s_2)$，我们可以利用网格离散化状态空间：

这里，每个网格单元代表不同的离散状态$\bar s$。我们可以通过离散状态$(\bar S,A,\{P_{\bar sa}\},\gamma, R)$来近似连续状态MDP，其中$\bar S$是离散状态的集合，$\{P_{\bar sa}\}$是在离散状态下的状态转移概率，其余部分类似。我们可以用值迭代或策略迭代来求解离散状态MDP$(\bar S,A,\{P_{\bar sa}\},\gamma, R)$的$V’(\bar s)$和$\pi’(\bar s)$。当我们的实际系统处于某个连续值状态$s\in S$并且我们需要选择要执行的动作时，我们计算相应的离散状态$\bar s $，并执行动作$\pi’(\bar s)$。

​ 这种离散化方法可以很好地解决许多问题。但是，这种方法有两个缺点。首先，它对$V’(\bar s)$和$\pi’(\bar s)$使用了相当粗糙的表示。具体地，它假设价值函数在每个离散化间隔上取恒定值（即，价值函数在每个网格单元中是分段常数）。

​ 为了更好地理解这种表示的局限性，考虑对以下数据集拟合的监督学习问题：

​ 显然，线性回归在这个问题上会做得很好。 但是，如果我们将$x$轴离散化，然后在每个离散间隔中使用分段常数的表示，那么我们对数据的拟合将如下所示：

​ 对许多光滑函数，这种分段常数表示都不是一种很好的表示。 它导致输入不平滑，并且不会对不同的网格单元进行泛化。 使用这种表示，我们还需要非常精细的离散化（非常小的网格单元）来获得良好的近似。

​ 第二个缺点是维数灾难。 假设$S=\mathbb R^n$，我们将$n$维状态的每一维离散化为$k$个值。 然后我们所拥有的离散状态的总数是$k^n$。该数量以指数方式快速增长，因此不能很好地扩展到大问题。 例如，对于$10$维状态，如果我们将每个状态变量离散化为$100$个值，那么我们将有$100^{10}=10^{20}$个离散状态，远远超过现代台式计算机能表示的范围。

​ 根据经验，离散化通常对于$1$维和$2$维问题非常有效（并且具有简单且能够快速实现的优点）。如果在选择离散化方法时聪明和谨慎一些，它通常适用于最多$4$维的问题。 如果你非常聪明，并且有点幸运，你甚至可以让它在$6$维问题上有效。但它很少适用于任何更高维度的问题。

​

4.2 价值函数近似

我们现在描述一种在连续状态MDP中寻找策略的替代方法，在该方法中，我们直接逼近$V’$，而不依赖于离散化。 这种方法，被称为价值函数近似，已经成功应用于许多RL问题。

4.2.1 使用模型或模拟器

为了开发一个价值函数近似算法，假设我们有一个MDP模型或模拟器。 非正式地，模拟器是一个黑盒子，它将任何（连续值）状态$s_t$和动作作为输入，然后输出根据状态转移概率$P_{s_ta_t}$采样下一状态$s_{t+1}$：

​ 有几种方法可以获得这样的模型。一种是使用物理模拟。例如，问题集4中倒立摆的模拟器是通过使用物理定律来计算推车/杆在时间$t+1$处的位置和方向，给定时间$t$的当前状态和采取的动作$a$，假设我们知道系统的所有参数，例如杆的长度，杆的质量等等。 或者，也可以使用现成的物理模拟软件包，它将机械系统的完整物理描述，当前状态$s_t $和动作$a_t$作为输入，并计算系统未来几分之一秒的状态$s_{t+1}$。

​ 获取模型的另一种方法是从MDP中收集的数据中学习一个。 例如，假设我们执行$m$次试验，每次试验为$T$个时间步长。这可以通过随机选择动作，然后执行某些特定策略或通过其他方式选择动作来完成。然后我们将观测到$m$个状态序列，如下所示：

$$s_0^{(1)} \overset{a_0^{(1)}} \longrightarrow s_1^{(1)} \overset{a_1^{(1)}} \longrightarrow s_2^{(1)} \overset{a_2^{(1)}} \longrightarrow ... \overset{a_{T-1}^{(1)}} \longrightarrow s_T^{(1)} \\ s_0^{(2)} \overset{a_0^{(2)}} \longrightarrow s_1^{(2)} \overset{a_1^{(2)}} \longrightarrow s_2^{(2)} \overset{a_2^{(2)}} \longrightarrow ... \overset{a_{T-1}^{(2)}} \longrightarrow s_T^{(2)} \\ ...\\ s_0^{(m)} \overset{a_0^{(m)}} \longrightarrow s_1^{(m)} \overset{a_1^{(m)}} \longrightarrow s_2^{(m)} \overset{a_2^{(m)}} \longrightarrow ... \overset{a_{T-1}^{(m)}} \longrightarrow s_T^{(m)} \\$$

然后我们可以应用学习算法来预测$s_{t+1}$作为$s_t$和$a_t$的函数。

​ 例如，我们可以选择如下线性模型

$$s_{t+1}= As_t + Ba_t \tag {5}$$

然后利用类似线性回归的算法。这里，模型的参数为矩阵$A$和$B$，然后我们可以利用$m$次实验收集的数据来估计参数，选择

$$\arg \min_{A,B} \sum_{i=1}^m \sum_{t=0}^{T-1} \Big |\Big| s_{t+1}^{(i)}- \Big(As_{t}^{(i)}+B a_t^{(i)} \Big)\Big |\Big|^2$$

​ 在学习了$A$和$B$之后，一个选择是建立一个确定性模型，其中给定输入$ s_t$和$a_t $，输出$s_{t+1} $被精确确定。具体而言，我们总是根据等式（5）计算$s_{t+1}$。 或者，我们也可以建立一个随机模型，其中$s_{t+1 }$是输入的随机函数，通过将其建模为

$$s_{t+1}= As_t + Ba_t + \epsilon_t$$

这里$\epsilon_t$是一个噪声项，通常建模为$\epsilon_t \sim \mathcal N(0,\Sigma)$。（协方差矩阵$\Sigma$也可以直接从数据中估算出来。）

​ 这里，我们将下一状态$s_{t+1} $写为当前状态和动作的线性函数；当然，非线性函数也是可能的。 具体来说，可以学习模型$s_{t+1}=A\phi_s(s_t)+B\phi_a(a_t)$，其中$\phi_s$和$\phi_a$是状态和动作的一些非线性映射。或者，也可以使用非线性学习算法， 例如局部加权线性回归，将$s_{t + 1}$作为$s_t$和$a_t$的函数进行估计。 这些方法也可用于构建MDP的确定性或随机模拟器。

4.2.2 拟合值迭代

我们现在描述拟合值迭代算法，用于近似连续状态MDP的价值函数。 在下文中，我们将假设问题具有连续的状态空间$S=\mathbb R^n$，但是动作空间$A$是规模小的离散空间。

​ 回顾一下，在值迭代中，我们想要执行更新

$$\begin{aligned} V(s): &= R(s) + \gamma\max_{a} \int_{s'} P_{sa}(s') V(s')ds' \\ &=R(s) + \gamma\max_{a}\mathbb E_{s'\sim P_{sa}}[V(s')] \end{aligned}\tag 6$$

注意这里使用积分号而不是求和号是因为此处为连续情形。

​ 拟合值迭代的主要思想是我们将在状态$s^{(1)},…,s^{(m)}$的有限样本上大致执行以下步骤。具体来说，我们将在下面的描述中使用监督学习算法——线性回归——将价值函数近似为状态的线性或非线性函数：

$$V(s)= \theta^T \phi(s)$$

这里，$\phi$是状态的某种特征映射。对于$m$个状态的有限样本中的每个状态$s$，拟合值迭代将首先计算$y^{(i)}$，这将是我们对$R(s) + \gamma\max_{a}\mathbb E_{s’\sim P_{sa}}[V(s’)]$的近似。然后，它将应用监督式学习算法以试图使$V(s)$接近$R(s) + \gamma\max_{a}\mathbb E_{s’\sim P_{sa}}[V(s’)]$（或者换句话说，试图使$V(s) $接近$y^{(i)}$）。

​ 具体的，算法如下：

• 1.从$S$中随机抽取$m$个状态$s^{(1)},s^{(2)},…s^{(m)}\in S$

• 2.初始化$\theta:=0$

• 3.重复{

  • 对$i=1,…,m$ {
    • 对每个$a\in A$ {
      • 取样$s_1’,…,s_k’\sim P_{s^{(i)}a}$（使用MDP模型）
        • 令$q(a)=\frac 1k \sum_{j=1}^k R(s^{(i)}) + \gamma V(s_j’)$
          • //因此，$q(a)$是对$R(s^{(i)}) + \gamma\mathbb E_{s’\sim P_{s^{(i)}a}}[V(s’)]$的估计
    • }
      • 令$y^{(i)}=\max_a q(a)$
        • //因此，$y^{(i)}$是对$R(s^{(i)}) + \gamma\max_{a}\mathbb E_{s’\sim P_{s^{(i)}a}}[V(s’)]$的估计
  • }
  • //在原本的值迭代算法中（离散状态的情形）
  • //我们根据$V(s^{(i)}):= y^{(i)}$更新价值函数
  • //在该算法中，我们希望$V(s^{(i)})\approx y^{(i)}$，这里将使用监督学习算法（线性回归）
  • 令$\theta :=\arg\min_{\theta}\frac 1 2 \sum_{i=1}^m (\theta^T\phi(s^{(i)})-y^{(i)})^2$
• }

​ 以上，我们给出一个使$V(s^{(i)})$逼近$y^{(i)} $的值迭代算法，该算法使用线性回归。该算法的该步骤完全类似于标准监督学习（回归）问题，其中我们具有训练集$(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),…,(x^{(m)},y^{(m)})$，并且想要学习从$x$到$y$的函数映射; 唯一的区别是$s$在这里扮演$x$的角色。 尽管我们上面的描述使用了线性回归，但显然也可以使用其他回归算法（例如局部加权线性回归）。

​ 与离散状态集上的值迭代不同，拟合值迭代不能被证明总是收敛。 然而，在实际中，它经常会收敛（或近似收敛），并且适用于许多问题。另请注意，如果我们使用MDP的确定性模拟器/模型，则可通过在算法中设置$k = 1$来简化拟合值迭代。这是因为等式（6）中的期望成为对确定性分布的期望，因此单个样本足以精确地计算该期望。 否则，在上面的算法中，我们不得不获得$k$个样本，并求平均值以尝试近似该期望（参见算法伪代码中的$q(a)$的定义）。

​ 最后，拟合值迭代的输出$V$是$V’$的近似值。这隐含地定义了我们的策略。 具体来说，当我们的系统处于某个状态$s$时，我们需要选择一个动作，我们想选择该动作为

$$\arg\max_a \mathbb E_{s'\sim P_{sa}}[V(s')]\tag 7$$

计算/近似的过程类似于拟合值迭代的内层循环，对于每个行动，我们采样$s_1’,…,s_k’\sim P_{sa}$来近似期望值。（如果模拟器是确定性的，我们可以设置$k=1$。）

​ 在实际中，通常还有其他方法来逼近这一步骤。例如，一个非常常见的情况是模拟器的形式为$s_{t + 1}= f(s_t,a_t)+\epsilon_t$，其中$f$是某些关于状态的确定性函数（例如$f(s_t,a_t)= As_t + Ba_t$），$\epsilon$是零均值高斯噪声。 在这种情况下，我们可以按如下方式给出动作

$$\arg\max_a V(f(s,a))$$

换句话说，这里我们设定$\epsilon_t=0$（即忽略模拟器中的噪声），并设置$k = 1$。或者等价地，这可以使用近似从等式（7）导出

$$\begin {aligned} \mathbb E_{s'}[V(s')] &\approx V(\mathbb E_{s'}[s'])\\ &= V(f(s,a)) \end {aligned}\tag 8$$

在这里的期望是关于$s’\sim P_{sa}$的。 只要噪声项$\epsilon_t$很小，这通常是合理的近似值。

​ 然而，对于不适合这种近似的问题，必须使用该模型采样$k|A|$个状态，用来接近上述期望，但这可能在带来很大计算量。