该书由清华大学李升波教授撰写的，主要面向工业控制领域的研究者和工程师，曾获得2024年度Springer中国新发展奖（China New Development Awards）。全书按照原理剖析、主流算法、典型示例的架构，系统地介绍了用于动态系统决策与控制的强化学习方法。全书共分为11章，内容涵盖了强化学习的基本概念、蒙特卡洛法、时序差分法、动态规划法、函数近似法、策略梯度法、近似动态规划、状态约束的处理和深度强化学习等知识点。书籍及源代码下载网站：书籍及代码链接点这里。

另外，由于本部分篇幅较长，因此分成三篇博客发表。其余两篇博客的地址参考我的系列博客的地址汇总。

书籍链接：Reinforcement Learning for Sequential Decision and Optimal Control

本篇博客主要介绍Dynamic Programming（DP），即动态规划，一种Model-Based的Indirect RL方法。DP与动态环境中的随机最优控制问题有紧密的联系。DP通常通过求解Bellman方程（离散时间）或Hamilton-Jacobi-Bellman方程（连续时间）来得到最优策略。对于大部分工程任务来说，以上两个方程是最优解的充要条件。DP的优点在于它的强大的适应性。如线性/非线性系统、离散/连续系统、确定性/随机性系统、可微分/不可微分系统等。但是，DP在实际应用中面临着维度灾难和缺少泛化能力的问题。但是，DP仍然在理论分析最优解的存在以及收敛速度等方面有着重要的作用。

5.3 DP的值迭代（Value Iteration）算法

5.3.1 DP的值迭代（for Discounted Cost）

5.3.1.1 算法描述

DP的值迭代算法并不需要中间的策略，也不需要初始时指定一个可行的策略。值迭代算法首先计算出最优的值函数，然后直接从这个最优的值函数中获得最优策略。另外，值迭代算法的收敛性由Bellman operator的contraction性质保证。回顾第一类Bellman方程：
$$v^{\ast }(s)=\underset{a\in \mathcal{A}}{\max }\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(s^{\prime }|s,a)\left(r_{s{s}^{\prime }}^a+\gamma v^{\ast }(s^{\prime })\right),\forall s\in \mathcal{S}.$$ 那么，一种最简单的值迭代算法就是直接利用上述方程进行迭代（其实是从Picard Fixed-Point Iteration的角度得来的）：

注意，与PEV那里迭代时$V$的右上角有一个上标$\pi$不同，这里的$V$是不带上标的，因为值迭代不涉及任何的中间策略。当迭代次数达到无穷的时候，值函数的估计值$V_k(s)$就收敛于真实值函数$v^{\ast }(s)$。

5.3.1.2 DP的值迭代的收敛性证明

首先，定义Bellman operator：
$$\mathcal{B}(V)=\underset{a\in \mathcal{A}}{\max }\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(s^{\prime }|s,a)\left(r_{s{s}^{\prime }}^a+\gamma V(s^{\prime })\right),$$ 那么值迭代的更新公式可以写成：
$$V_{k+1}=\mathcal{B}(V_k).$$ 我们下面证明这个operator是一个contraction operator：
$$\begin{array}{rl}\left|B\left(V_{k+1}(s_{(i)})\right)-B\left(V_k(s_{(i)})\right)\right|& =\left|\underset{a}{\max }\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(r+\gamma V_{k+1}(s^{\prime }))-\underset{a}{\max }\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(r+\gamma V_k(s^{\prime }))\right|\\ & \le \underset{a}{\max }\left|\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(r+\gamma V_{k+1}(s^{\prime }))-\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}(r+\gamma V_k(s^{\prime }))\right|\\ & =\gamma \underset{a}{\max }\left|\sum _{s^{\prime }\in \mathcal{S}}P{V}_{k+1}(s^{\prime })-\sum _{s^{\prime }\in \mathcal{S}}P{V}_k(s^{\prime })\right|\\ & \le \gamma \underset{a}{\max }\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}\left|V_{k+1}(s^{\prime })-V_k(s^{\prime })\right|\\ & \le \gamma \underset{a}{\max }\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}\underset{s\in \mathcal{S}}{\max }|V_{k+1}(s)-V_k(s)|\\ & =\gamma \underset{a}{\max }\left\{1\times \underset{s\in \mathcal{S}}{\max }|V_{k+1}(s)-V_k(s)|\right\}\\ & =\gamma \underset{s\in \mathcal{S}}{\max }|V_{k+1}(s)-V_k(s)|\end{array}$$ 右边第一式到第二式和第三式到第四式比较显然，举个小例子即可。第五式到第六式是因为${\sum }_{s^{\prime }\in \mathcal{S}}\mathcal{P}$后面乘的是一个公因式，直接提取出来。而${\sum }_{s^{\prime }\in \mathcal{S}}\mathcal{P}$求和由概率的性质可知等于1。注意，从第五步开始的s表示的是状态空间里的一个状态，该状态可以使得$|V_{k+1}(s)-V_k(s)|$取到最大值。而对最开始等号左边的式子取无穷范数可得：
$$\begin{array}{rl}{\Vert \mathcal{B}(V_{k+1}(s))-\mathcal{B}(V_k(s))\Vert }_{\infty }& =\underset{s}{\max }\left|\mathcal{B}\right(V_{k+1}(s))-\mathcal{B}(V_k(s)\left)\right|\\ & \le \gamma \underset{s}{\max }|V_{k+1}(s)-V_k(s)|\\ & =\gamma \Vert V_{k+1}(s)-V_k(s){\Vert }_{\infty }.\end{array}$$ 注意，这里的s则表示的是状态空间里的所有状态，对应的$V_{k+1}(s)$、$V_k(s)$均表示的是一个向量。这样就证明了Bellman operator在无穷范数下的$\gamma$-contractive性质。因此，值迭代算法是收敛的，会收敛到唯一的一个fixed-point，即最优值函数$v^{\ast }(s)$。

5.3.2 DP的值迭代（for Average Cost）

这里首先需要引入一种新的return（或说cost）（不同于discounted return、average return）：Differential Return：
$$G_{\Delta }(s_t)=\sum _{i=0}^{\infty }(r_{t+i}-G_{\mathrm{avg}}(\pi )),$$ 其中，$G_{\mathrm{avg}}(\pi )$是在策略$\pi$下的average return。那么根据第二单元博客里讲过的从return到值函数的的逻辑，我们可以定义一种新的状态值函数；
v Δ π ( s ) = E π { G Δ ( s t ) ∣ s t = s } = E π { ∑ i = 0 ∞ ( r t + i − G a v g ( π ) ) } , v_\Delta^\pi(s)=\mathbb{E}_\pi\{G_\Delta(s_t)|s_t=s\}=\mathbb{E}_\pi\left\{\sum_{i=0}^\infty\left(r_{t+i}-G_{\mathrm{avg}}(\pi)\right)\right\}, vΔπ​(s)=Eπ​{GΔ​(st​)∣st​=s}=Eπ​{i=0∑∞​(rt+i​−Gavg​(π))}, 这种值函数被称为Differential State Value Function。那么，也就顺理成章的引出了在这种值函数下的Bellman方程：
$$\begin{array}{rl}{v}_{\Delta }^{\ast }(s)& =\underset{a\in \mathcal{A}}{\max }\sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a(r_{s{s}^{\prime }}^a-G_{\mathrm{avg}}^{\ast }(\pi )+v_{\Delta }^{\ast }(s^{\prime }))\\ v_{\Delta }^{\ast }(s)+G_{\mathrm{avg}}^{\ast }(\pi )& =\underset{a\in \mathcal{A}}{\max }\sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{\mathrm{s}{\mathrm{s}}^{\prime }}^a\left(r_{\mathrm{s}{\mathrm{s}}^{\prime }}^a+v_{\Delta }^{\ast }(s^{\prime })\right).\end{array}$$ 这个式子被称为Average Cost Optimality Equation（ACOE），即Bellman方程的differential return版本，也被称为Differential Bellman Equation。求解这个方程主要使用三种方法，分别是Finite-Horizon Value Iteration、Relative Value Iteration和Vanishing Discount Factor Approach。将在下面分别介绍。

