强化学习之蒙特卡罗（MC）、动态规划（DP）、时间差分（TD）

强化学习笔记

1.马尔可夫决策过程(MDP)1.马尔可夫性质2.马尔可夫过程3.马尔可夫奖励过程(MRP)4.马尔可夫决策过程(MDP)2.蒙特卡罗（MC）、动态规划（DP）、时间差分（TD）1.蒙特卡SEO靠我罗(MC)2.动态规划(DP)3.时间差分(TD)4. MC、DP、TD之间的关系。

1.马尔可夫决策过程(MDP)

1.马尔可夫性质

当且仅当某时候的状态只取决于上一时刻的状态时，一个随机过程被称为具有马SEO靠我尔可夫性质

。

P(St+1∣St)=P(St+1∣S1,...,St)P(S_{t+1}|S_t)=P(S_{t+1}|S_1,...,S_t) P(St+1​∣St​)=P(St+1​∣S1​,...SEO靠我,St​) 2.马尔可夫过程

指具有马尔可夫性质的随机过程被称为马尔可夫过程，通常用元组<S,P>描述。

S表示有限数量的状态集合，终止状态是指它不会再转移到其他状态。

S={s1,s2,...sn}S=\{SEO靠我s_1,s_2,...s_n\} S={s1​,s2​,...sn​}

P是状态转移矩阵，定义所有状态对之间的转移概率，某个状态到其他状态的概率和必须为1。

P=[P(s1∣s1)...P(sn∣s1).SEO靠我........P(s1∣sn)...P(sn∣sn)]P=\begin{bmatrix} P(s_1|s_1) & ...& P(s_n|s_1) \\ ... & ... &...\\P(s_1|SEO靠我s_n)&...&P(s_n|s_n) \end{bmatrix} P=​P(s1​∣s1​)...P(s1​∣sn​)​.........​P(sn​∣s1​)...P(sn​∣sn​)​​3.马尔SEO靠我可夫奖励过程(MRP)

再马尔可夫过程的基础上加入奖励函数r和折扣因子γ，就可以得到马尔可夫奖励过程，通常由<S,P,r,γ>构成。

S是有限状态的集合。

P是状态转移矩阵。

r是奖励函数，某个状态s的奖励rSEO靠我(s)指转移到该状态时可以获得的奖励的期望。

γ是折扣因子，取值范围为[0,1)。

(1) 回报：

在马尔可夫奖励过程中，从第t时刻状态St开始，直到终止状态时，所有奖励的衰减之和称为回报。

Gt=Rt+γRSEO靠我t+1+r2Rt+2+...=∑i=0∞rkRt+kG_t=R_t+γR_{t+1}+r^2R_{t+2}+...=\sum_{i=0}^∞r^kR_{t+k} Gt​=Rt​+γRt+1​+r2RtSEO靠我+2​+...=i=0∑∞​rkRt+k​

(2) 价值函数：

在马尔可夫奖励过程中，一个状态的期望回报被称为这个状态的价值。价值函数输入为某个状态，输出为这个状态的价值。

V(s)=E[Gt∣St=s]VSEO靠我(s)=r(s)+γ∑s′∈SP(s′∣s)V(s′)V(s)=E[G_t|S_t=s]\\ V(s)=r(s)+γ\sum_{s∈S}P(s|s)V(s) V(s)=E[Gt​∣St​=s]V(s)SEO靠我=r(s)+γs′∈S∑​P(s′∣s)V(s′)

(3)贝尔曼方程:

V=R+γPV(I−rP)V=RV=(I−rP)−1RV=R+γPV\\ (I-rP)V=R\\ V=(I-rP)^{-1}R V=SEO靠我R+γPV(I−rP)V=RV=(I−rP)−1R

贝尔曼方程的计算复杂度O(n3)，求解较大规模的马尔可夫奖励过程的价值函数时，可以使用动作规划(DP)算法，蒙特卡洛方法(MC)和时序差分(TD)。4SEO靠我.马尔可夫决策过程(MDP)

