线性实现最优动作价值函数的 MDPs 规划的指数下界
本文考虑了使用生成模型进行有限轮次的 MDP 本地规划,并提出了一种名为 TensorPlan 算法的方法,在最优价值函数符合线性可实现性的情况下,能够以 poly ((dH/δ) 的复杂度找到相对于任何线性可实现性且存在界限参数的确定性策略的 δ 最优策略;此外,本文还将上限拓展到了近可实现性情况和无限时域折扣设置。
Feb, 2021
本研究考虑了在线规划中基于生成模型的固定时标马尔可夫决策过程(MDP)中的极小化查询复杂度,特别关注线性函数逼近的情况,并基于先前的研究,都采用了广泛的问题类别,提出了 TensorPlan,可在动作数量固定的情况下实现所有相关数量的多项式查询成本,但在本文中,我们在 (ii) 及 (iii) 情况下证明了当动作集大小可以选择为指数函数时查询复杂度为指数级,这意味着相对于对所有状态情况 (iii) 成立的 Du 等人的工作,查询复杂度有惊人的指数级分离,并且我们还证明了 TensorPlan 的上界可用于 (iii) 的情况,并且,对于具有确定性转换和随机奖励的 MDP,TensorPlan 的上界也可用于 (ii) 情况。
Oct, 2021
本研究讨论在线强化学习问题,探讨了是否能够通过加入一个常数子优性差值的假设来实现有效学习,结果发现即使假设线性实现了最优 Q 函数,仍然需要指数级别的样本量,进一步证明在线学习和生成模型学习之间存在指数差距。
Mar, 2021
开发多种学习用于 Markov Decision Processes 的无限时间平均奖励设置和线性函数逼近的算法,使用乐观原则和假设 MDP 具有线性结构,提出具有优化的计算效率的算法,并展开了详细的分析,改进了现有最佳结果。
Jul, 2020
本文介绍了一种基于加权线性回归方案的计算有效算法,用于处理线性马尔可夫决策过程的强化学习问题。该算法实现了近似最小化最优遗憾,具有较好的效率,对参数化转换动态有良好的适应性,可以对研究领域进行更细致的探讨。
Dec, 2022
该研究提出一种基于特征维度的参数 Q 学习算法,通过使用方差约减、单调性保持和置信区间等技术提高了其样本效率,并证明了该算法在任意初始状态下可以以高概率找到一个 ε- 最优的策略,适用于大规模的马尔可夫决策过程。
Feb, 2019
本论文介绍了一种基于特性映射的新算法,能够以线性的方式参数化转移核函数来处理强化学习中的大状态和行动空间,并且证明了该算法在一些强化学习的问题中,不需要访问生成模型就能取得多项式的最优后悔值,且总体上是近乎最优的。
Jun, 2020
线性马尔科夫决策过程(MDP)中的特征选择和零稀疏线性 MDP,以及通过凸规划有效计算的模拟器、低深度决策树上的区块 MDP 的学习算法。
Sep, 2023