Aug, 2013

一般强化学习的样本复杂度

PDF
TL;DR本文提出了一种新的泛化强化学习算法，适用于真实环境属于 N 个任意模型的情况下。该算法被证明在除 O（N log^2 N）步骤之外的大部分情况下都是最优的，并考虑了无限的情况。同时研究表明，紧致性是决定存在统一样本复杂度界限的关键标准，并为有限情况给出匹配的下界。
reinforcement learningalgorithmmodelssample-complexitylower bound
发现论文，激发创造
  • 强化学习中基于生成模型的样本复杂度研究

    本文使用生成模型证明了在马尔可夫决策过程中，基于值迭代算法的样本复杂度 PAC 上限为 O (Nlog (N/δ)/((1-γ)³ε²))，其中 N 为状态 - 动作对的数量，γ 为折扣因子，ε 表示动作价值函数的 ε- 最优估计，δ 为概率。同时证明了在任何强化学习算法中，基于每个状态 - 动作对估计最优动作值函数的样本复杂度下限为 Θ(Nlog (N/δ)/((1-γ)³ε²))，该上限和下限在 N，ε、δ、1/(1-γ) 方面匹配。

    Jun, 2012

  • 线性复合模型集合在强化学习中的样本复杂度

    本研究提出一种强化学习算法，使用一组预先训练的不准确模拟器的状态依赖线性组合来逼近真实环境，并且在未知参数数量的多项式样本复杂度下，无需状态空间或动作空间大小的限制下可获得近似最优策略，同时还讨论了模型选择时的困难情况并提供了一种经过证明的有效算法。

    Oct, 2019

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

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

    May, 2020

  • 使用线性函数逼近的强化学习的指数难度

    研究了线性回报学习中底层的计算下界问题，并在随机指数时间假设下显示出指数级下界，证明了底层计算困难性，并且展示了一个接近最优算法的时域依赖性下界。

    Feb, 2023

  • 突破样本复杂度障碍，实现后悔优化的无模型强化学习

    通过引入方差缩减策略，设计了一个记忆高效的算法来解决在线序列化强化学习中的勘探和开发之间的平衡问题，该算法的空间复杂度为 $ O (SAH)$，较以前的算法提高了 $S^5A^3$ 倍的效率。

    Oct, 2021

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

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

    Feb, 2023

  • 双线性类：在 RL 中可证明的泛化的结构化框架

    引入了新的框架 Bilinear Classes，用于增强学习的泛化，适用于通过函数逼近实现多种模型，其中 Best Known Sample Complexity Bounds 几乎与现有模型相匹配。

    Mar, 2021

  • 基于模型的多智能体强化学习在零和 Markov 博弈中的近似最优样本复杂度

    本文探究了基于模型的强化学习算法在多智能体环境中的样本复杂度，通过两人零和马尔科夫博弈问题的研究发现，此种算法的样本复杂度为大 O （SA（1-γ）-3ε-2）, 优于其他方法，但其依赖于动作空间大小，存在一定局限性。

    Jul, 2020

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

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

    Dec, 2023

  • 几乎极小化最优无奖学习

    研究奖励免费强化学习框架，提出新的有效算法 SS+TP，通过探索和计划两个阶段，分别进行轨迹收集和任意奖励函数优化，达到对多个奖励函数的策略优化。

    Oct, 2020