​ 马尔可夫过程和马尔可夫奖励过程都是自发改变的随机过程，在这基础上加一个外界的“刺激”（智能体的动作）来改变这个随机过程，就有了马尔可夫决策过程，通常由<S,A,P,r,SEO靠我γ>。

S是状态的集合。

A是动作的集合。

γ是折扣因子。

r(s,a)是奖励函数，此时奖励可能同时取决于状态s和动作a。

P(s’|s,a)是状态转移函数，表示在状态s执行动作a之后到达状态s‘的概率。

r’(SEO靠我s)表示在一个MRP状态s的奖励。

r′(s)=∑a∈Aπ(a∣s)r(s,a)r(s)=\sum_{a∈A}\pi(a|s)r(s,a) r′(s)=a∈A∑​π(a∣s)r(s,a)

P’(s’|s)SEO靠我表示在一个MRP的状态从s转移至s’的概率。

P′(s′∣s)=∑a∈Aπ(a∣s)P(s′∣s,a)P(s|s)=\sum_{a∈A}\pi(a|s)P(s|s,a) P′(s′∣s)=a∈A∑​π(SEO靠我a∣s)P(s′∣s,a)

(1)策略：

策略Π(a|s)表示输入状态为s的情况下采取动作a的概率。

π(a∣s)=P(At=a∣St=s)\pi(a|s)=P(A_t=a|S_t=s) π(a∣s)=P(SEO靠我At​=a∣St​=s)

(2)状态价值函数:

从状态s出发遵循策略Π能获得的期望回报，被称为状态价值函数VΠ(s)。

Vπ(s)=Eπ[Gt∣St=s]V^\pi(s)=E_\pi[G_t|S_t=s] SEO靠我Vπ(s)=Eπ​[Gt​∣St​=s]

(3)动作价值函数:

从状态s出发，遵循策略Π并执行动作a得到的期望回报，被称为动作价值函数QΠ(s,a)。

Qπ(s,a)=Eπ[Gt∣St=s,At=a]Q^\SEO靠我pi(s,a)=E_\pi[G_t|S_t=s,A_t=a] Qπ(s,a)=Eπ​[Gt​∣St​=s,At​=a]

状态s的价值等于在该状态下基于策略Π采取所有动作的概率和相应的价值相乘再求和的结果SEO靠我。

Vπ(s)=∑a∈Aπ(a∣s)Qπ(s,a)V^\pi(s)=\sum_{a∈A}\pi(a|s)Q^\pi(s,a) Vπ(s)=a∈A∑​π(a∣s)Qπ(s,a)

状态s下采取动作a的价值等于SEO靠我即时奖励加上经过衰减的所有可能的下一个状态的状态转移概率和相应的价值乘积。

Qπ(s,a)=r(s,a)+r∑s′∈SP(s′∣s,a)Vπ(s′)Q^\pi(s,a)=r(s,a)+r\sum_{s∈SEO靠我S}P(s|s,a)V^\pi(s) Qπ(s,a)=r(s,a)+rs′∈S∑​P(s′∣s,a)Vπ(s′)

(4)贝尔曼期望方程:

由上式推导可得

Qπ=r(s,a)+γ∑s′∈SP(s′∣s,a)∑SEO靠我a′∈Aπ(a′∣s′)Qπ(s′∣a′)Vπ(s)=∑a∈Aπ(a∣s)(r(s,a)+r∑s′∈SP(s′∣s,a)Vπ(s′))Q^\pi=r(s,a)+γ\sum_{s∈S}P(s|s,a)\SEO靠我sum_{a∈A}\pi(a|s)Q^\pi(s|a)\\V^\pi(s)=\sum_{a∈A}\pi(a|s)(r(s,a)+r\sum_{s∈S}P(s|s,a)V^\pi(s)) Qπ=r(s,SEO靠我a)+γs′∈S∑​P(s′∣s,a)a′∈A∑​π(a′∣s′)Qπ(s′∣a′)Vπ(s)=a∈A∑​π(a∣s)(r(s,a)+rs′∈S∑​P(s′∣s,a)Vπ(s′))

(5)贝尔曼最优方程SEO靠我：

强化学习的目标：通常是找到一个策略，使得智能体从初始状态出能获得最多的期望回报。

