arXiv:2502.07764v1 宣告类型: cross 摘要: 我们研究了近似一般约束马尔可夫决策过程的计算复杂性。我们的主要贡献是对广泛可递归计算的约束类别设计了一种多项式时间的 $(0,\epsilon)$-双准则近似算法，用于找到最优约束策略，包括几乎肯定、概率、期望及其任意时间变体。匹配的下界表明，只要 $P \neq NP$，我们的近似保证就最优。我们方法的普遍性回答了受约束强化学习文献中几个长期悬而未决的计算复杂性问题。具体而言，我们首次证明了以下设置的多项式时间近似可解性：在概率约束下的策略、在多个期望约束下的确定性策略、在非齐次约束下的策略（即，不同类型的约束）以及连续状态过程下的约束策略。