論文の概要: Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2610.02131v1
• Date: Thu, 01 Oct 2026 17:41:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.348706
• Title: Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
• Title（参考訳）: ロバストマルコフ決定過程の線形計画表現と強多項式アルゴリズム
• Abstract要約: 我々は、堅牢な決定プロセス(RMDP)のための線形プログラミング(LP)表現と強アルゴリズムについて研究する。 有限列のロバストなポリシイテレーションステップを符号化することにより、最適解がロバストな最適値を回復する単一のLPを構築する。 また、不確実性集合を最小化するコストと、ポリシーを評価するのに必要なイテレーション数とを組み合わせた、ロバストなポリシーの一般的な複雑性解析も開発した。
• 参考スコア（独自算出の注目度）: 14.695024781603037
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study linear programming (LP) representations and strongly polynomial algorithms for robust Markov decision processes (RMDPs) with rational polyhedral state-action rectangular uncertainty in rewards and transitions. By encoding a finite sequence of robust policy-iteration steps, we construct a single LP whose optimal solutions recover the robust optimal value and all optimal stationary randomized policies. At fixed discount, the LP has polynomial dimension and encoding length and can be constructed in strongly polynomial time. We also develop a general complexity analysis of robust policy iteration that combines the cost of minimizing over uncertainty sets with the number of iterations needed to evaluate a policy. For a fixed discount factor, we use this analysis to improve the known complexity bounds for $\ell_1$ and $\ell_\infty$ RMDPs and establish new strongly polynomial bounds for general interval, weighted $\ell_1$, and Wasserstein RMDPs, as well as turn-based stochastic games with these uncertainty sets.
• Abstract（参考訳）: 本稿では,リニアプログラミング(LP)表現と強多項式アルゴリズムを用いて,ロバストマルコフ決定過程(RMDP)と有理多面的状態-動作の不確実性を考慮した報酬と遷移について検討する。 有限列のロバストなポリシイテレーションステップを符号化することにより、最適解がロバストな最適値と全ての定常ランダム化ポリシーを回復する単一LPを構築する。 固定割引の場合、LPは多項式次元と符号化長を持ち、強い多項式時間で構築することができる。 また、不確実性セットを最小化するコストと、ポリシーを評価するのに必要なイテレーション数とを組み合わせた、ロバストなポリシー反復の一般的な複雑性解析も開発した。 固定割引係数に対して、この解析を用いて、既知の複雑性境界を$\ell_1$および$\ell_\infty$ RMDPsで改善し、一般区間に対する新しい強い多項式境界、重み付き$\ell_1$およびWasserstein RMDPs、およびこれらの不確実集合を持つターンベースの確率ゲームを構築する。

関連論文リスト

• Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes [3.2959629354399484]
  有限水平エピソードマルコフ決定における$(varepsilon, )$PAC-PACポリシー識別問題について検討する。 本稿では,後続サンプリングとオンライン学習アルゴリズムを組み合わせてMDPを誘導する,最適ポリシー識別のためのランダムで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-05-05T16:16:57Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs [7.694676064731969]
  頑健なポリシー反復は、定数(固定された)割引係数を持つ$(s, a)$-正方形$L_infty$RMDPsに対して強ポリノミカル時間で実行されることを示す。 マルコフと強い多項式時間アルゴリズムの存在は、これらの最適化モデルの基本的問題である。
  論文  参考訳（メタデータ） (2026-01-30T17:57:07Z)
• A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes [13.466249082564213]
  本稿では,全情報フィードバックを用いた表層線形MDPに対するPPOの楽観的変種を提案する。 既存のポリシーベースのアルゴリズムと比較して, 線形MDPと逆線形MDPの双方において, 完全な情報付きで, 最先端の後悔点を達成している。
  論文  参考訳（メタデータ） (2023-05-15T17:55:24Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  我々はロバストマルコフ決定過程(MDP)の解法を考える。 MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。 $(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
  論文  参考訳（メタデータ） (2022-09-21T18:10:28Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。 まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。 次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
  論文  参考訳（メタデータ） (2022-08-17T18:49:53Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation [48.744735294559824]
  政策最適化手法は、その漸進的かつ政治的性質が価値に基づくアルゴリズムよりも安定しているため、一般的な強化学習アルゴリズムである。 本稿では,PCPGのサンプル複雑性問題を克服し,モデルのミスセグメンテーションに頑健さを保ちながら,新しいアルゴリズムCOPOEを提案する。 その結果、PCPGの$widetildeO (1/epsilon11)$からPCPGの$widetildeO (1/epsilon3)$まで、サンプルの複雑さが改善され、値ベースの技術とのギャップがほぼ埋められます。
  論文  参考訳（メタデータ） (2021-03-24T01:42:59Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Partial Policy Iteration for L1-Robust Markov Decision Processes [13.555107578858307]
  本稿では、ロバストなMDPの共通クラスを解くための新しい効率的なアルゴリズムについて述べる。 我々は、ロバストなMDPのための部分ポリシーイテレーション、新しい、効率的で柔軟な、一般的なポリシーイテレーションスキームを提案する。 実験結果から,提案手法は最先端手法よりも桁違いに高速であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-16T19:50:14Z)

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

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