求解强化学习问题可以理解为如何最大化个体在与环境交互过程中获得的累积奖励。环境的动力学特征确定了个体在交互时的状态序列和即时奖励环境的状态是构建环境动力学特征所需要的所有信息。当环境状态是完全可观测时个体可以通过构建马尔科夫决策过程来描述整个强化学习问题。有时候环境状态并不是完全可观测的此时个体可以结合自身对于环境的历史观测数据来构建一个近似的完全可观测环境的描述。从这个角度来说几乎所有的强化学习问题都可以被认为或可以被转化为马尔科夫决策过程。正确理解马尔科夫决策过程中的一些概念和关系对于正确理解强化学习问题非常重要。2.1 马尔科夫过程在一个时序过程中如果t1t 1t1时刻的状态仅取决于 t 时刻的状态StS_tSt而与ttt时刻之前的任何状态都无关时则认为ttt时刻的状态StS_tSt具有马尔科夫性(Markov property)。若过程中的每一个状态都具有马尔科夫性则这个过程具备马尔科夫性。具备了马尔科夫性的随机过程称为马尔科夫过程(Markov process)又称马尔科夫链 (Markov chain)。马尔科夫过程中的每一个状态StS_tSt记录了过程历史上所有相关的信息而且一旦StS_tSt定了那么历史状态信息S1...StS_1 . . . S_tS1...St1 对于确定St1S_t1St1均不再重要可有可无。描述一个马尔科夫过程的核心是状态转移概率矩阵Pss′P[St1s′∣Sts](2.1)P_{ss} \mathbb{P}[S_{t1} s | S_t s] \qquad (2.1)Pss′P[St1s′∣Sts](2.1)公式 (2.1) 中的状态转移概率矩阵定义了从任意一个状态sss到其所有后继状态s′ss′的状态转移概率Pfrom[P11⋯P1n⋮⋱⋮Pn1⋯Pnn](2.2)P from \left[ \begin{matrix} P_{11} \cdots P_{1n} \\ \vdots \ddots \vdots \\ P_{n1} \cdots P_{nn}\\ \end{matrix} \right] \qquad (2.2)PfromP11⋮Pn1⋯⋱⋯P1n⋮Pnn(2.2)其中矩阵PPP中每一行的数据表示从某一个状态到所有 n 个状态的转移概率值。每一行的这些值加起来的和应该为 1。通常使用一个元组⟨S,P⟩⟨S, P⟩⟨S,P⟩来描述马尔科夫过程其中SSS是有限数量的状态集PPP是状态转移概率矩阵。图2.1:学生马尔科夫过程图 2.1: 学生马尔科夫过程图2.1:学生马尔科夫过程图 2.1 描述了一个假想的学生学习一门课程的马尔科夫过程。在这个随机过程中学生需要顺利完成三节课并且通过最终的考试来完成这门课程的学习。当学生处在第一节课中时会有50% 的几率拿起手机浏览社交软件信息另有 50% 的几率完成该节课的学习进入第二节课。一旦学生在第一节课中浏览手机社交软件信息则有 90% 的可能性继续沉迷于浏览而仅有 10%的几率放下手机重新听讲第一节课。学生处在第二节课的时有 80% 的几率听完第二节课顺利进入到第三节课的学习中也有 20% 的几率因课程内容枯燥或难度较大而休息或者退出。学生在学习第三节课内容后有 60% 的几率通过考试继而 100% 的进入休息状态也有 40% 的几率因为过于兴奋而出去娱乐泡吧随后可能因为忘掉了不少学到的东西而分别以 20%,40% 和 50% 的概率需要重新返回第一、二、三节课中学习。上图中我们使用内有文字的空心圆圈来描述学生可能所处的某一个状态。这些状态有第一节课C1、第二节课C2、第三节课C3、泡吧中Pub、通过考试Pass、浏览手机FB、以及休息退出Sleep共 7 个状态其中最后一个状态是终止状态意味着学生一旦进入该状态则永久保持在该状态或者说该状态的下一个状态将 100% 还是该状态。连接状态的箭头表示状态转移过程箭头附近的数字表明着发生箭头所示方向状态转移的概率。假设学生现处在状态“第一节课C1”中我们按照马尔科夫过程给出的状态转移概率可以得到若干学生随后的状态转化序列。例如下面的这 4 个序列都是可能存在的状态转化序列C1 - C2 - C3 - Pass - SleepC1 - FB - FB - C1 - C2 - SleepC1 - C2 - C3 - Pub - C2 - C3 - Pass - SleepC1 - FB - FB - C1 - C2 - C3 - Pub - C1 - FB - FB - FB - C1 - C2 - C3 - Pub - C2 - Sleep从符合马尔科夫过程给定的状态转移概率矩阵生成一个状态序列的过程称为采样sample。采样将得到一系列的状态转换过程本书我们称为状态序列(episode)。当状态序列的最后一个状态是终止状态时该状态序列称为完整的状态序列 (complete episode)。本书中所指的状态序列大多数指的都是完整的状态序列。2.2 马尔科夫奖励过程马尔科夫过程只涉及到状态之间的转移概率并未触及强化学习问题中伴随着状态转换的奖励反馈。如果把奖励考虑进马尔科夫过程则成为马尔科夫奖励过程Markov reward process, MRP。它是由⟨S,P,R,γ⟩⟨S, P, R, \gamma⟩⟨S,P,R,γ⟩构成的一个元组其中
强化学习入门 2 马尔科夫决策过程
求解强化学习问题可以理解为如何最大化个体在与环境交互过程中获得的累积奖励。环境的动力学特征确定了个体在交互时的状态序列和即时奖励环境的状态是构建环境动力学特征所需要的所有信息。当环境状态是完全可观测时个体可以通过构建马尔科夫决策过程来描述整个强化学习问题。有时候环境状态并不是完全可观测的此时个体可以结合自身对于环境的历史观测数据来构建一个近似的完全可观测环境的描述。从这个角度来说几乎所有的强化学习问题都可以被认为或可以被转化为马尔科夫决策过程。正确理解马尔科夫决策过程中的一些概念和关系对于正确理解强化学习问题非常重要。2.1 马尔科夫过程在一个时序过程中如果t1t 1t1时刻的状态仅取决于 t 时刻的状态StS_tSt而与ttt时刻之前的任何状态都无关时则认为ttt时刻的状态StS_tSt具有马尔科夫性(Markov property)。若过程中的每一个状态都具有马尔科夫性则这个过程具备马尔科夫性。具备了马尔科夫性的随机过程称为马尔科夫过程(Markov process)又称马尔科夫链 (Markov chain)。马尔科夫过程中的每一个状态StS_tSt记录了过程历史上所有相关的信息而且一旦StS_tSt定了那么历史状态信息S1...StS_1 . . . S_tS1...St1 对于确定St1S_t1St1均不再重要可有可无。描述一个马尔科夫过程的核心是状态转移概率矩阵Pss′P[St1s′∣Sts](2.1)P_{ss} \mathbb{P}[S_{t1} s | S_t s] \qquad (2.1)Pss′P[St1s′∣Sts](2.1)公式 (2.1) 中的状态转移概率矩阵定义了从任意一个状态sss到其所有后继状态s′ss′的状态转移概率Pfrom[P11⋯P1n⋮⋱⋮Pn1⋯Pnn](2.2)P from \left[ \begin{matrix} P_{11} \cdots P_{1n} \\ \vdots \ddots \vdots \\ P_{n1} \cdots P_{nn}\\ \end{matrix} \right] \qquad (2.2)PfromP11⋮Pn1⋯⋱⋯P1n⋮Pnn(2.2)其中矩阵PPP中每一行的数据表示从某一个状态到所有 n 个状态的转移概率值。每一行的这些值加起来的和应该为 1。通常使用一个元组⟨S,P⟩⟨S, P⟩⟨S,P⟩来描述马尔科夫过程其中SSS是有限数量的状态集PPP是状态转移概率矩阵。图2.1:学生马尔科夫过程图 2.1: 学生马尔科夫过程图2.1:学生马尔科夫过程图 2.1 描述了一个假想的学生学习一门课程的马尔科夫过程。在这个随机过程中学生需要顺利完成三节课并且通过最终的考试来完成这门课程的学习。当学生处在第一节课中时会有50% 的几率拿起手机浏览社交软件信息另有 50% 的几率完成该节课的学习进入第二节课。一旦学生在第一节课中浏览手机社交软件信息则有 90% 的可能性继续沉迷于浏览而仅有 10%的几率放下手机重新听讲第一节课。学生处在第二节课的时有 80% 的几率听完第二节课顺利进入到第三节课的学习中也有 20% 的几率因课程内容枯燥或难度较大而休息或者退出。学生在学习第三节课内容后有 60% 的几率通过考试继而 100% 的进入休息状态也有 40% 的几率因为过于兴奋而出去娱乐泡吧随后可能因为忘掉了不少学到的东西而分别以 20%,40% 和 50% 的概率需要重新返回第一、二、三节课中学习。上图中我们使用内有文字的空心圆圈来描述学生可能所处的某一个状态。这些状态有第一节课C1、第二节课C2、第三节课C3、泡吧中Pub、通过考试Pass、浏览手机FB、以及休息退出Sleep共 7 个状态其中最后一个状态是终止状态意味着学生一旦进入该状态则永久保持在该状态或者说该状态的下一个状态将 100% 还是该状态。连接状态的箭头表示状态转移过程箭头附近的数字表明着发生箭头所示方向状态转移的概率。假设学生现处在状态“第一节课C1”中我们按照马尔科夫过程给出的状态转移概率可以得到若干学生随后的状态转化序列。例如下面的这 4 个序列都是可能存在的状态转化序列C1 - C2 - C3 - Pass - SleepC1 - FB - FB - C1 - C2 - SleepC1 - C2 - C3 - Pub - C2 - C3 - Pass - SleepC1 - FB - FB - C1 - C2 - C3 - Pub - C1 - FB - FB - FB - C1 - C2 - C3 - Pub - C2 - Sleep从符合马尔科夫过程给定的状态转移概率矩阵生成一个状态序列的过程称为采样sample。采样将得到一系列的状态转换过程本书我们称为状态序列(episode)。当状态序列的最后一个状态是终止状态时该状态序列称为完整的状态序列 (complete episode)。本书中所指的状态序列大多数指的都是完整的状态序列。2.2 马尔科夫奖励过程马尔科夫过程只涉及到状态之间的转移概率并未触及强化学习问题中伴随着状态转换的奖励反馈。如果把奖励考虑进马尔科夫过程则成为马尔科夫奖励过程Markov reward process, MRP。它是由⟨S,P,R,γ⟩⟨S, P, R, \gamma⟩⟨S,P,R,γ⟩构成的一个元组其中
