基于经验回放Q-Learning的最优控制算法

2017年5月

第

38

卷第

5

期

COMPUTER ENGINEERING AND DESIGN

计算机工程与设计

May 2017Vol. 38 No. 5基于经验回放Q-Learning的最优控制算法黄小燕(成都信息工程大学控制工程学院，成都四川610225)摘要：针对实时系统的在线最优控制策略学计算开销高的缺点，提出基于经验回放和Q-Learning的最优控制算法。采用

经验回放（experience

replay，ER)对样本进行重复利用，弥孙实时系统在线获取样本少的不足；通过Q-Leaming算法并

ER-Q-Learning算法，分析其计算复杂

度。仿真结果表明，相比Q-Learning算法、Sarsa算法以及批量的BLSPI算法，ER-Q-Learning算法能在有限时间内平衡

更多时间步，具有最快的收敛速度。关键词：控制策略；经验回放；Q学习；实时系统；样本中图法分类号：TP181 文献标识号：A 文章编号：1000-7024 (2017) 05-1352-04

采用梯度下降方法对值函数参数向量进行更新；定义基于经验回放和Q-Learning的doi：

10. 16208/j.

issnl000-7024. 2017. 05. 043Optimal control based on experience replay and Q-Learning(Control Engineering School, Chengdu University of Information Technology, Chengdu 610225, China)Abstract： Aiming at the problem of high computation cost in on-line optimal control strategy for real time system, an optimal

control algorithm based on experience replay and Q-Learning was proposed. The experience replaying technique was adopted to

reuse the samples, to solve the problem that real time system can not get enough samples. Through Q-Learning algorithm and

gradient descent method, the parameter vector of value function was updated. The algorithm based on ER and Q-Learning was

named ER-Q-Learning, and its computation cost was analyzed Results of simulation show compared with Q-Learning, Sarsa and

BLSPI, ER-Q-Learning can balance more time steps than the three methods with higher convergence words： control strategy； experience replaying； Q-Learning； real-time system； samples〇引言目前经典的在线强化学习[M]算法主要包括：动态规

、TD算法(包括Q学习算法和Sarsa算法）和蒙

模型学习方法与经验回放方法相比，具有数据存储量小的

优点，但其增加了模型学习的计算开销，同时会引人模型

误差，导致最终可能无法学习到最优策略。因此，本文将经验回放与Q-Learning相结合，提出了

一个增量式的ER-Q-Leammg在线强化学习框架，并将其

应用于倒立摆实验中，通过与传统的Sarsa算法，Q-Lear-

nmg算法以及批量学习算法进行比较，验证了 ER-Q-Lear-

ning算法的有效性。HUANG

Xiao-yan划M特卡洛算法[9]等，为了提高在线强化学习的学习效率和控

制策略的最优性，需要对样本进行重复利用。对样本进行

重复利用的方法主要有直接利用和间接利用。直接利用样

本的方法最为经典的为经验回放（experience

replay,

ER),

ER由Lm提出，将在线学习过程中获得样本存储起来,

并采用在线学习算法进行重复学习，因此，能有效地增加

算法的数据效率，能取得与批量强化学习方法近似的性

能[11_13]。间接利用样本的方法是模型学习方法，即从数据

样本中学习一个环境模型，然后利用模型生成新数据，将

新数据输人到在线强化学习算法中，实现最优策略的学习。1马尔科夫决策过程马尔科夫决策过程可以表示为一个四元组（Markov

decision processes, MDPs) JP M = < X,

其中：Up />,

, ,(l)x是由状态构成的集合，任意状态表示2016-03-23;修订日期：2016-04-28

基金项目：国家自然科学基金项目（61502329)作者简介：黄小燕（1974-)，女，江西宜黄人，硕士，副教授，研究方向为模式识别和智能计算。E-mail: xyan919@收稿日期：

第38卷第5期黄小燕：基于经验回放Q-Learning的最优控制算法采用梯度下降算法求ft• 1353 •agent的状态。(2)

u是由动作构成的集合，任意状态表示

agent能采取的动作。0i+i = ft

十 a

其中，当采用Q-Learning学习方法时，(6)(x,

m)的

(3)

p

X奖赏。(4) /:

X«，概率。XUXX—R表示奖赏函数，pCx, 表示agent在状态z下采取动作《并转移到得到的立即XUXX后续状态乂以及后续状态对应的最优动作^组成的状态动

作对（V,

M)的Q值；当采用Sarsa算法时，0T穸为（X,

