第3章数学建模 马尔可夫决策过程(Markov Decision Process,MDP)是强化学习的数学理论基础。马尔可夫决策过程以概率形式对强化学习任务进行建模,并对强化学习过程中出现的状态、动作、状态转移概率和奖赏等概念进行抽象表达,从而实现对强化学习任务的求解,即得到最优策略,获得最大累计奖赏。 在线视频03 3.1马尔可夫决策过程 在介绍马尔可夫决策过程之前,先来简单介绍马尔可夫性质以及马尔可夫过程等概念。 马尔可夫性质: 在某一任务中,如果Agent从环境中得到的下一状态仅依赖于当前状态,而不考虑历史状态,即P[St+1|St]=P[St+1|S1,S2,…,St],那么该任务即满足马尔可夫性质。虽然从定义上来看只有当前状态和与其相邻的下一个状态具有关联性,但实际上当前状态蕴含了前面所有历史状态的信息,只不过在已知当前状态的情况下,可以丢弃其他所有的历史信息。然而,现实中的任务很多无法严格满足马尔可夫性质,为简化强化学习问题的求解过程,通常假设强化学习所需要解决的任务均满足马尔可夫性质。 马尔可夫过程(Markov Process,MP): 由二元组(S,S)中的(St,St+1)组成的马尔可夫链,该链中的所有状态都满足马尔可夫性质。 马尔可夫奖赏过程(Markov Reward Process,MRP): 由三元组(S,P,R)组成的马尔可夫过程。根据概率,状态自发地进行转移,其状态转移概率P与动作无关,记为P[St+1=s′|St=s]。 马尔可夫决策过程: 由四元组(S,A,P,R)组成的马尔可夫过程,状态依靠动作进行转移。根据状态空间或动作空间是否有穷,马尔可夫决策过程分为有穷马尔可夫决策过程(finite MDPs)和无穷马尔可夫决策过程(infinite MDPs)。其中四元组(S,A,P,R)定义如下。 1. 状态(state)或观测值(observation) 状态空间通常分为两种: 用S表示不包含终止状态的状态空间; 用S+表示包含终止状态的状态空间。状态空间可以用集合来表示。用s表示状态空间中的某一状态,可分为离散状态和连续状态两种类型。 有的资料也将状态分为环境状态(environment state)、Agent状态和信息状态(information state),本书不对状态进行以上区分。另外将状态和观测值视为同一概念,Agent从环境中获得观测值,而对Agent来说,观测值就是它的状态。 2. 动作(action) A表示动作空间,A(s)表示状态s的动作空间。动作空间可以用集合来表示。用a表示动作空间中的某一个动作,可分为离散动作和连续动作两种类型。 3. 状态转移(state transition)函数 P表示状态转移概率,即在状态s下,执行动作a转移到s′的概率。可以表示为如下两种形式: p(s′,r|s,a)=P[St+1=s′,Rt+1=r|St=s,At=a],∑s′∑rp(s′,r|s,a)=1 (3.1) p(s′|s,a)=P[St+1=s′|St=s,At=a],∑s′p(s′|s,a)=1 (3.2) 式(3.1)和式(3.2)都可用于表示MDP中的状态转移概率。式(3.1)既考虑到进入下一状态的随机性,又考虑了到达下一状态获得奖赏的随机性; 而式(3.2)只体现出Agent执行动作后进入下一状态的随机性。 在强化学习中,根据状态转移的状态转移概率,可以将环境分为确定环境(deterministic environment)和随机环境(stochastic environment)。通常将p(s′,r|s,a)恒为1的环境称为确定环境。也就是说,Agent在状态s下执行动作a后,所到达的下一状态是唯一确定的。因此在确定环境下,执行动作a后,状态s可以映射为下一个确定的状态s′; 除此之外其他类型的环境都称为随机环境。即Agent在状态s下执行动作a后,不一定能到达预期的下一状态s′,或者说到达下一状态存在多种可能性。随机环境通常使用式(3.1)或式(3.2)的形式来表达。可以看出,确定环境是随机环境的一个特例,即Agent在状态s下执行动作a后,以1的概率到达下一状态s′,以0的概率到达其他状态。 4. 奖赏(reward)函数 R表示奖赏空间。r(s′|s,a)表示Agent在状态s下采取动作a到达状态s′时,所获得的期望奖赏(expected reward)。可分为离散奖赏和连续奖赏两种类型。其公式可表示为 r(s,a,s′)=E[Rt+1|St=s,At=a,St+1=s′]=∑rrp(s′,r|s,a)p(s′|s,a)(3.3) r(s,a)=E[Rt+1|St=s,At=a]=∑rr∑s′p(s′,r|s,a)(3.4) 式(3.3)和式(3.4)都可以表示MDP中的奖赏。由于状态转移概率p(s′,r|s,a)的随机性,Agent在状态s下多次执行动作a得到的奖赏的期望,才是真实的奖赏。但是如果遵循先获得奖赏,再到达下一状态这一思想,在实际计算过程中,r通常都是确定的,此时r(s,a)即可表示相应的奖赏。 对于奖赏,可以从两个方面进行理解。 (1) 先获得奖赏再进入下一状态: 奖赏Rt+1与当前状态St和动作At相关。 (2) 先进入下一状态再获得奖赏: 奖赏Rt+1与当前状态St、动作At和下一状态St+1相关,这也是奖赏用Rt+1表示的一个重要原因,即与t+1时刻到达的状态St+1有关。 在线视频04 例3.1确定环境下扫地机器人任务的MDP数学建模。 图3.1扫地机器人环境 考虑图3.1所描述的确定环境MDP问题: 一个扫地机器人,在躲避障碍物的同时,需要到指定的位置收集垃圾,或者到指定位置给电池充电。 扫地机器人任务的MDP数学建模如下。 1. 状态 在该问题中,状态s用来描述机器人所在的位置,可以用2维向量表示。为了简化问题,将状态空间离散化为24个不同的状态(图3.1中,共25个小方格,除去[3,3]障碍物位置外,将每个小方格作为一个状态),按照图3.1中序号出现的先后顺序,用集合表示为 S+={S0: [1,1],S1: [2,1],S2: [3,1],…,S11: [2,3], S13: [4,3],…,S19: [5,4],…,S23: [4,5],S24: [5,5]} 其中,充电桩所在的位置为状态S0=[1,1],垃圾所在的位置为状态S19=[5,4]。坐标[3,3]表示障碍物的位置,机器人不会到达这里,因此不作为状态。通常状态S0和S19为终止状态或吸收状态(absorbing state),即一旦机器人到达这两个状态之一,就不会再离开,情节(episode)即结束。 2. 动作 动作a用来描述机器人运动的方向,可以用2维向量表示。为了简化问题,将动作空间离散化为上、下、左、右4个不同的动作,用集合表示为 A=上: [0,1],下: [0,-1],左: [-1,0],右: [1,0] 对于不同的状态s,动作空间可能不同。例如,对于状态S0=[1,1],它的动作空间为AS0=[0,1],[1,0],即机器人处于该状态时,只能采取向上、向右动作,但因为S0=[1,1]为吸收状态,无论采取哪个动作,都会保持原地不动; 对于状态S9=[5,2],它的动作空间为AS9=[0,1],[0,-1],[-1,0],即机器人处于该状态时,不能采取向右的动作; 对于坐标[3,3]周围的4个状态,动作空间中的4个动作都可以采用,但采取指向障碍物的动作时,会保持原地不动。 3. 状态转移函数 在确定环境下,状态转移可以用两种方式来表示: 既可以映射为下一个状态,又可以映射为到达下一个状态的概率。 映射为下一个状态: f(s,a)=s+a,s≠[1,1]且s≠[5,4]且s+a≠[3,3] s,其他(3.5) 映射为到达下一个状态的概率: p(s,a,s′)= 1,(s+a=s′且s+a≠[3,3])或((s=[1,1]或s=[5,4]或 s+a=[3,3])且s=s′) 0,其他(3.6) 4. 奖赏函数 到达状态S19=[5,4],机器人可以捡到垃圾,并得到+3的奖赏; 到达状态S0=[1,1],机器人充电,并得到+1的奖赏; 机器人采取动作向坐标[3,3]处移动时,会撞到障碍物,保持原地不动,并得到-10的奖赏; 其他情况,奖赏均为0。特别是当机器人到达吸收状态后,无论采取什么动作,只能得到0的奖赏。对应的奖赏函数为 r(s,a)= +3,s≠[5,4]且s+a=[5,4] +1,s≠[1,1]且s+a=[1,1] -10,s+a=[3,3] 0,其他(3.7) 在线视频05 例3.2随机环境下扫地机器人任务的MDP数学建模。 图3.2随机环境扫地机器人 状态转移示意图 重新考虑例3.1的扫地机器人问题。假设由于地面的原因,采取某一动作后,状态转换不再确定。当采取某一动作试图向某一方向移动时,机器人成功移动的概率为0.80,保持原地不动的概率为0.15,移动到相反方向的概率为0.05,具体如图3.2所示,其中s′表示下一个状态,s″表示相反方向的下一个状态。 该问题在随机环境下,状态空间、动作空间与确定环境是完全相同的,其随机性主要体现在状态转移函数和奖赏函数中。根据任务的随机性,状态转移只能用概率来表示。具体的状态转移函数可以定义为 p(s,a,s′)=0.80,s+a=s′且s≠s′ 0.15,s=s′且s≠[1,1]且s≠[5,4] 0.05,s-a=s′且s≠s′(3.8) 在随机环境下,奖赏的获取不单纯受(s,a)的影响,还与下一状态s′相关,具体的奖赏函数定义为 r(s,a,s′)=+3,s≠[5,4]且s′=[5,4] +1,s≠[1,1]且s′=[1,1] -10,s+a=[3,3]且s=s′ 0,其他(3.9) 3.2基于模型与无模型 从MDP四元组中可以看出,在强化学习任务求解中,状态转移概率p是非常重要的。但获取如例3.2的状态转移概率难度非常大,需要在保证环境完全相同的情况下,重复大量的实验。从状态转移概率是否已知的角度,强化学习可以分为基于模型(modelbased)强化学习和无模型(modelfree)强化学习两种。 (1) 基于模型: 状态转移概率p已知,能够通过建立完备的环境模型来模拟真实反馈。相关算法如动态规划法。 (2) 无模型: 状态转移概率p未知,Agent所处的环境模型是未知的。相关算法如蒙特卡洛法、时序差分法、值函数近似以及策略梯度法。 基于模型的优缺点如下。 优点: ①能够基于模拟经验数据直接模拟真实环境; ②具备推理能力,能够直接评估策略的优劣性; ③能够与监督学习算法相结合来求解环境模型。 缺点: 存在二次误差。两次近似误差具体体现在以下几方面。 (1) 第一次近似误差: 基于真实经验对模型进行学习,得到的模型仅仅是Agent对环境的近似描述。 (2) 第二次近似误差: 基于模拟模型对值函数或策略进行学习时,存在学习误差。 3.3求解强化学习任务 图3.3基于MDP的强化学习基本框架 对强化学习任务的求解是以MDP条件为基础的,因此构建基于MDP的强化学习基本框架,如图3.3所示。 在t时刻,Agent从环境中得到当前状态St,根据策略π执行动作At,并返回奖赏Rt+1和下一状态St+1。Agent通过不断地与环境交互进行学习,并在学习过程中不断更新策略,经过多次学习后,得到解决问题的最优策略。其中,Rt+1被理解为存在一定延迟的奖赏。 以吃豆人游戏为例,Agent的目标是在网络中,躲避幽灵、吃掉尽量多的食物,其 MDP模型的基本元素构成如下。 (1) 吃豆人是Agent,网格世界是环境,吃豆人在网格世界中的位置表示Agent所处状态。 (2) 吃豆人的动作空间为上、下、左、右。根据策略,即玩家想法,选择相应动作。 (3) 当吃豆人吃掉食物或被幽灵杀死时,将获得奖赏(奖赏也包括惩罚)。 (4) 达到回报阈值时,Agent赢得比赛。 在线视频06 3.3.1策略 在强化学习基本框架中,除了已知的MDP四元组外,还有一个核心要素,即策略(policy)π。强化学习的目的: 在MDP中搜索到最优策略。策略表示状态到动作的映射,即在某一状态下采取动作的概率分布。与状态转移概率不同,策略概率通常是人为设定的。根据概率分布形式,策略可以分为确定策略(deterministic policy)和随机策略(stochastic policy)两种。 1. 确定策略 在确定策略下,Agent在某一状态下只执行一个固定的动作。如确定策略扫地机器人任务,其动作概率分布形如(1,0,0,0),即在当前状态下,只能执行向上走的动作。确定策略可以将状态映射为一个具体的动作。确定策略函数可以表示为 a=π(s)(3.10) 式(3.10)表示Agent处于状态s时,根据策略π,将执行动作a。 2. 随机策略 在随机策略下,Agent在一个状态下可能执行多种动作,其动作概率分布形如(0.2,0.2,0.3,0.3),随机策略将状态映射为执行动作的概率。随机策略函数可以表示为 π(a|s)=P(a|s)=P(At=a|St=s)(3.11) 式(3.11)表示Agent处于状态s时,根据策略π,执行动作a的概率。 动态规划法、蒙特卡洛法和时序差分法都只能获得确定策略,而策略梯度法可以获得随机策略。 MDP应用一个策略产生序列的方法如下。 (1) 从初始状态分布中产生一个初始状态Si=S0。 (2) 根据策略π(a|Si),给出采取的动作Ai,并执行该动作。 (3) 根据奖赏函数和状态转移函数得到奖赏Ri+1和下一个状态Si+1。 (4) Si=Si+1。 (5) 不断重复第(2)步到第(4)步的过程,产生一个序列: S0,A0,R1,S1,A1,R2,S2,A2,R3,S3,… (6) 如果任务是情节式的,序列将终止于状态Sgoal; 如果任务是连续式的,序列将无穷延续。 在实际问题中,策略通常都是随机的。强化学习任务一般都具有两种随机性,即策略π(a|s)的随机性和状态转移概率p(s′,r|s,a)的随机性。策略的随机性可以是人为设定的,而状态转移的随机性是任务本身所固有的特性,如地面湿滑等。 在线视频07 3.3.2奖赏与回报 归根结底,策略是根据值函数进行更新的。当给定一个策略π时,Agent会依据该策略得到一个状态动作序列,其形式为 S0,A0,R1,S1,A1,R2,S2,A2,R3,S3,… 马尔可夫决策过程将回报(return)Gt定义为: 从当前状态St到终止状态ST所获得的奖赏值之和。其表达式如式(3.12)所示。这里R的下标从t+1开始: Gt=Rt+1+Rt+2+…+RT(3.12) 在实际情况中,对于未来的奖赏,总是存在较大的不确定性。为了避免序列过长或连续任务中回报趋于无穷大的情况,引入折扣系数(discounting rate)γ,用于对未来奖赏赋予折扣,带折扣回报定义如下所示: Gt=Rt+1+γRt+2+γ2Rt+3+…,γ∈[0,1](3.13) 从式(3.13)可知,距离当前状态越远的未来状态,对当前状态的回报贡献越小。可以用下一状态St+1的回报来表示当前状态St的回报时,其递归关系式的推导如下所示: Gt=Rt+1+γRt+2+γ2Rt+3+… =Rt+1+γ(Rt+2+γRt+3+…) =Rt+1+γGt+1(3.14) 折扣系数γ存在两种极端情况: 当γ=0时,未来状态无法对当前回报提供任何价值,也就是说,此时只关注当前状态的奖赏,即Agent“看得不够远”; 当γ=1时,若环境已知,则能够确定所有的未来状态,也就是说,Agent能够“清晰准确地向后看”,得到准确的回报值。 例3.3设折扣系数γ=0.2,T=4,奖赏序列为R1=2,R2=1,R3=5,R4=4,计算各时刻的回报: G0,G1,…,G4。 这里假设终止状态的回报为: G4=0。根据式(3.14),可通过下一个状态的回报来计算当前状态的回报。这样从最后一个状态开始,反向计算更加简便。计算结果如下: G4=0 G3=R4+γ×G4=4+0.2×0=4 G2=R3+γ×G3=5+0.2×4=5.8 G1=R2+γ×G2=1+0.2×5.8=2.16 G0=R1+γ×G1=2+0.2×2.16=2.432 例3.4考虑例3.1的确定环境下扫地机器人任务。机器人每走一步都伴随着奖赏,奖赏由奖赏函数给出。当机器人到达状态S19=[5,4]时,得到+3的奖赏; 当机器人到达状态S0=[1,1]时,得到+1的奖赏; 当机器人碰到障碍物[3,3]时,得到-10的奖赏,即惩罚; 其他情况都得到0的中性奖赏。图3.4为机器人的一段移动轨迹,令折扣系数γ=0.8,计算轨迹中每个状态的折扣回报。 图3.4扫地机器人的折扣回报示意图 在线视频08 3.3.3值函数与贝尔曼方程 在判定一个给定策略π的优劣性时,若p(s′,r|s,a)恒等于1,则每次执行一个动作后进入的下一状态是确定的,此时可以直接使用回报作为评判指标。但在实际情况中,由于状态转移概率的存在,环境通常具有随机性,Agent从当前状态到达终止状态可能存在多种不同的状态序列,也就存在多个不同的回报Gt,此时无法直接使用Gt来判定策略π的优劣性,需要以回报的期望作为策略优劣性的评判指标,于是引入值函数(value function)来改进策略。 1. 状态值函数(statevalue function) 状态值函数vπ(s)表示遵循策略π,状态s的价值,即在t时刻,从状态s开始,Agent采取策略π得到的期望回报。其计算公式如下所示: vπ(s)=Eπ(Gt|St=s)(3.15) 这里将函数vπ称为策略π的状态值函数。对状态而言,每个状态值函数是由该状态所具有的价值决定的。 2. 动作值函数(actionvalue function) 动作值函数qπ(s,a)表示遵循策略π,状态s采取动作a的价值,即在t时刻,从状态s开始,执行动作a后,Agent采取策略π得到的回报期望。其计算公式如下所示: qπ(s,a)=Eπ(Gt|St=s,At=a)(3.16) 这里将函数qπ称为策略π的动作值函数。对状态动作对而言,每个动作值函数是由每个状态采取动作所具有的价值决定的。 3. 状态值函数的贝尔曼方程 由式(3.15)和式(3.16)可知,动作值函数是在状态值函数的基础上考虑了执行动作a所产生的影响。根据这一联系,可以构建值函数之间的递归关系,结合回报递归关系式(3.14),对任意策略π,当前状态s的价值与其下一个状态s′的价值,满足如下关系式: vπ(s)=Eπ(Gt|St=s) =Eπ(Rt+1+γGt+1|St=s) =∑aπ(a|s)∑s′,rp(s′,r|s,a)r+γEπ(Gt+1|St+1=s′) =∑aπ(a|s)∑s′,rp(s′,r|s,a)r+γvπ(s′)(3.17) 该推导过程使用了期望公式的展开形式。在式(3.17)的最后一行,对每个(a、s′、r)三元组,首先计算π(a|s)p(s′,r|s,a)的概率值,并用该概率对相应的奖赏估计值进行加权,然后对所有可能的取值求和,得到最终期望。式(3.17)称为状态值函数vπ(s)的贝尔曼方程,用于估计在策略π下,状态s的期望回报。 这里,∑aπ(a|s)∑s′,rp(s′,r|s,a)也可以写成∑s′,rp[s′,r|s,π(s)]的形式。 图3.5状态值函数更新图 根据状态值函数贝尔曼方程,可以构建状态值函数更新图(backup diagram),如图3.5所示,这里空心圆表示状态,实心圆表示动作。 由图3.5可知,状态值函数与动作值函数满足关系式 vπ(s)=∑aπ(a|s)qπ(s,a)(3.18) 式(3.18)表示Agent遵循策略π,值函数vπ(s)等于状态s下所有动作值函数qπ(s,a)的加权和。其中,策略π(a|s)起到权重的作用。 4. 动作值函数的贝尔曼方程 与状态值函数的贝尔曼方程推导方式类似,同理可以得到动作值函数的贝尔曼方程。如下所示: qπ(s,a)=Eπ(Gt|St=s,At=a) =Eπ(Rt+1+γGt+1|St=s,At=a) =Eπ[Rt+1+γvπ(St+1)|St=s,At=a] =∑s′,rp(s′,r|s,a)r+γvπ(s′) =∑s′,rp(s′,r|s,a)r+γ∑a′π(a′|s′)qπ(s′,a′)(3.19) 根据动作值函数的贝尔曼方程,可以构建动作值函数更新图,如图3.6所示。 由图3.6可知,动作值函数与状态值函数满足如下关系式: qπ(s,a)=r+γ∑s′p(s′|s,a)vπ(s′)(3.20) 例3.5如图3.7所示,已知s′1、s′2、s′3、s′4的状态值,利用状态值函数的贝尔曼方程表示s的状态值。 图3.6动作值函数更新图 图3.7例3.5中状态值函数更新图 vπ(s)=Eπ(Gt|St=s) =π(a1|s)p(s′1,r1|s,a1)r1+γvπ(s′1)+π(a1|s)p(s′2,r2|s,a1)r2+γvπ(s′2)+ π(a2|s)p(s′3,r3|s,a2)r3+γvπ(s′3)+π(a2|s)p(s′4,r4|s,a2)r4+γvπ(s′4) 实际上贝尔曼方程给出了每个状态的状态值或每个状态动作对的动作值之间的关系。因此可以通过解方程组,得到实际的状态值或动作值。 阅读代码03 例3.6在例3.1确定情况扫地机器人任务中,采用的随机策略为: π(a|Si)=1|A(Si)|,a∈A(Si),这里,Si表示序号为i的状态,|A(Si)|表示状态Si可以采取的动作数。在折扣系数γ=0.8的情况下,求扫地机器人任务中每个状态的状态值。 根据状态值函数贝尔曼方程,可以通过联立线性方程组的方法求解得到在对应策略π下,每个状态的状态值。针对处于状态Si的扫地机器人,可以列出如式(3.21)的贝尔曼方程为 vπ(Si)=∑a∈A(Si)π(a|Si)p(Si,a,s′)[r(Si,a)+γvπ(s′)](3.21) 在式(3.21)中,确定环境下p(Si,a,s′)=1。状态值vπ(s)是对状态s的累积回报求期望。因为S0和S19是终止状态,在这两个状态下无论采取任何动作,都会保持原地不动,且累积奖赏为0,即这两个状态的状态值vπ(S0)、vπ(S19)均为0。将每个状态的值函数vπ(s)作为未知数,它们之间的关系满足贝尔曼方程,于是可以得到如下方程组: vπ(S1)=13×[0+0.8×vπ(S6)]+13×[1+0.8×vπ(S0)]+13×[0+0.8×vπ(S2)] vπ(S2)=13×[0+0.8×vπ(S7)]+13×[0+0.8×vπ(S1)]+ 13×[0+0.8×vπ(S3)]  vπ(S11)=14×[0+0.8×vπ(S16)]+14×[0+0.8×vπ(S6)]+ 14×[0+0.8×vπ(S10)]+14×[-10+0.8×vπ(S11)] vπ(S13)=14×[0+0.8×vπ(S18)]+14×[0+0.8×vπ(S8)]+ 14×[-10+0.8×vπ(S13)]+14×[0+0.8×vπ(S14)]  vπ(S23)=13×[0+0.8×vπ(S18)]+13×[0+0.8×vπ(S22)]+ 13×[0+0.8×vπ(S24)] vπ(S24)=12×(3+0.8×vπ(19))+12×[0+0.8×vπ(S23)] 求解方程组,得到状态值,如图3.8所示。 -1.111-1.359-1.615-0.3291.368 -1.417-2.372-4.369-0.9870.000 -1.831-4.716-3.987-0.300 -0.731-2.162-4.649-2.160-0.887 0.000-0.716-1.772-1.280-0.867 图3.8基于等概率策略的确定环境扫地机器人任务的状态值 3.3.4最优策略与最优值函数 利用强化学习方法解决任务的关键在于搜索出MDP中的最优策略。最优策略就是使得值函数最大的策略。在有穷MDP中,由于状态空间和动作空间都是有穷的,所以策略也是有穷的。通过计算值函数可以精确地得到至少一个最优策略π*,优于或等效于其他所有策略。对于一个更优策略π′,执行该策略时,所有状态的期望回报都大于或等于执行π策略的期望回报。也就是说,对于所有s∈S,π′优于π,都存在vπ′(s)优于vπ(s)。 最优策略可能不止一个,它们共享相同的状态值函数,称为最优状态值函数(optimal statevalue function),记为v*,定义为 v*(s)=vπ*(s)= maxπ vπ(s),s∈S(3.22) 式(3.22)表明,在状态s处,执行最优策略π*的期望回报,也就是在状态s处能够获得的最大价值。同理,最优策略共享相同的最优动作值函数(optimal actionvalue function),记为q*,定义为 q*(s,a)=qπ*(s,a)= maxπ qπ(s,a),s∈S,a∈A(3.23) 式(3.23)表明,在状态s处,执行动作a,并在随后的过程中采取最优策略π*得到的期望回报,也就是在状态动作对(s,a)处能够获得的最大价值。 1. 贝尔曼最优方程 对于最优策略值函数v*而言,一方面因为v*是策略的值函数,必定满足贝尔曼方程(3.17)。另一方面又因为它是最优的值函数,因此引入一种不与任何特定策略有关的表达形式来表示它,即贝尔曼最优方程(Bellman optimality equation)。贝尔曼最优方程表示: Agent在采用最优策略π*时,各个状态s的价值一定等于在该状态下执行最优动作a的期望回报。v*的贝尔曼最优方程定义为 v*(s)= maxa∈A(s)qπ*(s,a) = maxa Eπ*(Rt+1+γGt+1|St=s,At=a) = maxa E(Rt+1+γv*(St+1)|St=s,At=a) = maxa ∑s′,rp(s′,r|s,a)r+γv*(s′)(3.24) 式(3.24)中最后两行的表达式为关于v*的贝尔曼最优方程的两种表达形式。同理,q*的贝尔曼最优方程定义为 q*(s,a)=E[Rt+1+γv*(St+1)|St=s,At=a] =E[Rt+1+γmaxa′ q*(St+1,a′)|St=s,At=a] =∑s′,rp(s′,r|s,a)r+γmaxa′ q*(s′,a′)(3.25) 关于v*和q*的贝尔曼最优方程,其更新图分别如图3.9和图3.10所示,弧线表示取最大值,其他部分都与图3.5和图3.6的vπ、qπ的更新图相同。 图3.9关于v*的贝尔曼最优方程更新图 图3.10关于q*的贝尔曼最优方程更新图 2. 最优策略 Agent通过与环境不断地交互获得的信息来更新策略,以最终获得最优值函数。一旦获得最优状态值函数v*或最优动作值函数q*,Agent便能得到最优策略。 若已知v*,单步搜索后,最好的动作就是全局最优动作。即对于v*来说,任意贪心策略都是最优策略。贪心用于描述仅基于当前情况或局部条件进行的最优选择,不考虑未来的变化与影响,是一种基于短期视角的方案。由于v*本身包含了未来所有可能的动作产生的回报影响,因此可以将对最优的长期(全局)回报期望的求解,转化为计算每个状态对应的局部变量,以单步搜索方式产生长期的最优动作序列。简单来看,基于贪心策略,Agent总是朝着具有更大状态值函数的状态进行移动。 若已知q*,由于最优动作值函数以最大的长期回报期望来表达每组状态动作对的局部变量,最优动作的选择无须知道后续状态及其对应的价值,Agent可以直接选择最大动作值函数所对应的动作,这一方法也称为贪心动作选择方法,其表达式为 At= arg maxa qt(s,a)(3.26) 由于受环境的完备性、计算能力和计算资源的限制,在寻找最优策略时,直接对包含max的非线性最优贝尔曼方程组求解是比较困难的。通常采用迭代方式,如动态规划法,经过一轮一轮的迭代,最终收敛为最优解。第4章将会详细介绍动态规划法。 阅读代码04 例3.7求解例3.1中确定环境下扫地机器人任务的最优状态值函数,并给出最优策略。 设折扣系数γ=0.8。利用式(3.24),可以显式地给出在该扫地机器人任务中,状态Si的最优贝尔曼方程为 v*(Si)= maxa p(Si,a,s′)[r(Si,a)+γv*(s′)](3.27) 在式(3.27)中,确定环境下p(Si,a,s′)=1。将每个状态的值函数vπ(s)作为未知数,它们之间的关系满足最优贝尔曼方程,于是利用式(3.27)可以得到扫地机器人任务的最优贝尔曼方程组。利用第4章的值迭代算法,可以对贝尔曼最优方程组进行求解,并找到该扫地机器人任务的最优策略,计算结果如图3.11所示。 图3.11确定环境下扫地机器人任务的最优值函数和最优策略 通过图3.11可以看出,当机器人处于状态S6=[2,2]时,可以采取4个不同的动作。通过一步搜索,计算出上、下、左和右4个动作值,分别为1.229、0.8、0.8、1.229,于是得出状态S6=[2,2]的最优动作为向上和向右,共2个动作。当机器人处于状态S17=[3,4]时,仍可以采取4个不同的动作。通过一步搜索,计算出上、下、左和右4个动作值,分别为1.536、-8.080、1.536、2.400,于是得出状态S17=[3,4]的最优动作为向右,1个动作。 综上,利用最优值函数计算最优策略时,需要通过一步搜索,计算出其所有动作值,通过选取具有最大动作值的动作,得到最优策略。而利用动作值寻找最优策略时,由于动作值中包含了可采取动作的信息,因此只需要选取具有最大动作值的动作,即可得到最优策略。 3.4探索与利用 由于强化学习的目的是得到一个最优策略,使得回报最大化。这就导致了强化学习的一大矛盾: 探索与利用的平衡。一方面,Agent秉持利用机制(exploitation),为了得到最大回报,需要始终采用最优动作,即根据当前的值函数选择最优动作,最大限度地提升回报; 另一方面,Agent需要探索机制(exploration),摒弃基于值函数的贪心策略,找到更多可能的动作来获得更好的策略,探索更多的可能性。 通常我们采用具有探索性的策略来解决以上矛盾。常用的两种方法为同策略和异策略。使用这两种方法一方面保证足够的探索性,另一方面充分地利用最优策略。在介绍它们之前,先来了解行为策略和目标策略。 (1) 行为策略(behavior policy): 用于产生采样数据的策略,具备探索性,能够覆盖所有情况,通常采用ε柔性策略(εsoft policy)。 (2) 目标策略(target policy): 强化学习任务中待求解的策略,也就是待评估和改进的策略,一般不具备探索性,通常采用确定贪心策略。 下面对同策略和异策略的特点分别阐述。 (1) 同策略(onpolicy): 行为策略和目标策略相同。通过ε贪心策略平衡探索和利用,在保证初始状态动作对(S0,A0)不变的前提下,确保每一组(s,a)都有可能被遍历到。常用算法为Sarsa和Sarsa(λ)算法。 (2) 异策略(offpolicy): 行为策略和目标策略不同。将探索与利用分开,在行为策略中贯彻探索原则: 采样数据,得到状态动作序列; 在目标策略中贯彻利用原则: 更新值函数并改进目标策略,以得到最优目标策略。常用算法为QLearning算法和DQN算法。 同策略方法较为简单,通常会被优先考虑,但异策略方法更为通用,效果也更好,可以用来学习由传统的非学习型控制器或人类专家生成的数据。异策略方法的优缺点分别阐述如下。 异策略优点: 效果好,更具有一般性,可以从示例样本或其他Agent给出的数据样本中进行学习。 可以重复利用旧策略。 可以在使用一个探索策略的基础上,学习一个确定策略。 可以用一个行为策略进行采样,多个目标策略同时进行学习。 异策略缺点: 由于数据来源于一个不同的策略,存在方差较大、收敛速度慢等缺陷。 下面介绍2个概念。 偏差(bias): 在机器学习中,偏差和欠拟合相关,预测值与样本之间的偏差越大,说明精度越低。在强化学习中,偏差指通过采样数据获得的估计平均值与实际平均值的偏离程度。 方差(variance): 在机器学习中,方差和过拟合相关,样本值之间的方差越大,说明样本的置信度越差,模型适用性越差。在强化学习中,方差指单次采样结果相对于均值的波动大小。 3.5小结 本章主要介绍了强化学习的基础数学理论,以马尔可夫决策过程描述了Agent与环境的交互过程。状态是Agent选择动作的基础,通过动作的选择完成状态的转移,并以奖赏评判Agent动作选择的优劣。 有限的状态、动作和收益共同构成了有限马尔可夫决策过程,回报刻画了Agent能获得的全部未来奖赏,对于不同的任务,未来状态的奖赏会有不同的折扣,而Agent的任务就是最大化回报。动作的选择依赖于Agent所采取的策略,而强化学习的目的就是获得最优策略。 引入状态值函数和动作状态值函数来描述回报,通过贝尔曼最优方程将马尔可夫决策过程表达抽象化,从而可以相对容易地求解得到最优价值函数。在强化学习问题中,定义环境模型和明确最优值函数是计算最优策略的基础,在后续章节中,将进一步讨论如何求解最优策略。 3.6习题 1. 举例说明基于模型与无模型强化学习的异同点。 图3.12扫地机器人任务(变化) 2. 分别给出如图3.12所示的确定环境和随机环境下扫地机器人任务的MDP数学模型。与例3.1和例3.2相比,主要有两方面的变化: (1) 图3.12中障碍物、充电桩及垃圾位置不同; (2) 在任何状态下都有上、下、左、右4个不同的动作,当采取冲出边界的动作时,机器人保持原地不同。其他参数设置与例3.1和例3.2相同。 3. 考虑一个折扣系数为γ的连续式任务,其奖赏序列为R1,R2=R3=…=,计算G0,G1的值。 4. (编程)通过解方程组计算: 在确定环境、等概率策略下,图3.12扫地机器人在折扣系数γ=0.8的情况下,每个状态的状态值。 5. 简述同策略与异策略强化学习的异同点。