【强化学习】《动手学强化学习》马尔可夫决策过程

一、随机过程、马尔可夫过程、马尔可夫奖励过程

• 强化学习中的环境、模型其实就是一个马尔可夫决策过程，揭示了游戏的规则。如果想用强化学习的方法解决一个实际问题，第一步就是要将这个实际问题抽象成一个马尔可夫决策过程。马尔可夫决策过程由随机过程、马尔可夫过程、马尔可夫奖励过程一步步演化而来。
• 随机过程（stochastic process）
  某一随机现象在某时刻$t$的状态$S_t$是随机的，通常取决于$t$时刻之前的状态。已知历史信息$(S_1,...,S_t)$时下一时刻的状态为$S_{t+1}$的概率为$P(S_{t+1}|S_1,...,S_t)$。
• 马尔可夫过程（markov process）
  1.具有马尔可夫性质的随机过程，或者说某时刻状态只取决于上一时刻状态的随机过程，称之为马尔可夫过程，或者称为马尔可夫链。用公式表示如下：
  $$P(S_{t+1}|S_1,...,S_t)=P(S_{t+1}|S_t)$$
  2.$t+1$时刻状态只与$t$时刻相关，并不表明与历史状态完全没有关系，$t$时刻状态包含了$t-1$时刻状态信息，$t-1$时刻状态包含了$t-2$时刻状态信息…实际上$t$时刻状态包含了之前所有历史状态的信息。马尔可夫性质的存在大大简化了计算与分析。
  3.通常可用二元组$(\mathbf{S},\mathbf{P})$来表示一个马尔可夫过程，其中$\mathbf{S}$是有限个数的状态集，$\mathbf{P}$是状态转移矩阵。
  4.从某个状态出发，最终到达终结状态所形成的路径被称为一个状态序列（episode），这个步骤称为采样（sampling）。
• 马尔可夫奖励过程（markov reward process）
  1.在马尔可夫过程的基础上加入奖励函数$r$和折扣因子$\gamma$就得到马尔可夫奖励过程。可用如下四元组表示$(\mathbf{S},\mathbf{P},r,\gamma )$。奖励函数$r(s)$表示转移到状态$s$时获得的奖励，折扣因子$\gamma$为了让未来的奖励每步骤衰减$\gamma$，$\gamma =1$表示奖励不存在衰减因而更关注长远利益（当前利益只是单步，长远利益是多步），$\gamma =0$表示只关注当前利益，长远利益为0。
  2.在马尔可夫奖励过程中，从某状态开始到终结状态，所有奖励的衰减之和称为回报，公式如下：
  $$G_t=R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+...=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k}$$
• 价值函数（value function）
  在马尔可夫奖励过程中，一个状态的期望回报被称为这个状态的价值，所有状态的价值就组成了价值函数。价值函数的公式化表述为：
  V ( s ) = E [ G t ∣ S t = s ] = E [ R t + γ R t + 1 + γ 2 R t + 2 + . . . ∣ S t = s ] = E [ R t + γ ( R t + 1 + γ R t + 2 + . . . ) ∣ S t = s ] = E [ R t + γ G t + 1 ∣ S t = s ] = E [ R t + γ V ( S t + 1 ) ∣ S t = s ]
  V(s)=E[Gt|St=s]=E[Rt+γRt+1+γ2Rt+2+...|St=s]=E[Rt+γ(Rt+1+γRt+2+...)|St=s]=E[Rt+γGt+1|St=s]=E[Rt+γV(St+1)|St=s]" role="presentation" style="position: relative;">V(s)=E[Gt|St=s]=E[Rt+γRt+1+γ2Rt+2+...|St=s]=E[Rt+γ(Rt+1+γRt+2+...)|St=s]=E[Rt+γGt+1|St=s]=E[Rt+γV(St+1)|St=s]$$\begin{array}{rl}V(s)& =E[G_t|S_t=s]\\ & =E[R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+...|S_t=s]\\ & =E[R_t+\gamma (R_{t+1}+\gamma R_{t+2}+...)|S_t=s]\\ & =E[R_t+\gamma G_{t+1}|S_t=s]\\ & =E[R_t+\gamma V(S_{t+1})|S_t=s]\end{array}$$
  V(s)​=E[Gt​∣St​=s]=E[Rt​+γRt+1​+γ2Rt+2​+...∣St​=s]=E[Rt​+γ(Rt+1​+γRt+2​+...)∣St​=s]=E[Rt​+γGt+1​∣St​=s]=E[Rt​+γV(St+1​)∣St​=s]​​​
  其中回报$G_t$与时刻$t$相关，而价值函数与状态$s$有关，二者之间可以建立联系，即第$t$时刻所选择状态$S_t$的价值函数应该等于第$t$时刻的回报。
  $$G_t=V(S_t)$$
  在最后一个等式中，当前状态奖励的期望正是奖励函数在该状态的值，下一时刻状态价值函数可以从本状态$s$出发的转移概率表示，即
  V ( s ) = E [ R t + γ V ( S t + 1 ) ∣ S t = s ] = E [ R t ∣ S t = s ] + E [ γ V ( S t + 1 ) ∣ S t = s ] = r ( s ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s ) V ( s ′ )
  V(s)=E[Rt+γV(St+1)|St=s]=E[Rt|St=s]+E[γV(St+1)|St=s]=r(s)+γ∑s′∈SP(s′|s)V(s′)" role="presentation">V(s)=E[Rt+γV(St+1)|St=s]=E[Rt|St=s]+E[γV(St+1)|St=s]=r(s)+γ∑s′∈SP(s′|s)V(s′)$$\begin{array}{rl}V(s)& =E[R_t+\gamma V(S_{t+1})|S_t=s]\\ & =E[R_t|S_t=s]+E[\gamma V(S_{t+1})|S_t=s]\\ & =r(s)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s)V(s^{\prime })\end{array}$$
  V(s)​=E[Rt​+γV(St+1​)∣St​=s]=E[Rt​∣St​=s]+E[γV(St+1​)∣St​=s]=r(s)+γs′∈S∑​P(s′∣s)V(s′)​​​
  上式就是在强化学习中起到关键作用的贝尔曼方程（bellman equation）。

