强化学习-马尔科夫决策过程（MDP）

1、强化学习介绍

  • 强化学习任务通常使用马尔科夫决策过程（Markov Decision Process，简称MDP）来描述，具体而言：机器处在一个环境中，每个状态为机器对当前环境的感知；机器只能通过动作来影响环境，当机器执行一个动作后，会使得环境按某种概率转移到另一个状态；同时，环境会根据潜在的奖励函数反馈给机器一个奖赏。综合而言，强化学习主要包含四个要素：状态、动作、转移概率以及奖赏函数。

tbQcZj.png

根据上图，agent（智能体）在进行某个任务时，首先与environment进行交互，产生新的状态state，同时环境给出奖励reward，如此循环下去，agent和environment不断交互产生更多新的数据。强化学习算法就是通过一系列动作策略与环境交互，产生新的数据，再利用新的数据去修改自身的动作策略，经过数次迭代后，agent就会学习到完成任务所需要的动作策略。

2、马尔科夫决策过程（Markov Process）

马尔可夫性当前状态包含了对未来预测所需要的有用信息，过去信息对未来预测不重要，该就满足了马尔科夫性，严格来说，就是某一状态信息包含了所有相关的历史，只要当前状态可知，所有的历史信息都不再需要，当前状态就可以决定未来，则认为该状态具有马尔科夫性。用公式描述为：

P(St+1∣St)=p(St+1∣S1,S2,⋅⋅⋅,St)P(S_{t+1}|S_t)=p(S_{t+1}|S_1,S_2,···,S_t)

马尔科夫过程又叫做马尔科夫链（Markov Chain）,它是一个无记忆的随机过程，可以用一个元组<S, P>表示，其中

  • S 是有限数量的状态集S=s1,s2,s3,⋯ ,stS={s_1,s_2,s_3,\cdots,s_t}
  • P 是状态转移概率矩阵p(St+1=s′∣st=s)p(S_{t+1}=s'|s_t=s)其中s′s'表示下一时刻的状态，s表示当前状态如下所示：对于状态s1s_1来说，有0.1的概率保持不变，有0.2的概率转移到s2s_2状态，有0.7的概率转移到s4s_4状态。

tHJIg0.png

可以使用矩阵来表示：

image-20250131120432032

3、马尔科夫奖励过程（Markov Reward Process）

3.1、概念介绍

马尔科夫奖励过程是在马尔科夫过程基础上增加了奖励函数R和衰减系数γ\gamma，用<S,R,P,γ>< S,R,P,\gamma >表示

  • R：表示S状态下某一时刻的状态StS_t在下一个时刻(t+1)能获得的奖励的期望

Rs=E[Rt+1∣St=s]R_s = E[R_{t+1}|S_t =s]

  • GtG_t： 收获GtG_t为在一个马尔科夫奖励链上从t时刻开始往后所有的奖励的衰减收益总和

Gt=Rt+1+γRt+2+γ2Rt+3+⋅⋅⋅+γT−t−1RTG_t = R_{t+1}+\gamma R_{t+2}+ \gamma ^2 R_{t+3} + ···+\gamma ^{T-t-1}R_T

  • γ\gamma：折扣因子（Discountfactoryγ∈[0,1]）（Discount factory \gamma \in [0,1]）
  • 1、为了避免出现状态循环的情况
  • 2、系统对于将来的预测并不一定都是准确的，所以要打折扣
  • 很显然γ\gamma越靠近1，考虑的利益越长远。
  • V(s)V(s):状态价值函数（state value function表示从改状态开始的马尔科夫链收获GtG_t的期望

v(s)=E[Gt∣St=s]v(s)=E[G_t|S_t =s]

例子：对于如下状态，设定进入S1S_1状态奖励为5，进入S7S_7状态奖励为10，其余状态奖励为0。则R可以如下表示：R=[5,0,0,0,0,0,10]R=[5,0,0,0,0,0,10],折扣引子γ\gamma为0.5。则对于下面两个马尔科夫过程获得的奖励为：

  • S4,S5,S6,S7:0+0.5∗0+0.5∗0+0.125∗10=1.25S_4,S_5,S_6,S_7: 0+0.5*0+0.5*0+0.125*10=1.25
  • S4,S3,S2,S1:0+0.5∗0+0.25∗0+0.125∗5=0.625S_4,S_3,S_2,S_1: 0+0.5*0+0.25*0+0.125*5=0.625

image-20250131122653249

3.2、Bellman Equation 贝尔曼方程

v(s)=E[Gt∣St=s]v(s) = E[G_t|S_t=s]

=E[Rt+1+γRt+2+γ2Rt+3+⋅⋅⋅∣St=s]= E[R_{t+1}+ \gamma R_{t+2}+\gamma ^2 R_{t+3}+···|S_t=s]

=E[Rt+1+γ(Rt+2+γRt+3+⋅⋅⋅)∣St=s]= E[R_{t+1}+ \gamma (R_{t+2} + \gamma R_{t+3}+···)|S_t=s]

=E[Rt+1+γv(St+1)∣St=s]= E[R_{t+1}+ \gamma v(S_{t+1})|S_t=s]

=E[Rt+1∣St=s]+γE[v(St+1)∣St=s]=E[R_{t+1}|S_t=s]+ \gamma E[v(S_{t+1})|S_t=s]

其中E[Rt+1∣St=s]]E[R_{t+1}|S_t=s]]代表的当前奖励函数，γE[v(St+1)∣St=s\gamma E[v(S_{t+1})|S_t=s为下一时刻状态的价值期望

使用贝尔曼方程状态价值V可以表示为：

V(s)=R(s)+γ∑s′∈SP(s′∣s)V(s′)V(s)= R(s) + \gamma \sum _{s' \in S}P(s'|s)V(s')

其中R(s)为Immediatereward，γ∑s′∈SP(s′∣s)V(s′)为DiscountedsumoffuturerewardR(s)为Immediate reward，\gamma \sum _{s' \in S}P(s'|s)V(s')为Discounted sum of future reward

S 表示下一时刻的所有状态， s′s'表示下一时刻可能的状态

通过贝尔曼方程，可以看到价值函数v(s)v(s)