多维马尔可夫决策过程中的百分位查询
提供了一种高效的算法来解决多目标模型检验问题,该算法通过随机化策略来实现,在多项式时间内计算了一组 ω -regular 性质的近似 Pareto 曲线,并使用图论方法分析了一些定性多目标模型检验问题。
Oct, 2008
本文研究具有多个极限平均(或均值支付)目标的马尔可夫决策过程,囊括了优化期望和满足约束的两种语义,并考虑到具有风险规避策略的优化问题。文章的主要结果包括:多项式时间的算法、多项式大小的 Pareto 曲线近似计算和策略复杂性的完整刻画。
Feb, 2015
本文研究利用概率风险约束的马尔可夫决策过程,通过计算梯度并设计算法实现了局部最优策略,解决了累积成本最小化的顺序决策问题,例子包括最优停止问题和在线营销应用。
Dec, 2015
研究使用实值转移奖励的可数无限马尔可夫决策过程(MDPs),并针对不同奖励指标下的策略复杂性建立了完整的模型,确定了实现ɛ最优策略所需的最小记忆量。
Mar, 2022
用假均值将混合风险下的 MDP 转化为标准 MDP,并提出一种基于二级优化结构的统一算法框架,该框架还允许收敛性分析。通过数值实验,验证了该算法的有效性。
Jan, 2022
我们引入了一种网格型方法来解决具有一般特征的离散时间有限时间马尔科夫决策过程(MDPs),该过程具有一般的状态和动作空间,包括欧几里得空间的有限和无限(但合适地规则的)子集。
Jun, 2024
设计控制策略时,我们考虑在只有近似模型的情况下对无限时域折扣成本马尔可夫决策过程进行控制。对于在原始模型中使用近似模型的最优策略的性能如何,在原始模型中使用的近似模型的价值函数与原始模型的最优价值函数之间的差异的加权范数提供了上界的边界。通过考虑每步成本的仿射变换,我们进一步提供了可能更紧密的上界,并且上界明确取决于原始模型和近似模型之间成本函数和状态转移核之间的加权距离。我们提供示例以说明我们的结果。
Feb, 2024
马尔科夫决策过程(MDPs)为不确定性下的顺序决策制定了标准框架,但是 MDPs 中的转移概率通常是从数据中估计的,并且 MDPs 不考虑数据的不确定性。鲁棒马尔科夫决策过程(RMDPs)通过为每个转移分配不确定性集合而不是单个概率值来解决了 MDPs 的这个缺点。解决 RMDPs 的目标是找到一种策略,使得在不确定性集合上最大化最坏情况的性能。本文考虑多面体 RMDPs,在其中所有的不确定性集合都是多面体,并研究解决长期平均回报的多面体 RMDPs 的问题。我们关注计算复杂性方面和高效算法。我们提出了这个问题的一个新视角,并且证明它可以简化为解决具有有限状态和动作空间的长期平均回报的轮流随机游戏。这个简化使我们能够得出几个重要的结论,这些结论以前是未知的。首先,我们为解决长期平均回报的多面体 RMDPs 推导出新的计算复杂性界限,首次证明它们的阈值决策问题属于 NP coNP,并且它们具有具有亚指数期望运行时间的随机算法。其次,我们提出了鲁棒多面体策略迭代(RPPI),一种用于解决长期平均回报的多面体 RMDPs 的新型策略迭代算法。我们的实验评估表明,相比基于值迭代的现有方法,RPPI 在解决长期平均回报的多面体 RMDPs 方面更加高效。
Dec, 2023
本文提出了一种强化学习算法来解决多智能体马尔可夫决策过程 (MMDP),通过黑韦尔的可接近性定理,目标是将每个智能体的时间平均成本降低到预先指定的特定界限以下。通过在 Q-learning 算法中结合每个智能体成本的加权组合,其中成本是通过具有 Metropolis-Hastings 或乘法权重形式的传闻算法来调制传闻的平均矩阵,我们使用了多个时间尺度的算法,并证明在温和条件下,它近似实现了每个智能体的期望界限。我们还在具有联合控制的每个阶段成本的更一般的 MMDP 设置中展示了该算法的实证性能。
Nov, 2023
我们研究了不确定性下的序贯决策中马尔可夫奖励的表达能力,通过将马尔可夫决策过程 (MDPs) 中的奖励函数视为代理行为的特征化手段,研究了是否存在一种标量或多维度马尔可夫奖励函数,使得这个集合中的策略比其他策略更具吸引力。我们的主要结果给出了这样的奖励函数存在的必要和充分条件,同时也证明了对于任意非退化的确定性策略集合,都存在一个多维度的马尔可夫奖励函数来描述它。
Jul, 2023