Feb, 2021

线性可行最优状态价值函数下的 MDP 查询效率规划

PDF
TL;DR本文考虑了使用生成模型进行有限轮次的 MDP 本地规划，并提出了一种名为 TensorPlan 算法的方法，在最优价值函数符合线性可实现性的情况下，能够以 poly ((dH/δ) 的复杂度找到相对于任何线性可实现性且存在界限参数的确定性策略的 δ 最优策略；此外，本文还将上限拓展到了近可实现性情况和无限时域折扣设置。
local planningmdpsgenerative modellinear-realizabilitytensorplan algorithm
发现论文，激发创造
  • 线性实现最优动作价值函数的 MDPs 规划的指数下界

    本文研究了在具有线性函数逼近和生成模型的固定时间段和折扣式马尔可夫决策过程中的本地规划问题，并结合限制的特征映射来回答是否存在只需多项式数量查询的可靠规划器的问题，并提出了最小二乘值迭代算法用于计算优化方案。

    Oct, 2020

  • 基于线性实现最优值函数的 MDP 计划的张量计划及少动作下限

    本研究考虑了在线规划中基于生成模型的固定时标马尔可夫决策过程（MDP）中的极小化查询复杂度，特别关注线性函数逼近的情况，并基于先前的研究，都采用了广泛的问题类别，提出了 TensorPlan，可在动作数量固定的情况下实现所有相关数量的多项式查询成本，但在本文中，我们在 (ii) 及 (iii) 情况下证明了当动作集大小可以选择为指数函数时查询复杂度为指数级，这意味着相对于对所有状态情况 (iii) 成立的 Du 等人的工作，查询复杂度有惊人的指数级分离，并且我们还证明了 TensorPlan 的上界可用于 (iii) 的情况，并且，对于具有确定性转换和随机奖励的 MDP，TensorPlan 的上界也可用于 (ii) 情况。

    Oct, 2021

  • 在线线性 $ q^π $ 可实现 MDPs 中的 RL 与线性 MDPs 一样简单，只要你学会忽略什么

    在线强化学习中的线性可实现的马尔可夫决策过程 (MDP)，提出了一种计算效率较低的学习算法，通过跳过特定状态转化为线性 MDP，并证明了该算法在这种情况下具有多项式样本复杂度。

    Oct, 2023

  • 自信自然策略梯度用于 $q_π$ 可实现受限 MDP 中的本地规划

    这篇研究论文提出了一个新的基于受约束的马尔可夫决策过程（CMDP）框架的强化学习算法，通过离线数据评估和策略梯度更新来在线学习，实现了 CMDP 在线性设置中的多项式样本复杂度。

    Jun, 2024

  • 使用线性函数逼近实现高效的本地规划

    研究使用线性函数逼近和模拟器的查询和计算高效的计划算法，在这种情况下，我们提出了名为 “Confident MC-LSPI” 和 “Confident MC-Politex” 的两种算法，同时证明了我们的算法在特征，有效规划控制范围和目标次优性的维度中具有多项查询和计算成本，而这些成本与状态空间的大小无关。

    Aug, 2021

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

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

    Mar, 2021

  • 强化学习中的计算统计差距

    本文针对强化学习中的大状态空间问题，研究使用函数逼近的强化学习方法，并提出了寻找高效率算法的方案，同时探讨了计算难度与统计问题之间的关系。

    Feb, 2022

  • 马尔可夫决策过程的几何策略迭代

    探究了有限状态 - 动作折扣马尔可夫决策过程的价值函数多面体结构，并使用超平面排列表征了多面体的边界。提出了一种新的算法 Geometric Policy Iteration (GPI) 来解决折扣 MDPs，它使用单个状态的策略更新，以更快的价值改进不影响计算效率，同时允许状态值的异步更新。证明了 GPI 的复杂度达到了策略迭代的最佳已知界限，并展示了 GPI 在各种大小的 MDPs 上的优越性。

    Jun, 2022

  • 有限时间价值函数的张量低秩逼近

    本研究论文提出了一种非参数低秩随机算法，以近似有限时域 MDP 的价值函数。研究采用多维数组或张量表示未知的价值函数，利用从 MDP 采样得到的奖励来估计最优价值函数，并使用截断的 PARAFAC 分解设计了在线低秩算法，以恢复价值函数张量的条目。通过数值实验证明了该方法的高效性，并且低秩 PARAFAC 模型的大小以各个维度的加法方式增长。

    May, 2024

  • 在 q^π 可实现的 MDPs 中进行自信近似策略迭代，以实现高效的本地规划

    论文提出了一种新的拟动态规划算法 Confident Approximate Policy Iteration (CAPI)，并将其应用于以局部模拟器为基础的规划问题中，该算法通过一系列策略来获得越来越精确的结果，在最小代价（内存和计算代价）下输出最优策略，同时该算法的查询复杂度较先进算法有很大的改善。

    Oct, 2022