Robust Constrained MDP における効率的な政策最適化と反復計算複雑性の保証

arXiv:2505.19238v3 発表タイプ：置換 要約：制約付き意思決定は、現実世界の制御システムで安全な政策を設計するために不可欠ですが、シミュレーション環境はしばしば現実世界の悪質性を捉えることに失敗します。我々は、現実のモデルとアクセス可能なシミュレーター/基準モデルの間に不一致がある場合であっても、累積報酬を最大化しつつ制約を満たす政策を学習する問題を検討します。特に、未知の基準モデルを中心とする不確実性セットに対して、最悪の確率的モデルに対する報酬を最大化し制約を満たす必要がある強固な制約付きマルコフ決定問題 (RCMDP) を検討します。標準制約付きマルコフ決定問題 (CMDP) では有効であるが、強い対偶性がないためここで適用できない対偶法。さらに、報酬価値関数と制約価値関数において最悪ケースモデルが異なる場合があるため、標準的な制約付き価値反復アプローチも合成価値関数に対して適用できない。我々は、制約価値関数を最小化して制約を満たすとともに、すべての制約が満たされた場合は単純に強固な報酬価値関数を最大化できるという新しい手法を提案する。我々は、アルゴリズムが $\ ext{O}(\epsilon^{-2})$ 回反回で最悪 $\ ext{\epsilon}$ 分の非最適性と実行可能な政策を見つけることを証明する。最上級法の対照として、二分探索を用いる必要がなく、割引率 (\gamma) の値が小さい場合に少なくとも 4 倍、大きい場合に少なくとも 6 倍の計算時間を削減できる。

arXiv:2505.19238v3 Announce Type: replace Abstract: Constrained decision-making is essential for designing safe policies in real-world control systems, yet simulated environments often fail to capture real-world adversities. We consider the problem of learning a policy that will maximize the cumulative reward while satisfying a constraint, even when there is a mismatch between the real model and an accessible simulator/nominal model. In particular, we consider the robust constrained Markov decision problem (RCMDP) where an agent needs to maximize the reward and satisfy the constraint against the worst possible stochastic model under the uncertainty set centered around an unknown nominal model. Primal-dual methods, effective for standard constrained MDP (CMDP), are not applicable here because of the lack of the strong duality property. Further, one cannot apply the standard robust value-iteration based approach on the composite value function either as the worst case models may be different for the reward value function and the constraint value function. We propose a novel technique that effectively minimizes the constraint value function--to satisfy the constraints; on the other hand, when all the constraints are satisfied, it can simply maximize the robust reward value function. We prove that such an algorithm finds a policy with at most $\epsilon$ sub-optimality and feasible policy after $O(\epsilon^{-2})$ iterations. In contrast to the state-of-the-art method, we do not need to employ a binary search, thus, we reduce the computation time by at least 4x for smaller value of discount factor ($\gamma$) and by at least 6x for larger value of $\gamma$.