本文转载自微信公众号 机器人学家，根据其上发布的CMU翻译讲义进行整理。

大纲

• Exact solution methods:
  
  • Policy iteration
    
    • Policy Evaluation (a.k.a. DP)
    • Policy Improvement
  • Value iteration (a.k.a. DP)
  • Linear programming
• Approximate solution methods:
  
  • Asynchronous DP

策略评估

• 策略评估：对于给定的策略 <nobr> π </nobr>,计算状态价值函数 <nobr> vπ(s) </nobr>.
• 状态价值函数 <nobr> vπ(s) </nobr>的定义： <nobr> vπ(s)=Eπ[Gt|St=s] </nobr>
• 状态价值函数 <nobr> vπ(s) </nobr>的Bellman方程如下，是一个|S|元方程组，|S|为状态空间S的数量。
  <nobr> vπ(s)=∑a∈Aπ(a|s)(Ras+γ∑s′∈SPass′vπ(s′)) </nobr>

从MDPs到MRPs

当我们固定一个策略时，MDP问题就变成了马尔科夫奖励过程(Markov Reward Process，下简写为MRP)
由前面提到的状态价值函数的Bellman方程，可以得到：
<nobr> vπ(s)=∑a∈Aπ(a|s)Ras+γ∑a∈Aπ(a|s)∑s′∈SPass′vπ(s′))=Rπs+γ∑s′∈SPπsvπ(s′) </nobr>

矩阵形式

使用MRP，可以得到更加简洁的Bellman期望公式。如果有N个状态s，那么在策略评估的过程中，需要求解N个未知量（v(s)），有N个线性方程（每个状态有一个Bellman equation），这样可以得到一个N维线性系统，理论上可以直接求解。对这个N维线性系统可以得到如下的矩阵形式的表达。
<nobr> vπ=Rπ+γPπvπ </nobr>
其中v为向量表示的状态价值函数，向量中的每一个元素表示对应状态的价值。R为向量表示的即时收益的期望，
<nobr> Rπ(s)=∑a∈Aπ(s|a)Ras </nobr>
<nobr> Pπ=∑a∈Aπ(a|s)P(s′|s,a) </nobr>
得到解析解如下：
<nobr> vπ=(I−γPπ)−1Rπ </nobr>
计算复杂度为 <nobr> O(N3) </nobr>

迭代法

迭代策略评估算法

策略评估算法 收敛性证明

一个有|S|个状态的MDP，其所有价值函数V(s)构成的向量可以看成|S|维向量空间V中的一个点。要说明收敛性，就要说明策略评估里的计算——贝尔曼 backup 会对该空间中的点带来怎样变化？
下面我们说明，它每次迭代都会使这些点离得更近
所以贝尔曼backup在无穷次迭代后必然收敛到唯一解

价值函数的无穷范数 <nobr> ∞−Norm </nobr>

我们可以用 <nobr> ∞−Norm </nobr>来度量状态-价值函数u和v
即，两个状态价值之间的距离。
<nobr> ||u−v||∞=maxs∈S|u(s)−v(s)| </nobr>

贝尔曼back up是收缩的

定义贝尔曼Back up操作子 <nobr> Tπ </nobr>
<nobr> Tπ(v)=Rπ+γPπv </nobr>
这个操作子是 <nobr> γ </nobr>-收缩，即它会使价值函数之间的距离至少缩小到原来的 <nobr> γ </nobr>倍。 <nobr> γ </nobr>是定义价值时的折扣系数，小于1：
<nobr> ||Tπ(u)−Tπ(v)||∞ </nobr>= <nobr> ||(Rπ+γPπu)−(Rπ+γPπv)||∞=||γPπ(u−v)||∞≤||γPπ||u−v||∞||∞≤γ||u−v||∞ </nobr>

收缩映射定理

定理（收缩映射定理）
已知T是 <nobr> γ </nobr>收缩，对于操作T(v)下的任意完备（即闭合）的度量空间V，有：
T以线性收敛速率 <nobr> γ </nobr>收敛到唯一的固定点
（编者注：即策略评估一定会收敛到一个值）

结论：迭代策略评估是收敛的

贝尔曼期望操作子 <nobr> Tπ </nobr>有唯一的固定点。（根据贝尔曼期望方程） <nobr> vπ </nobr>是 <nobr> Tπ </nobr>上的一个固定点，所以根据收缩映射定理，迭代策略评估收敛于 <nobr> vπ </nobr>

策略迭代

广义策略 迭代(GPI)

最优性原理

称策略 <nobr> π(a|s) </nobr>在状态s处获得最优值，即 <nobr> vπ(s)=v∗(s) </nobr>，当且仅当：

• 对于从状态s可以到达任意的状态s’
• 策略 <nobr> π </nobr>也在状态s’处获得最优值，即 <nobr> vπ(s′)=v∗(s′) </nobr>

值迭代

<nobr> Vk+1(s)=maxa∑s′T(s,a,s′)[R(s,a,s′)+γVk(s′)] </nobr>
重复直到收敛
一次迭代的复杂度 <nobr> O(S2A) </nobr>
定理：会收敛到最优价值
策略可能先于状态价值很长时间收敛
不是就地更新
问题

• 速度慢一次迭代时间复杂读 <nobr> O(S2A) </nobr>
• 每个状态的max值很少变化
• 策略往往先于状态价值很长时间收敛

策略迭代

• 仍然是最优的
• 在某些情况下收敛更快

对比

• 值迭代
  
  • 每次迭代都更新了状态价值和（隐含地）策略
  • 不追踪策略，但是在对 <nobr> q(s,a) </nobr>取最大值的时候隐含地重新计算了它
• 策略迭代
  
  • 在固定此策略下多次更新utlities（每一次都很快，因为只考虑了一个action，而不是所有的）
  • 策略被评估完后，选择一个新的策略（跟一次价值迭代一样慢）
  • 新的策略会更好
• 都是解决MDPs的动态规划方法

总结

• 如果想：
  
  • 计算最优价值：使用值迭代或策略迭代
  • 计算特定策略价值：使用策略评估
  • 将状态价值转化成一个策略：使用策略提取(one-step lookahead)
• 这些看起来一样
  
  • 本质上都是Bellman uodates的变种
  • 都利用one-step looahead expectimax fragments
  • They differ only in whether we plug in a fixed policy or max over actions

异步动态规划

未完待续