«)的后续状态^以及在当前策略下，后续状态:^与其采取的动作《'组成的状态动作对（乂，《)求解。K—[0, 1]表示状态转移函数，/U,

表示agent在状态■!下采取动作m并转移到y的可以

强化学习算法以最大化长期的累积奖赏为目标，因此

假设初始状态为:r。，那么在策略A下的累积奖赏可以表

示为TRh(x〇) =

UmEx ■>,-■>

i t+1)}r一 °°

t=0,h(xt) ,x(1)根据当前的策略L状态动作对的值函数，称为Q值

函数，其可以表示为J

x ^

X^u =

h(_x)：Ct (,x,u) =

p(_x，U~) +

y^'J

f (_X，U，X’

TVh (.X’、 〇x

ex最优Q值函数，幻可以表示为如式（3)所示

V

X?u — /i(x):Q (x，?/)—p(_x,u) +

yx ex

^^Jf(、x，u，xf')

mu，euaxQ*

(_x ,u) (3)2 ER-Q~Learning

算法2.1基于近似的值函数表示在精确的强化学习算法中，状态值函数和动作状态值

函数都采用表格式的存储方式，当MDP的状态空间无穷大

时，Q值函数无法精确地表示，当采用线性函数逼近的表

示方式时，Q值函数可以近似表示为Q(6t ,t ^

E{

x =

xt

,u =

ut) (4)n=0式中：企是状态动作对（xt, «t)的特征向量，ft是线性函

数逼近器的参数变量。为了求取参数变量ft,需要构造关于时刻t关于参数

变量的目标方程。当目标为最小化所有状态动作对的Q

值的均方误差时，目标函数可以表示为J = ^p(x,u) (Ct(x,u) —

Qt(x,u))2 (5)式中：/>(X,

M)---状态动作对（X,

M)在所有状态动作对中的所占的比例，这里用来计算该状态动作对的Q值误

差在总的均方误差中的比重。由于在实时系统中，在遇到

相同的样本时候会重复地被计算，因此，通常将其忽略。

Ctix,

u)—策略A下任意状态动作对（x, «)的真实

值，Q(x, «)—时刻t时任意状态动作对（x, «)的Q

值的估计。表本为(r

十

一

0T少)少

(7)因此，在连续状态空间情况下，值函数的参数可以根据下

面的公式进行求解ft+i = ft

十 a(r

十

少一

0T

argmaxQCfl*，4>(x?u)) (9)2.2

ER-OLearning 算法描述ER-Q-Leammg算法框架能提供一个通用的强化学习平

台，它通过在与系统的交互过程中不断地收集样本和存储

样本，并重复地将其发送给最优控制策略学习算法进行学

习，因此，它是数据高效的，同时采用基于梯度下降的最

优控制策略学习算法具有计算高效的优点。ER-Q-Leammg算法框架主要包含2部分：最优控制策

略学习算法和样本收集与利用算法。在每个时间步^

agent可以观察到一个转移样本（■!„ :cI+1，rI+1),并将其存储在数据集D中，agent在每个时间步选择的动作

是根据某种探索策略来选取的，这里选择来选

取动作其中，e为一个接近〇的正数，使得算法能以较大的概率选

择当前计算的最优动作，而以较小的概率进行探索，以实

现探索和利用的平衡。每隔K个时间步，数据集D中样本被取出来重复使用

N次，用于根据式（8)更新值函数参数。算法1:采样和ER算法输人：样本每次重复利用的次数N,每个情节的最大

时间步T,折扣因子y,步长参数《，探索因子基函数

序列A ,…，八；步骤1初始化参数向量0，t=l;步骤2初始化数据集D,数据集中采用路径数为Z,

当前样本的序号^样本总数为h步骤3对于每个时间步，根据式（10)选择动作《„

即以e的概率来选择动作空间U中的任一动作，以1 一e的

概率来选择

• 1354 •计算机工程与设计执行&，获得下一个状态^+1和立即奖2017

年步骤4

赏厂出;步骤5步骤6样本的序列号s =

nl +

t (11)(12)更新样本数据集DD =

D

J {l,t,s,xt ,ut,xt+i ,rt+i}

步骤7判断t是否为T的整数倍：如果是则调用算法2对参数向量进行学习，/=/十1;

否则，n系统的动态系统方程为+l;1

式中：g—.=ffsin(l) —

rfil (1)2/2 — ?ycos(l)F

4"3

-

rfil

cos2

(%)(工‘)

重力加速度，通常取值为g=9.

8

m/s2，a =

步骤8更新当前状态;步骤9当满足时，此时值函数收敛，根据式(9)生成最优策略。算法1是主算法，主要是在获得新样本后，将其加入