二、马尔可夫决策过程

1.在MRP中状态的转移过程是随机的，如果在MRP的基础上对于状态转移加入人为干预便成了MDP。马尔可夫决策过程由五元组组成$(S,A,\gamma ,r(s,a),P(s^{\prime }|s,a))$。（区分一下MRP中的$r(s)$与MDP中的$r(s,a)$：第$t$阶段的奖励在MRP中成立$R_t=r(s)$，在MDP中成立$R_t=r(s,a)$，$r(s)$是指由某个状态转移到$s$所获得的奖励，$r(s,a)$是指在状态$s$下选择动作$a$所获得的奖励）
2.在MDP中智能体对于状态转移的干预方式定义为策略$\pi$，公式表示为$\pi (a|s)=P(A_t=a|S_t=s)$。策略分为确定性策略与随机性策略，确定性策略是指当前状态下选定了动作后转移到的策略是固定的。
3.价值函数在MDP中也分为两种：状态价值函数与动作价值函数。
MDP中基于策略$\pi$的状态价值函数定义为从状态$s$出发遵循策略$\pi$到达终结状态的回报，公式表达为：
$$V^{\pi }(s)=E_{\pi }[G_t|S_t=s]$$
MDP中基于策略$\pi$的动作价值函数定义为从状态$s$出发执行动作$a$后遵循策略$\pi$到达终结状态的回报，公式表达为：
Q π ( s , a ) = E π [ G t ∣ S t = s , A t = a ] = r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) V π ( s ′ )

Qπ(s,a)​=Eπ​[Gt​∣St​=s,At​=a]=r(s,a)+γs′∈S∑​P(s′∣s,a)Vπ(s′)​​​
状态价值函数与动作价值函数之间存在着如下的关系。
$$V^{\pi }(s)=\sum _{a\in A}\pi (a|s)Q^{\pi }(s,a)$$
状态价值函数与动作价值函数的贝尔曼期望（bellman expectation equation）方程定义如下：
Q π ( s , a ) = E π [ R t + γ Q π ( s ′ , a ′ ) ∣ S t = s , A t = a ] = r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) V π ( s ′ ) = r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) Q π ( s ′ ) V π ( s ) = E π [ R t + γ V π ( s ′ ) ∣ S t = s ] = ∑ a ∈ A π ( a ∣ s ) Q π ( s , a ) = ∑ a ∈ A π ( a ∣ s ) ( r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) V π ( s ′ ) )

Qπ(s,a)=Eπ[Rt+γQπ(s′,a′)|St=s,At=a]=r(s,a)+γ∑s′∈SP(s′|s,a)Vπ(s′)=r(s,a)+γ∑s′∈SP(s′|s,a)∑a′∈Aπ(a′|s′)Qπ(s′)" role="presentation" style="position: relative;">Qπ(s,a)=Eπ[Rt+γQπ(s′,a′)|St=s,At=a]=r(s,a)+γ∑s′∈SP(s′|s,a)Vπ(s′)=r(s,a)+γ∑s′∈SP(s′|s,a)∑a′∈Aπ(a′|s′)Qπ(s′)$$\begin{array}{rl}{Q}^{\pi }(s,a)& =E_{\pi }[R_t+\gamma Q^{\pi }(s^{\prime },a^{\prime })|S_t=s,A_t=a]\\ & =r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{\pi }(s^{\prime })\\ & =r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime })\end{array}$$

\\

Vπ(s)=Eπ[Rt+γVπ(s′)|St=s]=∑a∈Aπ(a|s)Qπ(s,a)=∑a∈Aπ(a|s)(r(s,a)+γ∑s′∈SP(s′|s,a)Vπ(s′))" role="presentation" style="position: relative;">Vπ(s)=Eπ[Rt+γVπ(s′)|St=s]=∑a∈Aπ(a|s)Qπ(s,a)=∑a∈Aπ(a|s)(r(s,a)+γ∑s′∈SP(s′|s,a)Vπ(s′))$$\begin{array}{rl}{V}^{\pi }(s)& =E_{\pi }[R_t+\gamma V^{\pi }(s^{\prime })|S_t=s]\\ & =\sum _{a\in A}\pi (a|s)Q^{\pi }(s,a)\\ & =\sum _{a\in A}\pi (a|s)(r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{\pi }(s^{\prime }))\end{array}$$

