Feb, 2021

Q-Learning 算法是否达到 Minimax 最优性？一种紧凑的样本复杂度分析

PDF
TL;DR本文研究 Q-learning 同步和异步情况下的样本复杂性和子优秀性，并展示在异步情况下的样本复杂性更强，Q-learning 算法是严格亚最优的。
q-learningmdpsample complexitysub-optimalityasynchronous q-learning
发现论文，激发创造
  • 异步 Q 学习的样本复杂度：更精确的分析和降低方差

    该研究通过异步 Q-learning 算法，在马尔科夫决策流程中的样本轨迹中学习最优动作价值函数，给出了基于 L∞的样本复杂度分析及等式组，并在此基础上提出一种新的方差缩减技术，进一步提高了算法的效率。

    Jun, 2020

  • 方差缩减 $Q$- 学习达到了最小极差优化

    介绍和分析了一种方差减少的 Q-learning 方法，为具有有限状态和动作空间的折扣 MDPs 提供了相对精确的最优 Q 函数估计，其采样数量与最小极值下界匹配。

    Jun, 2019

  • 最近邻 Q 学习

    该论文研究利用最近邻回归方法的最近邻 Q 学习算法，从单一样本路径中学习具有连续状态空间和未知转移核的无限期贴现 MDPs 的最优 Q 函数，提供了紧密的有限样本收敛速率分析和样本复杂度。

    Feb, 2018

  • 最优值估计中的实例最优性：通过方差缩减 Q 学习实现自适应

    本文提出一个本地极小极大方法，分析了计算强化学习下的最优 $Q$ 值函数的实例特定行为，并提供一个针对 $Q$ 学习中困难问题和易解问题的有力解释。

    Jun, 2021

  • 通过生成模型在模型为基础的强化学习中突破样本量限制

    研究强化学习的样本效率，证明了两种算法的最小最优性，同时实现了目标准确率的最小最优样本复杂度，这是目前首次提供涵盖整个样本范围的最小最优保证。

    May, 2020

  • 基于核的 Q-Learning 的样本复杂度

    本文论述了基于核心回归的 Q 学习在存在生成模型时的采样复杂度，提出了一种非参数 Q 学习算法，其样本复杂度优化到 ε 和核心复杂度的阶数，这是针对这种普遍模型的首个具有有限样本复杂度的结果。

    Feb, 2023

  • 具有恒定子最优性差异的可线性实现 MDPs 的指数下界

    本研究讨论在线强化学习问题，探讨了是否能够通过加入一个常数子优性差值的假设来实现有效学习，结果发现即使假设线性实现了最优 Q 函数，仍然需要指数级别的样本量，进一步证明在线学习和生成模型学习之间存在指数差距。

    Mar, 2021

  • 部分动力学知识的高效强化学习

    本文研究在线强化学习的样本复杂性问题，并考虑了有关系统动态的部分知识，提出了一种基于 Q-learning 的算法，能够在具有有限 Markov 决策过程的系统中实现近似最优策略。

    Dec, 2023

  • 无模型强化学习：从剪切伪懊恼到样本复杂度

    本文提出了一种无模型的算法来学习具有折扣因子的马尔可夫决策过程中的政策，该算法的成功概率为 (1-p)，且具有样本复杂度 O (SALn (1/p)/(ε^2 (1-γ)^3))，其中 S 是状态数，A 是行动数，γ 是折扣因子，ε 是一个近似阈值

    Jun, 2020

  • 方差减少的分布鲁棒 Q 学习的样本复杂性

    本论文提出了两种模型无关的算法，分别是分布鲁棒的 Q-learning 及其方差缩减的版本。这些算法可在处理分布移位时有效地学习强大的策略。在一系列数值实验中，这些算法的理论发现和效率得到了证实。

    May, 2023