到样本数据集，并在当前时刻为T的整数倍时，调用算法

2在线学习算法对参数向量进行更新。算法2:值函数参数学习算法步骤1采用均匀分布从数据集D中读取样本S j JCt j tit ^ ^t^rl ? ^+1 I ?步骤2读取数据集中与样本U，f，/，^，&，

心十1，具有相同的心和的所有样本，取出使后继

状态具有最大Q值的贪心动作u*

= argmaxQCx^+i

,u)

(13)步骤3根据特征基函数，生成状态动作对（am，

f )对应的特征向量必1，…，九；步骤4根据式（8)对参数向量0更新；步骤5重复执行步骤1〜步骤4直到ZTN次；步骤6输出值函数参数向量0。2. 3

ER-〇Learning算法复杂度分析ER-Q-Learning算法中的最大的计算开销来自对参数向

量的更新，存储样本和计算策略的开销远小于参数更新的

计算开销，因此，将其忽略。对于任意一个样本，都需根

据式（8)对其更新，假设动作空间中离散动作的个数为

M，这时式（12)可以通过对有限离散动作的枚举来实现，

这个复杂度为〇(M)。在算法2中，对于每个路径/对应的

ZT个样本，都需要更新N次，因此总的计算开销为0

(M/TN)，由于算法1共循环执行了 /次，因此ER-Q-

Leaming算法总的计算复杂度为CKMZ2

TN)。3仿真实验

3.1实验描述仿真实验采用倒立摆，如图1所示。在图1中，倒立摆位于一个可以在水平轨道上进行左

右移动的小车上，倒立摆的一端固定在车上，另一端可以

绕轴在轨道平面内自由转动。实验的目标是求取一个控制

策略，能在某段时间内通过对小车施加不同方向的作用力，

从而使倒立摆处于不倒的状态尽可能的长。2.0

kg为倒立摆的质量，l—倒立摆的长度，取值为7=

1/

U+W。系统仿真时间为0.2

s。在每个时间步，如果

倒立摆与竖直方向的交角小于tt/2,则这个时间步得到立即

奖赏〇,否则，倒立摆倒下，获得立即奖赏为一

1。3.2实验参数设置每个情节的最大时间步T=l〇〇，折扣因子7=0. 9，步

长参数8，探索因子e=0.

1。状态空间是2维的，第一维为倒立摆的速度，其范围

为[ — ;r/2, +；r/2]，第二维为倒立摆的角速度

[一

1，+1]。动作空间是一维的，其范围为{—50N，0,

50

N丨，即可以对小车施加水平方向的作用力一50

N、0N

和 50

N。状态动作对的特征向量设置为：在当前状态下：T =

(1，％)，根据选择的动作W对应的基函数向量为

ACr)，…，九(1)，其它动作对应的基函数向量为〇，因

此，特征向量的长度为3w，其中非0元素个数为wA (又），•••，九（又），…，〇------：------，' (15)对应于动作w的基函数序列么Cr)，…，九Cr)可以进

一步表示为(e

I

x—^2i^x-y

I 2，e

I

^2^I 2

，e

I

^2^丨丨乞

，…，e

I

^2^I ^ )T (16)从式（16)中可以看出，这里设定〃

=9,其在二维网

格中的中心点为彳一?r/4，0，X {—1，0，十1}。每轮的经验回放次数N是样本集中每轮调用时样本可

以被重复学习的次数，为了验证其对算法的性能结果造成

的影响，即统计不同的N在不同情节数中能有效平衡的步

数的差异，对算法进行仿真，得到的结果见表1。表1经验回放次数N对平衡步数的影响情节数050100300N=5327130369N=1N=35N=55N= 151N=262

第38卷第5期黄小燕：基于经验回放Q-Learning的最优.控制算法

7oo

6

5

4

oo3

21oooooooooo^从表1中可以看出，当N的值取小于50时，当N越

靠近50,其平衡的步数随着回放次数的增加呈现较大斜率

地增长，而当N的值大于5Q后，其平衡的时间步伴随N

的增加而增加，但增加的速度变的较为缓慢，而由于在N

的值大于50后，算法的计算复杂度会显著地增加，因此，

算法选择N= 5€。3.3实验分析_..................• 1355 •-knA软轺迟鍚.为了验证ER-Q-Leaming算法的优越性，将ER-Q-

50 300 0 50 100 150 200 2Learning算法与经典的Q-Learning算法、Sarsa算法以及

