MDP总结

MDP总结

---

强化学习建模

---

强化学习问题可以下图来表示：

上面右图中的大脑代表执行强化学习算法的个体（Agent、或称为代理）。个体通过强化学习算法计算出一个适合当前状态的动作$A_t$At​。地球代表强化学习问题中涉及的环境，它有自己的状态模型。个体在状态$S_t=s$St​=s下选择动作后，环境状态从$S_t=s$St​=s转移至$S_{t+1}=s'$St+1​=s′，同时个体获得采取动作$A_t$At​后的即时奖励$R_{t+1}$Rt+1​（注：$R_{t+1}$Rt+1​与$R_{t}$Rt​在本质上意义是相同的，但在描述RL问题中，涉及到状态S、行为A和奖励R时使用前者表示更为方便）。

强化学习模型要素

---

1. 环境的状态$S$S：一个集合，称为状态空间（状态集）。在$t$t时刻，环境的状态为$S_t\in S$St​∈S。
2. 个体的动作$A$A：一个集合，称为动作空间（动作集）。在$t$t时刻，此时环境状态为$S_t$St​，个体采取的动作为$A_t\in A$At​∈A。
3. 环境的奖励$R$R：一个函数，称为回报函数（奖励函数）。在$t$t时刻，此时环境状态为$S_t$St​，个体采取动作$A_t$At​；在$t+1$t+1时刻，个体得到动作对应得奖励$R_{t+1}$Rt+1​。
4. 收获（Return）$G_t$Gt​：在一个马尔科夫奖励链上从$t$t时刻开始往后所有的奖励的有衰减的总和。其公式为$G_t=R_{t+1}+\gamma R_{t+2}+...=\sum\limits_{k=0}^{\infty}\gamma^kR_{t+k+1}$Gt​=Rt+1​+γRt+2​+...=k=0∑∞​γkRt+k+1​
   1. $\gamma\in [0,1]$γ∈[0,1]，衰减因子（折现因子）。
   2. $\gamma=0$γ=0，表明个体是贪婪的，只关注于眼前的所能得到的利益（即时奖励）。
   3. $\gamma=1$γ=1，表明个体对即时奖励和延时奖励（即，未来的奖励）投于相同的关注（重视度）。
   4. $0<\gamma<1$0<γ<1，表明个体更关注于即时奖励，但同时也会考虑延时奖励，以此来避免“短视”。
5. 策略（Policy）$\pi$π：代表个体在状态$S_t$St​下采取动作得依据。$\pi$π可以是一个概率的集合/分布，此时其中元素$\pi(a|s)$π(a∣s)表示，在状态$s$s下，个体采取动作$a$a的概率值。
6. 价值函数（Value Function）：价值函数给出了某一状态或某一行为的长期价值。一个马尔科夫奖励过程中某一状态$S_t=s$St​=s的价值函数为从该状态开始的马尔可夫链收获的期望（从当前状态开始到最终状态时系统所获得的累加衰减回报的期望）。其公式如下：$V(s)=E[G_t|S_t=s]$V(s)=E[Gt​∣St​=s]价值可以仅描述状态，也可以描述某一状态下的某个行为，在一些特殊情况下还可以仅描述某个行为。
   1. 状态价值函数（价值函数，值函数）用于描述针对状态的价值。
   2. 行为价值函数（状态行为对价值函数，Q函数）用于描述某一状态下执行某一行为的价值。
7. 环境的状态转化模型（状态转移矩阵/函数）$P$P：可以理解为一个概率状态机，它可以表示为一个概率模型。通过$P$P可以得出，在$t$t时刻，个体于状态$S_t=s$St​=s下采取动作$a$a后，转移到下一个状态$S_{t+1}=s'$St+1​=s′的概率$P_{ss'}^a$Pss′a​。
8. 探索率$\epsilon$ϵ：这个比率主要用在强化学习训练迭代过程中，由于我们一般会选择使当前轮迭代价值最大的动作，但是这会导致一些较好的但我们没有执行过的动作被错过。因此我们在训练选择最优动作时，会有一定的概率$\epsilon$ϵ不选择使当前轮迭代价值最大的动作，而选择其他的动作。