*最优策略(Π(s))：**在有限状态和动作集合的MDP中，至少存在一个策略比其他所有策略都好或者至少存在一个策略不差SEO靠我于其他所有策略。

最优状态价值函数：

V∗(s)=max⁡πVπ(s)V^*(s)=\max_{\pi}V^\pi(s) V∗(s)=πmax​Vπ(s)

最优动作价值函数：

Q∗(s,a)=max⁡πQπ(SEO靠我s,a)Q^*(s,a)=\max_{\pi}Q^\pi(s,a) Q∗(s,a)=πmax​Qπ(s,a)

为了使用最优动作价值函数最大，需要在当前状态动作对(s,a)之后都执行最优策略。

Q∗(s,aSEO靠我)=r(s,a)+r∑s′∈SP(s′∣s,a)V∗(s′)V∗(s′)=max⁡a∈AQ∗(s,a)Q^*(s,a)=r(s,a)+r\sum_{s∈S}P(s|s,a)V^*(s)\\V^*(s)SEO靠我=\max_{a∈A}Q^*(s,a) Q∗(s,a)=r(s,a)+rs′∈S∑​P(s′∣s,a)V∗(s′)V∗(s′)=a∈Amax​Q∗(s,a)

根据最优状态价值函数和最优动作价值函数的关系SEO靠我，以及贝尔曼方程，得到贝尔曼最优方程。

V∗(s)=max⁡a∈A{r(s,a)+γ∑s′∈SP(s′∣s,a)V∗(s′)}Q∗(s,a)=r(s,a)+γ∑s′∈SP(s′∣s,a)max⁡a′∈ASEO靠我Q∗(s′,a′)V^*(s)=\max_{a∈A}\{r(s,a)+γ\sum_{s∈S}P(s|s,a)V^*(s)\}\\Q^*(s,a)=r(s,a)+γ\sum_{s∈S}P(s|s,a)\SEO靠我max_{a∈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′∈AmaxSEO靠我​Q∗(s′,a′)

V*(s)与VΠ(s)的区别：前者会按照获取最多期望回报的动作来取值，其他动作则不会赋予概率，类似于贪心算法；后者会根据策略Π对各个动作的概率分配获取的期望回报来求和， 就是求期望SEO靠我。

2.蒙特卡罗（MC）、动态规划（DP）、时间差分（TD）

这些方法用于找到一个策略，使得智能体从初始状态出能获得最多的期望回报。

1.蒙特卡罗(MC)

如图所示，蒙特卡罗需要一个完整的路径。

蒙特卡罗公式的SEO靠我推导：

(1).状态价值的期望回报：当策略在MDP上采样很多条序列，计算从这个状态出发的回报再求其期望。

Vπ=Eπ[Gt∣St=s]≈1N∑i=1NGt(i)V^\pi=E_\pi[G_t|S_t=s]SEO靠我\approx \frac{1}{N}\sum_{i=1}^NG_t^{(i)} Vπ=Eπ​[Gt​∣St​=s]≈N1​i=1∑N​Gt(i)​

(2).采用增量式更新来推导。

VNπ=1N∑i=1NSEO靠我Gt(i)=1N(Gt+∑i=1N−1Gt(i))=1N(Gt+(N−1)VN−1π(s))=VN−1π(s)+1N(Gt−VN−1π(s))(VN−1π(s)表示VNπ的前一步的值，都是表示同一状态SEO靠我)V^\pi_N=\frac{1}{N}\sum_{i=1}^NG_t^{(i)}\\=\frac{1}{N}(G_t+\sum_{i=1}^{N-1}G_t^{(i)})\\=\frac{1}{N}SEO靠我(G_t+(N-1)V^\pi_{N-1}(s))\\=V^\pi_{N-1}(s)+\frac{1}{N}(G_t-V^\pi_{N-1}(s))\\(V^\pi_{N-1}(s)表示V^\pi_NSEO靠我的前一步的值，都是表示同一状态) VNπ​=N1​i=1∑N​Gt(i)​=N1​(Gt​+i=1∑N−1​Gt(i)​)=N1​(Gt​+(N−1)VN−1π​(s))=VN−1π​(s)+N1​(SEO靠我Gt​−VN−1π​(s))(VN−1π​(s)表示VNπ​的前一步的值，都是表示同一状态)

(3).蒙特卡罗公式。

1.收集episode(S1,A1,R1,....St)2.状态St的回报为GtN(SSEO靠我t)←N(St)+1V(St)←V(St)+1N(St)(Gt−V(St))1.收集episode(S_1,A_1,R_1,....S_t)\\2.状态S_t的回报为G_t\\N(S_t)\gets SEO靠我N(S_t)+1\\V(S_t)\gets V(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t)) 1.收集episode(S1​,A1​,R1​,....St​)2.状态St​的回报SEO靠我为Gt​N(St​)←N(St​)+1V(St​)←V(St​)+N(St​)1​(Gt​−V(St​)) 2.动态规划(DP)

