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_{t+1}$作为$s_t$和$a_t$的函数。

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

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

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

这里$\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$是规模小的离散空间。

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

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

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

这里,$\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$时,我们需要选择一个动作,我们想选择该动作为

计算/近似的过程类似于拟合值迭代的内层循环,对于每个行动,我们采样$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$是零均值高斯噪声。 在这种情况下,我们可以按如下方式给出动作

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

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

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

本文标题:CS229 Lesson 17 离散与维数灾难

文章作者:Doraemonzzz

发布时间:2019年01月14日 - 14:57:00

最后更新:2019年03月28日 - 14:20:31

原始链接:http://doraemonzzz.com/2019/01/14/CS229 Lesson 17 离散与维数灾难/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。