强化学习引入MDP的原因

---

上一节中提到了状态转移模型，通过该模型可以得到个体在一状态执行动作转移到下一个状态的概率值。如果按照真实的环境转化过程看，转化到下一个状态$s'$s′的概率既与上一个状态$s$s有关，还与上上个状态，以及上上上个状态有关。这一会导致我们的环境转化模型非常复杂，复杂到难以建模。因此我们需要对强化学习的环境转化模型进行简化。简化的方法就是假设状态转化的马尔科夫性，也就是假设转化到下一个状态$s'$s′的概率仅与上一个状态$s$s有关，与之前的状态无关。用公式表示就是：$P_{ss'}^a=E(S_{t+1}|S_t=s,A_t=a)$Pss′a​=E(St+1​∣St​=s,At​=a)

假设把一强化学习问题形式化为马尔科夫决策过程$M$M。$M$M是一个元组：$\langle S,A,R,P,\gamma\rangle$⟨S,A,R,P,γ⟩，给定一个初始策略$\pi$π。

1. $S$S状态集，$S_t\in S$St​∈S
2. $A$A动作集，$A_t\in A$At​∈A
3. $R$R回报函数，$R_s^a=E(R_{t+1}|S_t=s,A_t=a)$Rsa​=E(Rt+1​∣St​=s,At​=a)
4. $P$P状态转移函数，$P_{ss'}^a=P(S_{t+1}=s'|S_t=s,A_t=a)$Pss′a​=P(St+1​=s′∣St​=s,At​=a)
5. $\gamma\in [0,1]$γ∈[0,1]，衰减因子
6. 收获，Return，$G_t=\sum\limits_{k=0}^{\infty}\gamma^kR_{t+k+1}$Gt​=k=0∑∞​γkRt+k+1​
7. 策略$\pi$π，或称为策略函数。可表示为$a=\pi(s)$a=π(s)的确定性形式，也可表示为$\pi(a|s)=P[A_t=a|S_t=s]$π(a∣s)=P[At​=a∣St​=s]的不确定性形式。
8. 强化学习的核心在于最优化策略，策略的优劣可以通过基于策略的价值函数来评判。该价值函数可以分为：状态价值函数和行为价值函数。通常被称为值函数和Q函数。
   1. 状态价值函数：$V^{\pi}(s)=E(G_t|S_t=s)$Vπ(s)=E(Gt​∣St​=s)
   2. 行为价值函数：$Q^{\pi}(s,a)=E(G_t|S_t=s,A_t=a)$Qπ(s,a)=E(Gt​∣St​=s,At​=a)

MDP问题求解核心 —— Bellman方程

---

策略的优劣可以通过价值函数来计算。那么最优策略对应的价值函数的值必为最大。为求解最优策略，我们需要找到最优价值函数，然后对最优价值函数进行求解获得最优策略。在这一过程中就涉及到Bellman方程。下面我们对$V^{\pi}(s)和Q^{\pi}(s,a)$Vπ(s)和Qπ(s,a)进行推导，使得当前的状态的价值函数能够用下一状态的价值函数递归表示，并且推导$V^{\pi}(s)和Q^{\pi}(s,a)$Vπ(s)和Qπ(s,a)之间的关系。

在推导前需要注意几个表示回报的符号的意义：$R_s^a,R_{ss'}^a,R_s^{\pi}$Rsa​,Rss′a​,Rsπ​

1. $R_{ss'}^a$Rss′a​：表示的是在状态$s$s下，执行动作$a$a后状态转移到$s'$s′时得到的即时奖励。
2. $R_s^a$Rsa​：$R_s^a=\sum\limits_{s'\in S}P_{ss'}^aR_{ss'}^a$Rsa​=s′∈S∑​Pss′a​Rss′a​
3. $R_s^{\pi}$Rsπ​：$R_s^{\pi}=\sum\limits_{a\in A}\pi(a|s)R_{s}^a$Rsπ​=a∈A∑​π(a∣s)Rsa​

KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ V^{\pi}(s)=&E_…

值函数和Q函数的关系和递推表达

---

1. 值函数、Q函数的递推表达：
   $V^{\pi}(s)=\sum\limits_{a\in A}\pi(a|s)\color{red}{\{}R_s^a+\gamma\sum\limits_{s'\in S}P_{ss'}^aV^{\pi}(s')\color{red}{\}}\\ Q^{\pi}(s,a)=R_s^a+\gamma \sum\limits_{s'\in S}P_{ss'}^a\sum\limits_{a'\in A}\pi(a|s)Q^{\pi}(s',a')$Vπ(s)=a∈A∑​π(a∣s){Rsa​+γs′∈S∑​Pss′a​Vπ(s′)}Qπ(s,a)=Rsa​+γs′∈S∑​Pss′a​a′∈A∑​π(a∣s)Qπ(s′,a′)
2. 值函数与Q函数之间关系：
   $V^{\pi}(s)=\sum\limits_{a\in A}\pi(a|s)Q^{\pi}(s,a)\\ Q^{\pi}(s,a)=R_s^a+\gamma \sum\limits_{s'\in S}P_{ss'}^aV^{\pi}(s')$Vπ(s)=a∈A∑​π(a∣s)Qπ(s,a)Qπ(s,a)=Rsa​+γs′∈S∑​Pss′a​Vπ(s′)

最优价值函数

---

解决强化学习问题意味着要寻找一个最优策略，该策略使个体与环境交互过程中获得始终比其他策略都要多的收获，这个最优策略我们可以用 $\pi^*$π∗ 表示。一旦找到这个最优策略，那么就意味着该强化学习问题被解决。一般来说很难找到一个最优策略，但是可以通过比较若干不同策略的优劣来确定一个较好的策略，也就是局部最优解。

对于比较策略的优劣，我们可以通过对应的价值函数来实现。换句话说，寻找较优策略可通过寻找较优的价值函数来完成。

1. 定义最优状态价值函数是所有策略下产生的众多状态价值函数中的最大者，即：$V^*(s)=\max\limits_{\pi}V^{\pi}(s)$V∗(s)=πmax​Vπ(s)
2. 最优动作价值函数是所有策略下产生的众多动作状态价值函数中的最大者，即：$Q^*(s,a)=\max\limits_{\pi}Q^{\pi}(s,a)$Q∗(s,a)=πmax​Qπ(s,a)
3. 对于最优策略，基于动作价值函数可以定义为：
   $\pi^*(a|s)= \begin{cases} 1, & \text {if $a=\arg\max\limits_{a\in A}Q^*(s,a)$} \\ 0, & \text{else} \end{cases}$π∗(a∣s)={1,0,​if a=arga∈Amax​Q∗(s,a)else​
4. 只要我们找到了最大的状态价值函数或者动作价值函数，那么对应的策略$\pi^*$π∗就是我们强化学习问题的解。

Bellman最优方程

---

根据上述最优价值函数的定义，我们可以将其推导为Bellman方程形式。

1. 最优状态价值函数：$V^{*}(s)=\max\limits_{\pi}V^{\pi}(s)$V∗(s)=πmax​Vπ(s)
   $\begin{aligned} V^{*}(s)=&\max\limits_{\pi}V^{\pi}(s)\\ =&\max\limits_{\pi}{}(\sum\limits_{a\in A}\pi(a|s)Q^{\pi}(s,a))\\ =&\max\limits_{\pi}\max\limits_{a\in A}Q^{\pi}(s,a)\\ =&\max\limits_{a\in A}Q^{*}(s,a) \end{aligned}$V∗(s)====​πmax​Vπ(s)πmax​(a∈A∑​π(a∣s)Qπ(s,a))πmax​a∈Amax​Qπ(s,a)a∈Amax​Q∗(s,a)​
   1. $\pi(a|s)\in [0,1]$π(a∣s)∈[0,1]，且$\sum\limits_{a\in A}\pi(a|s)=1$a∈A∑​π(a∣s)=1
   2. $\sum\limits_{a\in A}\pi(a|s)Q^{\pi}(s,a)$a∈A∑​π(a∣s)Qπ(s,a)的最大值：
      1. 假设在状态$s$s下执行动作$a^*$a∗时，$Q_{\pi}(s,a^*)$Qπ​(s,a∗)的值最大。$Q_{\pi}(s,a^*)\geq Q_{\pi}(s,a),a\in A$Qπ​(s,a∗)≥Qπ​(s,a),a∈A
      2. $\max\limits_{a\in A}\sum\limits_{a\in A}\pi(a|s)Q^{\pi}(s,a)=\max\limits_{a\in A}Q^{\pi}(s,a)$a∈Amax​a∈A∑​π(a∣s)Qπ(s,a)=a∈Amax​Qπ(s,a)
      3. 推导证明：假设$p_1+p_2+...+p_n=1$p1​+p2​+...+pn​=1，$v_i\geq 0,i\in [0,n]$vi​≥0,i∈[0,n]，且$i$i为整数。令$\max v_i=p_{max}$maxvi​=pmax​，对应的$p_i$pi​为$p_{max}$pmax​，那么：
         $\begin{aligned} p_1v_1+p_2v_2+...+p_{max}v_{max}+...+p_nv_n &\leq p_1v_{max}+p_2v_{max}+...+p_{max}v_{max}+...+p_nv_{max}\\ p_1v_1+p_2v_2+...+p_{max}v_{max}+...+p_nv_n &\leq (p_1+p_2+...+p_{max}+...+p_n)v_{max}\\ p_1v_1+p_2v_2+...+p_{max}v_{max}+...+p_nv_n &\leq v_{max}\\ \sum\limits_{i\in [0,n]}p_iv_i &\leq \max\limits_{i\in [0,n]}v_i \end{aligned}$p1​v1​+p2​v2​+...+pmax​vmax​+...+pn​vn​p1​v1​+p2​v2​+...+pmax​vmax​+...+pn​vn​p1​v1​+p2​v2​+...+pmax​vmax​+...+pn​vn​i∈[0,n]∑​pi​vi​​≤p1​vmax​+p2​vmax​+...+pmax​vmax​+...+pn​vmax​≤(p1​+p2​+...+pmax​+...+pn​)vmax​≤vmax​≤i∈[0,n]max​vi​​
         注：当$p_{max}=1$pmax​=1时等号成立。
2. 最优行为价值函数：$Q^{*}(s,a)=\max\limits_{\pi}Q^{\pi}(s,a)$Q∗(s,a)=πmax​Qπ(s,a)
   $\begin{aligned} Q^{*}(s,a)&=\max\limits_{\pi}Q^{\pi}(s,a)\\ &=\max\limits_{\pi}{}(R_s^a+\gamma\sum\limits_{s'\in S}P_{ss'}^aV^{\pi}(s'))\\ &=R_s^a+\gamma\sum\limits_{s'\in S}P_{ss'}^aV^{*}(s') \end{aligned}$Q∗(s,a)​=πmax​Qπ(s,a)=πmax​(Rsa​+γs′∈S∑​Pss′a​Vπ(s′))=Rsa​+γs′∈S∑​Pss′a​V∗(s′)​
3. $Q^{*}(s,a)$Q∗(s,a)和$V^{*}(s)$V∗(s)的递推表达式：
   $\begin{aligned} V^{* }(s)&=\max\limits_{a\in A}{}(R_s^a+\gamma\sum\limits_{s'\in S}P_{ss'}^aV^{*}(s'))\\ Q^{*}(s,a)&=R_s^a+\gamma\sum\limits_{s'\in S}P_{ss'}^a\max\limits_{a\in A}{}Q^{*}(s',a') \end{aligned}$V∗(s)Q∗(s,a)​=a∈Amax​(Rsa​+γs′∈S∑​Pss′a​V∗(s′))=Rsa​+γs′∈S∑​Pss′a​a∈Amax​Q∗(s′,a′)​
4. 在获取Bellman最优方程后，可以使用强化学习算法对方程进行求解获得最优策略。