动态规划：将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解SEO靠我得到目标问题的解。

基于动态规划的强化学习分为策略迭代(policy iteration)和价值迭代(value iteration)。

(1).策略迭代

策略迭代由两部分组成：策略评估(policy evSEO靠我aluation)和策略提升(policy improvement)。

i.策略评估：根据之前学习的贝尔曼期望方程，可以得到，当知道奖励函数r(s,a)和状态转移函数p(s’|s,a)时，可以根据下一个SEO靠我状态的价值来计算当前状态的价值。因此，可以把下一个可能状态的价值当成一个子问题，把当前状态的价值看作成当前问题。公式如下：

Vk+1(s)=∑a∈Aπ(a∣s)(r(s,a)+r∑s′∈SP(s′∣s,SEO靠我a)Vk(s′))V^{k+1}(s)=\sum_{a∈A}\pi(a|s)(r(s,a)+r\sum_{s∈S}P(s|s,a)V^k(s)) Vk+1(s)=a∈A∑​π(a∣s)(r(s,a)+SEO靠我rs′∈S∑​P(s′∣s,a)Vk(s′))

当子问题和当前问题之间的差值比较小时，则证明迭代已经收敛，可以结束策略评估。

ii.策略提升:可以贪心地在每一个状态选择动作价值最大的动作。

π′(s)=arSEO靠我gmax⁡aQπ(s,a)=argmax⁡a{r(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)}\pi(s)=arg \max_aQ^\pi(s,a)=arg \max_a\{r(s,a)+γSEO靠我\sum_{s∈S}P(s|s,a)V^\pi(s)\} π′(s)=argamax​Qπ(s,a)=argamax​{r(s,a)+γs′∈S∑​P(s′∣s,a)Vπ(s′)}

策略迭代算法：

(2)SEO靠我.价值迭代

价值迭代直接由贝尔曼最优方程来进行动态规划 ，得到最终的最优状态价值函数。

3.时间差分(TD)

时序差分：用来估计一个策略的价值函数的方法，它结合了蒙特卡罗和动态规划算法的思想。

时序差分方法和SEO靠我蒙特卡罗的相似之处在于可以从样本数据中学习，不需要事先知道环境(由他们公式可知，不需要知道P(s’|s,a)）；和动态规划的相似之处在于可以根据贝尔曼方程的思想，利用后续状态的价值估计来更新当前状态的SEO靠我价值估计。

时序差分(TD)：

rt+γV(st+1)−V(st)r_t+γV(s_{t+1})-V(s_t) rt​+γV(st+1​)−V(st​) 4. MC、DP、TD之间的关系。

右下角表示穷举法。SEO靠我

MC与TD的区别：

TD可以在每一步后在线学习。

MC 必须等到episode结束才能知道return。TD 可以从不完整的序列中学习。

MC 只能从完整序列中学习。TD 在连续（非终止）环境中工作。

MC SEO靠我仅适用于 episodic（终止）环境。TD利用马尔可夫特性，在马尔可夫环境中更高效。

MC 不利用马尔可夫特性，在非马尔可夫环境中更有效。

待续。。。强化学习TD的相关算法。

参考资料：

周博磊强化学习课程SEO靠我

张伟楠等动手学深度学习

强化学习相关代码：https://github.com/boyu-ai/Hands-on-RL