对于Average Cost问题，还需要进行一些额外的操作来保证最优解存在：如采用stationary policy（只与当前状态有关，与之前地1历史状态无关）；引入一些regularity条件。

另外注意，关于DP Value Iteration for Average Cost这部分内容，仅作为介绍，并没有面面俱到。有一些内容并没有很详细，因此看起来有些地方前后可能并不是很连贯（比如differential value function在后面叙述中并没有出现很多次），这里只是作为一个引子，希望大家能够有所启发。

5.3.2.1 Finite-Horizon Value Iteration

这种方法的思路是，将原问题转化为一个有限步长的问题，而当步长很大时，就可取得较好的近似效果，不过由于计算量较大，在实际中只有迭代次数较少的时候才会使用此种方法。这种方法首先定义了一个有限步长的值函数：
$$V(s,N)=\sum _{t=0}^{N-1}{r}_t$$ 之后可以通过求解Bellman方程得到$V^{\ast }(s,N)$，那么average cost就可以通过下式来近似得到：
$$G({\pi }^{\ast })\approx \frac{V^{\ast }(s,N)}{N}.$$ 不过这个方法面临着一个困境，即当我们选取的horizon N很大时，计算量会变得很大，而当N很小时，近似效果又不是很好。因此，这种方法在实际中的应用较少。

5.3.2.2 Relative Value Iteration

这里的思路是使用引入一个额外的变量，最后求出这个变量的最优值后可以发现其与ACOE的解是一样的。

这个方法的核心思路是从所有的值函数中减去一个相同的常量。方法的具体步骤如下。首先，定义一个新的值函数：
$$h(s)=V(s,N)-V(\zeta ,N),N\to \infty ,$$ 其中$\zeta$是一个固定的状态。$h(s)$称为Difference Value Function。使用fixed-point iteration的方法，可以得到$h(s)$的更新公式：
$$\begin{array}{rl}& h_{k+1}(s)\\ & =\underset{a}{\max }\sum {\mathcal{P}}_{s{s}^{\prime }}^a\left(r_{s{s}^{\prime }}^a+V_k(s^{\prime },N)\right)-\underset{a}{\max }\sum {\mathcal{P}}_{\zeta {\zeta }^{\prime }}^a\left(r_{\zeta {\zeta }^{\prime }}^a+V_k({\zeta }^{\prime },N)\right)\\ & =\underset{a}{\max }\sum {\mathcal{P}}_{s{s}^{\prime }}^a\left(r_{s{s}^{\prime }}^a+h_k(s^{\prime })+V_k(\zeta ,N)\right)-\underset{a}{\max }\sum {\mathcal{P}}_{\zeta {\zeta }^{\prime }}^a\left(r_{\zeta {\zeta }^{\prime }}^a+h_k({\zeta }^{\prime })+V_k(\zeta ,N)\right)\\ & =\underset{a}{\max }\sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a\left(r_{s{s}^{\prime }}^a+h_k(s^{\prime })\right)-\underset{a}{\max }\sum {\mathcal{P}}_{\zeta {\zeta }^{\prime }}^a\left(r_{\zeta {\zeta }^{\prime }}^a+h_k({\zeta }^{\prime })\right).\end{array}$$ 当迭代达到终止（$h^{\ast }(s)={\lim }_{k\to \infty }{h}_k(s)$）时，可以得到如下关系：
$$\begin{gathered} h^{\ast }(s)=-{\rho }^{\ast }+\underset{a}{\max }\sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a\left(r_{s{s}^{\prime }}^a+h^{\ast }(s^{\prime })\right), \\ {\rho }^{\ast }\stackrel{\mathrm{def}}{=}\underset{a}{\max }\sum {\mathcal{P}}_{\zeta {\zeta }^{\prime }}^a\left(r_{\zeta {\zeta }^{\prime }}^a+h^{\ast }({\zeta }^{\prime })\right), \end{gathered}$$ 注意上式左右两侧的变量一样，都是$h^{\ast }(s)$，因此可以使用fixed-point iteration的方法来求解$h^{\ast }(s)$。最后，可以得到最优对$[{\rho }^{\ast },h^{\ast }(s)]$。之后，可证明$[{\rho }^{\ast },h^{\ast }(s)]$与ACOE中的量有如下关系：$$h^{\ast }(s)=v_{\Delta }^{\ast }(s){\rho }^{\ast }=G_{\mathrm{avg}}^{\ast }(\pi )$$

5.3.2.3 Vanishing Discount Factor Approach

这里的核心思路是把average cost问题使用discounted cost问题来近似。核心思想是使得$\gamma \to 1$，核心是下述的式子：
G a v g ( π ) = lim ⁡ N → ∞ lim ⁡ γ → 1 E { ∑ i = 0 N − 1 γ i r t + i } ∑ i = 0 N − 1 γ i = lim ⁡ γ → 1 lim ⁡ N → ∞ E { ∑ i = 0 N − 1 γ i r t + i } lim ⁡ N → ∞ ∑ i = 0 N − 1 γ i = lim ⁡ γ → 1 ( 1 − γ ) E { ∑ i = 0 ∞ γ i r t + i } = lim ⁡ γ → 1 ( 1 − γ ) v γ ( s ) . \begin{aligned} G_{\mathrm{avg}}(\pi)& =\lim_{N\to\infty}\lim_{\gamma\to1}\frac{\mathbb{E}\{\sum_{i=0}^{N-1}\gamma^ir_{t+i}\}}{\sum_{i=0}^{N-1}\gamma^i} \\ &=\lim_{\gamma\to1}\frac{\lim_{N\to\infty}\mathbb{E}\{\sum_{i=0}^{N-1}\gamma^ir_{t+i}\}}{\lim_{N\to\infty}\sum_{i=0}^{N-1}\gamma^i} \\ &=\lim_{\gamma\to1}(1-\gamma)\mathbb{E}\left\{\sum_{i=0}^{\infty}\gamma^{i}r_{t+i}\right\} \\ &=\lim_{\gamma\to1}(1-\gamma)v_{\gamma}(s). \end{aligned} Gavg​(π)​=N→∞lim​γ→1lim​∑i=0N−1​γiE{∑i=0N−1​γirt+i​}​=γ→1lim​limN→∞​∑i=0N−1​γilimN→∞​E{∑i=0N−1​γirt+i​}​=γ→1lim​(1−γ)E{i=0∑∞​γirt+i​}=γ→1lim​(1−γ)vγ​(s).​ 右边第二式到第三式使用了等比数列求和公式（注意$\gamma$是小于1的）。这样，average cost问题就可以转化为discounted cost问题。这种方法的优点如下：

