论文部分内容阅读
强化学习是机器学习的一个主要分支,主要研究如何让智能体从与环境的交互中推断出最优控制决策。目前的强化学习算法往往需要大量的交互数据才能达到良好的学习效果,这限制了己有技术在交互数据较为昂贵的实际问题中的应用。为减少强化学习对于数据量的高度依赖,我们需要对相关算法的样本效率有更深入的了解。己有的理论分析虽然能够一定程度上刻画出算法、问题实例与样本效率之间的关系,然而其分析结果过于针对最难问题实例,对于一般难易度的问题上的样本效率则无法给出足够精确的预测。这就导致已有理论结果很难用来帮助使用者和研究者比较、挑选、设置、改善算法。本论文通过改善己有分析方法和提出新分析方法这两种思路来尝试得到能够更好地预测实际情况的样本效率理论。在第一个工作中,我们对于己有的PAC-MDP样本复杂度分析方法进行改善,提出停更样本复杂度分析方法,以使之能够更好地反映问题实例不同难易度对于算法样本效率的影响。在此基础之上,我们提出谨慎度逐增的乐观原则,以改善已有的具有PAC-MDP理论保证的算法,使其在保持原有良好理论性质的前提下,提高其实际样本效率。我们使用停更样本复杂度分析方法对改善后的算法进行分析,指出它们在非最难问题上比起原算法具有更好的理论样本效率。实验结果显示改善后的算法也具有更好的实际样本效率,展现出我们的分析方法对于分析和改善算法的有效性。在第二个工作中,我们提出强化学习成功概率分析法,直接刻画算法、具体问题实例、样本效率之间的数学关系,以得出在同一问题上算法不同参数设置对于最终样本效率的影响。我们对一个原型算法在链式MDP问题上的成功概率函数进行逐层分解并详细分析,给出算法成功找出良好策略的概率关于算法参数值和问题特性相关变量的具体数学表达式,并通过使用对数正态分布为成功概率给出了一个更易于计算的近似。实验结果表明我们的成功概率分析结果在链式MDP及迷宫MDP上以较高准确度和精确度预测出了算法在不同参数设置下的实际样本效率。在第三个工作中,我们深入分析导致同一算法在不同问题实例上样本效率有高有低的关键因素,指出估计价值的偏态特性正是这样一个因素。我们对第二个工作的一些结果进行推广,指出一个状态价值估计值等于一系列路径状态价值的加权和,而路径状态价值服从对数正态分布。因此,状态价值估计值服从的分布是一系列具有正偏态的对数正态分布与具有负偏态的“翻转”对数正态分布的卷积,其最终偏态可正可负,取决于两组分布的综合影响孰强孰弱。最终具有正偏态的估计价值有较高概率被低估,而具有负偏态的估计价值则有较高概率被高估,这对于算法正确判断状态价值优劣关系造成严重干扰。我们推导出估计价值偏态的方向与尺度关于问题特性和样本大小的数学表达式,并根据该结果指出一些能够减小负面影响的措施。