策略迭代

策略迭代算法直接操纵策略,而不是通过最优值函数间接找到策略。

简介

策略迭代是强化学习中较为基础的算法,主要的目的是获得最优策略。策略迭代算法包含两个模拟、交互的过程,一个是策略评估,通过计算函数对策略进行评估,使得值函数能与当前策略一致;另一个为策略改进,基于新的值函数对策略进行改进,使得策略与当前值函数不一致。在策略迭代过程中,这两个过程是交替学习的。示意图如下:

[描述来源: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

相关人物
约翰特西斯克里斯
约翰特西斯克里斯
马丁普特曼
马丁普特曼
F.L. Lewis
F.L. Lewis
理查德S.萨顿
理查德S.萨顿
Richard S. Sutton 教授博士毕业于马萨诸塞大学安姆斯特分校,现任阿尔伯塔大学计算机科学教授。Sutton 教授被认为是现代计算的强化学习创立者之一。他为该领域做出了许多重大贡献,包括:时间差分学习(temporal difference learning)、策略梯度方法(policy gradient methods)、Dyna 架构
迪米特里·伯特瑟卡斯
迪米特里·伯特瑟卡斯
简介
相关人物