• 可以处理ill-conditioned问题；
• 解决Discounted Cost问题的策略迭代和值迭代算法较为成熟，稳定性和收敛性较好。

5.4 关于DP问题的几点讨论

5.4.1 对于DP的策略迭代的扩展

在DP的策略迭代中，每一轮迭代中的PEV都要进行无穷轮迭代才能得到当前策略$\pi$下的值函数估计值。但是在实际编写算法的时候，不可能进行无穷次迭代的。因此，实际中只要两次迭代之间的值函数估计值的差值小于一个阈值时，就可以停止迭代：
$$\underset{s\in \mathcal{S}}{\max }|V_{j+1}^{\pi }(s)-V_j^{\pi }(s)|<\Delta .$$ 或者，也可以强行规定迭代次数，当迭代次数达到一定值时，就停止迭代，这也被称为Truncated DP。这里的DP在每轮大的迭代中，进行n轮PEV和1轮PIM，这样的迭代方法被称为n-step DP。当$n\to \infty$时，就是标准的DP的策略迭代算法。这种方法的通用框架如下：

注意，这里的每次PEV的更新公式：
$$V^{{\pi }_k}(s)\leftarrow \sum _{s^{\prime }}p(s^{\prime }|s,{\pi }_k(s)\left)\right(r+\gamma V^{{\pi }_k}(s^{\prime }))$$ 与我们在策略迭代哪里的公式稍有不同：
$$V_{j+1}^{\pi }(s)\leftarrow \sum _{a\in \mathcal{A}}\pi (a|s)\left\{\sum _{s^{\prime }\in \mathcal{S}}\mathcal{P}\left(r+\gamma V_j^{\pi }(s^{\prime })\right)\right\},\forall s\in \mathcal{S}$$ 这是因为我们这里采用的策略是确定性策略（greedy），因此自动就化简为这样了。

需要注意的是，上述DP被称为同步的（syncronous）的。大的迭代中每轮小的PEV迭代在进行之前都要先将此时的值函数取值储存在一个copy中，然后在该轮PEV扫过每个状态s的时候，右边的值函数的值用的都是copy中的。这样可以防止“串联更新”（学过数据结构的话会发现这里的设置copy的思路与目的与Bellman-Ford求最短路那里完全一样）。假设有m个动作和n个状态，该算法的时间复杂度为$O(m{n}^2)$（采用状态值函数）或$O(m^2{n}^2)$（采用动作值函数）。

5.4.2 用统一的视角来看Model-Based和Model-Free的RL方法

对于策略迭代的RL算法，我们可以把其中Model-Based和Model-Free的方法统一起来，放在Generalized Policy Iteration（GPI）的框架下。GPI的框架每轮更新策略的大迭代由PEV和PIM两部分构成。每次PEV是为了计算得到一个对于值函数更好的估计，而PIM则是为了在新的值函数的基础上得到一个更好的策略。

Model-Based和Model-Free的方法的区别在于PEV中如何获取环境的动力学（Environment Dynamics）的。Model-Based方法根据先验知识，直接使用环境模型来获得环境信息；而Model-Free方法则是通过与环境的交互（采样）来获得环境信息*。

两种方法的优缺点如下表所示：

优缺点	Model-Based RL	Model-Free RL
优点	1. 因为有了环境模型往往比Model-Free的算法更高效，因为环境模型是对环境的完整描述，而sample只是对于环境的局部的描述。	1. 不需要环境模型，因此更加通用； 2. 从采样器获得的数据往往比从环境模型得到的更准确。
缺点	1. 对环境建模很难，且获得的环境模型与实际的环境动力学之间难免有误差。	1. 效率较低，需要与环境进行很大量的交互才能达到比较满意的效果； 2. 样本通常只能获得局部的环境信息，很难通过采样覆盖到整个状态空间。

由上表我们也可以看出，想说出Model-Based和Model-Free哪个更好是不现实的，因为这两种方法各有优缺点，适用于不同的场景。如果一定要比较，应该指定需要处理的问题和超参数之后才能进行公平的比较。

5.4.3 使用Fixed-Point Iteration的角度来看策略迭代和值迭代

5.4.3.1 策略迭代和Fixed-Point Iteration技术

在策略迭代里面，使用fixed-point iteration的技术的地方是在PEV的过程中。总共有五种常见的PEV方法，分别是：Picard iteration，Krasnoselskij iteration，Mann iteration，Ishikawa iteration，Kirk iteration。下面汇总一下之前讲过的策略迭代算法使用的迭代分属于哪种iteration：

下面以两个例子来说明如何使用fixed-point iteration技术来解释策略迭代算法。首先，来看DP中的策略迭代算法。根据我们在使用Newton-Raphson法来解释DP的策略迭代那里的定义，这里用到的算子可以写成如下形式：
$$f(X)\stackrel{\mathrm{def}}{=}\gamma BX+b.$$ 我们之前已经证明了这个算子是收缩的（contractive），因此迭代最后必然会收敛到一个fixed-point。又因为之前已经证明了DP的策略迭代这里有且只有一个fixed-point，因此策略迭代算法一定会收敛到最优值函数$v^{\ast }(s)$。