BLSPf«进行比较，3种方法随着时间步的增加其平衡步

ig ------ER-Q-Learning

情节数-------Q-Learnir数的变化如图2所示。->------------- 2500------------'------------'------------>-------------'-----------^

2000 ■11500011；50 300 0 50 100 150 200 2ning -------情节数-~

ER-

Sarsa

Q-Leaming --------.........Q-LearBLSPI图2算法平衡步数比较从图2中可以看出，文中的ER-Q-Leaming算法随着

训练情节数的增加，平衡的时间步增加很快，在第300个

训练情节时，其平衡的时间步为2051，而Q-Leaming算

法、Sarsa算法和BLSPI算法所能平衡的时间步分别为:

1569、1443 和 1869。BLSPI算法在训练的初期平衡的时间步不如ER-Q-

Learning 算法、

Q-Learning 算法、

Sarsa 算法， 但在第 15〇

个情节后，其平衡的时间步增长很快，迅速超过了

Q-

Learning算法、Sarsa算法。这时因为BLSPI采用最小5乘

计算参数向量，其计算所需的矩阵在训练的初期与真实值

具有较大的误差，因此，平衡的时间步较少。随着训练情节的增加，矩阵越来越趋向真实值，所以

乎衡步很快地增加，同时，由于其矩阵也间接地保存了训

练样本，因此，在第150个情节处平衡的时间步超过了

Q-

Learning算法、Sarsa算法。从实验中可以发现，样本的直

接和间接利用（ER-Q-Leaming算法和BLSPI)效果优于直

接学习的算法（Q-Learning算法、Sarsa算法)。为了验证算法的收敛性，修改每个情节的最大时间步

为3000,当倒立摆持续平衡的时间步为3000时，该情节结

束；当连续多个情节平衡的时间步均为3000时，此时算法

收敛，即参数向量0接近或等于当情节数从〇增加到

300时，此时，3种算法对应的值函数参数0的均方误差的---------------------........................................RT

SPJ图3参数向量MSE误差变化

变化如图3所示。从图3中可以看出，ER-Q-Learning算法在115个情节

处参数向量的MSE不再发生变化，这表明此时算法已经收

敛。BLSPI在第140个情节处开始收敛，Q-Leaming算法

在第165个情节处收敛，4种算法中收敛速度最慢的是Sar-

^算法，在第200个情节时才收敛。从实验可以看出，ER-

Q-Learning

算法具有最 快的收 敛速度 ，从而 在实时 系统中

会表现更好的控制性能。4结束语为了提局实时控制系统的控制性能，提出了 一*种基于

经验回放的ER-Q-Leaming算法。为了解决连续状态空间

问题，对值函数采用线性函数逼近器近似。采用Q-Lear­ning 算法实现值函数参数向量的在线学习。 通过经验回放

方法对在线采集的样本进行存储，并重复地利用其进行值

函数参数向量的更新。描述了

ER-Q-Leaming算法框架，

并对其计算复杂度进行了分析。仿真结果表明，相比经典

的TD方法（Q-Leaming算法和Sarsa算法）以及BLSPI，

ER-Q-Leaming算法具有在有限时间内能平衡更多时间步，

同时收敛速度最快的优点s参考文献：[1] Bellman RE, Dreyfus SE. Applied dynamic programming

WQ. USA： Princeton UniYersity Press, 2015.[i] WANG Tao, ZHANG Huaguang. Stochastic linear quadratic

optimal control for continuous-time systems based on policy ite­ration [J]. Control and Decision, 2015, 30 (S)

； 1S74-1678

