vlambda博客
学习文章列表

• 论文题目：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，其由四大组成部分：

1. policy：接收一个当前状态，产生一个动作。
2. world：接收一个动作，产生下一个状态和奖励信息。
3. world model：与real model类似，接收状态动作，输出下一个状态
4. 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.