下面我们来看看Model-Free算法如何使用fixed-point iteration技术进行分析。直接使用fixed-point iteration技术来分析Model-Free算法是比较困难的，因为采样具有随机性，很难在两个相邻的sample之间定义出一个contractive的operator。为了解决这个问题，需要引入期望形式的算子。下面我们就以SARSA为例来分析一下。SARSA的PEV更新公式为：
$$Q_{j+1}(s,a)=Q_j(s,a)+{\alpha }_j(r+\gamma Q_j(s^{\prime },a^{\prime })-Q_j(s,a)),$$ 其中，${\alpha }_j$是第j轮迭代的学习率。将上式的同类项合并，得到：
$$Q_{j+1}(s,a)=(1-{\alpha }_j)Q_j(s,a)+{\alpha }_j(r+\gamma Q_j(s^{\prime },a^{\prime })).$$ 两边取期望，得到：
E π { Q j + 1 ( s , a ) } = ( 1 − α j ) E π { Q j ( s , a ) } + α j E π { r + γ Q j ( s ′ , a ′ ) } . \mathbb{E}_\pi\{Q_{j+1}(s,a)\}=(1-\alpha_j)\mathbb{E}_\pi\{Q_j(s,a)\}+\alpha_j\mathbb{E}_\pi\{r+\gamma Q_j(s',a')\}. Eπ​{Qj+1​(s,a)}=(1−αj​)Eπ​{Qj​(s,a)}+αj​Eπ​{r+γQj​(s′,a′)}. 注意这里的取期望操作是针对于环境模型的，即 E π { # } \mathbb{E}_\pi\{\#\} Eπ​{#}等价于 ∑ s ′ ∈ S { P s s ′ a ⋅ # } \sum_{s^{\prime}\in\mathcal{S}}\{\mathcal{P}_{ss^{\prime}}^a\cdot\#\} ∑s′∈S​{Pss′a​⋅#}。那么，接下来就可以得到一个基于期望的算子：
f ( Q ( s , a ) ) = d e f E π { r + γ Q ( s ′ , a ′ ) } = ∑ s ′ ∈ S P s s ′ a ( r + γ Q ( s ′ , a ′ ) ) . f\big(Q(s,a)\big)\stackrel{\mathrm{def}}{=}\mathbb{E}_\pi\{r+\gamma Q(s',a')\}=\sum_{s'\in\mathcal{S}}\mathcal{P}_{ss'}^a\big(r+\gamma Q(s',a')\big). f(Q(s,a))=defEπ​{r+γQ(s′,a′)}=s′∈S∑​Pss′a​(r+γQ(s′,a′)). 可以证明这个算子是contractive的，因此就可以得到一个类似于Mann iteration的fixed-point iteration算法：
$$Q_{j+1}(s,a)=(1-{\alpha }_j)Q_j(s,a)+{\alpha }_{j}f(Q_j(s,a)).$$ 这就是SARSA的PEV迭代公式。

其它的Model-Free算法也可以使用类似的方法来进行分析，找到对应于fixed-point iteration的解释。

5.4.3.2 值迭代和Fixed-Point Iteration技术

同样的，先放上一张表，汇总一下值迭代算法使用的迭代方法：

先来看看Model-Based的DP，正如我们之前讲过的，其值迭代算法天然就是一个fixed-point iteration算法。算子为：
$$f(X)\stackrel{\mathrm{def}}{=}\mathcal{B}(X).$$ 其中，$\mathcal{B}$是Bellman operator。其收敛性也已经证过了。还有一个问题，就是既然已经知道了值迭代可以用fixed-point iteration来解释，那么反过来能不能使用不同的fixed-point iteration技术设计新的值迭代算法呢？答案是肯定的。不过，一般对于DP的值迭代，我们使用上述基于Picard iteration的最简单的算法就可以了。

再来看看Model-Free的RL算法。这里以Q-Learning为例（为什么以Q-Learning为例参见第四单元博客。这是因为Q-Learning不显含PEV与PIM过程，而是合在一个公式中。而这个公式也可看成一种值迭代的算法）。因为Model-Free的RL算法主要通过采样来与环境进行交互，而在采样的时候自然会引入随机性。不能直接使用fixed-point iteration技术来分析。不过，我们可以通过引入期望的方式来进行分析。首先来看看学习率随迭代变化的Q-Learning算法：
$$Q_{k+1}(s,a)=Q_k(s,a)+{\alpha }_k\left(r+\gamma \underset{a^{\prime }}{\max }{Q}_k(s^{\prime },a^{\prime })-Q_k(s,a)\right),$$ 整理得：
$$Q_{k+1}(s,a)=(1-{\alpha }_k)Q_k(s,a)+{\alpha }_k{\mathbb{E}}_{\pi }\{r+\gamma \underset{a^{\prime }}{\max }{Q}_k(s^{\prime },a^{\prime })\}.$$ 那么，就可以得到一个算子：
$$f(Q(s,a))={\mathbb{E}}_{\pi }\{r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })\}.$$ 接下来，如果令
$$X_k=Q_k(s,a)$$ 那么，上式就可以写成：
$$X_{k+1}=(1-{\alpha }_k)X_k+{\alpha }_{k}f(X_k).$$ 这个式子恰好符合Mann iteration的形式。因此，Q-Learning的值迭代算法可以看成是一个Mann iteration的fixed-point iteration算法。那么，显然根据之前所述，我们也可以根据不同的fixed-point iteration技术来为Q-Learning设计新的值迭代算法。比如，可以使用Picard iteration来设计一个新的Q-Learning算法:
$$Q_{k+1}(s,a)=r+\gamma \underset{a^{\prime }}{\max }{Q}_k(s^{\prime },a^{\prime }).$$ 也可以根据Ishikawa iteration来设计一个新的Q-Learning算法：
$$\begin{gathered} Q^{\mathrm{temp}}(s,a)=(1-{\alpha }_k)Q_k(s,a)+{\alpha }_k\{r+\gamma \underset{a^{\prime }}{\max }{Q}_k(s^{\prime },a^{\prime })\}, \\ {Q}_{k+1}(s,a)=(1-{\beta }_k)Q_k(s,a)+{\beta }_k\{r+\gamma \underset{a^{\prime }}{\max }{Q}^{\mathrm{temp}}(s^{\prime },a^{\prime })\}. \end{gathered}$$ 这里是一个2-step的Q-Learning迭代公式，这里引入了中间变量$Q^{\mathrm{temp}}$。这样的迭代公式可以加速收敛，因为相当于在一次迭代中进行了两次值迭代。但是，为了保证收敛，对于学习率${\alpha }_k$和${\beta }_k$要求更严格：
$$\begin{array}{c}0\le {\alpha }_k,{\beta }_k<1,\\ \underset{k\to \infty }{\lim }{\beta }_k=0,\underset{k\to \infty }{\lim }{\alpha }_k=0,\\ \sum _{k=1}^{\infty }{\beta }_k=\infty ,\sum _{k=1}^{\infty }{\alpha }_k=\infty .\end{array}$$ 另外，Ishikawa iteration对于较弱的contractive operator可能具有更好的收敛性。因此，在遇到一些ill-conditioned的问题时，可以尝试使用Ishikawa iteration来加速收敛。

5.4.4 Exact DP with Backward Recursion

让我们来考虑一个离散时间的，具有固定终止时间的T的问题。那么显然，此时的值函数不仅与状态s有关，还与时间t有关。可以这样理解，因为值函数表示的是从当前状态开始到终止获得的回报的期望。那么，所有过程到达T时刻均会终止，因此自然从相同状态但是不同时刻开始获得的回报不会一样。因此，我们可以定义一个新的值函数：
$$V^{\ast }(s,t)=\underset{\pi }{\max }\{\sum _{i=0}^{T-t}{r}_{t+i}|s_t=s\}.$$ 计算这种值函数的值通常有两种顺序，一种是从t=T开始，逆向计算；另一种是从t=0开始，正向计算。逆向计算的方法显然更符合逻辑，因此我们下面主要介绍逆向计算的方法。那么，可获得如下与实践有关的Bellman方程：
$$V^{\ast }(s,t)=\underset{\pi }{\max }\{\sum _{i=0}^{T-t}{r}_{t+i}|s_t=s\}.$$ 为了获得时刻t的值函数，我们需要递推的先获得时刻t+1的值函数。因此，这种方法也被称为backward recursion。因为终止时刻的值函数可以直接得到，因此我们就可以迭代的从后向前计算。可以发现，这与之前DP的迭代是很像的，都是从一个初始值开始不断迭代。也即是说，当终止时刻T取为$\infty$时，这种方法就是DP的值迭代算法。

