马尔可夫奖励过程(MRP)

上一节中提到，马尔可夫奖励过程(Markov Reward Process,MRP)是在马尔可夫链(Markov Chain,MC)的基础上，针对每个时刻状态(一阶马尔可夫链示例) S t → S_t \to St​→下一时刻状态 S t + 1 S_{t+1} St+1​的广义上的收益。

本节主要讲述：广义上的收益是如何产生的 → \to → 马尔可夫奖励过程(Markov Reward Process,MRP)。

目录 逻辑场景回顾

在讲述马尔可夫奖励过程之前，回顾一下执行一步( t → t + 1 t \to t+1 t→t+1)马尔可夫决策过程(MDP)的逻辑场景： 前提条件：在当前时刻 t t t的状态为 S t S_t St​的情况下：

1. 根据决策 π \pi π选择一个动作(Action);
2. 执行该动作,系统根据动作的选择，从当前状态 S t S_t St​转移到下一时刻状态 S t + 1 S_{t+1} St+1​,并同时返回一个该时刻的奖励(Reward) R t + 1 R_{t+1} Rt+1​。
3. 以新状态 S t + 1 S_{t+1} St+1​作为前提条件，重复执行上述2个步骤。

概念介绍

针对上述逻辑场景中出现的概念进行介绍：

状态(State):

• 状态可以理解成对对某一时刻环境的描述；
• 执行动作后，状态会发生变化 → \to →该变化服从齐次马尔可夫假设；
• 状态空间(State Space)是MDP所有状态的集合，状态空间可以是离散/连续型随机变量； 以离散型随机变量为例，某个MDP的状态空间中包含 k k k个离散的状态，其数学语言表达： S = { S 1 , S 2 , . . . , S k } \mathcal S=\{S_1,S_2,...,S_k\} S={S1​,S2​,...,Sk​} 记作： S = { S i } ∣ i = 1 k \mathcal S=\{S_i\}|^{k}_{i=1} S={Si​}∣i=1k​

动作(Action):

• 动作是智能体行为的描述,是智能体根据策略(Policy)产生的结果。
• 动作空间(Action Space)表示所有可能动作的集合，和状态空间类似，动作空间可以是离散/连续型随机变量。 以离散型随机变量为例，某个MDP的动作空间中包含 m m m个离散的动作，其数学语言表达为： A = { A 1 , A 2 , . . . , A m } \mathcal A=\{A_1,A_2,...,A_m\} A={A1​,A2​,...,Am​} 记作： A = { A i } ∣ i = 1 m \mathcal A=\{A_i\}|^{m}_{i=1} A={Ai​}∣i=1m​

策略(Policy):

根据概率分布的形式，可以将策略分为2种：

• 确定性策略(deterministic policy) 在确定性策略下，智能体在某一状态下只能执行唯一一个确定的动作。 相比于随机性策略，确定性策略更像一种规则，通俗的话讲，该规则的指令是： 在执行决策过程中，一旦当前状态是** -> 只能选择**动作，其他动作均不可以选择； 可以想象，如果是确定性策略，在某一状态下执行动作的概率分布是：被选择动作对应的概率是1，其余动作对应概率是0； → \to → 形如 [ 0 , 0 , . . . , 0 , 1 , 0 , . . . ] [0,0,...,0,1,0,...] [0,0,...,0,1,0,...] 我们可以将动作和状态表示为“一一映射”的函数关系。确定性策略可以表示为： a = π ( s ) a = \pi(s) a=π(s)

• 随机性策略(stochastic policy) 在执行马尔可夫决策过程中，基于某一状态(State)下执行动作存在多种可能性，而随机性策略就是各种可执行动作被执行的可能性的概率分布。其本质上是关于动作(Action)和状态(State)的条件概率。 其中状态(State)作为条件,动作(Action)作为后验，记作： π ( a ∣ s ) = P ( A t = a ∣ S t = s ) ( a ∈ A t , s ∈ S t ) \pi(a\mid s)=P(A_t=a\mid S_t=s)(a \in \mathcal A_t,s \in \mathcal S_t) π(a∣s)=P(At​=a∣St​=s)(a∈At​,s∈St​) 其中 A t A_t At​表示 t t t时刻的动作(宏观概念)， A t \mathcal A_t At​表示 t t t时刻可以被选择的动作的集合； 解释：什么是可以被选择的动作？ 在某一时刻的状态 S t S_t St​中，并不是所有的动作都能被选择，有可能在 S t S_t St​状态下，某些动作不可能发生(发生概率为0) 满足这种条件的行为不会出现在 A t \mathcal A_t At​集合中。

奖励(即时奖励)(Reward)：

• 智能体执行动作(Action)后，系统对智能体的反馈。

• 与状态和动作相同，奖励同样存在相关的奖励空间 → \to → 可被分为离散/连续型随机变量。 以离散型随机变量为例，某个MDP的奖励空间中包含 n n n个离散的状态，数学语言表达： R = { R 1 , R 2 , . . . , R n } \mathcal R=\{R_1,R_2,...,R_n\} R={R1​,R2​,...,Rn​} 记作： R = { R i } ∣ i = 1 n \mathcal R=\{R_i\}|^{n}_{i=1} R={Ri​}∣i=1n​

• 奖励是系统内部产生的结果(也有可能是客观存在的结果)，这个结果不是智能体能干预的信息。 示例场景：

• 假设在某一地点 S S S，要去下一地点 S ′ S' S′，已知去 S ′ S' S′存在2条路径: A 1 A_1 A1​, A 2 A_2 A2​;

• 已知走 A 1 A_1 A1​路径花费时间大约45分钟，走 A 2 A_2 A2​路径花费时间大约1小时；

