策略迭代是强化学习中较为基础的算法，主要的目的是获得最优策略。策略迭代算法包含两个模拟、交互的过程，一个是策略评估，通过计算函数对策略进行评估，使得值函数能与当前策略一致；另一个为策略改进，基于新的值函数对策略进行改进，使得策略与当前值函数不一致。在策略迭代过程中，这两个过程是交替学习的。示意图如下：
[描述来源：Sutton R S, Barto A G. Reinforcement learning: An introduction[M]. Cambridge: MIT press, 1998.]
发展历史
描述
策略搜索早在1960年就被提出，并应用于马尔可夫决策过程中。1996年至2003年间，提出了近似策略迭代的概念，给出了一个严格的理论证明。2003-2010年，针对不同的应用场景，业界研究人员提出了策略迭代的改进算法来提高其效果。
主要事件
年份 | 事件 | 相关论文/Reference |
1960 | 策略迭代被Howard提出并用于马尔科夫决策过程 | Ronald A. Howard. Dynamic Programming and Markov Processes. MIT Press, Cambridge, Massachusetts, 1960. |
1996 | Bertsekas和Tsitsiklis证明了近似策略迭代的是一个健全的基本算法（a fundamentally sound algorithm） | Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, Belmont, Massachusetts, 1996. |
2003 | Munos通过使用无穷范数边界再一次证明了近似策略迭代是一个健全的基本算法 | R´emi Munos. Error bounds for approximate policy iteration. In Proceedings of the Twentieth International Conference on Machine Learning, pages 560–567, Washington, District of Columbia, 2003. |
2003 | 提出了一种最小二乘策略迭代（LSPI），它学习状态动作值函数，该函数允许在没有模型的情况下进行动作选择，以及在策略迭代框架内增加策略改进。 | Lagoudakis, M. G., and Parr, R., 2003. “Least-Squares Policy Iteration,” J. of Machine Learning Research, Vol. 4, pp. 1107-1149 |
2010 | 提出了一种使用参数λ∈（0,1）来推广价值迭代和策略迭代的方法。与传统的时间差异方法相比，可以有效地使用训练样本 | Thiery, C., and Scherrer, B., 2010. “Least-Squares Policy Iteration: Bias-Variance Trade-off in Control Problems,” Proc. of 2010 ICML, Haifa, Israel |
发展分析
瓶颈
策略迭代的收敛效果很大程度上依赖于值函数。基于表格的强化学习属于强化学习中的基础算法，在面对现实应用的一些问题时，效果不是很理想。此外，面对高维度问题时，容易出现维度灾难。
未来发展方向
未来通过与深度学习结合，解决海量数据的泛化，可以取得更加广阔的前景。
Contributor: Yilin Pan