5.5 对什么是一个“更好的”策略？以及从更好的策略的角度看PIM过程

在第三单元博客的策略改进定理那里，我们定义过什么是一个更好的策略，这是使用逐个元素的方式来定义的：
$$\pi \le \bar{\pi }⟺v^{\pi }(s)\le v^{\bar{\pi }}(s),\forall s\in \mathcal{S}$$ 该式子还有一种等价形式，即：
$$\pi \le \bar{\pi }⟺v^{\pi }(s)\le \sum _{a\in \mathcal{A}}\bar{\pi }(a|s)q^{\pi }(s,a),\forall s\in \mathcal{S}.$$ 但是，这种定义方式只能针对元素离散的情况，无法扩展到连续的情况。

5.5.1 什么是一个“更好的”策略？用期望的形式来定义的第一种方式

为了解决上述问题，我们可以使用期望的形式来定义什么是一个更好的策略。比如，上述第一式可以写为：
E s ∼ d ( s ) { v π ( s ) } ≤ E s ∼ d ( s ) { v π ‾ ( s ) } , \mathbb{E}_{s\sim d(s)}\{v^\pi(s)\}\leq\mathbb{E}_{s\sim d(s)}\{v^{\overline{\pi}}(s)\}, Es∼d(s)​{vπ(s)}≤Es∼d(s)​{vπ(s)}, 其中，$d(s)$是状态分布。这种定义方式可以扩展到连续的情况（求期望的时候离散情况就是按概率加权求和，连续情况就是积分）。这种期望形式相当于从原来逐个元素比较转化为了对于加权求和之后的整体比较。

引入了这种定义方式之后，就可以根据其设计PIM的策略更新方式。根据上述期望形式的定义，PIM可以被表述为一个优化问题：
π k + 1 = arg ⁡ max ⁡ π { δ − ρ ( π , π k ) } , s.t. E s ∼ d ( s ) { v π ( s ) } = δ + E s ∼ d ( s ) { v π k ( s ) } , δ ≥ 0 , \pi_{k+1}=\arg\max_{\pi}\{\delta-\rho(\pi,\pi_{k})\},\\\text{s.t.}\\\mathbb{E}_{s\sim d(s)}\{v^{\pi}(s)\}=\delta+\mathbb{E}_{s\sim d(s)}\{v^{\pi_{k}}(s)\},\\\delta\geq0, πk+1​=argπmax​{δ−ρ(π,πk​)},s.t.Es∼d(s)​{vπ(s)}=δ+Es∼d(s)​{vπk​(s)},δ≥0, 这里的$\rho (\pi ,{\pi }_k)$是一个度量两个策略之间的差异的函数。而$\delta$是一个常数，被称为value margin。有了下面的s.t.的限制条件，就可以保证每次的新策略一定比上一次的策略更好，因为：
E s ∼ d ( s ) { v π ( s ) } = δ + E s ∼ d ( s ) { v π k ( s ) } ≥ E s ∼ d ( s ) { v π k ( s ) } . \mathbb{E}_{s\sim d(s)}\{v^{\pi}(s)\}=\delta+\mathbb{E}_{s\sim d(s)}\{v^{\pi_{k}}(s)\}\geq\mathbb{E}_{s\sim d(s)}\{v^{\pi_{k}}(s)\}. Es∼d(s)​{vπ(s)}=δ+Es∼d(s)​{vπk​(s)}≥Es∼d(s)​{vπk​(s)}. 而优化时为什么要使得$\delta -\rho (\pi ,{\pi }_k)$最大呢？这是因为，$\rho (\pi ,{\pi }_k)\ge 0$，而两个策略越接近该函数的值就越接近于0又因为$\delta$是一个常数，所以最大化$\delta -\rho (\pi ,{\pi }_k)$就相当于最小化$\rho (\pi ,{\pi }_k)$，也就是说，我们优化的目标是使得这相邻两轮迭代的分布尽可能的接近。当$\rho (\pi ,{\pi }_k)=0$时，说明两个策略完全一样，此时就可以停止迭代了。根据这个规则进行PIM可以保证至少收敛到一个局部最优解。证明的要点有两点。首先是保证 E s ∼ d ( s ) { v π k ( s ) } \mathbb{E}_{s\sim d(s)}\{v^{\pi_{k}}(s)\} Es∼d(s)​{vπk​(s)}单调递增；其次是证明迭代到无穷轮时，此时的值函数$v^{\ast }{\pi }^{\infty }(s)$等于最优值函数$v^{\ast }(s)$。

首先，我们注意到 E s ∼ d ( s ) { v π k ( s ) } \mathbb{E}_{s\sim d(s)}\{v^{\pi_{k}}(s)\} Es∼d(s)​{vπk​(s)}其实就是之前在第5.1.2.2节定义过的折扣代价函数$J_{\gamma }(\pi )$。那么，为了回答上述证明药店的第一点，先看下面的定理：
$$\text{定理4}：J({\pi }_0)\le J({\pi }_1)\le \cdots \le J({\pi }_k)\le J({\pi }_{k+1})\le \cdots \le J({\pi }^{\ast }),$$ 其中，${\pi }^{\ast }$是最优策略。这个定理的证明十分简单，从每次迭代时求解的优化问题的的限制条件即可看出。即：
J ( π k + 1 ) = E s ∼ d ( s ) { v π k + 1 ( s ) } = δ + E s ∼ d ( s ) { v π k ( s ) } ≥ E s ∼ d ( s ) { v π k ( s ) } = J ( π k ) . J(\pi_{k+1})=\mathbb{E}_{s\sim d(s)}\{v^{\pi_{k+1}}(s)\}=\delta+\mathbb{E}_{s\sim d(s)}\{v^{\pi_{k}}(s)\}\geq\mathbb{E}_{s\sim d(s)}\{v^{\pi_{k}}(s)\}=J(\pi_k). J(πk+1​)=Es∼d(s)​{vπk+1​(s)}=δ+Es∼d(s)​{vπk​(s)}≥Es∼d(s)​{vπk​(s)}=J(πk​).

下面我们来证明第二点，即迭代到无穷轮时，此时的值函数$v^{\ast }{\pi }^{\infty }(s)$等于最优值函数$v^{\ast }(s)$。我们有下述定理：
$$\begin{gathered} \text{定理5：假设}J(\cdot )\text{是严格凸的。那么当PIM在第}k\to \infty \text{轮停止时},\text{我们有} \\ {\pi }_{\infty }(s)={\pi }^{\ast }(s),\forall s\in \mathcal{S}. \end{gathered}$$ 因为第k+1轮时，$J({\pi }_k)$可以看成是一个常数，因此我们可以把我们刚才提出的由PIM所转化为的优化问题的$\delta$使用$J({\pi }_k)$来替代。那么，我们的优化问题就变成了：
π k + 1 = arg ⁡ max ⁡ π { J ( π ) − ρ ( π , π k ) } , s.t. J ( π ) − J ( π k ) ≥ 0. \pi_{k+1}=\arg\max_{\pi}\{J(\pi)-\rho(\pi,\pi_{k})\},\\\text{s.t.}\\J(\pi)-J(\pi_{k})\geq0. πk+1​=argπmax​{J(π)−ρ(π,πk​)},s.t.J(π)−J(πk​)≥0. 下面来定义一个辅助的函数：
$$g(\pi ,{\pi }_k)\stackrel{\mathrm{def}}{=}J(\pi )-\rho (\pi ,{\pi }_k).$$ 因为$\rho (\pi ,{\pi }_k)\ge 0$，所以$g(\pi ,{\pi }_k)\le J(\pi )$。引入的这个函数可以作为J的一个下界。具体证明过程省略。

