机器学习笔记—增强学习

浏览: 1720

本文介绍增强学习和自适应控制。

在监督学习中,算法是要输出尽量模仿训练集中的标签 y,标签给每个输入 x 一个清楚的正确答案。与此不同,对于许多序列决策和控制问题,就很难对算法给出这种明确的监督。例如,如果要造一个四足机器人,并编程让它行走,起初我们并不知道让它行走的正确行动,所以也不知道怎么模仿学习算法给出明确的监督。

在增强学习框架中,我给算法一个回报函数,告诉学习代理执行得好坏。在四足行走的机器人例子中,当机器人往前走时,回报函数就给予正反馈,退后或者摔倒就给予负反馈。学习算法的工作就是弄清楚怎么随着时间选择动作,以使总回报最大。

增强学习的应用非常广泛,如无人机、运动机器人、蜂窝电话网络路由、市场策略选择、工业控制和高效的页面排序。我们对增强学习的研究将从 MDP 马尔科夫决策过程开始,形式化增强学习遇到的问题。

1、马尔可夫决策过程

一个马尔可夫决策过程是元组 (S,A,{Psa},γ,R),其中:

  • S 是状态集合。(例如,在无人机飞行中,S 可以是直升机所有可能的位置和方向)
  • A 是动作集合。(例如,直升机操纵杆能够转动的所有方向)
  • Psa 是状态转换概率。对每一个状态 s∈S 和动作 a∈A,Psa 是在状态空间上的分布。简单地说,Psa 给定的是,当在状态 s 采取行动 a,我们会变成哪种状态的分布概率。
  • γ 是折扣因子。
  • R:S×A—>R 是回报函数。(回报有时写成只有状态 S 的函数,R:S—>R)

MDP 执行的动态过程如下:从状态 s0 开始,在 MDP 中选择一些动作 a0∈A 来执行,作为选择的结果,根据 s1~Ps0a0, MDP 的状态随机切换到后继状态 s1,然后再选择另外一个动作 a1,作为动作的结果,根据 s2~Ps1a1,状态再次切换,然后选择 a2,等等。周期性的,这个过程可表示如下:

Clipboard Image.png

访问状态序列 s0,s1,...,并执行动作 a0,a1,...,总回报为:

Clipboard Image.png

或者,如果回报仅仅是状态的函数,那么总回报可写作:

Clipboard Image.png

对大部分应用来说,我们会使用更简单的状态回报 R(s),虽然状态动作回报 R(s,a) 的泛化也没有特别的困难。

增强学习的目标是随着时间选择动作以最大化总回报的期望值:

Clipboard Image.png

时间点 t 的回报通过乘以因子 γt 打了折扣,所以为使期望最大,我们希望正回报来得越早越好,负回报尽量往后面去。在经济应用中,R(·) 是挣钱的总金额,γ 自然可以解释为利率(今天的一英镑比明天的一英镑值钱)。

一个策略是一些从状态到动作的映射函数 π:S—>A。无论何时,我们在状态 s 执行了动作 a=π(s),就说在执行策略 π。定义 π 的值函数为:

Clipboard Image.png

V(s) 是从状态 s 开始,根据策略 π 采取行动,最终的折扣回报期望和。

给定固定策略 π,它的值函数 Vπ 满足 Bellman 方程:

Clipboard Image.png

也就是说,从 s 开始的折扣回报 Vπ(s) 的期望和由两部分组成:第一,从状态 s 开始的立即回报 R(s),第二,未来折扣回报的期望和。仔细检查第二项,和式可写为:

Clipboard Image.png

这是从状态 s' 开始的折扣回报的期望和,s' 符合分布 Psπ(s),也就是从状态 s 执行第一个动作 π(s) 后的状态分布,所以,第二项给的是在 MDP 中第一步后的折扣回报的期望和。

Bellman 方程能用于高效解出 Vπ,特别是在一个有限状态 MDP(|S|<∞),可以为每个状态写下这个方程 Vπ(s),这给定了一个有 |S| 个变量(每个状态都有个未知的 Vπ(S))的 |S| 个线性方程的集合,可以有效解出 Vπ(s)。

定义最优值函数:

Clipboard Image.png也就是能使用策略得到的最好的折扣回报期望和。还有另一个版本的 Bellman 方程。 

Clipboard Image.png

第一项跟之前一样是立即回报,第二项是执行动作 a 后的折扣回报未来期望和的最大值。要特别注意,这里的 max 是要从所有动作中选择回报最大的动作,而 max 后面的 γ 乘以求和项就是执行某动作后的回报期望。要确保你理解了上式的含义

定义策略 π*:S—>A 如下:

