强化学习的一种增强式方法

【作者团队】Nataly Brukhim,Elad Hazan,Karan Singh

【论文链接】https://arxiv.org/pdf/2108.09767.pdf

【推荐理由】本文研究了马尔可夫决策过程中强化学习的有效算法，其复杂性与状态数量无关。这种公式简洁地捕获了大规模问题，但也已知其一般形式在计算上是困难的。以前的方法试图通过假设转换函数或值函数中的结构，或通过将解保证放宽到局部最优条件来规避计算难度。本文考虑了从监督学习中借用的 增强式方法，用于将弱学习器转换为准确的策略。本文研究的弱学习的概念是基于采样的线性函数对策略的近似优化。在这种弱学习性假设下，本文给出了一种有效的算法，能够提高这种弱学习方法的准确性，直到达到全局最优。本文证明了此方法的样本复杂度和运行时间界限，它们是问题自然参数的多项式：近似保证、折扣因子、分布不匹配和动作次数。特别是，界限不依赖于状态的数量。应用之前的增强式结果的一个技术难点是策略空间上的价值函数不是凸的。本文展示了如何使用 Frank-Wolfe 方法的非凸变体，结合梯度提升的最新进展，允许将弱学习器与乘法近似保证结合起来，以克服非凸性并实现全局收敛。