上图展示了迭代过程中J函数和g函数的变化。可以看出，在迭代过程中g函数是逐渐逼近J函数的。当迭代到无穷轮时，g函数就会收敛到J函数。

另外，使用这种期望形式的定义方式，即可保证收敛。RL不需要每次去改进状态空间里的每个元素，但是在最后的策略中，每个元素仍然均达到了其最优值。

5.5.2 什么是一个“更好的”策略？用期望的形式来定义的第二种方式

仿照逐元素定义的第二种方式，可得其对应的期望形式：
E s ∼ d ( s ) { v π ( s ) } ≤ E s ∼ d ( s ) { ∑ a ∈ A π ˉ ( a ∣ s ) q π ( s , a ) } . \mathbb{E}_{s\sim d(s)}\{v^\pi(s)\}\leq\mathbb{E}_{s\sim d(s)}\left\{\sum_{a\in\mathcal{A}}\bar{\pi}(a|s)q^\pi(s,a)\right\}. Es∼d(s)​{vπ(s)}≤Es∼d(s)​{a∈A∑​πˉ(a∣s)qπ(s,a)}.

我们首先需要证明，对上式右端的最大化与greedy search得到的策略是一样的。
$$\begin{gathered} \text{定理6：对上式的最大化相当于greedy search，即} \\ {\bar{\pi }}^{\ast }\iff {\tilde{\pi }}^{\ast }, \end{gathered}$$ 其中，${\bar{\pi }}^{\ast }$是上式右端的最大化策略，${\tilde{\pi }}^{\ast }$是greedy search得到的策略。即：
$$\begin{gathered} {\bar{\pi }}^{\ast }=\arg \underset{\bar{\pi }}{\max }{\mathbb{E}}_{s\sim d(s)}\{\sum _{a\in \mathcal{A}}\bar{\pi }(a|s)q^{\pi }(s,a)\}, \\ {\tilde{\pi }}^{\ast }=\arg \underset{\tilde{\pi }}{\max }\{\sum _{a\in \mathcal{A}}\tilde{\pi }(a|s)q^{\pi }(s,a)\},\forall s\in \mathcal{S}. \end{gathered}$$ 注意，虽然两个策略在上面均显示为一个式子，但是对于${\bar{\pi }}^{\ast }$来说，确实就只有一个式子（所有的可能值根据分布加权平均了）；而对于${\tilde{\pi }}^{\ast }$来说，对于每个s都有一个这样的式子，所以总共有$|\mathcal{S}|$个式子。因为${\bar{\pi }}^{\ast }$是通过最大化${\mathbb{E}}_{s\sim d(s)}\{{\sum }_{a\in \mathcal{A}}\bar{\pi }(a|s)q^{\pi }(s,a)\}$得到的，那么自然有：
$${\mathbb{E}}_{s\sim d(s)}\{\sum _{a\in \mathcal{A}}{\bar{\pi }}^{\ast }(a|s)q^{\pi }(s,a)\}\ge {\mathbb{E}}_{s\sim d(s)}\{\sum _{a\in \mathcal{A}}{\tilde{\pi }}^{\ast }(a|s)q^{\pi }(s,a)\}.$$ 这是因为上述不等式左右两边形式相同，而${\bar{\pi }}^{\ast }$是通过最大化该形式的式子所得到最优策略，所以其自然优于包含${\tilde{\pi }}^{\ast }$在内的所有其他策略。现在假设${\bar{\pi }}^{\ast }$最大化了上述期望形式的目标式子，但是对于某个具体的${\sum }_{a\in \mathcal{A}}\tilde{\pi }(a|s)q^{\pi }(s,a)$并没有最大化。与此同时，${\tilde{\pi }}^{\ast }$是通过greedy search得到的，因为对于每个状态s，都最大化了${\sum }_{a\in \mathcal{A}}\tilde{\pi }(a|s)q^{\pi }(s,a)$，所以套上对于状态s分布的期望之后，下式仍成立：
$${\mathbb{E}}_{s\sim d(s)}\left\{\sum {\tilde{\pi }}^{\ast }(a|s)q^{\pi }(s,a)\right\}\ge {\mathbb{E}}_{s\sim d(s)}\left\{\sum {\bar{\pi }}^{\ast }(a|s)q^{\pi }(s,a)\right\},$$ 有以上两式得到，只能有：
$${\mathbb{E}}_{s\sim d(s)}\left\{\sum {\tilde{\pi }}^{\ast }(a|s)q^{\pi }(s,a)\right\}={\mathbb{E}}_{s\sim d(s)}\left\{\sum {\bar{\pi }}^{\ast }(a|s)q^{\pi }(s,a)\right\}.$$ 也即是说，${\bar{\pi }}^{\ast }$和${\tilde{\pi }}^{\ast }$是一样的。证毕。

