Agent的目标
由于动态规划法需要知道环境模型的具体信息，因此在这里我们需要对模型做出定义。Agent在发出动作前已经知道了如下信息：
模型的状态转移概率 p ( S t + 1 = s ′ ∣ S t = s , A t = a ) p(S_{t+1}=s'|S_t=s,A_t=a) p ( S t + 1 = s ′ ∣ S t = s , A t = a )
模型的奖励函数 r ( s , a , s ′ ) = E [ R t + 1 ∣ A t = a , S t = s , S t + 1 = s ′ ] r(s,a,s')=E[R_{t+1}|A_t=a,S_t=s,S_{t+1}=s'] r ( s , a , s ′ ) = E [ R t + 1 ∣ A t = a , S t = s , S t + 1 = s ′ ]
根据上面的信息求解出最优策略 π ( A t = a ∣ S t ) \pi(A_t=a|S_t) π ( A t = a ∣ S t )
策略迭代法（Policy Iteration）
策略迭代法过程可以拆解成两个部分：策略评估（Policy Evaluation）和策略改进（Policy Improvement）
策略评估
策略评估是指从策略到价值函数的推导。也就是说，对于某个策略 π \pi π v π ( s ) v_\pi(s) v π ( s )
v π ( s ) = E π [ R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ ∣ S t = s ] v_\pi(s)=E_\pi[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots|S_t=s] v π ( s ) = E π [ R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ ∣ S t = s ]
= E π [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s ] = E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s] = E π [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s ]
= ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v π ( s ′ ) ] = \sum\limits_a\pi(a|s)\sum\limits_{s'}p(s'|s,a)[r(s,a,s')+\gamma v_\pi(s')] = a ∑ π ( a ∣ s ) s ′ ∑ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v π ( s ′ )]
由于我们假设已经知道了环境模型的全部信息，所以在上面的公式中唯一未知的就是价值函数。求解这个公式有两种方法：一种是求公式的闭式解，也就是把它当成一个方程组去求解。如果模型中有 ∣ S ∣ |S| ∣ S ∣ ∣ S ∣ |S| ∣ S ∣ γ < 1 \gamma<1 γ < 1 0 0 0
输入：需要评估的策略 π \pi π
初始化 v ( s ) = 0 , ∀ s ∈ S + v(s)=0,\forall s\in S^+ v ( s ) = 0 , ∀ s ∈ S +
For each s ∈ S \text{For each } s\in S For each s ∈ S
temp ← v ( s ) \text{temp} \gets v(s) temp ← v ( s )
v ( s ) ← ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ ) ] v(s)\gets \sum_a\pi(a|s)\sum_{s'}p(s'|s,a)[r(s,a,s')+\gamma v(s')] v ( s ) ← ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ )]
Δ ← max ( Δ , ∣ temp − v ( s ) ) \Delta \gets \max(\Delta,|\text{temp}-v(s)) Δ ← max ( Δ , ∣ temp − v ( s ))
until Δ < θ \Delta<\theta Δ < θ
输出： v ≃ v π v\simeq v_\pi v ≃ v π
策略改进
策略评估完成了从策略到价值函数的转化，这就为下一步——寻找更好的策略打好了基础。寻找更好的策略需要调整策略内容，那么问题来了：当策略被调整后，价值函数会如何变化？对于某个状态 s s s a a a s s s v π ( s ) v_\pi(s) v π ( s ) a a a a ′ a' a ′
q π ( s , a ) = E π [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s , A t = a ] q_\pi(s,a)=E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s,A_t=a] q π ( s , a ) = E π [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s , A t = a ]
= ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v π ( s ′ ) ] =\sum\limits_{s'}p(s'|s,a)[r(s,a,s')+\gamma v_\pi(s')] = s ′ ∑ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v π ( s ′ )]
如果 q π ( s , a ′ ) q_\pi(s,a') q π ( s , a ′ ) v π ( s ) v_\pi(s) v π ( s ) s s s a ′ a' a ′ a ′ a' a ′ s s s a ′ a' a ′ π \pi π π ′ \pi' π ′ s s s
q π ( s , π ′ ( s ) ) ≥ v π ( s ) q_\pi(s,\pi'(s))\geq v_\pi(s) q π ( s , π ′ ( s )) ≥ v π ( s )
那么策略 π ′ \pi' π ′ π \pi π π ′ \pi' π ′ π \pi π
v π ′ ( s ) ≥ v π ( s ) v'_\pi(s)\geq v_\pi(s) v π ′ ( s ) ≥ v π ( s )
这就是策略改进的方法，先对既有策略进行评估，然后尝试寻找每一个状态 s s s
π ′ ( s ) = arg max a q π ( s , a ) \pi'(s)=\arg \max\limits_a q_\pi(s,a) π ′ ( s ) = arg a max q π ( s , a )
= arg max a E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s , A t = a ] = \arg \max\limits_a E[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s,A_t=a] = arg a max E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s , A t = a ]
= arg max a ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v π ( s ′ ) ] = \arg \max\limits_a\sum\limits_{s'}p(s'|s,a)[r(s,a,s')+\gamma v_\pi(s')] = arg a max s ′ ∑ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v π ( s ′ )]
从公式中可以看出，想让整体策略最优，那么每一步的策略都必须和其他策略配合，尽可能地保证最优。这和动态规划中最优子结构的思想十分一致。所以策略改进的目标就是利用上面的公式找到更好的字部分最优策略，然后利用动态规划中的最优子结构的特性将它们拼接起来，这样就完成了策略改进的工作。
策略迭代
当了解了上面提到的两个子步骤——策略评估和策略改进之后，我们将这两个部分串联起来，就得到了策略迭代的算法，如下面公式所示：
π 0 → E v π 0 → I π 1 → E v π 1 → I π 2 ⋯ → I π ∗ → E v ∗ \pi_0\xrightarrow[]{E}v_{\pi_0}\xrightarrow[]{I}\pi_1\xrightarrow[]{E}v_{\pi_1}\xrightarrow[]{I}\pi_2\cdots\xrightarrow[]{I}\pi_*\xrightarrow[]{E}v_* π 0 E v π 0 I π 1 E v π 1 I π 2 ⋯ I π ∗ E v ∗
其中的 E E E I I I
（1）初始化： v ( s ) ∈ R , π ( s ) ∈ A ( s ) , ∀ s ∈ S v(s)\in R,\pi(s)\in A(s),\forall s\in S v ( s ) ∈ R , π ( s ) ∈ A ( s ) , ∀ s ∈ S
（2）策略评估：
For each s ∈ S \text{For each } s\in S For each s ∈ S
temp ← v ( s ) \text{temp} \gets v(s) temp ← v ( s )
v ( s ) ← ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ ) ] v(s)\gets \sum_a\pi(a|s)\sum_{s'}p(s'|s,a)[r(s,a,s')+\gamma v(s')] v ( s ) ← ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ )]
Δ ← max ( Δ , ∣ temp − v ( s ) ) \Delta \gets \max(\Delta,|\text{temp}-v(s)) Δ ← max ( Δ , ∣ temp − v ( s ))
until Δ < θ \Delta<\theta Δ < θ
（3）策略改进：
policy stable ← true \text{policy stable}\gets \text{true} policy stable ← true
For each s ∈ S \text{For each} s\in S For each s ∈ S
a ← π ( s ) a \gets\pi(s) a ← π ( s )
π ( s ) ← arg max a ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ ) ] \pi(s)\gets\arg\max\limits_a\sum\limits_{s'}p(s'|s,a)[r(s,a,s')+\gamma v(s')] π ( s ) ← arg a max s ′ ∑ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ )]
If a ≠ π ( s ) , then policy stable ← False \text{If}\ a \neq \pi(s),\text{then policy stable} \gets \text{False} If a = π ( s ) , then policy stable ← False
If policy_stable, then stop and return v v v π \pi π
价值迭代（Value Iteration）
策略迭代存在一个问题，就是在做策略评估的过程中，为了保证价值函数可以收敛，需要做很多轮的迭代计算，这实际上也比较消耗时间。那么一定要等待它完全收敛吗？如果在不完全收敛的情况下就停止策略评估的过程会不会有问题呢？实际上提前停止迭代时可以的，不需要等到价值函数完全收敛，只要保证它有一定的更新即可。价值迭代就是基于这样的思想产生的，它的算法结构和策略迭代完全相同，但是在策略评估过程中选择了最为激进的策略——只做一轮迭代就结束。算法如下：
随机初始化数组 v v v v ( s ) = 0 , ∀ s ∈ S + v(s)=0,\forall s\in S^+ v ( s ) = 0 , ∀ s ∈ S +
For each s ∈ S \text{For each }s\in S For each s ∈ S
temp ← v ( s ) \text{temp} \gets v(s) temp ← v ( s )
v ( s ) ← max a ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ ) ] v(s)\gets \max_a\sum_{s'}p(s'|s,a)[r(s,a,s')+\gamma v(s')] v ( s ) ← max a ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ )]
Δ ← max ( Δ , ∣ temp − v ( s ) ∣ ) \Delta \gets \max(\Delta,|\text{temp}-v(s)|) Δ ← max ( Δ , ∣ temp − v ( s ) ∣ )
until Δ < θ \Delta < \theta Δ < θ
输出：满足如下条件的策略 π \pi π π ( s ) = arg max a ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ ) ] \pi(s)=\arg\max_a\sum_{s'}p(s'|s,a)[r(s,a,s')+\gamma v(s')] π ( s ) = arg max a ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s , a , s ′ ) + γ v ( s ′ )]
策略函数和价值函数关系
从前面的两种算法中可以看出，策略函数和价值函数在求解中都起到关键性作用，那么两者的关系如何呢？从策略迭代法中可以看出，当策略函数固定时，数需要求解价值函数，当价值函数固定时，策略函数又可以变动；在价值迭代法中，当策略函数固定时，可以求出新的当前最优价值函数，当价值函数固定时，新的策略又可以被确定下来。所以两种算法本质上都是采用固定其中一个优化另一个的方式进行的，只是在方法上稍有不同，但在思想上是完全一致的。而这个思想就是所谓的“泛化策略迭代”（Generalized Policy Iteration），如下图所示。
根据这样的思路，我们可以灵活地调配优化策略和优化价值这两部分，使得算法更好地完成收敛。比如可以采用两轮迭代的策略迭代法，这样策略评估的计算会更精确一些，由此带来的整体的迭代轮数也会相应地减少一些。一旦构建出这样一个泛化策略迭代的框架之后，我们就可以根据实际问题的需要调整价值函数和策略函数各自计算的权重了。
