基于强化学习的值迭代算法

崔军晓等

摘要：强化学习（Reinforcement Learning）是学习环境状态到动作的一种映射，并且能够获得最大的奖赏信号。强化学习中有三种方法可以实现回报的最大化：值迭代、策略迭代、策略搜索。该文介绍了强化学习的原理、算法，并对有环境模型和无环境模型的离散空间值迭代算法进行研究，并且把该算法用于固定起点和随机起点的格子世界问题。实验结果表明，相比策略迭代算法，该算法收敛速度快，实验精度好。

关键词：强化学习；值迭代；格子世界

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2014）31-7348-03

Abstract： Reinforcement learning is learning how to map situations to actions and get the maximize reward signal. In reinforcement learning， there are three methods that can maximize the cumulative reward. They are value iteration， policy iteration and policy search. In this paper， we survey the foundation and algorithms of reinforcement learning ， research about model-based value iteration and model-free value iteration and use this algorithms to solve the fixed starting point and random fixed starting point Gridworld problem. Experimental result on Gridworld show that the algorithm has faster convergence rate and better convergence performance than policy iteration.

Key words： reinforcement learning； value Iteration；Gridworld

强化学习可以解决自动控制，人工智能，运筹学等领域方面的各种问题。其中自动控制和人工智能是强化学习的重要发源地。在自动控制领域中，强化学习用于自适应的最优控制问题。在人工智能领域中，强化学习用于协助构建人工agent，可以在未被构建的未知环境中找到最优化的行为。

我们在这里对强化学习的值迭代算法进行研究，并以格子世界为例将该算法进行实际运用，以此表现出该算法的优势。

如图 1所示，agent做出了一个动作，环境对agent做出的动作产生回应，从而改变了agent的状态并且对agent给出一定的奖赏。在每个时间步中，agent都要实现从状态到每一个可能选到的动作的映射。这个映射就是agent的策略。

3 离散空间实验结果分析

现在来用基于模型的值迭代算法解决格子世界问题。将算法1直接运用在格子世界问题上。设定初始状态的状态值函数全部为0，折扣因子[γ]为0.5。对应的值迭代结果如图3所示，策略如图4所示。

图3每一步迭代的策略由图4表示，同时也是策略改进图像。根据值函数估计值得到的贪心策略的序列。箭头表示该状态中能取得最大值的动作。通过图4可得第五轮迭代和第六轮迭代的策略已经相同，此时策略为最优策略。

[V6]，[V7]时所有状态的值函数均已经相同，可以认为已经收敛。从图4可以得出经过多次迭代，策略从无序到有序，最终达到最优策略，通过值迭代得到的最终策略是正确的。

4 小结

本文简易介绍了强化学习基本概念，并说明如何使用强化学习值迭代方法在离散空间中找到最优策略。在离散空间中，若模型已知，可以使用动态规划的方法，通过策略评估和策略改进的迭代求出值函数和最优策略。策略评估和策略改进的迭代方式不同可以将动态规划分为值迭代和策略迭代。该文通过格子世界的实验，验证了值迭代的高效收敛性，弥补了策略迭代的不足。

参考文献：

[1] Barto A G.Reinforcement learning： An introduction[M].MIT press，1998.

[2] Busoniu L，Babuska R，De Schutter B，et al.Reinforcement learning and dynamic programming using function approximators[M].CRC Press，2010.

[3] Singh S， Jaakkola T，Littman M L，et al.Convergence results for single-step on-policy reinforcement-learning algorithms[J].Machine Learning，2000，38（3）：287-308.

[4] Boyan J A.Technical update： Least-squares temporal difference learning[J].Machine Learning，2002，49（2-3）：233-246.

[5] Singh S P，Sutton R S.Reinforcement learning with replacing eligibility traces[J].Machine learning， 1996，22（1-3）： 123-158.

[6] Barto A G，Sutton R S，Watkins C J C H.Learning and sequential decision making [M]//Gabriel M，Moore J W.Learning and computational neuroscience： Foundations of adaptive networks.Cambridge，MA：MIT Press， 1989.

[7] 陈浩.基于强化学习的蚁群聚类研究及应用[D].苏州：苏州大学， 2011.

[8] 高阳，陈世福，陆鑫.强化学习研究综述[J].自动化学报，2004， 30（1）： 86-100.