强化学习笔记（一）

参考书目：蘑菇书，链接蘑菇书
本系列笔记仅为个人学习所用，不涉及商业价值

回报与价值函数

范围是指一个回合的长度，即每个回合最大的时间步数，是由有限个步数决定的。

回报指奖励的逐步叠加。假设时间$t$后奖励序列为$r_{t+1},r_{t+2},\cdots ,r_{t+3}$，那么回报为
$$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+{\gamma }^3{r}_{t+4}+\cdots +{\gamma }^{T-t-1}{r}_T$$
其中$\gamma$为折扣因子，越往后得到的奖励，折扣越多，即希望得到现有的奖励，对未来的奖励打折扣。$\gamma =0$则只关注当前的奖励。

状态价值函数：定义为回报的期望，即
$$\begin{array}{rl}{V}^t(s)& =\mathbb{E}\left[G_t|s_t=s\right]\\ & =\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+{\gamma }^3{r}_{t+4}+\cdots +{\gamma }^{T-t-1}{r}_T|s_t=s\right]\end{array}$$其中$G_t$是折扣回报。对$G_t$取期望，可以看成是对未来可能获得奖励的当前价值的表现，即进入某一个状态后，现在有多大的价值。

贝尔曼方程

从价值函数里推导出贝尔曼方程
$$V(s)=\underset{即时奖励}{\underbrace{R(s)}}+\underset{未来奖励的折扣总和}{\underbrace{\gamma \sum _{s^{\prime }\in S}p\left(s^{\prime }|s\right)V(s^{\prime })}}$$

全期望公式

全期望公式也被称为叠期望公式（LIE）。如果$A_i$是样本空间的有限或可数的划分，则全期望公式为
$$\mathbb{E}[X]=\sum _i\mathbb{E}[X|A_i]p(A_i)$$即是一种加权求和。
同样地有
$$\begin{array}{rl}\mathbb{E}\left[G_{t+1}|s_{t+1}\right]& =\mathbb{E}[g^{\prime }|s^{\prime }]\\ & =\sum _{g^{\prime }}{g}^{\prime }p\left(g^{\prime }|s^{\prime }\right)\end{array}\text{\hspace{1em}(2.9)}$$如果$X,Y$都是离散型随机变量，则条件期望$\mathbb{E}[X|Y=y]$定义为
$$\mathbb{E}[X|Y=y]=\sum _{x}xp(X=x|Y=y)$$对式(2.9)求期望有
$$\mathbb{E}\left[\mathbb{E}\left[G_{t+1}|s_{t+1}\right]|s_t\right]=\mathbb{E}[g^{\prime }|s]=\mathbb{E}[G_{t+1}|s_t]$$
贝尔曼方程推导：
$$\begin{array}{rl}V(s)& =\mathbb{E}[G_t|s_t=s]\\ & =\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+{\gamma }^3{r}_{t+4}+\cdots |s_t=s\right]\\ & =R(s)+\gamma \mathbb{E}[G_{t+1}|s_t=s]\\ & =R(s)+\gamma \mathbb{E}[V(s_{t+1})|s_t=s]\\ & =R(s)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s)V(s^{\prime })\end{array}\text{\hspace{1em}(2.11)}$$上式也叫动态规划方程。表明当前状态的价值函数可以通过下个状态的价值函数来计算。它表明的是$V(s)$和$V(s^{\prime })$之间的关系。
向量形式的解析解：
$$\text{V}={\left(\text{I}-\gamma \text{P}\right)}^{-1}\text{R}$$

自举

根据其他估算值来更新估算值的思想，称为自举。当最后更新的状态与我们上一个状态的区别不大时，更新就可以停止，可以输出最新的$V^{\prime }(s)$作为当前状态的价值。此时贝尔曼方程变成了一个贝尔曼更新。

策略

策略定义了在某一个状态应该采取什么样的动作。知道当前状态后，可以把当前状态代入策略函数，得到一个概率
$$\pi (a|s)=p(a_t=a|s_t=s)$$即在状态$s$下采取$a$动作的概率。bf本质上是一个概率的表示。

