基于值函数迁移的启发式Sarsa算法

陈建平，杨正霞，刘全，吴宏杰，徐杨，傅启明



基于值函数迁移的启发式Sarsa算法

陈建平1,2,3，杨正霞1,2,3，刘全4，吴宏杰1,2,3，徐杨5，傅启明1,2,3

（1. 苏州科技大学电子与信息工程学院，江苏 苏州 215009；2. 苏州科技大学江苏省建筑智慧节能重点实验室，江苏 苏州 215009；3. 苏州科技大学苏州市移动网络技术与应用重点实验室，江苏 苏州 215009；4. 苏州大学计算机科学与技术学院，江苏 苏州 215000；5. 浙江纺织服装职业技术学院信息工程学院，浙江 宁波 315000）

针对Sarsa算法存在的收敛速度较慢的问题，提出一种改进的基于值函数迁移的启发式Sarsa算法（VFT-HSA）。该算法将Sarsa算法与值函数迁移方法相结合，引入自模拟度量方法，在相同的状态空间和动作空间下，对新任务与历史任务之间的不同状态进行相似性度量，对满足条件的历史状态进行值函数迁移，提高算法的收敛速度。此外，该算法结合启发式探索方法，引入贝叶斯推理，结合变分推理衡量信息增益，并运用获取的信息增益构建内在奖赏函数作为探索因子，进而加快算法的收敛速度。将所提算法用于经典的Grid World问题，并与Sarsa算法、Q-Learning算法以及收敛性能较好的VFT-Sarsa算法、IGP-Sarsa算法进行比较，实验表明，所提算法具有较快的收敛速度和较好的稳定性。

强化学习；值函数迁移；自模拟度量；变分贝叶斯

1 引言

强化学习（RL, reinforcement learning）又称激励学习、增强学习，是在未知、动态环境中通过agent与环境的交互实现从状态到动作的映射，并获得最大期望累计奖赏的一类在线学习方法[1]。在强化学习问题中，新的强化学习任务与历史任务之间会存在某种相似性，因此可利用两者之间的相似性来提高目标任务的学习速率，这需要运用迁移学习（TL, transfer learning）方法。1995年，迁移学习被首次以“learning to learn”的概念提出，引起学术界的广泛关注[2]。迁移学习主要包括3个方面：迁移什么、如何进行迁移、何时进行迁移。通过这3个方面，可以使迁移学习达到提高目标任务收敛速度的目的。然而迁移学习是对以往任务中学习的经验进行利用，从而提高目标任务的学习速率，但对于强化学习任务而言，其本身长期存在着平衡探索与利用之间关系的问题，有效地解决探索问题使agent获得最大化环境信息的轨迹，可以加快目标任务的学习速率。

近年来，迁移学习在强化学习领域已引起广大研究学者的关注。Ammar等[3]通过优化不同任务间可转移的知识库，并通过对该知识库间不同任务构建映射关系，使新任务快速收敛。Gupta等[4]通过构建状态空间到不变特征空间之间的映射关系，将知识映射到不变特征空间，并利用构建的映射关系实现知识的迁移，从而加快新任务的收敛速度。Laroche等[5]在假设不同任务具有相同状态空间与动作空间的基础上，通过添加探索因子构建新的奖赏函数，实现不同任务间的知识迁移，提高算法在后续任务中的收敛性能。Barreto等[6]提出在环境动态性不变的前提下，对不同任务之间的奖赏函数进行迁移，从而加快算法的收敛速度。

本文针对经典的Sarsa算法存在收敛速度慢的问题，提出一种基于值函数迁移的启发式Sarsa算法（VFT-HSA）。针对经典Sarsa算法中值函数初始值的设定直接影响算法收敛速度的问题，VFT-HSA算法引入知识迁移，利用自模拟度量的方法，构造目标任务与历史任务之间的度量关系，通过设定阈值，迁移历史任务中的最优值函数，提高算法的收敛速度。针对大量算法问题中探索与利用不平衡的问题，VFT-HSA引入启发式探索方法，利用贝叶斯推理，结合变分推理衡量信息增益，附加内在奖赏函数，从而提高算法的探索性能，加快算法的收敛速度。将VFT-HSA应用于Grid World问题，实验结果表明，VFT-HSA较其他算法具有更快的收敛速度和较好的稳定性。

