可数 MDP 中点收益、平均收益和总收益目标的策略复杂性
本文提出了度量具有无限状态的马尔可夫决策过程(MDPs)中状态相似性的指标,包括具有连续状态空间的MDPs。这样的指标为MDPs的同步关系提供了稳定的定量分析,适用于MDP逼近。我们展示了与我们的指标距离有关的贴现无限时域规划任务相关的最优价值函数连续变化的情况。
Jul, 2012
该论文提出了一种算法,用于确定性连续马尔可夫决策过程,该算法能够精确计算出最优策略,并且不依赖于状态空间的大小。此算法的时间复杂度为$O(|R|^3×|A|^2)$,空间复杂度为$O(|R|×|A|)$,并且还提出了一种伴随算法。与值迭代的算法相比,在可处理的马尔可夫决策过程中,算法的操作成果得到了一致的验证。
May, 2018
本文利用交互式定理证明器Isabelle/HOL,对于解决马尔科夫决策过程(MDPs)的可执行算法进行正式验证,并基于此分析验证动态规划算法来解决表格MDPs,实验结果表明该系统可以与最先进的系统竞争甚至超过它们。
Jun, 2022
本文提出了应用于马尔可夫决策过程和随机游戏的价值迭代算法的停止准则,这是该领域首个用于计算总体回报和平均回报的任何时刻算法。我们的方法通过将问题降低到马尔可夫决策过程领域和直接应用于随机游戏领域中,统一了先前的算法并提出了目标独立的概念。
Apr, 2023
我们研究了不确定性下的序贯决策中马尔可夫奖励的表达能力,通过将马尔可夫决策过程(MDPs)中的奖励函数视为代理行为的特征化手段,研究了是否存在一种标量或多维度马尔可夫奖励函数,使得这个集合中的策略比其他策略更具吸引力。我们的主要结果给出了这样的奖励函数存在的必要和充分条件,同时也证明了对于任意非退化的确定性策略集合,都存在一个多维度的马尔可夫奖励函数来描述它。
Jul, 2023
马尔可夫决策过程在强化学习中起着关键作用,本研究探讨了多种与强化学习相关的'成本',研究了策略评估的样本复杂度,并开发了一种具有实例特定误差界限的新估计器;在在线遗憾最小化设置下,通过引入基于奖励的常量和基于潜力的奖励塑形技术,提供了理论上的解释;提出了一种安全强化学习研究方法,建立了重置效率的量化概念;针对具有多个奖励函数的决策过程,开发了一个能够计算出帕累托最优随机策略的规划算法。
Aug, 2023
我们研究了一个基于生成模型的平均回报马尔科夫决策过程(MDP)中学习一个ε-最优策略的样本复杂度,建立了复杂度界限Ω(SA(H/ε^2))。我们的结果在参数S、A、H和ε上是极小极大最优的(最多有对数系数),进一步改进了现有工作,其中要么假定所有策略的混合时间均匀有界,要么对参数有次优的依赖。我们的结果基于将平均回报MDP简化为折扣MDP。为了证明这种简化的最优性,我们对γ折扣MDP进行了改进的界限,显示了在γ≥1-1/H的情况下,采样Ω(SA(H/((1-γ)^2ε^2)))足以在弱通信MDP中学习ε-最优策略,从而规避了适用于一般γ折扣MDP的Ω(SA/(1-γ)^3ε^2)的已知下限。我们的分析以跨度参数为基础,对某些实例相关方差参数进行了上界估计,这些上界比基于MDP的混合时间或直径的估计更紧凑,可能具有更广泛的应用。
Nov, 2023
马尔科夫决策过程(MDPs)为不确定性下的顺序决策制定了标准框架,但是MDPs中的转移概率通常是从数据中估计的,并且MDPs不考虑数据的不确定性。鲁棒马尔科夫决策过程(RMDPs)通过为每个转移分配不确定性集合而不是单个概率值来解决了MDPs的这个缺点。解决RMDPs的目标是找到一种策略,使得在不确定性集合上最大化最坏情况的性能。本文考虑多面体RMDPs,在其中所有的不确定性集合都是多面体,并研究解决长期平均回报的多面体RMDPs的问题。我们关注计算复杂性方面和高效算法。我们提出了这个问题的一个新视角,并且证明它可以简化为解决具有有限状态和动作空间的长期平均回报的轮流随机游戏。这个简化使我们能够得出几个重要的结论,这些结论以前是未知的。首先,我们为解决长期平均回报的多面体RMDPs推导出新的计算复杂性界限,首次证明它们的阈值决策问题属于NP coNP,并且它们具有具有亚指数期望运行时间的随机算法。其次,我们提出了鲁棒多面体策略迭代(RPPI),一种用于解决长期平均回报的多面体RMDPs的新型策略迭代算法。我们的实验评估表明,相比基于值迭代的现有方法,RPPI在解决长期平均回报的多面体RMDPs方面更加高效。
Dec, 2023
本文介绍了非累积马尔可夫决策过程(NCMDPs)与标准马尔可夫决策过程(MDPs)之间的一种映射关系,并展示了在强化学习中的应用,包括经典控制、金融组合优化和离散优化问题。通过我们的方法,相较于依赖标准MDPs,我们可以改善最终性能和训练时间。
May, 2024
我们回顾平均奖励马尔可夫决策过程(MDP)中 ε-最优策略的识别,并提出了一种新算法,在小 ε 范围内其样本复杂度为 SAD/ε^2;此外,我们还提出了一种在线算法,其样本复杂度为 SAD^2/ε^2,并且提出了一种有前景的基于数据相关的停止准则的新方法以进一步减小此样本复杂度界限。
May, 2024