在列举所有策略的天真方法中，执行了大量冗余工作，因为许多策略在很大程度上是相同的。他们可能只是略有不同。然而，每项政策都是全新生成和评估的。这表明为部分策略保存中间结果并重用它们。
1. 值迭代和动态编程263
这种解决优化问题的方法是由Richard
Bellman在1957年引入的动态编程
[Bel57]。贝尔曼认识到，对于最优政策，情况是：
独立于起始状态s t和第一动作a t，从每个可能的后继状态s t
+ 1开始的所有后续决定必须是最优的。
基于所谓的贝尔曼原理，通过局部优化个体动作，可以找到全局最优策略。我们将为MDP推导出这个原理以及合适的迭代算法。
期望的是一种最优策略π 其满足（ 10.3 页） 260 和（ 10.1
页） 260 。我们重写了两个方程并得到了
=
V（st）max
a t，t +
1，t + 2，……
（R（ST，在）+ γR（ST + 1，在+ 1）+ γ 2 R（ST + 2，在+ 2）+ …）。（10.4）
由于立即奖励r（st，at）仅取决于st和at，而不取决于后继状态和动作，因此可以分配最大化，这最终导致V的以下递归表征：
V（ST）= 最大值[ R（ST，在）+ γ 最大（R（ST + 1，在+ 1）+ γR（ST + 2，在+ 2）+ …）]
a t a t + 1，t + 2，……
一个牛逼
= max [ r（st，at） + γV（st + 1 ） ] 。（10.5）
→+
公式（ 10.5 ）来自（ 10.4 ）中的替换tt 1 。写得有点简单：
一个
V（s） = max [ r（s，a） + γV（δ（s，a）） ] 。（10.6）
与第260 页的（10.1 ）一样，该等式意味着，为了计算V（s），将立即奖励添加到所有后继状态的奖励中，由因子γ打折。如果已知V（δ（s，a）），则通过对状态s中的所有可能动作a的简单局部优化，清楚地产生V（s）。这符合贝尔曼原理，因此（10.6）也称为贝尔曼方程。
最优策略π（S）进行中状态的动作小号这导致最大值V。从而，
一个
π（s） = argmax [ r（s，a） + γV（δ（s，a）） ] 。（10.7）
根据递归方程（10.6），以简单的方式跟随用于近似V：的迭代规则：
一个
V （S） = 最大[ R（S，A）+ γV （δ（s，a））的]。（10.8）
为了开始近似值 V （S） 对所有状态被初始化，例如具有零值。现在， V （S） 反复通过递归回落的值更新的每一个状态 V （δ（S，A）） 最好的继承国。这个过程
计算V称为值迭代，如图10.7所示
]
ˆ
r（s，a）+ γV（δ（s，a））
一个
ˆ
V（s） = 最大 [
重复
V ALUE I TERATION（）
对于所有ŝ ∈ 小号
图10.7 值迭代的算法
V （S） = 0
对于所有ŝ ∈ 小号
直到 V （S） 不会改变
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
×
图10.8具有3 3个状态的示例中的值迭代。在过去的两个图像显示了两个最优策略。箭头旁边的数字给出了每个动作的直接奖励 r（s，a）
在页264。可以证明，值迭代收敛于V [SB98]。在[Sze10]中可以找到对动态编程算法的出色分析，其中，基于特定算法的收缩属性（例如，值迭代），可以使用Banach的定点理论证明收敛。
2.
学习步行机器人及其模拟265
=
在图 10.8中，该算法应用于第 257 页的示例 10.1 ，其中γ0为0 。9。
在每次迭代中，状态从左下角到右上角逐行处理。示出了几个开始迭代，并且在底行的第二个图像中示出了V的稳定极限值。
我们清楚地看到了这个序列中学习的进展。代理重复探索所有状态，对每个状态执行值迭代，并以表格函数V的形式保存策略，然后可以将其进一步编译成有效可用的表π。
= +
顺便提一下，为了从V找到最优策略，在状态st中选择导致具有最大V 值的状态的动作是错误的。对应于第263 页的（10.7 ），还必须添加直接奖励r（st，at），因为我们正在搜索V（st）而不是V（st 1 ）。施加到状态S（ 2 ， 3 ）在图10.8 页264，此装置
=
π（2，3）argmax
一∈{ 左，右，向上}
[ r（s，a） + γV（δ（s，a）） ]
=
argmax
{ left ， right ， up }
=
argmax
{ left ， right ， up }
{ 1 + 0 。9 ・ 2 。66 ，– 1 + 0 。9 ・ 4 。05 ， 0 + 0 。9 ・ 3 。28 }
{ 3 。39 ， 2 。65 ， 2 。95 } =左。
=
在（10.7 页）263，我们看到，在国家的代理人ST必须知道的立即回报RT和继承国ST + 1 δ（ST，AT）选择最佳行动的。它还必须具有函数r和δ的模型。因为事实并非如此
在许多实际应用中，需要算法，这些算法也可以在不知道r和δ的情况下工作。第10.6 节专用于这种算法。