当已经知道每个状态下可能采取的动作的概率后，可以直接把动作进行加和，去掉$a$，得到对于马尔可夫奖励过程的转移，其中没有动作
$$P_{\pi }(s^{\prime }|s)=\sum _{a\in A}\pi (a|s)p(s^{\prime }|s,a)\text{\hspace{1em}(2.18)}$$理解为：从$s\to s^{\prime }$的概率=采取$a$时从$s\to s^{\prime }$的概率$p$ $\times$ 在$s$下采取$a$的概率$\pi$。

对于奖励函数，亦可以把动作去掉，得到奖励函数
$$r_{\pi }(s)=\sum _{a\in A}\pi (a|s)R(s,a)\text{\hspace{1em}(2.19)}$$

马尔可夫决策过程和马尔可夫过程/马尔可夫奖励过程的区别

马尔可夫过程/马尔可夫奖励过程的状态转移是直接决定的，从当前$s$直接通过转移概率决定下一个状态。
马尔可夫决策过程中间多了一层动作$a$，智能体在当前$s$首先要决定采取一种动作，到达下图的黑色节点。到达黑色节点后，由于具有不确定性，智能体进入未来的状态也是一个概率分布。在当前状态与未来状态转移过程中多了一层决策性，这是主要区别。在马尔可夫决策过程中，动作是由智能体决定的，智能体会采取动作来决定未来的状态转移。

马尔可夫决策过程中的价值函数

$$V_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|s_t=s]\text{\hspace{1em}(2.20)}$$当策略决定后，对策略进行采样，得到一个期望，从而得出价值函数。

Q函数，也被称为动作价值函数，定义是在某一状态采取某一动作，可能得到的回报的期望
$$Q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|s_t=s,a_t=a]$$这里的期望也是基于策略函数的。Q是采取单个$a$得到的价值，即单一动作$a$的动作价值。
由于可能采取不同的策略，因此需要对策略函数进行加和，得到策略的价值。对Q函数中的动作进行加和（即遍历所有可能取到的动作），就可以得到价值函数
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)Q_{\pi }(s,a)\text{\hspace{1em}(2.22)}$$V是单一状态$s$下所有动作带来的价值的期望，总体来说是单一状态$s$的状态价值。

对Q函数的贝尔曼方程进行推导
$$\begin{array}{rl}Q(s,a)& =\mathbb{E}[G_t|s_t=s,a_t=a]\\ & =[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots |s_t=s,a_t=a]\\ & =\mathbb{E}[r_{t+1}|s_t=s,a_t=a]+\gamma \mathbb{E}[r_{t+2}+\gamma r_{t+3}+{\gamma }^2{r}_{t+4}+\cdots |s_t=s,a_t=a]\\ & =R(s,a)+\gamma \mathbb{E}[G_{t+1}|s_t=s,a_t=a]\\ & =R(s,a)+\gamma \mathbb{E}[V(s_{t+1})|s_t=s,a_t=a]\\ & =R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V(s^{\prime })\end{array}\text{\hspace{1em}(2.23)}$$$$\{\begin{array}{l}状态价值V(s)，某状态s的价值\\ 动作价值Q(s,a)，采取某动作a的价值\end{array}$$

贝尔曼期望方程

可以把状态价值函数V和动作价值函数Q进行拆分，拆分成即时奖励和后续状态的折扣价值，进而由式(2.20)得到贝尔曼期望方程
$$V_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|s_t=s]={\mathbb{E}}_{\pi }[r_{t+1}+\gamma V_{\pi }(s_{t+1})|s_t=s]$$对于Q函数亦然
$$Q_{\pi }(s,a)={\mathbb{E}}_{\pi }[r_{t+1}+\gamma Q_{\pi }(s_{t+1},a_{t+1})|s_t=s,a_t=a]$$根据式(2.22)
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)Q_{\pi }(s,a)\text{\hspace{1em}(2.22)}$$与式(2.23)
$$Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V_{\pi }(s^{\prime })\text{\hspace{1em}(2.23)}$$可以看出，式(2.22)为V和Q的关系（由Q推V），式(2.23)为Q和V的关系（由V推Q）。把式(2.23)代入(2.22)有
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V_{\pi }(s^{\prime })\right)\text{\hspace{1em}(2.28)}$$该式表明当前状态的V与未来状态的V之间的关系。
同样地，把(2.22)代入(2.23)有
$$Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)\sum _{a\in A}\pi (a^{\prime }|s^{\prime })Q_{\pi }(s^{\prime },a^{\prime })\text{\hspace{1em}(2.29)}$$该式表明当前时刻的Q与未来时刻的Q的关系。
(2.28)和(2.29)都是贝尔曼方程的形式。

