迭代策略评估(Iterative Policy Evaluation)

我们对于策略的评估是通过当前策略 π\pi 的价值函数 VπV_{\pi} 来决定的。对于 VπV_{\pi} ,我们用反向迭代的方式来求:

  • 在第 k+1k + 1 次迭代中
  • 对于 sS\forall s \in \mathcal{S}
  • vk(s)v_k(s') 更新 vk+1(s)v_{k + 1}(s) ,其中 ss'ss 的上一状态

此方法最后会收敛至 VπV_{\pi} ,收敛性在后面会证明。

由贝尔曼方程可知:

vk+1(s)=aAπ(as)(Rsa+γsSPssavk(s))v_{k+1}(s) = \sum_{a\in \mathcal{A}}\pi (a|s) \left ( \mathcal{R}^a_s + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} v_{k}(s') \right )

其矩阵形式如下:

vk+1=Rπ+γPπvkv^{k + 1} = \mathcal{R}^{\pi} + \gamma \mathcal{P}^{\pi} v^k

策略迭代(Policy Iterative)

通过策略评估的方式,我们可以在每一步行动之后贪心的去更新策略。即:

  • 评估策略

vπ=E[Rt+1+γRt+2+St=s]v_{\pi} = \mathbb{E}[R_{t + 1} + \gamma R_{t + 2} + \cdots | S_t = s]

  • 贪心的改进策略

π=greedy(vπ)\pi' = \text{greedy}(v_{\pi})

可以证明的是,这个过程最后会收敛于 π\pi_*

策略改进(Policy Improvement)

我们考虑一个确定的策略,a=π(s)a = \pi(s)
依据上文,我们可以贪心地改进策略,即:

π(s)=arg maxaAqπ(s,a)\pi'(s) = \argmax _{a\in \mathcal{A}} q_{\pi} (s,a)

我们可以证明它确实改进了价值函数:

qπ(s,π(s))=maxaAqπ(s,a)qπ(s,π(s))=vπ(s)vπqπ(s,π(s))=Eπ[Rt+1+γvπ(St+1)St=s]Eπ[Rt+1+γqπ(St+1,π(St+1))St=s]Eπ[Rt+1+γRt+2+γ2qπ(St+2,π(St+2))St=s]Eπ[Rt+1+γRt+2+St=s]=vπ(s)q_\pi(s, \pi'(s)) = \max_{a\in \mathcal{A}}q_\pi(s, a) \geq q_\pi(s, \pi(s)) = v_\pi(s) \\ \begin{align*} v_\pi &\leq q_\pi(s, \pi'(s)) = \mathbb{E}_{\pi'}[R_{t + 1} + \gamma v_\pi(S_{t+ 1})|S_t = s] \\ &\leq \mathbb{E}_{\pi'}[R_{t + 1} + \gamma q_\pi(S_{t + 1}, \pi'(S_{t + 1}))|S_t = s] \\ &\leq \mathbb{E}_{\pi'}[R_{t + 1} + \gamma R_{t + 2} + \gamma^2q_\pi(S_{t + 2},\pi'(S_{t + 2}))|S_t = s] \\ &\leq \mathbb{E}_{\pi'}[R_{t + 1} + \gamma R_{t + 2} + \cdots |S_t = s] = v_{\pi'}(s) \\ \end{align*}

当Improvement停止后,

qπ(s,π(s))=maxaAqπ(s,a)=qπ(s,π(s))=vπ(s)q_\pi(s, \pi'(s)) = \max _{a\in \mathcal{A}}q_\pi(s, a) = q_\pi (s, \pi(s)) = v_\pi(s)

所以,

vπ(s)=maxaAqπ(s,a)(1)v_\pi(s) = \max_{a\in \mathcal{A}} q_\pi(s, a) \tag1

由于最优化原则告诉我们:

如果策略 π\pi 是最优策略,当且仅当对于 π\pi 中状态 ss 所能达到的任意状态 ss' 均有 vπ(s)=v(s)v_\pi(s') = v_*(s)

因此从 (1)(1) 中可知 sS   vπ(s)=v(s)\forall s\in \mathcal{S} \ \ \ v_\pi(s) = v_*(s) ,所以 π\pi 是最优策略。