Clipboard Image.png

π*(s) 给出了能使总回报最大的行动 a。

事实上,对每一个状态和每一个策略有:

Clipboard Image.png

第一个等式是说 Vπ*,π* 的值函数,等于对每个状态 s 来说的最优值函数 V*。第二个不等式是说,π* 的值至少跟其它策略一样大。换句话说,π* 就是最优策略。

注意到 π* 有一个有趣的属性,对所有的状态它都是个最优策略。特别的,并不是说,如果从 s 开始就有针对那个状态的最优策略,如果从其它的 s' 开始就有针对 s' 的其它最优策略。特别的,同样的策略 π* 对所有的状态都能获得最大值,这意味着我们可以使用同样的策略 π*,而不管 MDP 的初始状态是什么。

 

2、值迭代和策略迭代

现在介绍两种解决有限状态 MDP 的高效算法,这里只考虑有限状态和动作空间的 MDP。

第一个算法,值迭代,如下: 

Clipboard Image.png

这个算法可以看作是使用 Bellman 方程重复更新估计值函数。这里 R(s) 是回报函数,V(s) 是值函数,注意这两者的区别,有助于理解该算法。

有两种方法执行算法内环的更新,第一种是,先对每一个状态 s 计算新值 V(s),并覆盖旧值,这被称为同步更新;另一种是异步更新,以一定顺序循环遍历状态,一次更新一个值。

不管是同步更新还是异步更新,值函数 V 都会收敛到 V*,找到 V* 后,就能够使用上面介绍过的如下方程找到最优策略。

Clipboard Image.png

除了值迭代,还有一种寻找最优策略的算法,策略迭代

Clipboard Image.png

所以,内循环重复地为当前策略计算值函数,然后使用当前值函数更新策略。注意到步骤 (a) 可以通过解之前描述的 Bellman 方程来完成,在策略固定的情况下,它是一个有 |S| 个变量的 |S| 个线性方程的集合。

Clipboard Image.png

在算法的有限次迭代后,V 将收敛到 V*,π 将收敛到 π*。

值迭代和策略迭代都是解 MDP 的标准算法,关于哪个算法更好没有一致的看法。对于小的 MDPs,策略迭代经常很快,很少迭代就能收敛;但对于有大量状态空间的 MDPs 来说,解 MDPs 会涉及大量线性方程,就比较困难,这种情况使用值迭代更好,由于这个原因,实际中值迭代会比策略迭代用得多。

3、为 MDP 学习一个模型

目前为止,我们讨论了 MDPs 和它的算法,假定状态转换矩阵和回报是已知的,在许多现实问题中,并不知道状态转换矩阵和清晰的回报,但可以从数据中估计出来。(通常 S,A 和 γ 是知道的)

例如,在倒立摆问题中,在 MDP 中有一些尝试:

Clipboard Image.png

这里 si(j) 表示我们在时间点 i 尝试 j 时所处的状态, ai(j) 是在那个状态采取的相应动作。实际上,上面的每一次尝试都可以一直运行直到 MDP 终止,或者运行一个很大但是有限的时间步。

有了这些在 MDP 中尝试的经验,我们就很容易推导出状态转换矩阵的最大似然估计。

Clipboard Image.png