2 相关理论

2.1 马尔可夫决策过程

式(3)和式(4)也被称为Bellman最优方程。

2.2 Sarsa算法

在强化学习算法中，Sarsa算法能够在未知奖赏函数与状态转移函数的情况下，采用状态动作值迭代找到最优策略，是一种在线学习算法。在Sarsa算法学习过程中，当状态动作对被无数次访问时，Sarsa以概率1收敛到最优策略以及最优状态动作值函数，且策略将在有限的时间步内收敛至贪心策略。然而，Sarsa算法是一种保守算法，为了减少损失，在学习过程中会选择相对安全的动作，这使Sarsa算法在选取动作时缺乏一定的探索，进而使Sarsa算法收敛速度相对较慢。Sarsa算法具体流程如算法1所示[1]。

算法1 Sarsa算法

2) repeat (对于每一个情节)

3) 初始化状态

4) 在状态下，根据行为策略选择动作

5) repeat (对于情节中的每一步)

10) end repeat

11) end repeat

12) 输出：值函数

2.3 自模拟度量

2003年，Givan等[14]首次将自模拟关系引入MDP，并利用自模拟关系度量不同MDP中状态之间的距离。其自模拟关系可简单表述为：若2个状态之间满足自模拟关系，那么2个状态之间的最优值函数或最优动作可相互共享。

对于任意2个状态，它们之间的自模拟关系是“是”或“非”的关系，要么满足自模拟关系，要么不满足自模拟关系，但在实际应用中，该方法太过于严苛。如果2个状态的奖赏分布与状态转移概率分布极其近似，则2个状态极其近似，根据以上条件可推测2个状态具有相似的最优动作和最优值函数，但自模拟关系无法证明该推测。因而Ferns等[15]针对该问题，利用Kantorovich距离，提出衡量2个状态之间相似性关系的自模拟度量方法，并得到定理1。

2.4 变分贝叶斯

变分贝叶斯最早由Beal[16]提出，其可应用于隐马尔可夫模型、混合因子分析、非线性动力学、图模型等。变分贝叶斯可较好地处理复杂统计模型。复杂统计模型由观测变量、未知参数和潜变量这3类变量组成，其中，未知参数和潜变量统称为不可观测变量。

采用变分贝叶斯具有如下优点：1)将不可观测变量的后验概率近似成其他变量，方便不可观测变量的推断；2)对于一个模型，给出边缘似然函数的下界，当边缘似然函数值最高时，表明模型拟合程度越好，通过该方法可获取最优模型。

3 VFT-HAS算法思想及简介

3.1 值函数迁移

通常，对于MDP，可以通过迭代方法求出最优状态值函数或最优动作值函数，再由最优值函数求解最优策略。但对于每一个MDP，求解最优值函数都需要进行迭代计算，这会造成计算资源的浪费，因此考虑将已求解的历史最优值函数用于后续的MDP中，进而求解最优值函数。若2个状态相似，它们应该具有相似的最优状态值函数，并利用自模拟度量关系，对相似状态进行值函数迁移。在对值函数迁移方法进行介绍之前，先做如下假设。

关于定理2的证明可参考文献[17]，为了更加充分地说明定理2，给出如下说明。

图1 MDP状态转移示意

由定理2，给出不同MDP之间基于自模拟度量的值函数迁移算法，如算法2所示。

算法2 基于自模拟度量的值函数迁移算法

4) end for

5) end for

10) else

12) end if

13) end for

3.2 基于变分贝叶斯的启发式探索

证毕。

图2 Kullback-Leibler散度关系

结合上述原理，给出一种改进的启发式内部奖赏函数的更新式，如式(9)所示。

(14)

3.3 VFT-HAS简介

