Sep, 2020

强化学习是否比赌博机问题更困难？一种逃离时限诅咒的近似最优算法

HTML
PDF
TL;DR提出了一种新的基于 Bernoulli 奖励的算法 Monotonic Value Propagation（MVP）来应对具有长期规划的暂态强化学习问题，并通过证明其具有与语境损失算法相同且优于最先进的算法的范围复杂度，使其能够有效地处理此类问题。
发现论文，激发创造
  • 驯服怪兽：一种快速简单的上下文赌博算法

    本文提出了一种在线学习算法，具有上下文匹配学习问题中的统计最优保证，并通过少量的机器学习调用来完成，而且在性能方面非常优秀。

    Feb, 2014

  • 使用值函数界限在没有领域知识的情况下加强强化学习的问题相关遗憾范围

    该研究针对有限时间段的离散马尔科夫决策问题，提出了一种算法并分析了其性能上限，得出了最先进的范围和如果环境规范小则更紧的限制，其不需要先前对应环境规范的知识，能解决经验学习中常常遇到的限制问题。

    Jan, 2019

  • 线性上下文臂优化中的自适应探索

    我们设计了一种渐近上限最优算法，并充分利用线性结构和精确探索，从而减少了在多种合理情境下的失算，数值结果表明，与其他基准算法相比，我们的方法大大减少了失算。

    Oct, 2019

  • 长期强化学习是否比短期强化学习更困难？

    通过构建 ε-网络和在线轨迹合成算法，证明纯表格的情况下，对于每个长度的规划时间，可以通过对数级的样本复杂度在多项式时间内发现适当规范化后的最佳策略，从而证明了一个假设，即规划时间的增加并不会增加学习长时序的RW的难度。

    May, 2020

  • 基于不同实例的情境臂和强化学习复杂度：一种基于反对的视角

    该研究提出了一种用于上下文Bandit问题的复杂度度量方法，展示了其与最优实例相关遗憾的关系，并给出了新的算法来实现当存在一个最优选择时能够分辨性地进行探索。同时，该研究还在采用函数近似的强化学习问题上提出了新的算法，达到了优化的样本规模。

    Oct, 2020

  • 无先验知识的非平稳强化学习：一种最优黑盒方法

    本文提出一种黑盒化的方法，将某些强化学习算法在（近）平稳环境下的优化遗憾转化为在非平稳环境下的优化动态遗憾，并且不需要事先了解非平稳度。通过把不同的算法插入到这个黑盒中，我们给出一系列的例子，表明该方法不仅可以重构最近通过特殊算法实现的（上下文）多臂赌博机问题，而且还可以显著改进广义线性赌博机问题、周期性马尔科夫决策问题和无限时间马尔科夫决策问题的状态，特别是在大多数情况下，我们的算法可以达到最优动态遗憾。

    Feb, 2021

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

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

    Oct, 2021

  • 线性混合MDP的高效无界强化学习算法

    该研究论文提出了第一个计算高效、无横向界限算法，其中采用了加权最小二乘法，以用于未知状态转移动态的估算，并能够应用于异构线性bandits中，达到了比已知算法更优的效果。

    May, 2022

  • 带有长期回报的随机情境赌博机

    该研究探讨了基于上下文的线性赌博机，考虑到先前的行动和语境对当前奖励的影响，提出了利用稀疏性建立依赖模式和臂参数的新算法，并在两种情境下证明了规避多项式依赖于奖励层面的新保证。

    Feb, 2023

  • 在对抗性线性混合MDPs中的无限制视野强化学习

    本文通过提出第一个无界时间步长多次对抗强化学习的策略搜索算法，使用方差-不确定性感知加权最小二乘估计器和基于占用度量的在线搜索技术，以解决探索和对抗性奖励所带来的挑战，证明算法在全信息反馈下具有 O((d+log(|S|^2|A|))sqrt(K)) 的后悔界，其中 d 是未知转移核线性参数化的已知特征映射的维数，K 是剧集数量，|S| 和 |A| 是状态和行为空间的基数。

    May, 2023