如果上面的比率是 0/0,也就是说从没在状态 s 采取动作 a,那就简单估计 Psa(s') 为 1/|S|,也就是估计 Psa 在所有状态上均匀分布。

使用类似的过程,如果 R 是未知的,我们也可以估计状态 s 的期望立即回报 R(s) 为在状态 s 观察到的平均回报。

从 MDP 中学习到一个模型后,就可以使用值迭代或者策略迭代来解 MDP,该 MDP 使用的是估计转换概率和回报。例如,结合模型学习和值迭代,这是一个可能的算法,在状态转换矩阵未知的 MDP 中学习。

Clipboard Image.png

注意到针对这个算法,有一个简单的优化能使它运行得更快。在使用值迭代的内循环中,如果不初始化 V=0,而是用算法上一轮迭代使用的结果,就会为值迭代提供一个更好的起始点,使它更快收敛。

4、连续状态 MDPs

目前为止,我们讨论的都是有限状态的 MDPs。现在讨论无限状态的 MDPs 算法,例如,一辆汽车的状态可以表示为 (x,y,θ,x.,y.,θ.),(x,y) 是位置,方向 θ,x 和 y 方向的速度 x. 和 y.,θ 的角速度为 θ.。所以,S=R6 是一个无限状态的集合,因为对于一辆车有无限个位置和方向。类似的,PS4 中的倒立摆的状态为 (x,θ,x',θ'),θ 是杆的角度。直升机在 3D 空间中的状态为 (x,y,z,Φ,θ,Ψ,x',y',z',Φ',θ',Ψ'),其中翻滚角 Φ,俯仰角 θ 和偏航角 Ψ 指定了飞机的 3D 方向。

下面我们讨论状态空间 S=Rn 的情况,并描述解 MDPs 的方法。

4.1 离散化

或许解连续状态 MDP 最简单的方法就是离散化状态空间,然后使用之前介绍的值迭代或策略迭代算法。

例如,如果是 2d 的状态,那么就可以用表格来离散化状态空间:

Clipboard Image.png

这里每一个表格单元代表一个分离的离散状态 s¯¯¯s¯ ,我们可以通过离散状态 (S¯¯¯,A,{Ps¯¯¯a},γ,R)(S¯,A,{Ps¯a},γ,R) 来近似连续状态的 MDP,其中 S¯¯¯S¯ 是离散状态的集合,Ps¯¯¯aPs¯a 是离散状态的状态转换矩阵。我们可以使用值迭代或策略迭代来解出离散状态 MDP (S¯¯¯,A,{Ps¯¯¯a},γ,R)(S¯,A,{Ps¯a},γ,R) 的 V∗(s¯¯¯)V∗(s¯) 和 π∗(s¯¯¯)π∗(s¯),当我们实际的系统在连续值状态 s∈S,需要选择一个动作来执行,我们就计算相应的离散状态 x¯¯¯x¯,然后执行动作  π∗(s¯¯¯)π∗(s¯)。

这种离散化可以解决很多问题,但是有两个弊端。

首先,它用的是一种比较简单的方法来表示 V* 和 π*,特别是,它假定值函数在离散区间取的是常量(值函数在每个表格中是分段常量)。 

为了更好地理解这种表示的限制,看一个监督学习问题,用一个函数来拟合这些数据:

Clipboard Image.png

很清楚,线性回归在这个问题上会做得很好,但如果在 x 轴上离散化,然后使用分段函数来对应每一个区间,拟合的数据会像这样。

Clipboard Image.png

这种分段常量表示对很多平滑函数都不是一个好的选择,它会导致输入不再平滑,在不同的表格中没有泛化能力,使用这种表示,我们也需要一种好的离散化(非常小的表格单元)来得到一种好的近似。

这种表示的第二个弊端被称为维度诅咒。假设 S=Rn,我们要把 n 个状态的维度都离散化为 k 个值,那么离散状态的总数目为 kn。这种状态维度的指数增长非常快,不适用于大型问题。例如有 10d 个状态,每个状态变量离散化为 100 个值,就有 10010=1020 个离散状态,这对于当代的桌面电脑来说还是太庞大了。

一般来说,离散化对于 1d 和 2d 问题工作得很好(有简单和快速执行的好处)。或许聪明加上小心选择离散化方法,在顶多 4d 问题上都能工作很好。如果你极其聪明,加一点运气,你可以用到 6d 问题上。但是,它很少能运行在比那更高维问题上。

4.2 值函数近似

这里介绍一种在连续状态 MDPs 寻找策略的可选方法,直接近似于 V*,而不是用离散化。这种方法被称为值函数近似,已经被成功用到很多增强学习问题中。

4.2.1 使用模型或模拟器

为实现值函数近似算法,我们假定对于 MDP 有一个模型,或者模拟器。非正式地解释,模拟器是个黑盒子,把连续值状态 st 和动作 at 作为输入,输出下一个状态 st+1,根据的是状态转换概率 PstatPstat:

Clipboard Image.png

有许多方法得到这样的模型,一种是使用物理模拟,例如,PS4 中的倒立摆的模拟器就是使用物理法则来计算杆在时间点 t+1 的位置和方向,给定了当前时间点 t 的状态和要采取的动作 a,假定知道系统的所有参数,如杆的长度、质量等等;也可使用现成的模拟软件包,把输入当作一个数学系统的完整物理描述,当前状态 st 和动作 at,计算下一个状态 st+1。

还有一个可选的方法是从 MDP 收集的数据中学习模型。例如,假设我们在 MDP 中重复执行动作执行了 m 次尝试(trial),每次尝试 T 个时间步。做这些尝试可以随机选择动作,执行一些特定的策略,或通过其它方法来选择动作。然后就可以观察到如下 m 个状态序列。

Clipboard Image.png

现在用学习算法来预测 st+1,把它作为 st 和 at 的函数。

例如,可以选择线性模型的形式:

st+1=Ast+Batst+1=Ast+Bat

使用类似于线性回归的算法。这里模型的参数是矩阵 A 和 B,使用 m 次尝试的数据来估计它们:

Clipboard Image.png这跟参数的极大似然估计有关。

学习到 A 和 B 之后,一个选择是建立确定性的模型,给定输入 st 和 at,就确定了 st+1。另一个选择是建立随机性的模型,st+1 是输入的随机函数。

Clipboard Image.png

这里 εt 是一个噪声项,通常建模为 εt~N(0,Σ),协方差矩阵 Σ 也可以直接从数据中估计。

这里我们把下一个状态 st+1 作为当前状态和动作的线性函数,当然,非线性函数也是可能的,比如可以学到模型 st+1=AΦs(st)+BΦa(at),Φs 和 Φa 是状态和动作的非特性映射,可以使用非线性学习算法,如局部权重线性回归,把 st+1 作为 st 和 at的函数来估计。这些方法也可以用来建立 MDP 的确定性或随机性模拟器。

4.2.2 拟合值函数

这里介绍一种趋近连续状态 MDP 的值函数的拟合值迭代算法。假定问题有连续状态空间 S=Rn,但动作空间 A 是很小和离散的。

同之前介绍的离散状态的值迭代类似,我们执行如下更新:

Clipboard Image.png

这里把和换成了积分,表示这是在连续状态空间下。

拟合值迭代的主要思想是,在有限的状态采样中 s(1),...,s(m),趋近执行这一步。 特别的,我们使用监督学习算法——线性回归来近似值函数,作为状态的线性或非线性函数:

V(s)=θTϕ(s)V(s)=θTϕ(s)

这里,Φ 是一些状态的近似特征映射。

对于 m 个状态的有限采样的每一个状态,拟合值迭代将首先计算量值 y(i),将是 R(s)+γmaxaEs′ Psa[V(s′)]R(s)+γmaxaEs′ Psa[V(s′)] 的近似,也就是上面方程的右边部分,然后我们将使用学习算法来得到接近 R(s)+γmaxaEs′ Psa[V(s′)]R(s)+γmaxaEs′ Psa[V(s′)] 的 V(s)(或者换句话说,获得 V(s) 以接近 y(i))。

详细算法如下:

Clipboard Image.png

上面所写的拟合值函数使用线性回归算法以使 V(s(i)) 趋近 y(i)。算法的那一步完全可以类比标准的监督学习问题,有一个训练集 (x(1),y(1)),(x(2),y(2)),...,(x(m),y(m)),要学习一个函数从 x 映射到 y,唯一的不同是这里的 s 扮演着 x 的角色,虽然上面的描述使用了线性回归,但明显其它的回归算法(如局部权重线性回归)也可以使用。

不像离散状态的值迭代,拟合值迭代不能证明会一直收敛,不过实际中经常是收敛的,或近似收敛。同时也注意到,如果我们使用 MDP 的确定性模拟器,那么拟合值迭代就能通过在算法中设置 k=1 来简化,这是因为方程 R(s)+γmaxaEs′ Psa[V(s′)]R(s)+γmaxa⁡Es′ Psa[V(s′)]变成了一个确定性分布的期望。否则,在上面的算法中,我不得不作 k 次采样并平均,以近似期望(见上面伪代码中 q(a) 的定义)。

最后,拟合值迭代算法输出了 V,它是对 V* 的近似。这隐含定义了我们的策略。特别的,当系统在状态 s,需要选择一个动作,我们会这样选择:

argmaxaEs′ Psa[V(s′)]argmaxa⁡Es′ Psa[V(s′)]

这个计算近似过程类似于拟合值迭代的内循环,对每一个动作,都取 s′1s1′ ,...,s′ksk′ ~PsaPsa 以近似期望(如果模拟器是确定性的,可以设 k=1)。

在实际中,经常有其它的方法来近似这一步,例如,一个通用的例子是,如果模拟器的形式为 st+1=f(st,at)+ε,其中 f 是状态的确定性函数(比如 f(st,at)=Ast+Bat),ε 是零均值高斯噪声。在这种情况下,可以选择动作:

argmaxaV(f(s,a))argmaxa⁡V(f(s,a))

换句话说,这里设置 εt=0(例如,忽略模拟器的噪声),设置 k=1。等同的,这能够使用如下近似从方程 argmaxaEs′ Psa[V(s′)]argmaxa⁡Es′ Psa[V(s′)] 推导。

Clipboard Image.png

这里期望是指 s'~Psa,噪声项 εt 很小,这通常是一个合理的近似。

尽管如此,对于不使用这些近似的问题,不得不使用模型采样 k|A| 个状态,以近似上面的期望,这会是很高的计算复杂度。

推荐 1
本文由 疯狂的拖鞋 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册