在上述证明的基础上，我们可以得到下面的PIM更新方式：
π k + 1 = arg ⁡ max ⁡ π { δ − ρ ( π , π k ) } , s.t. E s ∼ d ( s ) { ∑ π ( a ∣ s ) q π k ( s , a ) } = δ + E s ∼ d ( s ) { ∑ π k ( a ∣ s ) q π k ( s , a ) } , = δ + E s ∼ d ( s ) { v π k ( s ) } δ ≥ 0. \begin{aligned} \pi_{k+1}=\arg&\max_{\pi}\{\delta-\rho(\pi,\pi_{k})\}, \\ &\text{s.t.} \\ \mathbb{E}_{s\sim d(s)}\left\{\sum\pi(a|s)q^{\pi_k}(s,a)\right\}& =\delta+\mathbb{E}_{s\sim d(s)}\big\{\sum\pi_{k}(a|s)q^{\pi_{k}}(s,a)\big\}, \\ &=\delta+\mathbb{E}_{s\sim d(s)}\big\{v^{\pi_{k}}(s)\big\}\\ &\delta\geq0. \end{aligned} πk+1​=argEs∼d(s)​{∑π(a∣s)qπk​(s,a)}​πmax​{δ−ρ(π,πk​)},s.t.=δ+Es∼d(s)​{∑πk​(a∣s)qπk​(s,a)},=δ+Es∼d(s)​{vπk​(s)}δ≥0.​ 下面给出是否按照上述方式得到的策略${\pi }_{k+1}$按照逐元素的“更好的策略”的定义也是更好的。假设存在一个状态$s_{(}i)$，使得单个元素的第二类判断方式不成立，即：
$$v^{{\pi }_k}(s_{(i)})>\sum {\pi }_{k+1}(a|s_{(i)})q^{{\pi }_k}(s_{(i)},a).$$
那么，构造一个替代的策略：
$$\tilde{\pi }(a|s)=\{\begin{array}{c}{\pi }_{k+1}(a|s),s\in S\setminus \left\{s_{(i)}\right\}\\ {\pi }_k(a|s),s\in \left\{s_{(i)}\right\}\end{array},$$ 那么，显然对于这个新构建的策略来说，逐元素的第二类判断方式是成立的：
$$v^{{\pi }_k}(s)\le \sum \tilde{\pi }(a|s)q^{{\pi }_k}(s,a),\forall s\in S$$ 对于$\tilde{\pi }$和${\pi }_{k+1}$，它们的$\delta$分别为：
δ ~ = E s ∼ d ( s ) { ∑ π ~ ( a ∣ s ) q π k ( s , a ) } − E s ∼ d ( s ) { v π k ( s ) } . δ k + 1 = E s ∼ d ( s ) { ∑ π k + 1 ( a ∣ s ) q π k ( s , a ) } − E s ∼ d ( s ) { v π k ( s ) } . \begin{aligned} \tilde{\delta}& =\mathbb{E}_{s\sim d(s)}\left\{\sum\tilde{\pi}(a|s)q^{\pi_k}(s,a)\right\}-\mathbb{E}_{s\sim d(s)}\{v^{\pi_k}(s)\}. \\ \delta_{k+1}& =\mathbb{E}_{s\sim d(s)}\left\{\sum\pi_{k+1}(a|s)q^{\pi_k}(s,a)\right\}-\mathbb{E}_{s\sim d(s)}\{v^{\pi_k}(s)\}. \end{aligned} δ~δk+1​​=Es∼d(s)​{∑π~(a∣s)qπk​(s,a)}−Es∼d(s)​{vπk​(s)}.=Es∼d(s)​{∑πk+1​(a∣s)qπk​(s,a)}−Es∼d(s)​{vπk​(s)}.​ 接下来，定义$\Delta =\tilde{\delta }-{\delta }_{k+1}$，那么有：
$$\begin{array}{rl}& ={\mathbb{E}}_{s\sim d(s)}\left\{\sum \tilde{\pi }(a|s)q^{{\pi }_k}(s,a)\right\}-{\mathbb{E}}_{s\sim d(s)}\left\{\sum {\pi }_{k+1}(a|s)q^{{\pi }_k}(s,a)\right\}\\ & ={\mathbb{E}}_{s\sim d(s)}\left\{v^{{\pi }_k}\left(s_{(i)}\right)-\sum {\pi }_{k+1}(a|s_{(i)}\left)q^{{\pi }_k}\right(s_{(i)},a)\right\}\\ & \text{>0.}\end{array}$$ 其中，第二式到第三式是根据我们之前的假设。又因为$\tilde{\pi }$与${\pi }_{k+1}$除了在$s_{(i)}$处不同之外，其它地方都是一样的，而$\tilde{\pi }$在$s_{(i)}$处等于上一个策略${\pi }_k$的取值。因此，$\tilde{\pi }$更接近于${\pi }_k$，所以相应的策略之间的距离度量越小：
$$\rho (\tilde{\pi },{\pi }_k)\le \rho ({\pi }_{k+1},{\pi }_k).$$ 结合上述两式，有：
$$\left(\tilde{\delta }-\rho (\tilde{\pi },{\pi }_k)\right)>\left({\delta }_{k+1}-\rho ({\pi }_{k+1},{\pi }_k)\right),$$ 这与${\pi }_{k+1}$是通过最大化$\delta -\rho (\pi ,{\pi }_k)$得到的策略矛盾。因此，假设不成立，即对于所有的状态$s_{(i)}$，逐元素的第二类判断方式都是成立的。证毕。

5.6 Policy Entropy？以及从Policy Entropy的角度看PIM过程

5.6.1 什么是Policy Entropy

Policy Entropy定义如下：
$$\mathcal{H}(\pi )=\sum _{a\in \mathcal{A}}-\pi (a|s)\log \pi (a|s),$$或写成：
$$\mathcal{H}(\pi )=\sum _{a\in \mathcal{A}}-p(a)\log p(a),$$，其中$p(a)=\pi (a|s)$。显然，一个策略的随机性越大，其Policy Entropy越大。因此，可以通过最大化一个基于Policy Entropy的目标函数来获得一个随机策略。使用这种最大化基于Policy Entropy的目标函数的方法的一个好处是，获得的相应的动作分布只取决于优化时所加的限制。一些常见的case如下：
Type Probability density Constraints Acton space Uniform (discretete) p ( a ) = 1 / ∣ c A ∣ − a ∈ { a 1 , a 2 , . . . , a ∣ c A ∣ } Uniform (cont) p ( a ) = 1 / ( a h i g h − a l o w ) − a ∈ [ a l o w , a h i g h ] Bernoulli p ( a ) = μ a ( 1 − μ ) 1 − a E ( a ) = μ a ∈ { 0 , 1 } Normal p ( a ) = 1 2 π σ 2 exp ⁡ ( − ( a − μ ) 2 2 σ 2 ) E ( a ) = μ a ∈ ( − ∞ , + ∞ ) \begin{array}{|c|c|c|c|}\hline\text{Type}&\text{Probability density}&\text{Constraints}&\text{Acton space}\\\hline\text{Uniform}&&&\\\text{(discretete)}&p(a)=1/|cA|&-&a\in\{a_1,a_2,...,a_{|cA|}\}\\\hline\text{Uniform}&&&\\\text{(cont)}&p(a)=1/(a_{\mathrm{high}}-a_{\mathrm{low}})&-&a\in[a_{\mathrm{low}},a_{\mathrm{high}}]\\\hline\text{Bernoulli}&p(a)=\mu^a(1-\mu)^{1-a}&\mathbb{E}(a)=\mu&a\in\{0,1\}\\\hline\text{Normal}&p(a)=\frac1{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(a-\mu)^2}{2\sigma^2}\right)&\mathbb{E}(a)=\mu&a\in(-\infty,+\infty)\\\hline\end{array} TypeUniform(discretete)Uniform(cont)BernoulliNormal​Probability densityp(a)=1/∣cA∣p(a)=1/(ahigh​−alow​)p(a)=μa(1−μ)1−ap(a)=2πσ2 ​1​exp(−2σ2(a−μ)2​)​Constraints−−E(a)=μE(a)=μ​Acton spacea∈{a1​,a2​,...,a∣cA∣​}a∈[alow​,ahigh​]a∈{0,1}a∈(−∞,+∞)​​

