带折扣求和目标的 POMDP 中带有概率保证的期望优化
本文研究了如何通过计算部分可观察马尔可夫决策过程的总期望奖励的下界来解决通常难以解决的问题,提供了两种技术:使用良好策略的简单技术和使用概率之间的最小移位的更高级别的技术。同时,本文还使用混合整数线性规划找到这样最小概率移位,并在实验中表明了这些技术的可扩展性和其提供的紧缩的下界值。
Jan, 2022
本文研究具有多个极限平均(或均值支付)目标的马尔可夫决策过程,囊括了优化期望和满足约束的两种语义,并考虑到具有风险规避策略的优化问题。文章的主要结果包括:多项式时间的算法、多项式大小的 Pareto 曲线近似计算和策略复杂性的完整刻画。
Feb, 2015
通过简化解决方案与理论上最优解之间的确定性关系,解决了在计算上昂贵的部分可观测马尔可夫决策过程(POMDPs)困难,为自主代理在不完全信息环境下的规划提供了确定性界限。
Oct, 2023
针对部分可观察的马尔可夫决策问题 (POMDPs),本文研究了一种新颖的最优可观测性问题 (OOP):如何在固定预算下选择一种代理人的传感器,使其达到预期目标。研究表明该问题在一般情况下是不可判定的,而考虑位置策略时是可判定的。我们提出了两种算法解决可判定的 OOP 问题:一种基于 M 的潜在马尔可夫决策过程的最优策略,另一种基于 SMT 的参数合成。我们对 POMDP 文献中的典型示例的变体进行了实验,并获得了有希望的结果。
May, 2024
本文研究了带安全可达性目标的部分可观测马尔可夫决策过程(POMDPs),提出了一种基于目标约束信念空间和符号约束的方法来合成能实现安全可达性目标的策略,并通过实验结果表明,该方法能够在大量信念空间中高效地搜索有效策略。
Jan, 2018
本研究考虑了有限状态和动作空间的无穷时部分观察到的马尔可夫决策问题中,根据折扣或平均收益准则找到最佳的无记忆随机策略并描述了优化问题作为可行状态 - 动作频率空间中的线性优化问题并使用了多项式优化的最大化奖励来解决导航问题。
Oct, 2021
部分可观察马尔可夫决策过程(POMDPs)依赖于概率分布的精确性,而鲁棒 POMDPs 通过定义不精确的概率(称为不确定性集)来缓解这一问题。本研究通过展示:1)不同的不确定性集假设会影响最优策略和价值;2)RPOMDPs 具有部分可观察随机博弈(POSG)语义;以及 3)相同的 RPOMDP 在不同的假设下会导致语义上不同的 POSG,从而产生不同的策略和价值,从而扩展了 RPOMDP 的理论理解。这些新颖的 RPOMDPs 语义为广泛研究的 POSG 模型提供了实际结果,具体而言,我们展示了纳什均衡的存在性。最后,我们使用这些语义对现有的 RPOMDP 文献进行分类,澄清了这些现有研究在哪些不确定性假设下进行。
May, 2024
在部分可观察域中,面临不确定性的风险规避决策是人工智能领域的一个基本问题,对于可靠的自主代理至关重要。本研究使用部分可观察的马尔可夫决策过程(POMDPs)建模并采用回报的条件风险价值(CVaR)作为值函数。这项工作开发了一个简化框架,以加快值函数的评估速度,并提供性能保证。我们考虑了一种计算代价更低的信念 - MDP 转移模型作为简化方法,该模型可以对应于更廉价的观察或转移模型。我们的贡献包括一般的 CVaR 界限,通过假设两个累积分布之间的界限,可以使用一个随机变量 Y 来限制随机变量 X 的 CVaR。然后,我们推导出 POMDP 设置下 CVaR 值函数的界限,并展示了如何使用计算代价更低的信念 - MDP 转移模型来限制值函数,而无需实时访问计算代价高昂的模型。接着,我们提供了对估计边界的理论性能保证。我们的结果适用于对信念 - MDP 转移模型的一般简化,并可以同时简化观察和状态转移模型。
Jun, 2024
本文研究部分可观察马尔可夫决策过程 (POMDPs),带有一组目标状态并且每个转移都有一个整数成本。研究的最优化目标是在确保(概率为 1)几乎达到目标集时最小化预期总成本。我们证明,对于整数成本,近似最优成本是不可判定的。对于正成本,我们的结果有:(i)我们建立了最优成本的匹配下限和上限,上限是双指数;(ii)我们表明,近似最优成本的问题是可判定的,并且提出了建立在具有有限时间段目标的 POMDP 算法上的近似算法。虽然这个算法的最坏运行时间是双指数的,但我们还介绍了算法的有效停止标准,并实验性地表明它在许多有意义的示例中表现良好。
Nov, 2014