論文の概要: Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

• arxiv url: http://arxiv.org/abs/2601.23229v1
• Date: Fri, 30 Jan 2026 17:57:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-02 18:28:15.598166
• Title: Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs
• Title（参考訳）: L_\infty$ロバストMDPに対する政策イテレーションの強い多項式時間複素性
• Authors: Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano,
• Abstract要約: 頑健なポリシー反復は、定数(固定された)割引係数を持つ$(s, a)$-正方形$L_infty$RMDPsに対して強ポリノミカル時間で実行されることを示す。 マルコフと強い多項式時間アルゴリズムの存在は、これらの最適化モデルの基本的問題である。
• 参考スコア（独自算出の注目度）: 7.694676064731969
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilities and optimizing against the worst-case realization of that uncertainty. In particular, $(s, a)$-rectangular RMDPs with $L_\infty$ uncertainty sets form a fundamental and expressive model: they subsume classical MDPs and turn-based stochastic games. We consider this model with discounted payoffs. The existence of polynomial and strongly-polynomial time algorithms is a fundamental problem for these optimization models. For MDPs, linear programming yields polynomial-time algorithms for any arbitrary discount factor, and the seminal work of Ye established strongly--polynomial time for a fixed discount factor. The generalization of such results to RMDPs has remained an important open problem. In this work, we show that a robust policy iteration algorithm runs in strongly-polynomial time for $(s, a)$-rectangular $L_\infty$ RMDPs with a constant (fixed) discount factor, resolving an important algorithmic question.
• Abstract（参考訳）: マルコフ決定プロセス(MDP)は、シーケンシャルな意思決定の基本的なモデルである。 ロバストMDP(RMDP)はこの枠組みを拡張し、遷移確率の不確実性を許容し、その不確実性の最悪の実現に対して最適化する。 特に、$(s, a)$-正方形RMDPと$L_\infty$不確実性集合は、古典的MDPやターンベースの確率ゲームに代入して、基本的で表現力のあるモデルを形成する。 割引の支払いを伴うこのモデルについて検討する。 多項式と強多項式時間アルゴリズムの存在は、これらの最適化モデルの基本的問題である。 MDP の場合、線形プログラミングは任意の割引係数に対して多項式時間アルゴリズムを出力し、Ye のセミナル作業は固定割引係数に対して強い多項式時間を確立した。 このような結果のRMDPへの一般化は、依然として重要なオープンな問題である。 本研究では、ロバストなポリシー反復アルゴリズムが、(s, a)$-rectangular $L_\infty$ RMDPsに対して、一定の(固定された)割引係数で強ポリノミカル時間で動作し、重要なアルゴリズム問題を解決することを示す。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Solving Long-run Average Reward Robust MDPs via Stochastic Games [6.183091173390457]
  ロバストマルコフ決定過程(RMDP)は、各遷移に単一の確率値ではなく不確実性集合を割り当てる。 我々は、有限状態およびアクション空間を持つ長期平均報酬ターンベースのゲームに還元可能であることを示す。 本稿では、長期平均ポリトピックRMDPを解くための新しいポリシー反復アルゴリズムであるRobust Polytopic Policy Iteration(RPPI)を提案する。
  論文  参考訳（メタデータ） (2023-12-21T15:00:06Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model [71.59406356321101]
  本稿では,強化学習(RL)におけるモデルロバスト性を検討した。 我々は,デプロイ環境が,名目MDPに規定された不確実性に陥る場合に,最悪の場合のパフォーマンスを最適化する政策を学習することを目的とした,分布的に堅牢なマルコフ決定プロセス(RMDP)の枠組みを採用する。
  論文  参考訳（メタデータ） (2023-05-26T02:32:03Z)
• A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes [13.466249082564213]
  本稿では,全情報フィードバックを用いた表層線形MDPに対するPPOの楽観的変種を提案する。 既存のポリシーベースのアルゴリズムと比較して, 線形MDPと逆線形MDPの双方において, 完全な情報付きで, 最先端の後悔点を達成している。
  論文  参考訳（メタデータ） (2023-05-15T17:55:24Z)
• Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization [64.60253456266872]
  マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。 規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。 ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
  論文  参考訳（メタデータ） (2023-03-12T13:03:28Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Twice regularized MDPs and the equivalence between robustness and regularization [65.58188361659073]
  報酬を損なうMDPのポリシーイテレーションは、正規化MDPと同じ時間複雑性を持つことを示す。 正規化MDPを2倍の正規化MDPに一般化する。
  論文  参考訳（メタデータ） (2021-10-12T18:33:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。