algorithm - 价值迭代的收敛

Question

为什么值迭代算法的终止条件（例如http://aima-java.googlecode.com/svn/trunk/aima-core/src/main/java/aima/core/probability/mdp/search/ValueIteration.java )

在 MDP（马尔可夫决策过程）中是

||Ui+1-Ui||< 误差*(1-gamma)/gamma, 其中

Ui 是效用向量
Ui+1 更新的效用向量

error - 算法中使用的错误界限

算法中使用的 gamma 折扣因子

“error*(1-gamma)/gamma”从何而来？“除以伽玛”是因为每一步都被伽玛打折吗？但是错误*（1-伽玛）？错误必须有多大？

Answer 1

这称为贝尔曼误差或贝尔曼残差。

有关在 MDP 中的使用，请参见Williams 和 Baird，1993。

参见Littman , 1994 在 POMDP 中的使用。