May, 2023

参数化和加权 MDP 的基于图形的约简

PDF
TL;DR本文章研究了参数化马尔可夫决策过程中、权重可达性问题的缩减复杂度。该问题的计算复杂度为 coETR-complete，但是我们在此研究中提出了一种多项式时间算法，可以计算马尔可夫链的 order 等价类，并且描述和实现了两个推断规则，用于近似评估该问题，并且证实此方法可以作为大型马尔可夫决策过程分析的有效预处理步骤。
weighted reachabilityparametric markov decision processescomputational complexityequivalence classesinference rules
发现论文，激发创造
  • POMDP 中的最优成本几乎确定可达性

    本文研究部分可观察马尔可夫决策过程 (POMDPs)，带有一组目标状态并且每个转移都有一个整数成本。研究的最优化目标是在确保（概率为 1）几乎达到目标集时最小化预期总成本。我们证明，对于整数成本，近似最优成本是不可判定的。对于正成本，我们的结果有：（i）我们建立了最优成本的匹配下限和上限，上限是双指数；（ii）我们表明，近似最优成本的问题是可判定的，并且提出了建立在具有有限时间段目标的 POMDP 算法上的近似算法。虽然这个算法的最坏运行时间是双指数的，但我们还介绍了算法的有效停止标准，并实验性地表明它在许多有意义的示例中表现良好。

    Nov, 2014

  • 一般马尔可夫决策过程的加权网格算法：收敛性与可计算性

    我们引入了一种网格型方法来解决具有一般特征的离散时间有限时间马尔科夫决策过程（MDPs），该过程具有一般的状态和动作空间，包括欧几里得空间的有限和无限（但合适地规则的）子集。

    Jun, 2024

  • 多维马尔可夫决策过程中的百分位查询

    本文研究带有多维权重的马尔可夫决策过程中百分位查询的复杂性，并给出了算法以综合满足这样的限制的策略，扩展了 Etessami 等人在非加权 MDPs 上研究的多目标模型检查问题到数量级问题。

    Oct, 2014

  • 一种基于符号 SAT 的 POMDP 几乎必达性小策略算法

    研究 POMDPs 的几乎确定可达性问题，提出了具有小内存的策略的符号算法，通过有效编码到 SAT 并使用 SAT solver 来解决问题。

    Nov, 2015

  • 加速参数概率验证

    提出了一种新颖的方法，用于计算参数离散时间马尔可夫链的可达性概率，其转移概率是参数集合上多项式的分数。该算法基于图的分解为强连通子图和多项式的新因数分解策略。实验评估表明，这些方法可以使速度提高几个数量级，相对于现有方法。

    Dec, 2013

  • 游戏指标算法

    基于模拟和双模拟的指标可以用于系统验证和性能评估，适用于定量的 mu - 演算和相关概率逻辑，对于马尔可夫链，我们提供了一个 PSPACE 算法，以匹配最佳算法，并且这些算法可以通过二分搜索来逼近指标。

    Sep, 2008

  • POMDP 中的期望总奖励欠估计算

    本文研究了如何通过计算部分可观察马尔可夫决策过程的总期望奖励的下界来解决通常难以解决的问题，提供了两种技术：使用良好策略的简单技术和使用概率之间的最小移位的更高级别的技术。同时，本文还使用混合整数线性规划找到这样最小概率移位，并在实验中表明了这些技术的可扩展性和其提供的紧缩的下界值。

    Jan, 2022

  • 无折扣 POMDP 中带有可达性目标的声音启发搜索值迭代

    该研究论文探讨了部分可观测马尔可夫决策过程（POMDPs）中的最大可达性概率问题（MRPP），研究了一种基于点估计方法和基于试探性启发式搜索的新算法，解决了处理无限时域问题中循环的问题，并在实验评估中表现出优越性。

    Jun, 2024

  • 用于计算马尔可夫决策过程近似最优解的模型简化技术

    介绍了一种新方法，用于解决具有非常大状态空间的隐式（分解式）马尔可夫决策流程（MDPs）。该方法通过 epsilon-homogeneous 分区算法将大型 MDP 转化为较小的 BMDP 以分析大型隐式 MDPs。

    Feb, 2013

  • 加权因果有向无环图的新度量和搜索算法

    通过研究自适应干预下的因果图发现，提出了一种新的基准，捕捉任何搜索算法的最坏干预成本，并提出了在各种设置下实现对数逼近的自适应搜索算法。

    May, 2023