> 文档中心 > 马尔可夫奖励过程(MRP)

马尔可夫奖励过程(MRP)

马尔可夫奖励过程

  • 目录
    • 逻辑场景回顾
    • 概念介绍
      • 状态(State):
      • 动作(Action):
      • 策略(Policy):
      • 奖励(即时奖励)(Reward):
    • 状态转移函数(State Transition Function)
    • 回报(Return)和衰减因子 γ\gamma γ
    • 下一节内容

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

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

目录

逻辑场景回顾

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

  1. 根据决策π \pi π选择一个动作(Action);
  2. 执行该动作,系统根据动作的选择,从当前状态 St S_t St转移到下一时刻状态 S t + 1S_{t+1} St+1,并同时返回一个该时刻的奖励(Reward) R t + 1R_{t+1} Rt+1
  3. 新状态 S t + 1S_{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 = 1k \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 = 1m \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) π(as)=P(At=aSt=s)(aAt,sSt)
    其中 A t A_tAt表示 t tt时刻的动作(宏观概念), A t \mathcal A_tAt表示 t tt时刻可以被选择的动作的集合;
    解释:什么是可以被选择的动作
    在某一时刻的状态 S t S_tSt中,并不是所有的动作都能被选择,有可能在 S t S_tSt状态下,某些动作不可能发生(发生概率为0)
    满足这种条件的行为不会出现在 A t \mathcal A_tAt集合中。

奖励(即时奖励)(Reward):

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

  • 与状态和动作相同,奖励同样存在相关的奖励空间 → \to 可被分为离散/连续型随机变量
    离散型随机变量为例,某个MDP的奖励空间中包含 n nn个离散的状态,数学语言表达:
    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 SS,要去下一地点 S ′ S'S,已知去 S ′ S'S存在2条路径: A 1 A_1A1, A 2 A_2A2;

  • 已知走 A 1 A_1A1路径花费时间大约45分钟,走 A 2 A_2A2路径花费时间大约1小时;

  • 目标:走到 S ′ S'S
    上述场景可以将“走 A 1 A_1A1路径”,“走 A 2 A_2A2路径”视为动作,选择完动作并执行后,下一步状态 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情况下, St+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 ∣St = s ,At = a ] , ∑ s ′ ∑ rp ( s ′, r ∣ s , a ) = 1p(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,rs,a)=P[St+1=s,Rt+1=rSt=s,At=a],srp(s,rs,a)=1
p (s′ ∣ s , a ) = P [S t + 1 =s′ ∣St = s ,At = 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(ss,a)=P[St+1=sSt=s,At=a],sp(ss,a)=1
上述2个公式表达的逻辑意思基本相同,均表达了"当前时刻状态和动作确定的情况下,下个状态发生的条件概率。"
上述两种表达方式均可以表示状态转移概率,只是式1表达了关于转移后状态奖励的联合概率分布,是二维信息;而式2只表现出转移后状态的概率分布信息,两种公式之间存在如下转换关系:
p (s′ ∣ s , a ) = ∑ r ∈ Rp( s ′ ,r∣s,a) p(s'\mid s,a)=\displaystyle\sum_{r \in \mathcal R}p(s',r \mid s,a) p(ss,a)=rRp(s,rs,a)
策略(policy)类似,状态转移概率可以根据环境分为确定性环境(deterministic environment)随机性环境(stochastic environment)

  • 确定性环境的逻辑:在给定当前状态 St = s S_t=s St=s和动作 At = 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) = 1p(St+1=sSt=s,At=a)=1
  • 随机性环境逻辑:在给定当前状态 St = s S_t=s St=s和动作 At = a A_t=a At=a,到达下一状态存在多种可能性;使用上述2种公式表达。

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

在逻辑场景中,奖励(Reward)只是在 t t t时刻状态 S t → t + 1 S_t \to t+1 Stt+1时刻状态 St+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+...+γT1Rt+T=k=0T1γkRt+k+1
其中 γ \gamma γ折扣系数(discounting rate),表示未来奖励在当前时刻的价值比例;
γ ∈ [ 0 , 1 ] \gamma \in [0,1] γ[0,1]

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

下一节内容

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

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

小吃零食网