下面我们来看看如何通过最大化基于Policy Entropy的目标函数来获得$ϵ$-greedy策略。简而言之，可以通过如下的优化问题：
π k + 1 = arg ⁡ max ⁡ π { π ( a ∗ ∣ s ) + κ H ( π ) } , s.t. a ∗ = max ⁡ a q π k ( s , a ) , ∀ s ∈ S , π ( a ∗ ∣ s ) + ∑ a ∈ A ∖ a ∗ π ( a ∣ s ) = 1 , \begin{gathered} \pi_{k+1}=\arg\operatorname*{max}_{\pi}\{\pi(a^*|s)+\kappa\mathcal{H}(\pi)\}, \\ \text{s.t.} \\ a^{*}=\operatorname*{max}_{a}q^{\pi_{k}}(s,a) ,\forall s\in\mathcal{S}, \\ \pi(a^*|s)+\sum_{a\in\mathcal{A}\setminus a^{*}}\pi(a|s)=1, \end{gathered} πk+1​=argπmax​{π(a∗∣s)+κH(π)},s.t.a∗=amax​qπk​(s,a),∀s∈S,π(a∗∣s)+a∈A∖a∗∑​π(a∣s)=1,​ 注意，这里的s是固定的某个状态（也就是说，对于每个状态空间中的s，都需要做一遍上述优化）。如果我们把系数$\kappa$取为：
$$\kappa =\frac{1}{\ln (1-|\mathcal{A}|(ϵ-1)/ϵ)}.$$ 此时得到的策略就是$ϵ$-greedy策略。可以使用拉格朗日乘子的方法来求解上述优化问题，最后可解得：
$$\pi (a^{\ast }|s)=1-ϵ+\frac{ϵ}{|\mathcal{A}|},\pi (a|s){|}_{a\ne a^{\ast }}=\frac{ϵ}{|\mathcal{A}|}.$$ 这与我们在第三单元博客里讲过的$ϵ$-greedy策略的公式是一样的。

由此可见，通过引入Policy Entropy，可以获得更多不同的策略。

附录：Fixed-Point Iteration技术

附录1：Fixed-Point Iteration技术

先来看看固定点的定义：

Fixed-Point: 当一个迭代函数的输入和输出一样时，该输入（或输出）值被称为固定点。设$\mathbb{X}$为Banach空间，$f:\mathbb{X}\to \mathbb{X}$为Banach空间上的一个映射，如果存在$X\ast \in \mathbb{X}$，使得$f(X^{\ast })=X^{\ast }$，那么$X^{\ast }$就是$f$的一个固定点。

Contraction Mapping: 如果一个映射$f$满足：$$\Vert f(X)-f(Y)\Vert \le \gamma \cdot \Vert X-Y\Vert ,\forall X,Y\in \mathbb{X}$$ 这里的$\gamma \in (0,1)$是一个李普希茨系数。

Fixed-Point理论关注的两个重点是存在性和收敛性。该理论主要的作用在于求解方程，可以用来求解复杂的非线性方程。

$$\begin{gathered} \text{定理7：}\text{设}\mathbb{X}\text{是一个完备的Banach空间，}f:\mathbb{X}\to \mathbb{X}\text{是一个收缩映射，} \\ \text{那么f 有一个唯一的固定点}{X}^{\ast }\text{，且其柯西序列收敛到该固定点}： \\ {X}_n\to X^{\ast },\mathrm{as}n\to \infty , \end{gathered}$$ 这里的 { X n } \{X_n\} {Xn​}来自于Picard iteration，其初始值任选。该定理就是著名的Banach Fixed-Point定理，也被称为Contraction Mapping定理。

上面定理中的迭代点序列来自于Picard iteration。除了Picard iteration，还有其他四种常见的Fixed-Point迭代方法：

• Picard iteration: $$X_{n+1}=f(X_n)$$ 如果f是一个收缩映射，那么该迭代方法收敛到f的固定点。
• Krasnoselskii iteration: $$X_{n+1}=\lambda f(X_n)+(1-\lambda )X_n$$ 这里的$\lambda \in (0,1)$。如果引入一个算子：$f_{\lambda }=(1-\lambda )I+\lambda f$，那么这种迭代方式就是Picard iteration。这种迭代也于bootstrap方法类似，通过加权已知的过去值和新的信息来获得。
• Mann iteration: $$X_{n+1}=(1-{\alpha }_n)X_n+{\alpha }_{n}f(X_n)$$ 这里的${\alpha }_n\in (0,1)$$。这种迭代方式是Krasnoselskiiiteration的一个特例，当$\alpha_n=\lambda$时，就是Krasnoselskii iteration。
• Ishikawa iteration: $$X_{n+1}=(1-{\alpha }_n)X_n+{\alpha }_{n}F(X_n)$$ 这里的${\alpha }_n\in (0,1)$，${\beta }_n\in (0,1)$。这种迭代方式的收敛要求：
  $$\begin{gathered} 0\le {\alpha }_n,{\beta }_n<1,\underset{n\to \infty }{\lim }{\beta }_n=0,\underset{n\to \infty }{\lim }{\alpha }_n=0 \\ \sum _{n=1}^{\infty }{\alpha }_n=\infty ,\sum _{n=1}^{\infty }{\beta }_n=\infty . \end{gathered}$$ 当${\alpha }_n=0$时，Ishikawa iteration就是Mann iteration。
• Kirk iteration: $$X_{n+1}=c_0{X}_n+c_{1}f(X_n)+c_{2}f\left(f(X_n)\right)+\cdots +c_k{f}^k(X_n),$$ 这里，k是一个常数，$k\ge 1$, $c_i\ge 0$，${\sum }_{i=0}^k{c}_i=1$。当k=1时，Kirk iteration就是Krasnoselskii iteration。

上述四种迭代方式都有其对应的柯西序列。其收敛速度由每次迭代得到的值于最优值（固定点）的距离决定。在Picard iteration中，收敛速度至少是由李普希茨系数$\gamma$和第一次的误差$||X_1-X_0||$决定的:
$$\Vert X_n-X^{\ast }\Vert \le \frac{{\gamma }^n}{1-\gamma }\Vert X_1-X_0\Vert ,$$ 有趣的是，对于well-defined的任务，其它四种迭代方式与Picard iteration的收敛速度是同阶的。

附录2：使用Fixed-Point Iteration技术解线性方程组

Fixed-Point Iteration技术在解大规模线性方程组时也有广泛的应用。对于有m个方程的方程组，使用Fixed-Point Iteration技术求解每轮迭代的操作数为$m^2$量级，而使用直接求解的方法的操作数为$m^3$量级。而且，达到收敛所需的迭代轮数通常独立于方程组的规模。

假设现在我们有一个线性方程组$Ax=b$，其中A是一个满秩的方阵。那么其迭代序列（柯西序列）为：
$$\begin{gathered} X_{n+1}=P{X}_n+(I-P)A^{-1}b, \\ P=I-A, \end{gathered}$$ P被称为迭代矩阵。这个算法只有当$\rho (P)<1$时才能收敛。这里的$\rho (P)$是P的谱半径。因为$\rho (P)$是P的特征值的绝对值里面的最大值，所以显然$\rho (P)$越小，迭代收敛的速度越快。为了获得更好的收敛性，可以使用一些技巧，比如把A分成两部分，即A=M-N。这样处理之后就可以使用一系列的迭代方法，比如Jacobi iteration、Gauss-Seidel iteration、relaxation method等。