基于值函数迁移的启发式Sarsa算法主要利用自模拟度量方法对相似状态之间的以往值函数知识进行迁移，从而提高初始化值函数的精确性，并利用变分贝叶斯理论，获得信息增益作为内在奖赏函数进行启发式探索，结合Sarsa算法框架，利用V-Q算法中的更新方法更新值函数[18]，提高算法收敛速度，具体如算法3所示。

算法3 基于值函数迁移的启发式Sarsa算法

2) repeat (对于每一个情节)

4) repeat(对于情节中的每一个时间步)

12) end repeat

14) 算法终止

15) end if

18) end repeat

基于值函数迁移的启发式Sarsa算法主要分为3个部分，第一部分利用算法2知识迁移进行初始化状态值函数；第二部分对状态和动作及下一个状态进行采样，通过变分贝叶斯理论衡量信息增益作为内部奖赏函数；第三部分在第二部分的基础上更新状态值函数和状态动作值函数，求解问题最优策略，提高算法学习速率。

4 实验及结果分析

为了研究算法的性能，将VFT-HSA应用在Grid World问题中，并针对算法收敛的速度以及算法的稳定性等方面进行分析，将VFT-HSA与Sarsa算法、Q-Learning算法、VFT-Sarsa算法[17]、IGP-Sarsa[19]算法在相同的实验环境中重复实验24次，取每次实验的平均值比较各算法的性能。

4.1 Grid World问题介绍

图4 格子世界（目标MDP）

4.2 实验设置

图5 格子世界（原始MDP）

4.3 实验分析

图6 5×6的Grid World问题中5种算法性能比较

图7 10×10的Grid World问题中5种算法性能比较

为了验证算法采用值函数迁移方法和启发式探索方法的收敛性能，图8分别表示Sarsa算法、本文提出的VFT-HSA、不采用值函数迁移算法、不采用启发式探索算法在10×10的Grid World问题中达到收敛时所需的平均时间的变化趋势，其中，横坐标为情节数，纵坐标为情节结束后到达目标状态所需的时间。在实验过程中，每一个算法都独立执行24次，取其平均值。在图8中，Sarsa算法不能保证较好收敛，收敛性能较差；不采用值函数迁移算法在大约40个情节处收敛，而VFT-HSA在大约30个情节处收敛，VFT-HSA相比于不采用值函数迁移算法收敛速度提升近25%，因而不采用值函数迁移算法收敛速度较慢，这是因为不采用值函数迁移算法使算法运行过程中值函数的初始值未获得最优设置，算法收敛需要更多的样本数量，最终导致算法收敛速度慢；不采用启发式探索算法在大约50个情节处收敛，相比较而言，VFT-HSA收敛速度提升近40%，不采用启发式探索算法收敛性能不及VFT-HSA，这是因为启发式探索算法在算法收敛过程中可以提供更多的启发式信息，加大agent探索力度，提高算法收敛速度。综上所述，在值函数迁移方法与变分贝叶斯启发式探索方法共同作用下，VFT-HSA的收敛速度更快，收敛性能更好。

图8 10×10的Grid World问题中4种算法的性能比较

图9 不同规模的Grid World问题中VFT-HSA取不同η值时收敛性能比较

表1 不同规模的Grid World问题中VFT-HSA取不同值时收敛所需平均步数比较

5 结束语

本文针对Sarsa算法在维度较大的状态空间和动作空间的MDP中存在收敛速度慢的问题，提出一种改进的VFT-HSA。在不同任务间具有相同状态空间和动作空间的MDP中，该算法运用自模拟度量的方法构建不同任务下状态之间的距离关系，当2个MDP达到一定相似度时，进行值函数知识迁移，减少算法收敛所需的样本，提高算法的收敛性能；针对强化学习问题中存在的探索与利用的平衡问题，结合贝叶斯推理，利用变分推理获取信息增益并用其构建内部奖赏函数模型，加大agent探索力度，提高算法收敛速度。将本文提出的VFT-HSA与Q-Learning算法、IGP-Sarsa算法用于经典的Grid World问题，实验表明，VFT-HSA克服了经典的Sarsa算法中存在的收敛速度慢以及收敛不稳定的问题，在保证收敛精度的情况下，提高了算法的收敛速度和稳定性。

