策略迭代(Policy Iteration)

1. 策略迭代算法：

初始化 $\hat{V}(s)=0$ .

策略评估：(一般而言，下式中 $\pi(s,a)$ 为固定策略由于策略更新)
$V^{(k+1)}(s) \leftarrow \sum_{a \in A} \pi(s, a) \sum_{s^\prime \in S}\Pr(s^\prime | s, a)(r(s,a) + V^{k}(s^\prime)) \quad \forall s \in S$

策略更新：
$\pi(s) \leftarrow \arg \max_{a} (R(s) + \gamma \sum_{s^\prime \in S} \Pr(s^\prime|s, a) V^\pi(s)) \quad \forall s \in S$

如果 $\pi(s)$ 与上次迭代相比没有变化，则停止；否则，转回2。

2. 策略改进分析

(Lemma 1)策略更新可以使得 $V(s)$ 单调递增，最终收敛于 $V^*(s)$ 。

假设第k次迭代前的策略为 $\pi^k$ , 迭代后的策略为 $\pi^{k+1}$ . 而 $\pi^{k+1}$ 为 $Q^\pi(s)$ 下的贪婪策略。所以需要证明， $V^{k+1}(s) \geq V^k(s) \quad \forall s \in S.$

下面证明更加通用的定理：

(Lemma 2)对任意的 $\pi$ 和 $\pi'$ ，并且对于任意的 $s \in S$ ,

$V^{\pi'}(s) - V^\pi (s) = \frac{1}{1-\gamma} \mathbb{E}_{s' \sim \eta^{\pi'}_{s'}}[A^\pi(s', \pi')] \geq 0.$
这里 $\eta^{\pi'}_{s'}$ 是折扣的state occupancy，由 $\pi'$ 从起始状态 $s$ 引入。

Proof:

考虑一个策略序列 $\{\pi_i\}$ , 其中 $\pi_0=\pi, \pi_{\infty}=\pi'。$ 对于任意中间的 $0 \leq i \leq \infty, \pi_i$ 是一个随时间变化的策略，前 $i$ 个时间步采用策略 $\pi'$ 而后面的时间步采用策略 $\pi$ 。
根据差分求和，有，
$V^{\pi'}(s) - V^\pi (s) = \sum_{i=0}^{\infty}[V^{\pi_{i+1}}(s) - V^{\pi_i}(s)]$

策略集π.png

可见 $\pi_{i+1}$ 和 $\pi_i$ 仅在 $s=s_{i+1}$ 上的动作选择有差异，所以两者的值函数差异就体现在 $\pi_{i+1}(s=s_{i+1}) = \arg\max_{a} Q^\pi(s=s_{i+1}, a)$
所以
$\begin{align*} V^{\pi'}(s) - V^\pi (s) &= \sum_{i=0}^{\infty} \gamma^i \sum_{s' \in S} \mathbb{P}[s_i=s'|s_1=s, \pi'](Q^\pi(s', \pi'(s'))-Q^\pi(s', \pi(s))) \\ &= \sum_{i=0}^{\infty} \gamma^i \sum_{s' \in S} \mathbb{P}[s_i=s'|s_1=s, \pi']A^\pi(s', \pi') \\ &= \frac{1}{1-\gamma} \eta^{\pi'}_s(s') A^\pi(s', \pi') \\ &= \frac{1}{1-\gamma} \mathbb{E}_{s' \sim \eta^{\pi'}_{s'}}[A^\pi(s', \pi')] \\ &\geq 0 . \end{align*}$
综上，策略提升得证。