- 论文题目:Integrated architectures for learning, planning, and reacting based on approximating dynamic programming
所解决的问题?
提出Dyna-PI结构和Dyna-Q结构。
背景
Dyna结构是用机器学习的方法逼近动态规划算法,动态规划算法本身并不是一种学习算法,是一种居于模型的最优策略计算方法。它与state-space search算法非常像,但是与之不同的是动态规划是一种增量式的学习算法,并不考虑action sequences。正是这种增量式的学习算法,使得其更容易处理随机环境和非完美信息问题。对于learned world model问题,通常都是随机的和不确定的,因此动态规划算法就非常合适。Dyna框架就是learn a world model online,与此同时,用动态规划算法学习规划最优行为。
所采用的方法?
Dyna-PI:Dyna by Approximating Policy Iteration
Dyna-PI中的PI表示的是Policy Iteration,其由四大组成部分:
- policy:接收一个当前状态,产生一个动作。
- world:接收一个动作,产生下一个状态和奖励信息。
- world model:与real model类似,接收状态动作,输出下一个状态
- evaluation function:评估状态的好坏。
其结构如下所示:
Evaluation Function和Policy可以用函数近似的方法来拟合:决策树、K-D tree,神经网络或者符号规则。
算法流程:
但是当world model发生改变之后,算法需要很长一段时间才能去适应改变了的model。产生这类问题的原因在于,算法收敛之后,对于非最优策略下的action是很少去选择的,概率基本为0,因此当model改变之后,需要大量的采样才能知道新的最优策略。
Dyna-Q:Dyna by Q-Learning
将Q-Learning算法融入进来,其实也就是max那一步引入进来,并且作者在选择动作的时候用的玻尔兹曼分布,并且在奖励函数上加噪声来增加探索。
总结
算法分为两步:1. 使用当前策略与环境互动产生数据,并用这些数据学一个world model出来。2. 基于learned model产生的数据也用来做策略改进,进而减少与真实model的交互。
其它参考链接
- 论文PDF链接:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.7362&rep=rep1&type=pdf
- Richard S Sutton. Dyna, an integrated architecture for learning, planning, and reacting. ACM SIGART Bulletin, 2(4):160–163, 1991.
- Richard S Sutton. Planning by incremental dynamic programming. In Machine Learning Proceedings 1991, pages 353–357. Elsevier, 1991.