本文主要在Grid World仿真平台中对算法进行实验分析，实验结果表明，本文所提算法具有较快的收敛速度和较好的收敛稳定性。本文主要对较大规模、离散的问题进行实验分析，接下来的工作是将算法运用于更大规模的问题和连续问题中进一步验证算法的有效性。

[1] SUTTON R S, BARTO G A. Reinforcement learning: an introduction[M]. Cambridge: MIT Press, 1998.

[2] SCHMIDHUBER J, INFORMATIK T T. On learning how to learn learning strategies[R]. Germany: Technische University, 1995.

[3] AMMAR H B, EATON E, LUNA J M, et al. Autonomous cross-domain knowledge transfer in lifelong policy gradient reinforcement learning[C]//The 15th International Conference on Artificial Intelligence. 2015: 3345-3351.

[4] GUPTA A, DEVIN C, LIU Y X, et al. Learning invariant feature spaces to transfer skills with reinforcement learning[C]//The 5th International Conference on Learning Representations. 2017: 2147-2153.

[5] LAROCHE R, BARLIER M. Transfer reinforcement learning with shared dynamics[C]//The 31th International Conference on the Association for the Advance of Artificial Intelligence. 2017: 2147-2153.

[6] BARRETO A, DABNEY W, MUNOS R, et al. Successor features for transfer in reinforcement learning[C]//The 32th International Conference on Neural Information Processing Systems. 2017: 4055-4065.

[7] DEARDEN R, NIR F, STUART R. Bayesian Q-learning[C]//The 21th International Conference on the Association for the Advance of Artificial Intelligence. 1998: 761-768.

[8] GUEZ A, SILVER D, DAYAN P. Scalable and efficient Bayes- adaptive reinforcement learning based on Monte-Carlo tree search[J]. Journal of Artificial Intelligence Research, 2013, 48(1): 841-883.

[9] LITTLE D Y, SOMMER F T. Learning and exploration in action-perception loops[J]. Frontiers in Neural Circuits, 2013, 7(7): 37-56.

[10] MANSOUR Y, SLIVKINS A, SYRGKANIS V. Bayesian incentive-compatible bandit exploration[C]//The 16th International Conference on Economics and Computation. 2015: 565-582.

[11] VIEN N A, LEE S G, CHUNG T C. Bayes-adaptive hierarchical MDPs[J]. Applied Intelligence, 2016, 45(1): 112-126.

[12] WU B, FENG Y. Monte-Carlo Bayesian reinforcement learning using a compact factored representation[C]//The 4th International Conference on Information Science and Control Engineering. 2017: 466-469.

[13] 傅启明, 刘全, 伏玉琛, 等. 一种高斯过程的带参近似策略迭代算法[J]. 软件学报, 2013, 24(11): 2676-2687.

FU Q M, LIU Q, FU Y C, et al. Parametric approximation policy strategy iteration algorithm based on Gaussian process[J]. Journal of Software, 2013, 24(11): 2676-2687.

[14] GIVAN R, DEAN T, GREIG M. Equivalence notions and model minimization in Markov decision processes[J]. Artificial Intelligence, 2003, 147(1): 163-223.

[15] FERNS N, PANANGADEN P, PRECUP D. Metrics for finite Markov decision processes[C]//The 20th International Conference on Uncertainty in Artificial Intelligence. 2004: 162-169.

[16] BEAL M J. Variational algorithms for approximate Bayesian inference[D]. London: University of London, 2003.

[17] 傅启明, 刘全, 尤树华, 等. 一种新的基于值函数迁移的快速Sarsa算法[J]. 电子学报, 2014, 42(11): 2157-2161.

FU Q M, LIU Q, YOU S H, et al. A novel fast sarsa algorithm based on value function transfer[J]. Acta Electronica Sinica, 2014, 42(11): 2157-2161.