(2.28)和(2.11)关系：
这里列出两式：
$$V(s)=R(s)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s)V(s^{\prime })\text{\hspace{1em}(2.11)}$$$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V_{\pi }(s^{\prime })\right)\text{\hspace{1em}(2.28)}$$两式是开括号的关系。如果我们使用(2.18)和(2.19)：
$$P_{\pi }(s^{\prime }|s)=\sum _{a\in A}\pi (a|s)p(s^{\prime }|s,a)\text{\hspace{1em}(2.18)}$$$$r_{\pi }(s)=\sum _{a\in A}\pi (a|s)R(s,a)\text{\hspace{1em}(2.19)}$$把(2.18)和(2.19)代入(2.11)有
$$\begin{array}{rl}V(s)& =R(s)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s)V(s^{\prime })\\ & =R(s)+\gamma \sum _{s^{\prime }\in S}\left[\sum _{a\in A}\pi (a|s)p(s^{\prime }|s,a)\right]V(s^{\prime })\\ & =\sum _{a\in A}\pi (a|s)R(s,a)+\gamma \sum _{s^{\prime }\in S}\left[\sum _{a\in A}\pi (a|s)p(s^{\prime }|s,a)\right]V(s^{\prime })\\ & =\sum _{a\in A}\pi (a|s)\left[R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V_{\pi }(s^{\prime })\right]\end{array}$$即为式(2.28)。

式(2.28)的理解：
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)\left(R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V_{\pi }(s^{\prime })\right)\text{\hspace{1em}(2.28)}$$式右边$\gamma \sum pV$表示：$s^{\prime }$为从$s$出发，能够到达的那些状态。这些$s^{\prime }$对应的状态价值函数$V(s^{\prime })$，乘以从$s$采取动作$a$到达$s^{\prime }$的概率$p$，再对所有$s^{\prime }$求和，得到$\sum pV$。折扣$\gamma$后，加上$s$本身离开自己的奖励$R$，整理再乘以采取该动作$a$的概率$\pi$，再把所有可能的$a$加和，就能得到$V$了。
$$\{\begin{array}{l}\pi (a|s)-从s出发，采取a的概率\\ p(s^{\prime }|s,a)-s状态下，从a出发，发展为s^{\prime }的概率\end{array}$$

备份图

备份图中，每一个实心圆圈代表一个状态-动作对，每一个空心圆圈代表一个状态。

在上图中：

• 奖励$r$只出现在实心圆到空心圈的过程中（$\bullet \to \circ$），因为必须先采取了动作$a$（即$\bullet$）才能有奖励$r$！

在式样书(2.28)中有2层加和：1）第一层对叶子节点$s^{\prime }$进行加和，往上备份一层，这样就能把未来的价值$s^{\prime }$备份到黑色节点。2）第二层是对动作进行加和，得到黑色节点（$a$）的价值后，再往上备份一层，得到根节点的价值，即当前状态$s$的价值。

在上图中，(b)为第一层，对应为式(2.22)，即从Q计算出V；( c )为第二层，对应式(2.23)，即从V计算出Q。二式合并即得式(2.28)。