(in Chinese).[王涛，张化光.基于策略迭代的连续时间系统

的随机线性二次最优控制1674-1678.![J].控制^决策，2015, 30 (9):

[I.] Zhang HG,

gramming for

Liu DR,

control-algorithms

Luo YH,

and

al.

stability

Adaptive dynamic

[M]. London

pro­：

Springer-Verlag，2013

： 2:23-:.255:..(下转第1365页)

第38卷第5期何凯霖，丁晓峰：基于低维流形的人体行为跟踪方法报，• 1365 •tion using kinect data [M], MultiMedia Modeling. Berlin：

Springer, 2014： 473-483.[7] YIN Jianqin, TIAN Guohui, ZHOU Fengyu. Human activity

representation and recognition based on temporal order histo­gram in intelligent space [J], Chinese Journal of Computers,

2014，37 (2): 47〇_479 (inChinese).[尹建芹，田国会，周

风余.智能空间下基于时序直方图的人体行为表示与理解

[J].计算机学报，2014, 37 (2): 470-479.][8] Joey Wilson, Neal Patwari. See through walls： Motion trac­king using variance-based radio tomography networks [J],

IEEE Transactions on Mobile Computing, 2011，10 (5)

： 612­621.[9] Herath HMSPB, Perera PH, Fernando WSK, et al. Human

motion tracking under dynamic background conditions [C] //

9th International Conference on Industrial and Information Sys­tems, 2013

： 1-6.[10] SUN Jingle, TANG linbo, ZHAO Baojun, et al. A new par­ticle filter tracking algorithm based on rayleigh distribution

[J], Journal of Electronics Information Technology, 2013,

35 (4): 763-769 (inChinese).[孙景乐，唐林波，赵保军，

等.基于瑞利分布的粒子滤波跟踪算法[J].电子与信息学(上接第1355页）2013，35 (4): 763-769.][11] Ades M, Van Leeuwen PJ. The equivalent-weights particle

filter in a high-dimensional system [J], Quarterly Journal of

the Royal Meteorological Society, 2015, 141 ( 687

)：

2694-2707.[12] Su Yingya, Zhao Qingjie, Zhao Liujun, et al. Abrupt mo­tion tracking using a visual saliency embedded particle filter

[J]. Pattern Recognition, 2014, 47 (5)： 1826-1834.[13] Leopoldo Perez de Isla, Gisela Feltes, Joel Moreno, et al.

Quantification of left atrial volumes using thre亡dimensional

wall motion tracking echocardiographic technology： Compari­son with cardiac magnetic resonance [J], European Heart

Journal-Cardiovascular Imaging, 2014, 15 (3)

： 793-799.[14] Yonemoto H, Murasaki K, Osawa T, et al. Egocentric ar­ticulated pose tracking for action recognition [C] //14th IA-

PR International Conference on Machine Vision Applications,

2015： 98-101.[15] Britton Wolfe, Monica Gloudemans. A comparison of algo­rithms for handheld wand tracking [J]. Applied Artificial In­telligence ：An International Journal, 2014, 28 ( 9

)： [J], Journal of Computer Research and Development,

2015, 52 (12)： 2764-2775 (inChinese).[钟珊，刘全，傳

启明，等.一种近似模型表示的启发式Dyna优化算法[J].

计算机研究与发展，2015, 52 (12): 2764-2775.][9] Robert C, Casella G. Monte Carlo statistical methods [M].

New York： Springer Science Business Media, 2013.[10] Lin LJ. Self-improvement based on reinforcement learning,

planning and teaching [C] //Proceedings of the Eight Inter­national Workshop in Machine Learning, 2014

： 323-327.[11] Cunha J, Serra R, Lau N，et al. Batch reinforcement learning

for robotic soccer using the Q-batch updat^rule [J], Journal of

Intelligent Robotic Systems, 2015, 80 (3-4)： 385-399.[12] Yao H, Szepesvari C. Approximate policy iteration with li­near action models [C] //AAAI，2012.[13] ZHOU Xin, LIU Quan, FU Qiming, et al. Batch least-

squares policy iteration [J], Computer Science, 2014，41

(9): 232-238 (inChinese).[周鑫，刘全，傳启明，等.一

种批量最小二乘策略迭代方法[J].计算机科学，2014, 41

(9)： 232-238.][4] Bertsekas DP. Constrained optimization and Lagrange multip­lier methods [M]. Pittsburgh： Academic Press, 2014.[5] WEI Hua, LONG Danli, LI Jinghua. Policy iteration-approxi­mate dynamic programming for large scale unit commitmentproblems [J]. Proceedings

〇£ the CSEE, 2014, 25 (34):

4420-4429 (inChinese).[韦化，龙丹丽，黎静华.求解大规

模机组组合问题的策略迭代近似动态规划[J].中国电机工程

学报，2014，25 (34): 4420-4429.][6] WAN Haichuan, HE Zhiming, SONG Tengfei. An improved

value-iteration algorithm based on dynamic planning theory

[J]. Radar Science and Technology, 2015，13 (5)

： 501-507

(inChinese).[万海川，贺知明，宋腾飞.基于动态规划理论

的改进型价值迭代算法[J].雷达科学与技术，2015, 13

(5)： 501-507.][7] Hasselt H, Mahmood A, Sutton R. 0££-policy TD (X) with a

true online equivalence [ C] //Conference on Uncertainty in

Artificial Intelligence, 2014.[8] ZHONG Shan, LIU Quan, FU Qiming, et al. A heuristic

Dyna optimization algorithm using approximate model represen­