Qπ(s,a)​=Eπ​[Rt​+γQπ(s′,a′)∣St​=s,At​=a]=r(s,a)+γs′∈S∑​P(s′∣s,a)Vπ(s′)=r(s,a)+γs′∈S∑​P(s′∣s,a)a′∈A∑​π(a′∣s′)Qπ(s′)​​​Vπ(s)​=Eπ​[Rt​+γVπ(s′)∣St​=s]=a∈A∑​π(a∣s)Qπ(s,a)=a∈A∑​π(a∣s)(r(s,a)+γs′∈S∑​P(s′∣s,a)Vπ(s′))​​​
4.我们可以将MDP转化成MRP，通过定义奖励函数与状态转移函数如下。一些小型的MDP问题转化为MRP之后，便可以使用MRP的解析解的方法求解价值函数了。当状态集合或者动作集合较大时，可以使用动态规划以及蒙特卡洛采样的方法来计算价值函数。
$$\begin{gathered} r^{\prime }(s)=\sum _{a\in A}\pi (a|s)r(s,a) \\ {P}^{\prime }(s^{\prime }|s)=\sum _{a\in A}\pi (a|s)P(s^{\prime }|s,a) \end{gathered}$$

三、蒙特卡洛方法

• 蒙特卡洛方法（monte carlo method）也被称为统计模拟方法，是一种基于概率统计的数值计算方法。使用采样的方法归纳出我们想要得到的目标的数值估计。举个简单的例子，使用蒙特卡洛方法来计算圆形的面积，在一个正方形中随机打点，统计打点位置在正方形内切圆的个数，当打点个数足够大时，两个形状的打点个数之比与面积之比就非常接近了。
• 使用蒙特卡洛方法来计算某个策略下的状态价值函数。使用该策略采样足够多的序列，计算从这个状态出发的回报再求其期望就可以了。其中$G_t^{(i)}$表示第$i$次采样序列中出现当前状态s时的回报。
  $$V^{\pi }(s)=E_{\pi }[G_t|S_t=s]\approx \frac{1}{N}\sum _{i=1}^N{G}_t^{(i)}$$
  注意：在一条序列中某个状态可能出现0次、1次或者很多次。第一种采样方法是每次出现都计算回报，第二种采样方法是每个状态只取某个序列中第一次出现时的回报。两种方法各有应用，本文应用第一种方法。
• 具体来说，使用蒙特卡洛方法近似计算状态价值函数的流程如下：
  1.使用策略$\pi$采样若干条序列。
  2.对于每一条序列，从后往前遍历每一个状态转移过程。并采用增量的方式更新价值函数。
  $$\begin{gathered} N(s)\leftarrow N(s)+1 \\ V(s)\leftarrow V(s)+\frac{1}{N(s)}(G-V(s)) \end{gathered}$$

四、最优策略与贝尔曼最优方程

• 在状态$s$处选择最优的策略$\pi$从而最大化状态价值函数，称之为最优状态价值函数：
  $$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s),\forall s\in S$$
• 在状态动作对$(s,a)$之后选择最优策略$\pi$从而最大化动作价值函数，称之为最优动作价值函数：
  $$Q^{\ast }(s,a)=\underset{\pi }{\max }{Q}^{\pi }(s,a),\forall s\in S,a\in A$$
• 二者之间存在着如下关系：
  $$\begin{gathered} Q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{\ast }(s^{\prime }) \\ {V}^{\ast }(s)=\underset{a\in A}{\max }{Q}^{\ast }(s,a) \end{gathered}$$
• 根据上述关系，可以得到贝尔曼最优方程（bellma opyimality equation）
  V ∗ ( s ) = max ⁡ a ∈ A { r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) V ∗ ( s ′ ) } Q ∗ ( s , a ) = r ( s , a ) + γ ∑ s ′ ∈ S P ( s ′ ∣ s , a ) max ⁡ a ′ ∈ A Q ∗ ( s ′ , a ′ ) V^*(s)=\max_{a\in A}\{r(s,a)+\gamma \sum_{s'\in S}P(s'|s,a)V^*(s')\}\\ Q^*(s,a)=r(s,a)+\gamma\sum_{s'\in S}P(s'|s,a)\max_{a'\in A}Q^*(s',a') V∗(s)=a∈Amax​{r(s,a)+γs′∈S∑​P(s′∣s,a)V∗(s′)}Q∗(s,a)=r(s,a)+γs′∈S∑​P(s′∣s,a)a′∈Amax​Q∗(s′,a′)
  贝尔曼方程的意义：某一阶段最优决策的问题，通过贝尔曼方程转化为下一阶段最优决策的子问题，从而初始状态的最优决策可以由终状态的最优决策(一般易解)问题逐步迭代求解。存在某种形式的贝尔曼方程，是动态规划方法能得到最优解的必要条件。