混合强化学习突破线性马尔可夫决策过程中的样本数量限制
内容提要
本文探讨了在折扣无限时间马尔可夫决策过程中的强化学习算法，包括策略价值估计、离线强化学习方法、基于悲观主义的算法及混合强化学习算法Hy-Q。研究表明了批处理与在线学习的区别，并提出了新算法在样本效率和遗憾最小化方面的理论保证。
延伸解读
理论下界与算法框架
文章指出，在折扣无限时间MDP中，即使已知精确奖励和转移函数，策略与目标策略的价值估计仍存在指数级信息论下界。为此，作者提出“oracle+ batch algorithm”框架，证明该下界适用于每个分布。这揭示了批处理与在线强化学习之间的指数分离，为理解样本复杂度提供了新的理论视角。
离线与混合强化学习的进展
文章回顾了离线强化学习在数据分布转移和覆盖受限下的最优样本复杂度，以及基于悲观主义的线性MDP算法达到极小极大最优。混合算法Hy-Q结合离线数据与在线交互，在Montezuma's Revenge等任务上表现更优。这些工作表明，利用离线数据可以显著提升在线学习的效率。
遗憾最小化与样本效率
针对有限时间不均匀MDP，修改版的单调值传播算法实现了遗憾最小化的最优性，且无预烧成本。在线性可实现的MDP中，通过跳过特定状态转化为线性MDP，算法具有多项式样本复杂度。这些结果强调了在理论保证下平衡计算效率与样本效率的重要性。
Q&A
什么是混合强化学习算法Hy-Q？
混合强化学习算法Hy-Q结合离线数据集和在线实时交互，提高了算法设计的效率。
离线强化学习方法如何实现最优样本复杂度？
一种无需进一步探索的离线强化学习方法通过精心设计的模型实现了最优样本复杂度，适合处理数据分布转移和数据覆盖范围受限的情况。
批处理和在线强化学习之间有什么区别？
研究显示批处理和在线强化学习之间存在显著的指数分离。
基于悲观主义的离线线性MDP算法有什么优势？
该算法能够匹配性能下限，并扩展到两人零和马尔可夫博弈，验证了算法的极小极大最优性。
如何通过线性规划优化强化学习算法？
提出了一种基于线性规划的原对偶优化方法，针对有限时间或使用表格的强化学习范式提供了理论保证。
在有限时间不均匀马尔可夫决策过程中，如何最小化遗憾度？
修改版的单调值传播算法在理论上达到了遗憾度最小化的最优性，并且没有任何预烧成本。