• 目标：走到 S ′ S' S′； 上述场景可以将“走 A 1 A_1 A1​路径”,“走 A 2 A_2 A2​路径”视为动作,选择完动作并执行后，下一步状态 S t + 1 = S ′ S_{t+1}=S' St+1​=S′的奖励是花费时间。 该场景中，“花费时间”是客观存在的，并不随智能体的主观意识的变化而变化。

状态转移函数(State Transition Function)

在逻辑场景回顾中，在确定 S t = s S_t=s St​=s和作 A t = a A_t = a At​=a情况下， S t + 1 = s ′ S_{t+1}=s' St+1​=s′事件发生的概率被称为状态转移概率。 而状态转移函数本质上是基于 S t = s S_t=s St​=s和 A t = a A_t = a At​=a情况下状态转移概率的完整分布。 数学表达有如下2种形式： p ( s ′ , r ∣ s , a ) = P [ S t + 1 = s ′ , R t + 1 = r ∣ S t = s , A t = a ] , ∑ s ′ ∑ r p ( s ′ , r ∣ s , a ) = 1 p(s',r \mid s,a)=P[S_{t+1}=s',R_{t+1}=r \mid S_t=s,A_t=a], \displaystyle\sum_{s'}\displaystyle\sum_{r}p(s',r \mid s,a)=1 p(s′,r∣s,a)=P[St+1​=s′,Rt+1​=r∣St​=s,At​=a],s′∑​r∑​p(s′,r∣s,a)=1 p ( s ′ ∣ s , a ) = P [ S t + 1 = s ′ ∣ S t = s , A t = a ] , ∑ s ′ p ( s ′ ∣ s , a ) = 1 p(s' \mid s,a)=P[S_{t+1}=s' \mid S_t=s,A_t=a], \displaystyle\sum_{s'}p(s' \mid s,a)=1 p(s′∣s,a)=P[St+1​=s′∣St​=s,At​=a],s′∑​p(s′∣s,a)=1 上述2个公式表达的逻辑意思基本相同，均表达了"当前时刻状态和动作确定的情况下，下个状态发生的条件概率。" 上述两种表达方式均可以表示状态转移概率,只是式1表达了关于转移后状态和奖励的联合概率分布，是二维信息；而式2只表现出转移后状态的概率分布信息，两种公式之间存在如下转换关系： p ( s ′ ∣ s , a ) = ∑ r ∈ R p ( s ′ , r ∣ s , a ) p(s'\mid s,a)=\displaystyle\sum_{r \in \mathcal R}p(s',r \mid s,a) p(s′∣s,a)=r∈R∑​p(s′,r∣s,a) 和策略(policy)类似，状态转移概率可以根据环境分为确定性环境(deterministic environment)和随机性环境(stochastic environment)。

• 确定性环境的逻辑：在给定当前状态 S t = s S_t=s St​=s和动作 A t = a A_t=a At​=a,可以唯一地转移到下一个确定状态 S t + 1 = s ′ S_{t+1}=s' St+1​=s′，数学表达式为： p ( S t + 1 = s ′ ∣ S t = s , A t = a ) = 1 p(S_{t+1}=s' \mid S_t=s,A_t=a) = 1 p(St+1​=s′∣St​=s,At​=a)=1
• 随机性环境逻辑：在给定当前状态 S t = s S_t=s St​=s和动作 A t = a A_t=a At​=a,到达下一状态存在多种可能性；使用上述2种公式表达。

回报(Return)和衰减因子 γ \gamma γ

在逻辑场景中，奖励(Reward)只是在 t t t时刻状态 S t → t + 1 S_t \to t+1 St​→t+1时刻状态 S t + 1 S_{t+1} St+1​的即时(1个时刻)的反馈信息，但在实际过程中， t t t时刻状态 S t S_t St​选择的行为 A t A_t At​可能对后续所有状态产生深远影响，而不是单独对 t + 1 t+1 t+1时刻状态产生影响。 因此，引入一个新的量：回报(Return),它表示从当前状态开始，到MDP执行结束所有奖励的加权和。

令 t t t时刻的回报为 G t G_t Gt​，终止状态(MDP执行结束时刻)为 T T T, G t G_t Gt​的数学表达如下：

G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . + γ T − 1 R t + T = ∑ k = 0 T − 1 γ k R t + k + 1 \begin{aligned} G_t & =R_{t+1} + \gamma R_{t+2} + \gamma ^2R_{t+3} +...+\gamma^{T-1}R_{t+T} \\ & = \displaystyle\sum_{k=0}^{T-1} \gamma^kR_{t+k+1} \\ \end{aligned} Gt​​=Rt+1​+γRt+2​+γ2Rt+3​+...+γT−1Rt+T​=k=0∑T−1​γkRt+k+1​​ 其中 γ \gamma γ为折扣系数(discounting rate)，表示未来奖励在当前时刻的价值比例； γ ∈ [ 0 , 1 ] \gamma \in [0,1] γ∈[0,1]

• 从逻辑角度讲，这种设计满足齐次马尔可夫假设 → \to → 回报(Return)结果只和当前状态和未来状态的奖励相关，和过去状态的奖励无关；
• γ \gamma γ的设计同样满足显示过程中的逻辑 → γ \to \gamma →γ以指数形式演绎从当前时刻开始，后续所有收益的衰减过程；

下一节内容

结合本节介绍，详细讲述如何使用马尔可夫决策过程(MDP)求解强化学习任务。

相关参考： 【强化学习】马尔科夫决策过程【白板推导系列】 马尔科夫奖励过程 - 简书 深度强化学习原理、算法pytorch实战 - 刘全，黄志刚编著