【MIT博士论文】数据高效强化学习，176页pdf

强化学习(Reinforcement learning, RL)是一种学习复杂决策策略的通用而强大的解决方案，为游戏和机器人等多个领域的近期成功提供了关键的基础。然而，许多最先进的算法需要大量的数据，计算成本很高，需要大量的数据才能成功。虽然这在某些情况下是可能的，例如在可用数据稀少的社会科学和医疗健康应用程序中，这自然会昂贵或不可行的。随着人们对将RL应用到更广泛的领域的兴趣的激增，对其算法设计中涉及的数据的使用形成一种明智的观点是势在必行的。

因此，本文主要从结构的角度研究RL的数据效率。沿着这个方向发展自然需要我们理解算法何时以及为什么会成功;并在此基础上进一步提高数据挖掘的数据效率。为此，本文首先从实证成功案例中汲取启示。我们考虑了基于模拟的蒙特卡洛树搜索(MCTS)在RL中的流行，以AlphaGo Zero的卓越成就为例，并探讨了纳入这一关键成分的数据效率。具体来说，我们研究了使用这种树结构来估计值和描述相应数据复杂性的正确形式。这些结果进一步使我们能够分析将MCTS与监督学习相结合的RL算法的数据复杂性，就像在AlphaGo Zero中所做的那样。

有了更好的理解之后，下一步，我们改进了基于模拟的数据高效RL算法的算法设计，这些算法可以访问生成模型。我们为有界空间和无界空间都提供了这样的改进。我们的第一个贡献是通过一个新颖的低秩表示Q函数的结构框架。提出的数据高效的RL算法利用低秩结构，通过一种新的矩阵估计技术，只查询/模拟状态-动作对的一个子集来执行伪探索。值得注意的是，这导致了数据复杂度的显著(指数级)提高。说到我们对无界空间的努力，我们必须首先解决无界域引起的独特的概念挑战。受经典排队系统的启发，我们提出了一个适当的稳定性概念来量化策略的“好”。随后，通过利用底层系统的稳定性结构，我们设计了高效、自适应的算法，采用改进的、高效的蒙特卡洛oracle，以良好的数据复杂度(对感兴趣的参数是多项式)保证了所需的稳定性。总之，通过新的分析工具和结构框架，本文有助于数据高效的RL算法的设计和分析。

https://dspace.mit.edu/handle/1721.1/138930