Feb, 2024

通过寻求帮助避免连续空间中的灾难

PDF
TL;DR通过假设每个回合的付出代表避免灾难的机会，我们提出了一种上下文匹配问题的变体，目标是尽量减少灾难的可能性，进而通过最大化付出的乘积来尽量避免灾难的总体机会。我们提供了一个算法，可以在时间范围增长时使后悔和对导师提问的频率都趋近于 0，假设有一个连续的 1D 状态空间和相对简单的付出函数。同时，我们提供了一个匹配的下界：在没有简单假设的情况下，任何算法要么持续寻求帮助，要么几乎肯定会造成灾难。最后，我们确定了将我们的算法推广到多维状态空间的关键障碍。
reinforcement learningcontextual bandit problemcatastrophepayoff functionmulti-dimensional state space
发现论文，激发创造
  • 具有平滑遗憾的情境臂控算法：连续行动空间高效学习

    提出了一种平滑遗憾函数的背景自适应算法，可用于大量或连续动作空间下的通用背景自适应问题，并能适应各种光滑度级别的问题，取得了先前优化遗憾函数的最优性保证。

    Jul, 2022

  • 上下文连续型强化学习：静态对动态遗憾的比较

    我们研究了上下文连续性强化学习问题，证明了任何达到次线性静态遗憾的算法都可以扩展到达到次线性动态遗憾，我们提出了一种算法，通过自协调屏障和内点法实现了次线性动态遗憾，并且得出两个关键事实：首先，对于上下文不连续的函数，没有算法可以达到次线性动态遗憾；其次，对于强凸和光滑函数，我们提出的算法达到了最小极大动态遗憾速率的最优值，仅相差对数因子。

    Jun, 2024

  • 上下文臂针对高效优化学习

    本文介绍了一种在线学习算法，它使用了一种基于代价敏感分类器的方法，并实现了最优遗憾率，与之前的算法相比，具有指数级别的运行速度优势，并且在反馈延迟方面实现了加性遗憾而非乘性遗憾。

    Jun, 2011

  • 比例响应：用于简单和累积遗憾最小化的情境赌博机算法

    提出了一种新的基于上下文 Bandit 算法的族群，利用 “保序手臂集” 提供每个上下文的一组手臂，覆盖了上下文特定的最优手臂，在简单遗憾最小化和累积遗憾最小化方面都有优异表现。

    Jul, 2023

  • 多臂赌博问题的纯探索

    研究随机多臂老虎机问题的性质和限制，探讨具有在线探索特性的预测器的表现，其中简单后悔被评估，讨论简单后悔与累计后悔的关系，在有限臂数的情况下展示了一种性能下限和预测器的上限后悔，并针对连续老虎臂问题进行了研究。

    Feb, 2008

  • 顺序任务设置中最小化局部遗憾的谬误

    强化学习中，研究任务间具有变化时，通过最小化后悔累积可以实现更好的结果，即在每个任务中过度探索，尤其在任务之间出现重大变化时。

    Mar, 2024

  • 可预测奖励的情境决策学习

    本研究探讨了一种基于可实现性假设下的上下文强化学习问题，并提出了一种新算法 —— 回归器消除，证明了其在保证可实现性前提下，也具有与不可实现性假设情况相似的遗憾率；同时在任意一组策略的情况下，我们证明了本算法具有恒定遗憾，相对于之前的方法而言。

    Feb, 2012

  • 无折扣连续强化学习的在线遗憾界

    该研究针对连续状态空间中的无折扣强化学习问题，提出了一种结合状态聚合和使用置信上界实现面对不确定性乐观的算法，在 rewards 和 transition probabilities 保持 Holder 连续性的情况下，给出了子线性遗憾界。

    Feb, 2013

  • 连续博弈中的自适应学习：最优遗憾边界和纳什均衡收敛

    本文提出了一种基于乐观的镜像下降的无悔策略算法，可以在非稳态环境下实现 O (sqrt (T)) 的后悔度，并可在变分稳定游戏中收敛到纳什均衡。

    Apr, 2021

  • 用最优后悔学习在度量空间中控制

    探讨了针对具有任意状态和动作空间的有限时间确定性控制系统的在线强化学习问题，提出了一种基于上置信强化学习的 Q 函数的乐观估计算法，证明了算法的性能界限和下界。

    May, 2019