计算机学报                                          2018 年 another  extreme  point.  It  is  also  difficult  for  SGD  to  choose  a  suitable  learning  rate.  A  learning  rate  that  is  too small leads to a slower convergence rate, and too large leads to an obstacle to convergence. If different dimensions of  training  data  have  different  characteristics  and  value  statistics  space,  different  dimensions  should  adopt different learning rates. Thus, the drawback of the stochastic gradient descent method is that it sometimes brings about the optimization oscillation, which makes the number of iterations increases and the convergence rate slows down.  In  this  paper,  we  proposed  an  Adaptive  Learning  Rate  on  Integrated  Stochastic  Gradient  Descent  - ALRI-SGD,  which  makes  two  improvements  on  the  traditional  SGD:  Add  the  gradient  at  time  t -1  to  the current  t   time  gradient,  to  update  the  parameters  as  an  integrated  gradient.  Based  on  the  prediction  of  model parameters,  the  historical  gradient  information  is  used  to  calculate  the  gradient  of  the  current  time-step.  This improvement makes the oscillation reduced in the direction with a larger gradient, and the speed of approaching an extremum faster in the direction with a smaller gradient. In the same dimension, it makes the parameter update faster before it approaches the extremum. If the parameter exceeds the extremum and the oscillation occurs, it will actively reduce the update speed; the learning rate of each dimension is dynamically calculated according to the historical  gradient  sum  of  squares  of  the  dimension.  The  cumulative  square  sum  of  the  gradients  gradually increases as the training progresses, so that the learning rate will gradually decrease. The ALRI-SGD based  Q-learning algorithm was used to enhance the classical Mountain Car tasks and the Pole Balancing problem, which were  compared  with  SGD-based  Q -learning  algorithm.  The  experimental  results  showed  that  ALRI-SGD  can dynamically  match  the  gradient  differences  of  model  parameters  in  different  dimensions  and  can  update  the learning-rate  automatically  to  adapt  to  the  data  features  of  different  dimensions.  The  algorithm  has  obvious advantages in both convergence process and convergence efficiency.  There are still some problems to be further studied and improved in this paper's work, including: the convergence performance of the algorithm is sensitive to the  historical  gradient  discount  rate,  and  its  setting  still  needs  further  study;  in  the  convergence  proof  of  the ALRI-SGD method, the convex function is assumed to be Its application brings theoretical restrictions. Keywords reinforcement learning; ALRI-SGD; Adaptive learning-rate; Parameters prediction;  Q -Learning  1  引言 强化学习(Reinforcement  Learning,  RL)的基本思想是通过最大化智能体(agent)从环境中获得的累计奖赏，学习到达目标的最优策略。强化学习可以模仿人类从婴儿到成年的学习过程，这种学习方式更接近人类的学习过程，如感觉和直觉的学习[1]。谷歌公司将具有感知能力的深度学习和具有决策能力的强化学习结合，形成了深度强化学习(Deep Reinforcement Learning, DRL)。AlphaGo Zero[2]通过深度强化学习方式自我学习和完善，不再使用人类知识学习围棋，以100:0 击败了此前版本的AlphaGo。强化学习目前已经广泛应用于仿真模拟[3]、优化与调度[4,5]、游戏博弈[6,7]等领域。 梯度下降(Gradient  Descent,  GD)是求解强化学习优化问题最常用的方法，用于逼近最小偏差模型。梯度下降算法包括全量梯度下降、随机梯度下降和小 批 量 随 机 梯 度 下 降 。 其 中 随 机 梯 度 下 降(Stochastic  Gradient  Descent,  SGD)每次随机选择一个样本在线更新模型参数，单次学习的速度快，适合于在线强化学习。 由于目标函数在不同维度上梯度变化率的差异，SGD 可能使优化目标收敛到另外的极值点，这种震荡导致收敛过程复杂化，迭代次数增多，收敛速度变慢。Dauphin  等[8]认为，这种现象是目标函数的鞍点造成的。另外，SGD 难以选择合适的学习率，学习率太小导致收敛速度变慢，太大会阻碍收敛[9]。实际应用中一般采用逐步降低学习率的方式，对凸函数和非凸函数都能保证收敛到极值。但是人工安排学习率需要根据训练数据集的特征提前定义列表或阈值[10,11]，否则不能反映数据集特性，因此不适合不同场景下强化学习模型参数的自适应优化。另外，如果不同维度的训练数据有不同特点和取值统计空间，则不同维度应该采用不同的学习率。这些存在的问题，都要求根据具体的应用场景，人工对 SGD 方法进行优化。 近年来，随着深度神经网络的发展，梯度下降作为监督学习的模型优化方法再次成为研究热点。Qian 等[12]提出 Momentum 方法，在更新模型参数时，对当前梯度与上次梯度方向相同的维度进行梯度加强，与上次梯度方向不同的维度进行梯度减弱，以减少震荡获得更快的收敛速度。NAG 方法[13]在计算参数的梯度时，在损失函数中减去梯度项，将其作为下一次参数的预估，使参数更新速率自适应梯度变化，显著提高了循环神经网络在一些任务上的性能。Adagrad 方法[14]针对不同维度自适应调整学习率，对低频出现的参数增加学习率，高频出现计算机学报        金海东等：一种带自适应学习率的综合随机梯度下降 Q -学习方法                         3 的参数减少学习率，适合处理稀疏数据。Dean  等人[15]发现，Adagrad 方法能提升 SGD 的鲁棒性。谷歌公司使用 Adagrad 方法训练大规模多层卷积神经网络，能识别 Youtube 视频中的猫。Pennington  等[16]使用 Adagrad 方法训练 GloVe 单词向量，低频词自适应 使用更大的学习率。 Adadelta 方法1是Adagrad 的扩展，仅计算有限时间区间内的梯度累积和，解决 Adagrad 学习率单调下降问题。 由于强化学习自身的特点，上述针对监督学习的 SGD 改进难以用于强化学习。从机器学习的角度看，强化学习呈现出了一系列挑战。强化学习在与环境交互的同时进行在线学习，因此需要一个效率很高的模型。在监督学习算法中，假设数据样本是独立的，但是在强化学习中数据是高度序列化的。与监督学习假设数据服从同一分布不同，按照 GPI流程[1]，强化学习训练样本分布随着算法学习到的新行为而改变，要优化的是非稳态目标函数。此外，强化学习要从稀疏、有噪声和延迟的奖励信号中学习。这些特点，给强化学习的值函数拟合模型以及基于 SGD 的优化算法带来很大挑战，一些基于监督学习的 SGD 改进方法难以用于强化学习，例如深度 Q -网络(Deep  Q -Network,  DQN)[4,5]采用的是传统 SGD 进行反向误差传播。本文从基于线性值函数逼近的强化学习模型出发，针对 SGD 存在的问题，提出一种带自适应学习率的综合随机梯度下降 ALRI-SGD 方法，对 SGD 做了两方面改进：1)在基于参数预测的基础上，利用历史随机梯度信息综合计算当前时间步的参数更新梯度；2)根据不同维度的历史梯度平方和，在每个时间步动态计算不同维度的学习率。本文在一定的数学约束条件下证明了 ALRI-SGD 方法能够收敛，并把 ALRI-SGD 方法用于线性函数逼近的离策略 Q-学习算法，求解强化学习中经典的 Mountain Car 和平衡杆问题，并与基于 SGD 的 Q-学习算法进行了实验比较。ALRI-SGD 能动态匹配目标函数在不同维度上的梯度差异，并使梯度学习率自动更新以适应不同维度的数据特征。基于 ALRI-SGD 的 Q-学习算法在收敛效率和稳定性两个方面，都有显著提高。 2  背景知识                                                              1Matthew  D.  Zeiler.  ADADELTA:  An  Adaptive  Learning  Rate Method. arXiv preprintarXiv:1212.5701, 2012.  2.1  强化学习 强化学习通过与环境的交互，来实现学习目标。“学习者”称为 agent，agent 之外与之交互的一切要素都称为环境(environment)。目标是使 agent 在与环境交互过程中获得最大累积奖赏即回报[7]。借助马尔可夫决策过程(Markov  Decision  Process，MDP)，可以形式化 RL 问题[17]。 定义 1.  马尔科夫决策过程 MDP 为四元组(S, A, r, f) ，其中： (1) S 是环境中所有状态的集合。ts ÎS 表示agent 在 t 时刻的状态；  (2) A 是 agent 在环境 S 中可执行动作的集合。ta ÎA 表示 agent 在 t 时刻采取的动作； (3) r: S ´A ®R 是奖赏函数。 ( , )t t tr =rs a 表示agent 在状态ts 执行动作ta 获得的立即奖赏，奖赏一般为标量； (4) f: S ´A´S ®[0,1] 为状态转移概率函数。1( , , )t t tf s a s+表示 agent 在状态ts 执行动作ta 转移到下一状态t1s+的概率。 在 RL 中，策略p: S ®A是从状态空间到动作空间的映射，表示 agent 在状态ts 执行动作ta ，并以概率1( , , )t t tf s a s+转移到下一状态t1s+，同时接受来自环境的立即奖赏tr 。根据奖赏的累积方式，有几种不同类型的回报[18]，其中折扣回报是从t 时刻开始到T 时刻情节结束时带折扣率的累积回报，折扣回报定义为： ' ''Tt tt tt tR gr-=å  其中g Î[0,1]用于衡量未来奖赏对回报的影响，可以直观地解释为 agent 在考虑回报时的“远视”程度，或者解释为对未来奖赏不确定性的考虑程度[19]。 策略 p 的状态-动作值函数 Q(s, a)p是在当前状态 s 下执行动作 a ，并遵循策略p 直到情节结束，agent 获得的回报，表示为： ( , ){ , ,}t t tQ s a E R s s a ap= | = =p  对于所有的状态-动作对，如果策略*p 的期望回报大于或等于其他所有策略的期望回报，则称*p 为最优策略。强化学习任务的目标是求解最优策略*p 以获得最大期望回报。最优策略可能有多个，但都有相同的最优状态-动作值函数： { }*( , ) max , ,t t tQ s a E R s s a ap= | = =p  计算机学报                                  计算机学报                                          2018 年 最优状态-动作值函数满足贝尔曼最优方程( Bellman optimality equation)，即： { }* *''( , ) max ( ', ') ,s SaQ s a =E r +gQ s a |s a  经典 RL 算法一般使用贝尔曼方程迭代求解Q值函数： { }1 ' 1'( , ) max ( , ') ,t s S t taQ s a E r gQ s a s a+ += + |  (1) Q 值迭代算法从任意0Q 开始迭代，在第 l 轮的迭代中，利用式(1)更新 Q 值，式(1)也称为 Q 值迭代映射。 定义 2.  两轮迭代之间的 Q 值之差，称为时间差分(Temporal Difference, TD)： 11'( , ) ( , )max ( , ') ( , )t t tt t taQ s a Q s ar Q s a Q s adg++-= + -탌     (2) 当 i ® ¥时，*iQ ®Q ，即通过不断迭代使得状态-动作值函数*Q 最终收敛，并求得最优策略： * *arg max ( , )a ApQ s aÎ 2.2  线性函数逼近 大规模状态空间的强化学习任务中，无法精确存储每一个状态回报值，因此不能采用基于数据表的 Q 值迭代算法  [19]。当前的一些研究成果，如著名的 DQN，其值函数估计部分采用参数方程形式的近似值函数。 由于强化学习过程是在线的、动态的，训练集是 agent 与环境交互动时动态得到的，因此要求函数逼近方法必须能够从增量式的训练集中学习，另外，还要求能够解决目标函数不确定的问题。在基于梯度下降的函数逼近方法中，由于线性函数逼近计算量较小，基函数形式简单，且易于分析算法的理论性质[19]，近年来，在强化学习中得到广泛应用。 假设 Q 值函数逼近器包含一个 n 维的参数向量θ 。近似函数逼近器可以表示为近似映射 F ，:nF R ® C ，其中 Rn 是 n 维的参数空间，C 是 Q 值函数空间，则每个参数向量θ都对应一个近似的Q值函数空间： ˆQ(s, a) =F(θ)  也可以等价写成关于状态-动作对的形式： ˆQ(s, a) =F(θ)(s, a)  其中 F(θ)(s,a)表示近似 Q 值函数 F(θ) 对状态-动作对 (s,a) 的值评估。因此，这种近似表示方法不需要存储每一个状态动作对的Q 值，只需要存储一个 n维的向量θ。如果状态-动作空间是离散的，一般 n远小于|S |×|A| ，因此近似值函数相对目标值函数，存在一定的近似误差。 线性 Q 值函数逼近器一般包含 n 个基函数(Basis Functions, BFs)，1 2, , , :nf f fS ´A ®R 以及一个 n 维的参数向量θ ，基函数与参数向量之间满足线性关系。线性条件下，在策略p 下，状态-动作对 ( , )t ts a 的近似 Q 值的计算如下： 10( , ) ,nt t t n t ttnQs a E r s s a apg¥+ +=ì ü= í| = = ýî þå        (3) [ ]1( ) ( , ) ( , ) ( , )nTt t l t t t tlF s a s a s a=» θ= å φ θ=φ θ   (4) 其中 [ ]1 2( , ) ,( , ), ( , ), , ( , )Tnφs a = φs a φs a φs a 是 n 维的基函数向量。在一些文献中，基函数φ(s,a)也称作状态-动作对(s,a) 的特征向量[18]。 线性函数逼近条件下，式(2)表示的TD 误差td为： 1 1( , ') ( , )T Tt t t t t t tdr gs a s a+ += + φ θ-φ θ     (5) 3  强化学习中的随机梯度方法 梯度下降法是利用负梯度方向来寻找每次迭代的搜索方向，使得迭代向目标函数增长最快的方向优化。 3.1  随机梯度下降 随机梯度下降(SGD)的简单形式如下： 1( ) ( ) ( )t tf k f k f kka+¶= -¶ 其中 f(k) 是目标函数， ( )kf k¶¶是 f(k) 的梯度，a是学习率。通过 SGD 方式，可以逐步逼近目标函数 f(k) 的极值。 在基于梯度的 Q-学习算法中，需要假设近似函数 F(θ) 关于参数θ 可导。由于强化学习要优化的是非稳态目标函数，而函数逼近属于监督学习的技巧，需要静态训练样本集。为了得到基于梯度的 Q-学习算法，在当前状态ts 执行动作ta 后，需要假设能够获得当前状态-动作对真实回报值*( , )t tQ s a ，以及后续的状态k1s+及奖赏值k1r+。因此，构造的强化学习训练样本为：*( , ) ( , )t t t ts a ®Q s a 。 定义 3.  训练样本集与拟合模型之间的均方误差 MSE 为： ( )2*0( , ) [ ( )]( , )Tt t t t ttMSE Q s a F s a=å- θ  其中*( , )t tQ s a 是样本 ( , )t ts a 的真实值， ( )tFθ 是基于参数tθ 的拟合模型。 强化学习算法的目标是使得当前 Q 值函数[ ( )]( , )t t tFθs a 与极值函数 *( , )t tQ s a 之间的均方差计算机学报————— 本课题得到国家自然科学基金(61772355, 61702055, 61303108, 61373094, 61472262, 61502323, 61502329)、江苏省高等学校自然科学研究重大项目(17KJA520004)、吉林大学符号计算与知识工程教育部重点实验室资助项目(93K172014K04, 93K172017K18)、苏州市应用基础研究计划工业部分(SYG201422)、江苏省高等学校自然科学研究项目重大项目（17KJA520004）、苏州市重点产业技术创新-前瞻性应用研究项目（SYG201804）资助．  金海东,男,1973 年生,博士研究生,主要研究方向为强化学习、深度学习和深度强化学习,Email: haidong@suda.edu.cn .刘全(通讯作者),男,1969 年生,博士,教授,博士生导师,中国计算机协会(CCF)高级会员,主要研究方向为强化学习、深度强化学习和自动推理. E-mail: quanliu@suda.edu.cn.  陈冬火,男,1974年生,博士,讲师，中国计算机协会(CCF)会员,主要研究方向为强化学习、软件形式化方法,Email: dhchen@suda.edu.cn.   一种带自适应学习率的综合随机梯度下降 Q-学习方法  金海东 1)     刘全 1),2),3),4)     陈冬火 1)  1) (苏州大学计算机科学与技术学院  江苏  苏州 215006) 2) (软件新技术与产业化协同创新中心  南京  210000) 3) (吉林大学符号计算与知识工程教育部重点实验室  长春  130012) 4)(苏州大学江苏省计算机信息处理技术重点实验室  江苏  苏州  215006) 摘 要  在线强化学习中，值函数的逼近通常采用随机梯度下降(Stochastic Gradient Descent ,SGD)方法。在每个时间步，SGD方法使用强化学习算法获取的随机样本，计算损失函数的局部梯度，单次模型参数更新的计算量小，适合在线学习。但是，由于目标函数不同维度存在梯度差异，SGD 方法会产生优化震荡，导致迭代次数增多，收敛速度变慢甚至不能收敛。提出一种带自适应学习率的综合随机梯度下降方法(Adaptive Learning Rate on Integrated Stochastic Gradient Descent, ALRI-SGD)，对 SGD 做了两方面改进：1)在基于参数预测的基础上，利用历史随机梯度信息综合计算当前时间步的更新梯度；2)根据不同维度的历史梯度信息，动态计算每个维度的学习率。在一定的数学约束条件下，证明了 ALRI-SGD 方法的收敛性。把ALRI-SGD 方法与基于线性函数逼近的离策略 Q -学习算法结合，用于求解强化学习中经典的 Mountain Car 问题和平衡杆问题，与基于 SGD 的 Q -学习算法进行实验比较。实验结果表明，ALRI-SGD 方法能动态匹配模型参数在不同维度上的梯度差异，并使学习率自动更新以适应不同维度的数据特征。ALRI-SGD 方法在收敛效率和收敛稳定性两个方面都有提升。 关键词  强化学习；综合随机梯度下降；自适应学习率；参数预测；Q -学习 中图法分类号  TP18     Adaptive learning-rate on Integrated Stochastic Gradient Decreasing Q-Learning JIN hai-dong1)   LIUquan1),2),3),4)   CHEN dong-huo1) 1) (School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu, 215006) 2) (Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing, 210000) 3) (Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, 130012) 4) (Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, Suzhou, Jiangsu, 215006) Abstract The basic idea of reinforcement learning is to learn the best strategy to reach the goal by maximizing the cumulative rewards that agents receive from the environment. In the online reinforcement learning method based on value function approximation, SGD is used to update the weight of the value function, that is, to update the model  parameters  in  the  negative  gradient  direction  and  to  minimize  the  loss  function.  On  each  time-step  a random sample is obtained according to the ε-greedy strategy to update the model parameters. Therefore, each update requires a small amount of computation and which is suitable for online learning. Due to the difference in gradient rate of the objective function in different dimensions, SGD may make the optimization goal converge to 计算机学报        金海东等：一种带自适应学习率的综合随机梯度下降 Q -学习方法                         5 MSE 最小。构造损失函数 ( )tJ θ 为： ( )2*( ) ( , ) [ ( )]( , )t t t t t tJ θQ s a -Fθs a  损失函数相对参数q梯度为： ( )( )2**( ) ( , ) [ ( )]( , )=-2 ( , ) [ ( )]( , ) [ ( )]( , )t ttt t t t t tt t t t t t t tJ Q s a F s aQ s a F s a F s a¶ ¶¶ ¶¶¶= --θ θθθ θθ θ 采用 SGD 方法进行参数更新： 11 2*( )( , )[ ( )]( , )[ ( )]( , )ttt t t tt tt t t t tt t tJQ s aF s aF s aaa¶+ ¶¶¶= -æ ö= + ç ÷ç ÷-è øθθθ θ θθ θθ   (6) 这里ta 是t 时刻的学习率。 *( , )t tQ s a 其实是未知的，可以通过式(1)的计算来近似替代。通过这种替代，得到近似 Q-学习算法的更新式： 11 1'max[ ( )]( , ')[ ( )]( , )[ ( )]( , )ttt t tat t t t tt t tr F s aF s aF s aga++ +¶¶æ+ ö= + ç ÷ç ÷-è øθθθθ θθ  (7) 式(7)中，求解了t 时刻*( , )t tQ s a 的近似值ˆtQ 。1 1'ˆmax[ ( )]( , ')t t t taQ r gF s a+ += + θ 因此， *1 1'( , )ˆmax[ ( )]( , ')t tt t t taQ s aQ r gF s a+ +» = + θ        (8) t 时刻 ( , )t ts a 的近似损失函数ˆ( )tJ q 改写为： [ ] [ ]21 1'ˆ( , ) ( , )max[ ( )]( , ')[ ( )]( , )t t t t t tt t tat t tJ s a J s ar F s aF s ag+ +»æ+ ö= ç ÷ç ÷-è øθ θθθ         (9) 3.2  线性函数的随机梯度 线性条件下，式(8)表示的近似极值函数ˆtQ 可以简化为： 1 1'ˆmax( ( , ')Tt t t taQ r gs a+ += + φ θ 式(9)表示的t 时刻( , )t ts a 近似损失函数简化为： 21 1'max ( , ')( )( , )Tt t tatTt t tr s aJs ag+ +æ +ö=ç ÷ç ÷-è øφ θθφ θ    (10) 因此： ( )1 1'( )ˆ-2 ( , ) ( , )max ( , ')-2 ( , )( , )ttTt t t t t tTt t tat tTt t tJQ s a s ar s as as ag¶¶+ += -æ +ö=ç ÷ç ÷-è øθθφ θ φφ θφφ θ 把 SGD 用于式(4)表示的线性函数逼近器，式(7)的参数更新可以简化为： 1 1'1max ( , ')( , )( , )Tt t tat t t t tTt t tr s as as aga+ ++æ +ö= +ç ÷ç ÷-è øφ θθ θ φφ θ (11) 式(11)的含义是使用样本ˆ( , )t t ts a ®Q 对参数向量θ采用随机梯度下降方法进行更新，可以形式化表示为： ( )1ˆ;( , );tt t t t t t ta ¶s a Q+ ¶= - ×θθ θ θ      (12) 其中ta 是t 时刻的参数学习率。 定理 1.  如果目标函数 ( )tJ θ 是凸函数，并且 ˆtQ是*( , )t tQ s a 的无偏估计，随机梯度方法 ( )1ˆ;( , );tt t t t t t ta ¶s a Q+ ¶= - ×θθ θ θ 以概率 1 收敛到θ* 。 式 (11) 表 示 的 TD( 0 )算 法 ， 由 于ˆtQ 不 是*( , )t tQ s a 的无偏估计，随机梯度下降方法在这种情况下，不能在理论上证明可以收敛到局部最优。尽管如此，这类自举算法在一些实际应用中能获得更快的收敛速度，文献[1]对此有详细的实验研究。 4  综合随机梯度下降 由于目标函数在不同维度上梯度变化率的差异，SGD 更新值的方差很大，频繁更新之后，SGD可能使目标函数跳入另一个极值。这种震荡使得收敛到特定极值的过程复杂化，导致迭代次数增多，收敛速度变慢甚至发散。 4.1  综合随机梯度 如果在某时刻t ，损失函数 ( )tJ θ 在 i 方向的梯度远大于 j 方向的梯度，由于这种陡谷在极值中经常出现[8]，随机梯度在i 方向由于梯度很大导致不断震荡，收敛过程不稳定，而在 j 方向由于梯度很小导致更新缓慢，并且总体收敛速度由梯度较小的 j方向决定。一种改进方案是在当前t 时刻梯度基础上加上t -1时刻的梯度，作为θ更新的综合梯度，记作I 。在i 方向上，在震荡阶段由于前后两次梯度方向相反，梯度是抵消的，而在 j 方向上，在逼近极值阶段由于前后两次梯度方向相同，梯度是累加的。采用综合梯度的效果是，在梯度较大的i 方向减小了震荡，而在梯度较小的 j 方向上逼近极值的速度会加快。在同一个维度上，这种改进使得参数计算机学报                                  计算机学报                                          2018 年 在接近极值之前更新速度不断加快，在超过极值而产生震荡时，会主动降低更新速度。 定义 4.  目标函数 J(θ) 在 t 时刻的综合梯度tI为： 10 1 2, ( )tt t tl ¶J- ¶= = × +θI 0 I I θ  其中 l 是 t -1时刻综合梯度历史折扣率，( )ttJ¶¶θθ是目标函数在t 时刻的梯度。 定义 5.  基于线性函数逼近的TD(0)算法中，t时刻综合梯度tI 为： 1 1'1max ( , ')( , )( , )Tt t tat t t tTt t tr s as as agl+ +-æ +ö= × -ç ÷ç ÷-è øφ θI I φφ θ 因此，基于综合梯度的θ更新式为： 11 1'1max ( , ')( , )( , )t t t tTt t tat t t t tTt t tr s as as aaga l++ +-= -æ æ +öö= -ç × -ç ÷÷çç ÷ ÷-èè ø øθ θ Iφ θθ I φφ θ 其中ta 是t 时刻的学习率。参数更新过程中，算法需要保存t -1时刻的综合梯度t -1I 。 上述更新过程很好地适应了不同维度的梯度变化。但是如果在达到极值之前沿着梯度方向盲目加快更新速度，很容易错过极值，实验效果并不令人满意。计算梯度时，如果能够提前得到下一个时间步参数t +1θ 的值，并以t +1θ 计算损失函数的梯度，就可以预知梯度的变化，在到达极值之前减速从而避免错过极值。由于实际上无法预知t +1θ 的值，可以使用t t1l-θ- I 作为t +1θ 的近似预计。 信息回放机制[20]通过存储并利用历史样本，来消除训练数据的关联性。与之相比，综合随机梯度方法用于降低值函数逼近过程中的震荡，利用的是历史梯度信息，并且算法不需要增加额外的空间。 定义 6.  目标函数 J(θ) 在t 时刻基于参数预测的综合梯度tI 为： 0I= 0, ( )11 21tt t t tl ¶J l- ¶-= + -θI I θ I     (13) 其中 l 是 t -1时刻综合梯度历史折扣率，( )ttJ¶¶θθ是目标函数在t 时刻的梯度。 为表示方便，设： ( )( )1 1 1'1max ( , ')       ( , )Tt t t t taTt t t tr s as ad g ll+ + --= + -- -φ θ Iφ θ I 对于线性函数逼近的TD(0)算法，式(13)可简化表示为： 1( , )t t t t tl ds a-I= I- φ 定义 7.  目标函数 J(θ) 在时间步t 对第i 维度iq基于参数预测的综合梯度t,iI 为： ( )0,1, 1, 210,iit i t i t tl ¶J l- ¶-== + -θII I θ I      (14) 因此，在线性函数逼近的TD(0)算法中，时间步t 对第i 维度iq 基于参数预测的综合梯度t,iI 为：  , 1,( , )t i t i t i t tl ds a-I= I- φ        (15) 这种改进的综合梯度计算方法，使得参数更新速度可以自动适应不同维度的梯度变化。 t 时刻第 i 维度参数t +1,iθ 更新规则为： t1,i t,i t,ia+θ=θ- I           (16) 4.2  自适应学习率 在t 时刻，式(16)对所有维度都采用了相同的学习率a ，并不适合具有不同数据特征的不同维度上的强化学习任务。如果将学习率a 按不同维度进行修正，t 时刻第i 维度的学习率t,ia 调整为： ,,t it iaa ®G+ Á 其中 G 是一个向量，t,iG 表示从 0 时刻到 t 时刻J(θ) 对于第 i 维参数iθ 梯度的累积平方和。Á 是常数平滑项，以避免分母为 0 的情况。这里分母开平方是经验式，否则试验中容易导致不收敛等问题。对于强化学习中的线性函数逼近器，t 时刻第i 维度的t,iG 为： 0,0iG=  2 2, 1,( , )t i t i t i t tds a-G=G+ φ           (17) 因此，时间步t 在维度i 上的学习率t,ia 为： 2 2, 1,( , )t i t i t i t ta a ds a-= G+ φ+ Á        (18) 改进后的参数更新式为： t1,i t,i t,i t,ia+θ=θ- I 累积的梯度平方和随着训练过程逐步增大，式(18)计算的学习率t,ia 会逐步减小。 定义 8.  在强化学习模型参数更新方法中，如果采用式(15)所示的基于参数预测的综合随机梯度，并采用式(18)所示的自适应学习率，称为带自适应学习率的综合随机梯度下降(ALRI-SGD)方法。 算法 1.  基于 ALRI-SGD 的 Q-学习算法 输入：折扣因子g，探索方案{ }0kke¥= 基函数1 2, , , :nf f fS ´A ®R 计算机学报        金海东等：一种带自适应学习率的综合随机梯度下降 Q -学习方法                         7 1：初始化，如：0θ=0 ，a =0.1，b =0.9 ，0G=0 ，0I=0  2：获取初始状态0s  3：FOR  每个时间步 t =0,1,2,... 4：'arg max ( , ')a t t ttta Q s aaaeeìÎ= íÎî    以概率1-A中的均匀随机动作  以概率 5：采取动作ta ，观测下一状态t1s+和奖赏t1r+ 6：FOR  tθ 的每个维度i ： (a)  式(15)计算t,iI  (b)  式(17)计算t,iG  (c)  式(18)计算t,ia (d) t1,i t,i t,i t,ia+θ=θ- I 由于ALRI-SGD方法自动调节不同维度的学习率，基于 ALRI-SGD 的 Q-学习在特征稀疏的维度上采用相对较高的学习率，其他特征采用相对较低的学习率。这种基于预测的综合随机梯度更新方法，能避免过快的更新速度，并能提高算法的响应能力，同时参数更新速度自动适应不同维度的梯度变化。存在的问题是，式(18)分母项积累了梯度平方和，导致随着训练过程学习率不断缩小甚至渐进为 0，有可能导致的问题还需要进一步研究。 5  理论分析 从理论上证明基于ALRI-SGD参数更新方法能够收敛，需要满足一定的数学约束条件。 假 定 1.  式 (8) 中 ， 假 定ˆ( , )t tQ s a 是 值 函 数*( , )t tQ s a 的无偏估计。 如蒙特卡洛方法是无偏估计，而TD(l) 值函数估计方法是有偏估计。虽然收敛性证明需要无偏估计的假定，但在一些实际应用中，基于 on-policy或者 off-policy 的自举算法也能够与线性函数近似的梯度下降方法可靠结合，并收敛至一个解。 假定 2.  如果损失函数 J(θ) 满足如下条件，称其满足 Lipschitz 连续： 1 2 1 2J(θ) -J(θ) £Lθ-θ  其中 L 是Lipschitz常数，对于一个确定的损失函数，L 是定值。假定 2 对损失函数的值相对参数的变化率进行了限制。 假定 3.  如果 J(θ) 的梯度函数满足值为 b 的Lipschitz 连续，称 J(θ) 为 b 平滑： 2 21 2 1 2¶J( ) ¶J( ) b¶ ¶- £ -θ θθ θ θ θ  其中2Tθ=θθ。假定 3 对损失函数梯度的变化进行了限制：损失函数梯度之差的模长，不超过 b 倍模型参数之差的模长。 定理 2.  满足 b 平滑的损失函数有如下性质： 1 2 2 1 22121 2( ) ( ) ( ) ( )TJ J Jb¶¶- - -£ -θθ θ θ θ θθ θ     (19) 证明.  构造插值函数2 1 2g(t) =J(θ+t(θ-θ)) ，其关于t 的导数为： 2 1 2 1 2'( ) ( ( )) ( )Tg t J t¶¶= + - -θθ θ θ θ θ  把函数值之差转化为积分： 11 20J(θ) -J(θ) =g(1) -g(0) = òg'(t)dt  12 1 2 1 20( ( )) ( )TJ t dt¶¶= ò+ - -θθ θ θ θ θ  代入式(19)左侧： 1 2 2 1 2( ) ( ) ( ) ( )TJ J J¶¶- - -θθ θ θ θ θ  12 1 2 1 202 1 2( ( )) ( )( ) ( )TTJ t dtJ¶¶¶¶+ - -=- -òθθθ θ θ θ θθ θ θ 12 1 2 1 2012 1 20( ( )) ( )( ) ( )TTJ t dtJ dt¶¶¶¶+ - -=- -òòθθθ θ θ θ θθ θ θ 12 1 2 1 202 1 2( ( )) ( )( ) ( )TTJ tdtJ¶¶¶¶æ + - -ö= ç ÷ç ÷- -è øòθθθ θ θ θ θθ θ θ 12 1 2 1 202 1 2( ( )) ( )( ) ( )TTJ tdtJ¶¶¶¶+ - -£- -òθθθ θ θ θ θθ θ θ 12 1 2 2 1 20( ( )) ( ) ( )TJ t J dt¶ ¶¶ ¶£ é+ - - ù-òë ûθ θθ θ θ θ θ θ1 2 22 1 2 2 1 20J( t( )) J( ) dt¶ ¶¶ ¶£ ò+ - - -θ θθ θ θ θ θ θ  利用假定 3： 12 21 2 1 20£ òbt(θ-θ) ×θ-θdt  12 211 2 21 20=b θ-θòtdt =b θ-θ  证毕. 定理 3.  如果 J(θ) 是满足 b 平滑的凸函数，则： 1 2211 1 2 21 2( ) ( )( ) ( ) ( ) ( )TJ JJ J Jb¶ ¶ ¶¶ ¶ ¶-£ - - -θ θ θθ θθ θ θ θ θ     (20) 证明.  设 12 2 1( J( ) J( ))b¶ ¶¶ ¶= - -θ θx θ θ θ         (21) 把式(20)的左边分解为： 1 2 1 2J(θ) -Jθ) =J(θ) -J(x) +J(x) -J(θ)  计算机学报8                                                计算机学报                                          2018 年 根据凸函数的假定： 1 1 1( ) ( ) ( ) ( )TJ J J¶¶- £ -θθ x θ θ x  则， 11 1 2 1 2( ) ( )( ) ( ) ( ) ( )T TJ JJ J¶ ¶¶ ¶-£ - + -θ θθ xθ θ θ θ θ x     (22) 由定理 3 得到： 22 2 2 22( ) ( ) ( ) ( )TJ J J¶b¶- £ - + -θx θ θ x θ x θ  222 2 22( ) ( )( ) ( )TJ JJ¶b¶-£ - - + -θx θθ θ x x θ       (23) 式(22)和式(23)的左、右边对应项相加，合并2θ-x项： 1 2 1 1 221 2 2 22( ) ( ) ( ) ( )( ( ) ( )) ( )TTJ J JJ Jb¶¶¶ ¶¶ ¶- £ - +- - + -θθ θθ θ θ θ θθ θ θ x x θ    (24) 由式(21)得： 12 2 1( J( ) J( ))b¶ ¶¶ ¶- = -θ θθ x θ θ  代入式(24)： 21 2 1 1 211 2 2 12121 2( ) ( ) ( ) ( )( ( ) ( )) ( ( ) ( ))( ) ( )TTJ J JJ J J JJ Jbbb¶¶¶ ¶ ¶ ¶¶ ¶ ¶ ¶¶ ¶¶ ¶- £ -+ - -+ × -θθ θ θ θθ θθ θ θ θ θθ θ θ θθ θ 因此， 1 2 1 1 22121 2( ) ( ) ( ) ( )( ) ( )TJ J JJ Jb¶¶¶ ¶¶ ¶- £ -- -θθ θθ θ θ θ θθ θ 证毕. 定理 4.  满足假定 1、假定 2 和假定 3 的条件下，收敛条件2 2* *t +1 tθ-θ£θ-θ 成立。 其中*θ 是损失函数 J(θ) 负梯度方向的极值点。 在满足假定 1 的条件下，ALRI-SGD 方法在接近最终解产生震荡之前，由于维度 i 上不同时刻的梯度方向相同，也即 ( )tJ¶¶θθ 的符号相同，根据式(17)计算的tÑ 必定沿着梯度方向接近最终解。 下面进一步证明满足假定 2 和假定 3 条件下，ALRI-SGD 方法在逼近最终解的震荡阶段，能够收敛。 证明.  t 时刻的参数解tθ 到最终解θ* 的距离为： 2 2* *t1 t ta+θ-θ=θ- ×I-θ  2 2* * 22 ( )Tt t t t=θ-θ-aI θ-θ+a I   (25) 根据定理 4，考察在*θ 点的线性拟合： * *21*2( ) ( ) ( ) ( )( ) ( )Tt t ttJ J JJ Jb¶¶¶ ¶¶ ¶- £ é ù-ë û- -θθ θθ θ θ θ θθ θ    (26) 由于*θ 为最终解，因此： *( ) ( ) 0tJ θ-J θ³ ，并且 J(θ*) =0  再由式(26)得： 2* 12( ) ( ) ( ) 0Tt t tJ Jb¶ ¶¶ ¶é ù- - ³ë θû θθ θ θ θ  2* 12( ) ( ) ( )Tt t tJ Jb¶ ¶¶ ¶-é ù- £ -ë θû θθ θ θ θ     (27) 式(27)代入式(25)右侧中间项： 2*12 2 2* 2( )tt t tJaba+¶¶-£ - - +θθ θθ θ θ I      (28) 在参数更新的震荡阶段，由于不同时刻的梯度方向不同，即-1( )tJ¶¶θθ 与 ( )tJ¶¶θθ 异号，根据式(17)，必定存在22( )t tJ¶¶£θI θ 。因此： 2 2 2 2* * 2t1 t t taba+θ-θ£θ-θ- I+ I  2 2 2* * 11( )t t bta a+θ-θ£θ-θ- - I   (29) 因此，只要21( ) 0bta -a I³ ，即a £1/ b ，就可以保证2 2* *t +1 tθ-θ£θ-θ ，收敛条件成立。利用式(18)计算t,ia 时，常数a 设置为一个特定值，即能满足,1 /t ia £b 条件，该特定值由梯度累计平方和以及 b 确定。                             证毕. 6  实验及结果分析 6.1 Mountain Car 实验 本实验用于求解 Mountain Car 问题，有两个实验目的：1)分析 ALGI-SGD 方法在历史梯度折扣率l 取不同值时的收敛特性；2)比较 ALRI-SGD 方法与 SGD 方法的收敛性能。 Mountain Car 实例是把强化学习方法用于连续控制的经典例子。实例如图 1 所示，由于小车的重力大于动力，无法通过直接加速到达右侧坡顶，需要借助左侧的小坡，加足油门获得足够的惯性后，才能把小车带到右侧山坡上的顶点。状态空间是连续的，由位置 x 和速度 v 两个分量表示。小车到达右侧坡顶获得+1 的立即奖赏，其他情况的立即奖赏为 0。状态转换如下： [ ]t1 t t1x bound x v+ += + ( )10.001 0.0025cos 3t t t tv bound v a x+=é + + -ùë û 计算机学报