看完策略迭代和价值迭代的定义后，我还是有点迷糊：为什么得到的策略一定会收敛呢？两种方法的本质区别是什么呢？

于是搜罗了一些更“数学”的解释，来阐明这个问题。

Bellman 算子

定义状态空间：\(S={\{s_1, s_2, ..., s_n \}}\)；动作空间：\(A={\{a_1, a_2, ..., a_n \}}\)

贝尔曼期望方程： \[ V(s)=E_{a\sim\pi(a|s)}[r(s,a)+\gamma E_{s'\sim p(s'|s,a)}[V(s')]] \]

贝尔曼最优方程： \[ V(s)=\max_a(r(s,a)+\gamma E_{s'\sim p(s'|s,a)}[V(s')]) \]

根据以上方程，定义贝尔曼期望算子\(B_\pi\)和贝尔曼最优算子\(B_*\)，分别代表对当前价值函数集\(V\)利用贝尔曼方程更新的操作： \[ B_\pi V(s)=E_{a\sim\pi(a|s)}[r(s,a)+\gamma E_{s'\sim p(s'|s,a)}[V(s')]], for all s\in S \]

\[ B_*V(s)=\max_a(r(s,a)+\gamma E_{s'\sim p(s'|s,a)}[V(s')]), for all s\in S \]

其中，\(V=\{V(s_1),V(s_2),...,V(s_n)\}\), \(|V|=|S|\)。

强化学习的过程是求解 Markov 决策过程，贝尔曼方程提供一种通过动态规划求解的方式。

只有证明了贝尔曼算子的收敛性，才能说明贝尔曼方程有解。

如何证明 Bellman 算子收敛？

不断对值函数集\(V\)采用 Bellman 算子操作，得到一个序列：\(\{V, BV, B^2V, ..., B^nV\}\)

需要证明以上序列会收敛到一个不动点，即：\(BV=V\)。转为证明：Bellman 算子是一个完备度量空间内的一个压缩映射，则其产生的序列是柯西序列；根据巴拿赫不动点定理，该序列有且仅有唯一的不动点。

相关数学概念

不动点

求解\(x\)，使得：\(f(x)=x\)。

假设对任意的值\(x_0\)应用\(f()\)无限次，得到\(x_*\)，可以表示为：\(x_*=\lim\limits_{x\to \infin}f^n(x_0)\)，可以证明：\(x_*=f(x_*)\).

即：如果一个函数在某个点收敛，那么在该点的函数值收敛。

柯西序列

假设在度量空间\((X, d)\)中存在一个元素序列\(\{ x_1, x_2,...,x_N\}\)，如果对于任意的正整数\(\epsilon\)，存在一个整数\(n\)，使得满足： \[ d(x_a,x_b)<\epsilon; a,b>n \] 则该序列称为柯西序列。直观地说，对于任意微小的距离，序列都在某一项后收敛到该距离之内（类似级数的收敛）。

完备度量空间

对于度量空间\((X, d)\)，集合\(X\)中每个可能的柯西序列的收敛极限，依旧在集合\(X\)中，当前度量空间称为完备度量空间。

压缩映射

如果存在一个常数\(\gamma\in[0,1)\)，使得度量空间上\((X,d)\)的映射\(f\)，对于度量空间中的任意两个元素\(x_1,x_2\)均满足： \[ d(f(x_1), f(x_2))\leq \gamma d(x_1, x_2) \] 称该映射\(f\)为度量空间\((X,d)\)上的\(\gamma\)-压缩映射。

直观地说，对于序列中的元素应用压缩映射\(f(·)\)后，距离会缩短。

巴拿赫不动点定理

在一个完备度量空间\((X,d)\)中，对集合\(X\)中的任意元素\(x\)，不断地应用压缩映射\(f(·)\)，最后得到唯一的最优值\(x_*\)。（证明省略）

收敛性证明

回到贝尔曼算子\(B\)，转而证明\(B\)是某个完备度量空间\((X,d)\)上的压缩映射（由巴拿赫不动点定理，可以得到最终会收敛到唯一的一个值函数集）。

构造度量空间\((X,d)\)，其中： \[ X:V(s)\in\mathbb{R} \]

\[ X:V\in\mathbb{R}^{|\mathbb{S}|} \]

值\(V(s)\)属于实数集；值函数集\(V\)属于\(|\mathbb{S}|\)维的实数集。

度量\(d\)使用\(L-\infin\)范数： \[ ||V||_{\infin}=\max_{i\in{|0,|V||}}|V_i| \] 两个价值函数集\(V_1,V_2\)之间的距离等于两者之间的最大元素差。

对于具备有限奖励的有限MDP，价值函数将始终保留在度量空间中；因此值函数不可能超越实数集，度量空间永远是完备的。

转而证明：Bellman 算子\(B\)是完备度量空间\((\mathbb{R}^{|\mathbb{S}|},L_\infin)\)上的一个压缩映射。

Bellman 期望算子的收敛性证明

\[ \begin{align*} |B_\pi V_1(s)-B_\pi V_2(s)| &= \gamma |E_{a\sim\pi(a|s),s'\sim p(s'|s,a)}[V_1(s')-V_2(s')]|\\ &\leq \gamma E_{a\sim\pi(a|s),s'\sim p(s'|s,a)}[|V_1(s')-V_2(s')|]\\ &\leq \gamma E_{a\sim\pi(a|s),s'\sim p(s'|s,a)}[\max_s|V_1(s)-V_2(s)|]\\ &= \gamma ||V_1-V_2||_\infin \end{align*} \]

即对于任意状态\(s\)，均满足：\(|B_\pi V_1(s)-B_\pi V_2(s)|\leq\gamma||V_1-V_2||_\infin\)

因此，\(|B_\pi V_1-B_\pi V_2|_\infin=\max_{s}|B_\pi V_1(s)-B_\pi V_2(s)|\leq\gamma||V_1-V_2||_\infin\)

由巴拿赫不动点定理，存在\(V_\pi\in\mathbb{R}^{|\mathbb{S}|}\)，使得：\(\lim\limits_{n\to\infin}B_n^\pi V=V_\pi\).即不断地对任意的状态集合\(V\)进行 Bellman 期望算子操作，会收敛到状态集合\(V_\pi\).

Bellman 最优算子的收敛性证明

\[ \begin{align*} |B_*V_1(s)-B_*V_2(s)| &= |\gamma\max_a E_{s'\sim p(s'|s,a)}[V_1(s')-V_2(s')]| \\ &\leq \gamma\max_a |E_{s'\sim p(s'|s,a)}[V_1(s')-V_2(s')]| \\ &\leq \gamma\max_a \sum_{s'}p(s'|s,a)|V_1(s')-V_2(s')| \\ &=\gamma \sum_{s'}p(s'|s,a_*(s))|V_1(s')-V_2(s')| \\ &\leq \gamma \sum_{s'}p(s'|s,a_*(s))\max_s|[V_1(s)-V_2(s')]| \\ &=\gamma ||V_1-V_2||_{\infin} \end{align*} \]

即对于任意状态\(s\)，均满足：\(|B^* V_1(s)-B^* V_2(s)|\leq\gamma||V_1-V_2||_\infin\)

因此，\(|B^* V_1-B^* V_2|_\infin=\max_{s}|B^* V_1(s)-B^* V_2(s)|\leq\gamma||V_1-V_2||_\infin\)

由巴拿赫不动点定理，存在\(V^*\in\mathbb{R}^{|\mathbb{S}|}\)，使得：\(\lim\limits_{n\to\infin}B_*^n V=V_*\).即不断地对任意的状态集合\(V\)进行 Bellman 期望算子操作，会收敛到状态集合\(V_*\).

两种算子的解释

Bellman 期望算子\(B_\pi\)是一个线性操作（求期望），具有不动点\(V_\pi\)，即：\(B_\pi V_\pi=V_\pi\).

Bellman 优化算子\(B_*\)是一个非线性操作（求\(max\)），具有不动点\(V_*\)，即：\(B_* V_*=V_*\).

两个算子均具备单调性质：

定义：对于任意的值函数集合\(V_1, V_2\)，\(V_1\leq V_2\) 意味着：\(V_1(s)\leq V_2(s)\)，对于所有的状态\(s\)。

单调性质可以描述为： \[ V_1\leq V_2 \rightarrow B_\pi V_1\leq B_\pi V_2 \\ V_1\leq V_2 \rightarrow B_* V_1\leq B_* V_2 \]

两种算子的联系：

都可以将一个值函数集合\(V\)，转换为另一个值函数集合\(V'\)。

然而，\(B_\pi\)是针对\(\pi\)而言的；对任意值函数集合\(V\)，做多次操作后可以得到唯一不动点\(V_\pi\)，即策略\(\pi\)对应的值函数集合。

而\(B_*\)与策略无关；对任意值函数集合\(V\)，做多次操作后可以得到唯一不动点\(V_*\)，\(V_*=\max_{\pi}V_\pi\)。

即：\(V_*\)是\(V_\pi\)最大的策略\(\pi\)对应的值函数集合。

假设一个贪心策略\(G_V(s)\)（是基于当前的值函数集合\(V\)构建的确定性策略），输入一个状态\(s\)，输出能够最大化预期奖励\(Q(s,a)\)的动作\(a\)。即： \[ G_V(s)=argmax_a(r(s,a)+\gamma E_{s'\sim p(s'|s,a)}[V(s')]) \] \(B_*\)对于当前值函数集\(V\)的操作可以写成： \[ \begin{align*} B_*V(s)&=\max_a(r(s,a)+\gamma E_{s'\sim p(s'|s,a)}[V(s')]) \\ &=r(s,G_V(s))+\gamma E_{s'\sim p(s'|s,G_V(s))}[V(s')] \\ &=E_{a\sim G_V(s)}[r(s,a)+\gamma E_{s'\sim p(s'|s,a)}[V(s')]] \\ &=B_{G_V}V(s) \end{align*} \]

对于任意状态\(s\in S\)，如果遵循策略\(G_V(s)\)选出的动作\(a\)，利用对应的贝尔曼期望算子\(B_{G_V}\)对当前值函数集\(V\)进行一次更新；相当于使用贝尔曼最优算子\(B_*\)对当前值函数集\(V\)进行一次操作，即： \[ B_*V=B_{G_V}V \] 对于任意的值函数集均成立，实际上是使用策略\(G_V\)代替\(B_*\)中的\(max\)操作。

注意：\(B_*V=B_{G_V}V\)只在贝尔曼算子的单次操作成立：

\[ B_*^2V=B_*(B_*V)=B_*V_{new} \\ B_{G_V}^2V=B_{G_V}(B_{G_V}V)=B_{G_V}V_{new} \\ B_*^2V=B_*V_{new}=B_{G_{new}}V_{new}\neq B_{G_V}^2V \]

策略迭代

策略迭代分为两步：策略评估和策略提升。

策略评估

策略迭代的具体操作是：不断对当前值函数集\(V\)利用当前策略\(\pi\)的贝尔曼期望算子\(B_\pi\)操作直至收敛，即： \[ \lim\limits_{n\to\infin}B_\pi^nV=V_{\pi} \]

在实际操作中，一般设置一个阈值\(\delta\)，当\(|V_{k+1}-V_k|\)小于这个阈值时停止迭代。

由价值函数\(V\)的定义： \[ \begin{align*} V_{\pi}(s_t) &=E_\pi[\sum_{t'=t}^T\gamma^{t'-t}[r(s_t,a_t)|s_t]] \\ &=E_{a\sim\pi(a|s)}[r(s_t,a_t)+\gamma E_{s'\sim p(s'|s,a)}[V_\pi(s_{t+1})]] \end{align*} \] 引出两种估计\(V\)的方法：

  1. 利用采样的轨迹\(\tau\)（MonteCarlo估计）做估计：对\(V_\pi\)的无偏估计（上式的中间项），但是由于轨迹数目太多（指数级），难以全部采样。该估计方法对应策略评估的整个过程，对当前函数集\(V\)进行无穷次贝尔曼期望算子操作，理论上得到准确的\(V_\pi\)；
  2. 利用TD做估计：通过transition(\(s_t, a_t, r_t, s_{t+1}\))估计（估计上式中的最后一项）。实际使用的是\(V(s_{t+1})\)，来自当前的值函数集，并没有经过无限次的贝尔曼期望算子操作，因此相比\(V_\pi(s_{t+1})\)有偏差。该估计方法对应策略评估的一次操作，得到的值函数集合\(B_\pi V\)不太准确，但相比之前的\(V\)更接近\(V_\pi\)。

策略提升

在第\(k\)次策略迭代中，得到当前的策略\(\pi_k\)，策略评估后得到对应的值函数集\(V_{\pi_k}\).

策略提升的过程是令\(\pi_{k+1}\)满足： \[ \pi_{k+1}=G_{V_{\pi_{k}}}(s) \] 需要证明：\(\pi_{k+1}\geq \pi_k\).

采用最优策略有： \[ B_*V=B_{G_V}V=B_{\pi_{k+1}}V \]

对当前值函数集\(V_{\pi_k}\)进行贝尔曼最优算子操作\(B_{\pi_{k+1}}\)有（由算子定义知\(B_*V\geq B_\pi V\)）： \[ B_{\pi_{k+1}}V_{\pi_k}=B_{G_{V_{\pi_k}}}V_{\pi_k}=B_*V_{\pi_k}\geq B_{\pi_k}V_{\pi_k}=V_{\pi_k} \] 说明该操作单调递增。

有： \[ V_{\pi_{k+1}}=\lim\limits_{n\to\infin}(B_{\pi_{k+1}}^nV_{\pi_k})\geq V_{\pi_k} \] 策略提升设置为：\(\pi_{k+1}=G_{V_{\pi_k}}\)，相当于对当前策略的值函数集\(V_{\pi_k}\)进行无穷次贝尔曼最优算子操作\(B_{\pi_{k+1}}\)，每一次算子操作使得当前值函数\(V_{\pi_k}\)递增，因此新策略\(\pi_{k+1}\)变好了。

当策略\(\pi_{k+1}=\pi_k\)时，\(B_*V_{\pi_k}=V_{\pi_k}\)。由于\(B_*\)有且只有一个不动点\(V_*\)，如果对此时的策略\(\pi_{k+1}\)进行策略评估，得到的值函数集是唯一的\(V_*\).

策略迭代

策略迭代的每一次迭代，都会单调地提高\(V\)，或者收敛于最优的\(V_*\).

当前已经证明：在策略提升阶段，采用\(\pi_{k+1}=G_{V_{\pi_{k}}}\)会收敛到最优值函数集\(V_*\)；

还剩下最后一个问题，当策略迭代收敛时，虽然策略\(\pi_{k+1}=G_{V_*}\)对应的是最优值函数集\(V_*\)，策略提升时\(G_{V_*}\)依然能被作为最优策略\(\pi_*\)选出吗？

回到最优策略的定义，需要证明：策略\(\pi_{k+1}=G_{V_*}\)对应的价值函数\(V_{\pi_{k+1}}=V_*\).

有：\(B_{G_{V_*}}V_*=B_*V_*=V_*\)（\(B_{G_V}V=B_*V\)对于任意值函数\(V\)均成立）

另外，\(B_{G_{V_*}}\)作为贝尔曼期望算子，有着唯一的不动点\(V_{G_{V_*}}\)，因此： \[ V_{G_{V_*}}=V_* \] 结合： \[ V_{\pi_{k+1}}=V_* \]

因此， \[ G_{V_*}=\pi_{k+1}=\pi_* \]

直观地说，如果从最优值函数集\(V_*\)中构造一个贪心策略\(G_{V_*}\)作为新策略\(\pi_{k+1}\)，沿着这个策略实际达到的是最优值函数集\(V_*\).

也即：\(G_{V_*}\)是一个最优的确定性策略\(\pi_*\).

价值迭代

上一节已经证明：得到最优价值函数集\(V_*\)后，其对应的贪心策略\(G_{V_*}\)是一个最优的确定性策略；因此可以抛开策略\(\pi\)直接计算\(V_*\).

价值迭代隐去显式策略\(\pi\)，只维护价值函数集\(V\)，利用贝尔曼最优算子\(B_*\)求解。（隐式的策略\(\pi\)是贪心策略） \[ V_*=\lim\limits_{n\to\infin}B_*^nV \]

\(B_*\)的非线性算子\(max\)会带来两个问题：

  1. 每一次都需要找到\(argmax_a\)才能利用\(B_*\)更新\(V_*\)：需要在环境中尝试所有动作，并已知环境转移模型\(p(s'|s,a)\)。解决方案是维护并更新动作价值函数\(Q(s,a)\)，引出了Q-learning, SARSA, DQN等一系列的Value-based的方法。

  2. \(max\)导致价值迭代无法直接应用在连续动作上（因为此时可以执行的动作有无限个），解决方案是利用一个神经网络\(\pi_\theta\)学习该\(max\)操作符，引出了以DDPG为首的一系列用于连续控制的强化学习算法。