强化学习基本知识

强化学习基础知识作为人工智能领域、机器学习(MachineLearnig)热点研究内容之一的强化学习(ReinforcementLearning,RL)，旨在通过在无外界“教师”参与的情况下，智能体(Agent)自身通过不断地与环境交互、试错，根据反馈评价信号调整动作，得到最优的策略以适应环境。一、Markov决策过程（MDP）强化学习的来源是马尔科夫决策过程：M=S,A,P,RMarkov性的意思是x取x(1),x(2),x(3)...x(n)所得到x(n+m)的分布与x只取x(n)所得到的x(n+m)的分布相同，既是说未来状态的分布只与当前状态有关，而与过去状态无关。（无后效性）若转移概率函数P（s,a,s’）和回报函数r(s,a,s’)与决策时间t无关，即不随时间t的变化而变化，则MDP称为平稳MDP。当前状态s所选取的动作是由策略h决定：S*A[0,1]A=(s)在状态s下用策略所选取的动作。动作后的结果是由值函数以评估，它是由Bellman公式得到。（折扣因子)1,0(）值函数UuSssVsasPasRashsV])'()',,(),()[,()('动作—状态值函数SsAaasQsasPasRasQ'')','()',,(),(),(对于确定性策略，有))(,()(ssQsV；——一个状态转移概率对于不确定性策略，有AaasQassV),(),()(——多个状态转移概率强化学习的最终目的是找到最优策略，选择值函数最大的动作。最优值函数])'()',,(),(max[)('*SssVsasPasRsV或者最优动作—状态值函数SsasQsasPasRasQ'*)}','(){max',,(),(),(或者兼而有之为了避免局部最优需要进行随机探索，为了逼近既定目标需要抽取最优策略，所以算法中存在一个探索与利用的平衡。达到平衡有两种方法：greedy策略和Boltzmann分布方法（平衡离散域）对于电磁微阀控制s——当前四个微阀状态a——操作四个微阀的动作，0为关闭，1为开启s’——动作后微阀的新状态P(s,a,s’)——状态s调控微阀使其达到新状态s’的概率)(sV——在调控后这个状态的累计奖赏值),(asR——本次动作的立即奖赏值，根据各点温度及标准差的计算评估得到(s,a)——调节微阀的各种策略二、基于模型的动态规划算法动态规划是一个多阶段的决策问题,在最优决策问题中，常规动态规划算法主要分为下面四类：第一类是线性规划法，根据Bellman方程将值函数的求取转化为一个线性规划问题；线性规划方程包含|S|个变量，|S|*|A|个不等式约束，其计算复杂度为多项式时间。SsSsAaSssVsasPasRsVtssV',),'()',,(),()(..)(max第二类是策略迭代，仍然是基于Bellman最优方程的算法，通过策略评估与策略迭代的交替进行来求取最优策略；策略迭代分为策略评估和策略改进两部分：在评估部分，对于一个给定的策略k，根据Bellman公式求解)(sVk和),(asQk。对于评估部分，用贪婪策略得到改进的策略1k第三类是值函数迭代法，其本质为有限时段的动态规划算法在无限时段上的推广，是一种逐次逼近算法；将Bellman公式改写为SstAatSssVsasRsasPsV'1)),'()',,()(',,(max)(,就可跳过策略改进步骤，直接用迭代法逼近最优值函数V*,从而求取最优策略*第四类是广义策略迭代法，综合了策略迭代和值迭代方法特点。广义策略评估是策略评估与策略改进相结合的学习过程。策略评估总是试图让策略和相应的值函数一致，而策略改进总是破坏策略评估得到的一致性。最终策略和值函数都不再变化是迭代结束。下图在两个维度上（两条线表示）描述了广义策略迭代的逼近过程，学习的最终目的是获得最优策略，具体的学习过程可以在值函数唯独和策略策略维度上灵活的变化。值函数迭代方法只在值函数维度上工作，而策略迭代方法在值函数维度和策略维度上交叉进行。许多动态规划与强化学习算法的思想都来源于广义策略迭代。初始状态——|决策1|——|决策2|——.....——|决策n|——结束状态三、模型未知的强化学习对于求解模型未知的MDP问题，通常有如下3类解决思路：第一类是学习MDP的相关模型，然后用动态规划算法予以求解，此类方法称为间接强化学习；第二类方法不需要估计MDP的模型，直接利用采样对值函数或策略函数进行评估，此类方法成为直接强化学习算法；第三类是前两类方法的混合。1.蒙特卡罗方法蒙特卡洛方法是一种以部分估计整体，利用随机数来解决问题的方法，其通过统计模拟或抽样以获得问题的近似解。该方法只是用于场景中存在终止状态的任务。MC策略评估主要是利用大数定律，以各个状态的回报值的样本平均来估计值函数，最终发现最优策略。))((Re)(sturnaveragesV得到的回报金额已赋给第一次访问的s，也可以将每次访问到终止状态Ts的回报平均后赋予给s的值函数。鉴于MC策略评估只有在只有在无穷次迭代时才能精确计算Q，因此有人提出了改进策略，在一幕赋值完成后将kQ用贪婪算法来更新以得到改进策略1k，这样有利于维持探索与利用的平衡，也提高了Q的精确度。VVV)(VgreedyV**),(maxarg)(asQsAa但是面对着以上方法只利用不探索的缺陷将贪婪策略进行的改进，引入了基于ε-贪婪策略的在线MC控制策略，主要做了两个改动：第一个是将初始策略用ε-贪婪策略来选择；第二个是利用ε-贪婪策略来进行策略更新。即对于每一个Aa，*|,|/*|,|/1),(aaAaaAas),(max)1(),(||),(),('))(',(asQasQAasQasssQAaAaAa在线策略MC控制算法中，产生样本的行为策略'核和进行Q值估计的评估策略是同一策略，而在离线策略学习中两者是独立的，评估策略用ε-贪婪策略进行改进。而行为策略'可以根据具体情况灵活设计。蒙特卡罗学习方法优点是不必依赖于马尔科夫决策过程，在模型未知时也能选择出感兴趣的状态以求其值函数，而不必遍历所有值函数。2.时间差分TD算法时间差分指的是对同一个变量在连续两个时刻观测到的值的差异。假设在时刻t，系统的状态st的值函数表示为V(st)，rt为在当前状态下根据某种动作选择策略采取动作at后，使得状态发生变化转移至新状态st+1时得到的即时奖赏。状态st下新的值函数的估计值：)()('1tttsVrsV那么，时刻t的时间差分为：)()(1ttttsVsVrTD方法通过预测每个动作的长期结果来给先前动作赋予奖励或惩罚，即依赖于后续状态的值函数来更新先前状态值函数的自举方法，主要应用于预测问题。只向后追踪一步的预测问题TD(0)的迭代公式为(0≤α≤1表示学习率因子)))()(()()()(1tttttttsVsVrsVsVsV追踪多步的预测问题TD()的迭代公式为)())()(()()()(1ttttttttsesVsVrsVsVsV)(tse为状态的资格迹。对某一特定状态，其资格迹随状态被访问次数的增加而增加，该状态对整体的影响越大。资格迹定义方式分为增量型和替代型两类。3.Q学习和sarsa学习Q学习不同于TD时序差分算法在于它用状态-动作值函数Q(s,a)作为评估函数，而不是值函数V(s)。它只需采取-贪心策略选择动作而无需知道模型就可以保证收敛，是目前最有效的强化学习算法。在Q学习中Q都是估计值而不是实际值，是从不同动作的估计值中选择最大Q值函数进行更新。相对于Q学习利用模拟Q值进行迭代的离线学习，SARSA学习更像是一种在线学习，是严格根据策略实时更新，行为决策与值函数迭代是同时进行的。它们之间的区别是更新Q(s,a)时，一个用的是根据以往经验预测的最优策略，一个用的是当前实际动作状态值函数。)),(),(max(),(),('1asQasQrasQasQttattttt——Q-learning)),(),((),(),('1asQasQrasQasQttttttt——Sarsa四、Q学习的优化方法当传统的强化学习的问题空间S×A变得庞大的时候,有两个严重的问题影响了强化学习的实用性.其一是速率问题:S×A数据量庞大,因此强化学习算法常常收敛较慢。其二是复用问题:无论是值函数V(s)还是动作值函数Q(s,a)或者是策略π,强化学习的结果总是依赖于S×A的具体表示,这意味着只要问题略微改变,以前的学习结果就变得毫无用处.但对于某些实际问题,由于训练代价较高,学习结果的可复用性是非常重要的。这两方面激励了强化学习的迁移。迁移学习就是复用过去的学习经验和结果以加速对于新任务的学习。传统的强化学习方法适于处理小规模的离散状态或离散动作学习任务而不能求解连续状态空间和连续动作空间的问题。1.Dyna-Q学习对于环境复杂、信息量大、必须快速学习的情况，例如矿井下的线路规划，Q学习学习效率会很低，它需要采集环境中的“足够多”的状态动作对和相应值函数才能收敛，所花费时间过长，不能及时指定路线。针对这个问题，提出了改进策略，将Dyna学习框架加入到Q学习中可以利用少许真实数据建立环境估计模型，然后用规划法产生虚拟样本并更新值函数，这样可以以增加计算复杂度来降低时间复杂度。Dyna-Q学习与Q学习算法过程的区别是真实样本T不仅要更新值函数、策略函数，还要更新环境的估计模型P，模型训练好便可产生虚拟样本自行更新，转在线为离线，集试错于认知，将得鱼变成了得渔，提高了学习效率。但要处理好学习与规划的平衡问题。2.最小二乘时间差分Q算法（LSTDQ）Q学习的查找表形式只适用于求解小规模、离散空间问题，而对于实际大规模或连续空间问题，智能体不能遍历所有状态，而用最小二乘法策略迭代法即可解决，它主要通过估计值来逼近动作值函数),(asQ。其矩阵描述形式为：Qˆ其中，TASTTTasasas)],(),...,,(),...,1,1([||||表示大小为|S||A|*k的基函数矩阵。通过最小二乘不动点逼近法来学习参数，有RPI1])'([其中，P’是大小为|S||A|*|S|的矩阵，P’((s,a),s’)=P(s,a,s’)，大小为|S||A|*|S|矩阵，)'())','(,'(sass。输出或TAaass),(maxarg)(最小二乘策略迭代框架如下：3.解决维数灾难的方法高维空间训练形成的分类器，相当于在低维空间的一个复杂的非线性分类器，这种分类器过多的强调了训练集的准确率甚至于对一些错误/异常的数据也进行了学习，而正确的数据却无法覆盖整个特征空间，维数越多，接近球心样本越稀疏。这导致训练数据量严重不足，要是这时产生一个错误的新数据就会在预测时产生极大的误差。这种现象称之为过拟合，同时也是维灾难的直接体现。动态规划问题的维数是指各阶段状态变量的维数。当状态变量的维数增加时，其计算量会呈指数性增长，产生过拟合使Q学习难以收敛，对新数据也缺乏泛化能力。只能通过降维来解决。核函数可以将m维高维空间的内积运算转化为n维低维输入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维数灾难”等问题，在高维特征空间解决复杂的分类或回归问题奠定了理论基础。常见的有Sigmoid核函数，可以通过将Q学习与神经网络或支持向量机的结合来加快算法的收敛速度。值函数逼近先行结构TasasQ),(),(ˆ贪婪策略AaasQsT,),(maxarg)(策略评估、投影LSTDQ策略改进MaximizationSamples