1. Policy Evaluation收敛性证明
1.1 压缩映射
定义 ： 对于一个度量空间$\langle M, d\rangle$，和一个函数映射$f : M \mapsto M$, 如果存在实数$k \in[0,1)$, 使得对于$M$中的任意两个点$x,y$，满足$d(f(x), f(y)) \leq k d(x, y)$,那么就称$f$是该度量空间中的一个压缩映射，其中满足条件的最小的$k$值称为Lipschitz常数。
1.2 压缩映射定理
对于完备的度量空间$\langle M, d\rangle$，如果$f : M \mapsto M$是它的一个压缩映射，那么
- 在该度量空间中，存在唯一的点$x_{*}$满足$f\left(x_{*}\right)=x_{*}$。
- 并且，对于任意的$x \in M$, 定义序列$f^{2}(x)=f(f(x)), f^{3}(x)=f\left(f^{2}(x)\right) |, \cdots,f^{n}(x)=f\left(f^{n-1}(x)\right)$，该序列会收敛于$x_{*}$，即$\lim_{n \rightarrow \infty} f^{n}(x)=x_{*}$
结论：完备度量空间上的压缩映射具有唯一的不动点。从度量空间任何一点出发，只要满足压缩映射，压缩映射的序列必定会收敛到唯一的不动点。因此证明一个迭代序列是不是收敛，只要证明该序列所对应的映射是不是压缩映射。
1.3 贝尔曼期望方程及其向量形式
贝尔曼期望方程为：\(v_{\pi}(s)=\sum_{a \in A} \pi(a | s)\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{\pi}\left(s^{\prime}\right)\right) \tag1\)
可进一步拆解为 \(v_{\pi}(s)=\sum_{a \in A} \pi(a | s)R_{s}^{a}+\sum_{a \in A} \pi(a | s)\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{\pi}\left(s^{\prime}\right) \tag2\)
如图所示：
接下来将它写为向量矩阵形式。因为状态是有限的，设状态集合为
状态价值矩阵为 \(V_{\pi}=\left\{V_{\pi}\left(s_{0}\right), V_{\pi}\left(s_{1}\right), \cdots, V_{\pi}\left(s_{n}\right)\right\}^{T}\)
计算状态价值函数所用的概率矩阵为:
收益矩阵为
由公式（2）前半部分可知，在当前状态、动作、新状态确定的情况下, $R_{\pi}$也是确定的，为常数矩阵 所以所有状态的价值函数用矩阵形式表示为：
\[V_{\pi}=R_{\pi}+\gamma P_{\pi} V_{\pi} \tag3\]1.4 收敛性证明
从当前值函数到下一个迭代值函数的映射可表示为：
\[T_{\pi}(v)=R_{\pi}+\gamma P_{\pi} v\]证明为压缩映射：
\[\begin{equation} \begin{aligned} &\rho\left(T_{\pi}(u), T_{\pi}(v)\right) =\left\|T_{\pi}(u)-T_{\pi}(v)\right\|\_{\infty} \\\ &=\left\|\left(R_{\pi}+\gamma P_{\pi} u\right)-\left(R_{\pi}+\gamma P_{\pi} v\right)\right\|\_{\infty} \\\ &=\left\|\gamma P_{\pi}(u-v)\right\|\_{\infty} \\\ & \leqslant\left\|\gamma P_{\pi}\right\| u-v\left\|\_{\infty}\right\|\_{\infty} \\\ & \leqslant \gamma\|u-v\|\_{\infty} \\\ \end{aligned} \end{equation}\]证明收敛： 根据压缩映射定理，
- 贝尔曼期望方程收敛于唯一的$v_{\pi}$
- 迭代式策略评价算法以的线性速率收敛于$v_{\pi}$
2. Policy Improvement收敛性和最优性证明
我们可以通过单调递增来证明。 假设我们有一个确定性的策略$a=\pi(s)$，那么我们可以通过贪心地选择动作来改进策略：@\pi^{\prime}(s)=\underset{a \in \mathcal{A}}{\operatorname{argmax}} q_{\pi}(s, a)@ 这样贪婪的策略可以保证提升一步后的动作值函数： \(q_{\pi}\left(s, \pi^{\prime}(s)\right)=\max_{a \in \mathcal{A}} q_{\pi}(s, a) \geq q_{\pi}(s, \pi(s))=v_{\pi}(s)\) 因此可以保证提升值函数：
\[\begin{aligned} v_{\pi}(s) & \leq q_{\pi}\left(s, \pi^{\prime}(s)\right)=\mathbb{E}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s,A_{t}=\pi'(s)\right] \\\ & = \mathbb{E}\_{\pi^{\prime}}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right] \\\ & \leq \mathbb{E}\_{\pi^{\prime}}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) | S_{t}=s\right] \\\ & \leq \mathbb{E}\_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} q_{\pi}\left(S_{t+2}, \pi^{\prime}\left(S_{t+2}\right)\right) | S_{t}=s\right] \\\ & \leq \mathbb{E}\_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\ldots | S_{t}=s\right]=v_{\pi^{\prime}}(s) \end{aligned}\]由于状态空间和动作空间是有限的，我们一定可以遍历所有<状态，动作>对。当遍历结束之后，即改进停止时，我们可以满足如下条件：
\[q_{\pi}\left(s, \pi^{\prime}(s)\right)=\max_{a \in \mathcal{A}} q_{\pi}(s, a)=q_{\pi}(s, \pi(s))=v_{\pi}(s)\]此时已经满足贝尔曼最优方程：
\[v_{\pi}(s)=\max_{a \in \mathcal{A}} q_{\pi}(s, a)\]此时，对于所有状态来说$V_{\pi}(s)=v_{*}(s)$，即$\pi$就是最优策略。
对应$\epsilon$-greedy Policy Improvement来说，假设$m$个动作都以非零的$\epsilon/m$的概率被探索，$1-\epsilon$的概率选择贪心动作，那么：
\[\pi(a | s)=\left\{\begin{array}{ll}{\epsilon / m+1-\epsilon} & {\text { if } a^{*}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q(s, a)} \\ {\epsilon / m} & {\text { otherwise }}\end{array}\right.\]对于任意一个$\epsilon$-greedy的策略$\pi$来说，可证基于$q_{\pi}$的$\epsilon$-greedy的策略$\pi’$，$v_{\pi^{\prime}}(s) \geq v_{\pi}(s)$：
\[\begin{aligned} q_{\pi}\left(s, \pi^{\prime}(s)\right) &=\sum_{a \in \mathcal{A}} \pi^{\prime}(a | s) q_{\pi}(s, a) \\\ &=\epsilon / m \sum q_{\pi}(s, a)+(1-\epsilon) \max_{a \in \mathcal{A}} q_{\pi}(s, a) \\\ & \geq \epsilon / m \sum_{a \in \mathcal{A}} q_{\pi}(s, a)+(1-\epsilon) \sum_{a \in \mathcal{A}} \frac{\pi(a | s)-\epsilon / m}{1-\epsilon} q_{\pi}(s, a) \\\ &=\sum_{a \in \mathcal{A}} \pi(a | s) q_{\pi}(s, a)=v_{\pi}(s) \end{aligned}\]因此，根据policy improvement theorem，$v_{\pi^{\prime}}(s) \geq v_{\pi}(s)$
支付宝打赏
微信打赏
您的打赏是对我最大的鼓励！
