Jun, 2024

分离潜在马尔可夫决策过程中的近优学习与规划

PDF
TL;DR我们研究了学习潜在马尔可夫决策过程（LMDPs）的计算和统计学方面。本文的主要目标是建立一个几乎精确的统计阈值，以实现有效学习所需的时间长度。在计算方面，我们证明，在最优策略下具有较弱的分离性假设时，存在一个几乎多项式的算法，时间复杂度与统计阈值成比例。我们还基于指数时间假设，展示了一个近似的时间复杂度下界。
latent markov decision processeslearningcomputational aspectsstatistical aspectshorizon length
发现论文，激发创造
  • 潜在 MDP 中的强化学习是可行的：通过离线策略评估实现在线保证

    我们介绍了没有任何附加结构假设的 Latent Markov Decision Processes (LMDPs) 的第一个样本高效算法，并建立了新的离线评估引理和 LMDPs 的新覆盖系数，通过这些结果可以推导出一种乐观探索算法的近似最优保证。我们相信这些结果对于广泛的交互式学习问题，特别是部分观测环境中，具有重要价值。

    Jun, 2024

  • 潜在 MDPs 的强化学习：遗憾保证和下界

    在本文中，我们考虑了隐式马尔科夫决策过程中强化学习的遗憾最小化问题，我们提出了一个具有局部保证的有效算法，以解决这个问题。

    Feb, 2021

  • 基于无界时间跨度和方差的隐含马尔可夫决策过程强化学习

    本文研究基于后知的上下文中的潜在马尔可夫决策过程（LMDPs）的强化学习中的遗憾最小化问题，设计了一种新的基于模型的算法框架，证明了具有一定时间复杂度的遗憾上限。

    Oct, 2022

  • 稀疏线性 MDP 中的探索和学习，无需计算难解的预测器

    线性马尔科夫决策过程（MDP）中的特征选择和零稀疏线性 MDP，以及通过凸规划有效计算的模拟器、低深度决策树上的区块 MDP 的学习算法。

    Sep, 2023

  • 潜在马尔可夫决策过程的前瞻性侧信息

    在许多交互决策的场景中存在着潜在且未被观察到的固定信息。本文研究了拥有潜在上下文信息的潜在马尔可夫决策过程（LMDP）类的问题，证明了任何具有样本高效算法的算法必须至少具有 Ω(K^(2/3)) 的后悔，提出了一个具有匹配上限的算法。

    Oct, 2023

  • 有界最优探索在 MDP 中的应用

    本文提出简单算法来解决在短期内实现理论驱动的探索方法和实际需求之间的纠葛，并通过理论分析和数字示例展示所提出的放宽条件的好处，同时维持任何时候的误差边界和平均损失边界，并且适用于贝叶斯和非贝叶斯方法。

    Apr, 2016

  • 马尔可夫决策过程中最佳策略识别的自适应采样

    本文研究在马尔可夫决策过程中，通过生成模型来识别最优策略，提出了 KLB-TS 算法，并提供了其样本复杂度的渐近保证。

    Sep, 2020

  • 几乎没有视野限制的离线强化学习

    本文利用离线强化学习技术研究了时域同质马尔可夫决策过程上的策略评估和优化问题，并提出了一种递归方法来限制离线场景下的 “总方差” 项，得到了近似无视野远的样本复杂度上限。

    Mar, 2021

  • 通过线性规划对偶解决大规模马尔可夫决策问题

    本文提出了一种针对状态空间较大的 MDP 问题进行优化的方法，该方法基于一小组策略的占用度量的低维度逼近，并提出了一个有效的算法，可用于在该类策略中找到低过度损失相对于最佳策略的策略。作者限定了平均成本和折扣成本情况下的过量损失，并在队列应用中展示了该方法的有效性。

    Jan, 2019

  • 合作多智能体马尔可夫决策过程中的近似线性规划和分散策略改进

    我们提出了适用于合作多智能体有限和无限时域折扣马尔可夫决策过程的逼近策略迭代算法，其中使用近似线性规划计算近似值函数并实施分散策略改进。

    Nov, 2023