[18] MIERING M, HASSELT H V. The QV family compared to other reinforcement learning algorithms[C]//The 17th International Conference on Approximate Dynamic Programming and Reinforcement Learning. 2008: 101-108.

[19] CHUNG J J, LAWRANCE N R J, SUKKARIEH S. Gaussian processes for informative exploration in reinforcement learning[C]//The 20th International Conference on Robotics and Automation. 2013: 2633-2639.

Heuristic Sarsa algorithm based on value function transfer

CHEN Jianping1,2,3, YANG Zhengxia1,2,3, LIU Quan4, WU Hongjie1,2,3, XU Yang5, FU Qiming1,2,3

1. Institute of Electronics and Information Engineering, Suzhou University of Science and Technology, Suzhou 215009, China 2. Jiangsu Province Key Laboratory of Intelligent Building Energy Efficiency, Suzhou University of Science and Technology, Suzhou 215009, China 3. Suzhou Key Laboratory of Mobile Networking and Applied Technologies, Suzhou University of Science and Technology, Suzhou 215009, China 4. School of Computer Science and Technology, Soochow University, Suzhou 215000, China 5. Institute of Information Engineering, Zhejiang Fashion Institute of Technology College, Ningbo 315000, China

With the problem of slow convergence for traditional Sarsa algorithm, an improved heuristic Sarsa algorithm based on value function transfer was proposed. The algorithm combined traditional Sarsa algorithm and value function transfer method, and the algorithm introduced bisimulation metric and used it to measure the similarity between new tasks and historical tasks in which those two tasks had the same state space and action space and speed up the algorithm convergence. In addition, combined with heuristic exploration method, the algorithm introduced Bayesian inference and used variational inference to measure information gain. Finally, using the obtained information gain to build intrinsic reward function model as exploring factors, to speed up the convergence of the algorithm. Applying the proposed algorithm to the traditional Grid World problem, and compared with the traditional Sarsa algorithm, the Q-Learning algorithm, and the VFT-Sarsa algorithm, the IGP-Sarsa algorithm with better convergence performance, the experiment results show that the proposed algorithm has faster convergence speed and better convergence stability.

reinforcement learning, value function transfer, bisimulation metric, variational Bayes

TP391

A

10.11959/j.issn.1000−436x.2018133

陈建平（1963−），男，江苏南京人，博士，苏州科技大学教授，主要研究方向为大数据分析与应用、建筑节能、智能信息处理。

杨正霞（1992−），女，江苏扬州人，苏州科技大学硕士生，主要研究方向为强化学习、迁移学习、建筑节能。

刘全（1969−），男，内蒙古牙克石人，博士，苏州大学教授、博士生导师，主要研究方向为智能信息处理、自动推理与机器学习。

吴宏杰（1977−），男，江苏苏州人，博士，苏州科技大学副教授，主要研究方向为深度学习、模式识别、生物信息。

徐杨（1980−），女，河北深州人，浙江纺织服装职业技术学院讲师，主要研究方向为数据分析与应用、智能化与个性化教学。

傅启明（1985−），男，江苏淮安人，博士，苏州科技大学讲师，主要研究方向为强化学习、深度学习及建筑节能。

2018−03−22；

2018−07−13

傅启明，fqm_1@126.com

国家自然科学基金资助项目（No.61502329, No.61772357, No.61750110519, No.61772355, No.61702055, No.61672371, No.61602334）；江苏省自然科学基金资助项目（No.BK20140283）；江苏省重点研发计划基金资助项目（No.BE2017663）；江苏省高校自然科学基金资助项目（No.13KJB520020）；苏州市应用基础研究计划工业部分基金资助项目（No.SYG201422）

The National Natural Science Foundation of China (No.61502329, No.61772357, No.61750110519, No.61772355, No.61702055, No.61672371, No.61602334), The Natural Science Foundation of Jiangsu Province (No.BK20140283), The Key Research and Development Program of Jiangsu Province (No.BE2017663), High School Natural Science Foundation of Jiangsu Province (No.13KJB520020), Suzhou Industrial Application of Basic Research Program Part (No.SYG201422)